Work-in-Progress: Multi-Deadline DAG Scheduling Model for Autonomous Driving Systems

Yano, Atsushi; Azumi, Takuya · 2024 · Crossref

DOI: 10.1109/rtss62706.2024.00049

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This work-in-progress paper addresses the challenge of providing end-to-end timing guarantees for Autoware, an open-source autonomous driving system built on Robot Operation System (ROS) 2. Ensuring safety in autonomous driving requires strict real-time performance, yet existing ROS 2 cause-effect chain models struggle to accurately represent Autoware’s complexities. Specifically, these models fail to adequately handle sync callbacks that synchronize data from multiple topics, complex queue consumption patterns that deviate from simple FIFO behavior, and feedback loops in data flow. Incorporating these features into cause-effect chains significantly increases analysis complexity, hindering the development of practical schedulers. To resolve this, the authors propose a multi-deadline Directed Acyclic Graph (DAG) scheduling model that decomposes global end-to-end timing constraints into local relative deadlines for individual sub-DAGs. The proposed model segments the Autoware callback graph at points where data is transferred via queues or member variables, effectively isolating complex communication patterns. Each sub-DAG is treated as a task with a single source and one or more sink vertices, each associated with a specific relative deadline. This approach assumes that if all local relative deadlines are met, the system operates safely, thereby eliminating the need for intricate analysis of data propagation through queues and loops. The authors formalize this model and extend the Global Earliest Deadline First (GEDF) algorithm to support multiple deadlines within a single DAG. They introduce a Reference Absolute Deadline (RAD) metric to determine vertex priorities, using the earliest absolute deadline among descendant sink vertices to guide scheduling decisions. To evaluate the effectiveness of the extended GEDF algorithm, the authors conducted simulations using a synthetic workload derived from Autoware’s callback structures and execution times measured by the CARET tool. The experiments were performed on a simulated homogeneous multi-core processor with seven cores, matching the total utilization of the workload. The evaluation compared the extended GEDF against two baseline algorithms: a work-conserving scheduler and a Rate Monotonic (RM) scheduler. The primary metric was the acceptance ratio, defined as the proportion of simulations completed without deadline misses. Results demonstrated that the extended GEDF outperformed both baselines across all tested utilization levels. This superior performance is attributed to EDF’s inherent ability to minimize deadline misses by prioritizing tasks with the earliest deadlines, a property successfully inherited by the extended algorithm. The significance of this work lies in providing a practical scheduling model that balances analytical simplicity with empirical safety for autonomous driving systems. By abstracting complex data flows into local DAG constraints, the model facilitates the application of existing real-time DAG scheduling algorithms without requiring extensive new research into end-to-end timing analysis. The authors conclude that this approach simplifies scheduler design and improves real-time performance. Future work will focus on determining appropriate relative deadlines for each DAG and analyzing how satisfying local constraints impacts measured end-to-end reaction times and data age.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• teleoperation remote driving