Heterogeneous multiprocessor system scheduling algorithm based on edge cover queue

Heterogeneous multiprocessor system refers to a group of interconnected processors with different computing and storage capabilities. Due to the diversity of task computing requirements and differences in processor architecture, heterogeneous multiprocessor systems are widely present in various computing scenarios. In heterogeneous multiprocessor systems, excellent task scheduling algorithms can shorten task completion time, improve system parallelism and utilization. This article proposes a new task scheduling algorithm, the Heuristic Edge Cover Queue Scheduling Algorithm (HECSA), based on the edge cover theory of directed acyclic graphs (DAG) for heterogeneous multiprocessor systems. HECSA first utilizes an improved heuristic method to generate edge cover queue for DAG while ensuring topological correctness. Then, we use heuristic method with low computational complexity to sequentially allocate edge cover queue to heterogeneous multiprocessor system for execution. The simulation results of common digital signal processing tasks and scientific workflow tasks show that the HECSA can achieve better scheduling results under lower computational complexity.