Prioritizing DAGs to Meet Real-Time and Data-Dependency Constraints with Best Efforts

In autonomous driving (AD) systems, it is challenging for a functional module to properly fuse the data flows generated from multiple sensors in a real-time manner. Data fusion performs well when strictly complying with the data dependencies between modules, but meanwhile, the end-to-end latency of critical execution paths (from sensor to controller) may be worsened and become out of bounds. At the other extreme, simply minimizing the end-to-end latency may lead to insufficient data fusion. To tackle this challenging problem, this paper uses the directed acyclic graph (DAG) to model the AD system with multi-source data flows. We apply priority techniques to reduce the end-to-end latency of the critical execution paths and propose an integer linear programming (ILP) based method to derive a reasonable vertex priority assignment such that the end-to-end latency of each critical execution path satisfies its real-time constraint, and moreover, the execution order of vertices determined by vertex priorities keep consistent with data-dependency constraints with best efforts. Experimental work shows that our ILP method can solve the reasonable priority assignment problem for the DAG with hundreds of vertices in a few seconds.