A Structure-Aware DAG Scheduling and Allocation on Heterogeneous Multicore Systems
Yao Gao, Huixuan Yi, Hao Chen, Xinwei Fang, Shuai Zhao · 2024
With the ever-increasing complexity of real-time applications, heterogeneous architectures are often applied, with tasks modelled as a Direct Acyclic Graph (DAG) to reflect their execution dependency. However, existing methods assign node priority based on a single node characteristic (e.g., execution time), which cannot leverage the DAG structure to improve performance. In addition, the allocation methods solely consider the ready nodes, which neglects their impact on the upcoming nodes, prolonging the DAG makespan. This paper introduces a novel DAG scheduling algorithm for heterogeneous real-time systems that overcomes the limitations of existing methods. First, a novel node-level priority assignment is proposed that fully exploits the DAG structure to enhance the timing performance. Then, an allocation is constructed that speeds up the execution of high-priority nodes, with upcoming nodes taken into account. The experimental results demonstrate that the proposed method outperforms the existing one up to 14.35% in the DAG makespan.