A new direct acyclic graph task scheduling method for heterogeneous Multi-Core processors. (December 2022)

• Record Type: Journal Article
• Authors: Feng, Xiao; Shushan, Chen; Xingxing, Han; Shujuan, Huang; Wenjuan, Zhang
• Is Part Of: Computers & electrical engineering. Volume 104:Part A(2022)
• Publication Date: 2022-12
• Subjects: Heterogeneous multi-core processors -- Task scheduling -- DAG -- Worst response time; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.108464
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: At present, the traditional methods of calculating the worst response time upper bounds for direct acyclic graph (DAG) task scheduling on heterogeneous multi-core platforms suffer from problems such as nonself-sustainability, too many blocking nodes, and excessive estimation of the overhead time required for task scheduling, all of which cause response time upper bound estimates to be far too pessimistic. We propose to reconstruct the DAG graph by adding execution edges in order to eliminate blocking nodes. The specific method is to first use triples to represent each node of the DAG task graph, then to select blocking nodes according to the priority rules with which we add execution edges graph to reconstruct it, and finally to remove the blocking nodes again and repeat the process until all blocking nodes have been eliminated. Our experiments show that the worst response time upper bound from this method can achieve a 20% improvement in accuracy compared to the traditional methods for calculating the worst response time upper bound.