A High-Performance DAG Task Scheduling Algorithm for Heterogeneous Networked Embedded Systems

A high-performance scheduling for a DAG (Directed Acyclic Graph) task graph on heterogeneous networked embedded systems or parallel and distributed systems is to maximize concurrency and minimize inter-processor communication. Most of the algorithms using upward rank value for task prioritizing and earliest finish time for processor assignment. But both approaches ignored the heterogeneity of system and could not create accurate and efficient schedules. Yet no one has doubled about and recognized that. A fully heterogeneous task scheduling algorithm is proposed to address the above problems in this paper. The fundamentals of DAG model and corresponding algorithms are investigated. New concepts called Heterogeneous Upward Rank Value (HURV) and Heterogeneous Priority Rank Value (HPRV) are defined. An algorithm called Heterogeneous Select Value (HSV) is proposed in paper. Both benchmark and extensive experimental evaluation demonstrate the significant improvements in proposed algorithm.