MPPTS: Multi-factor Predictive Priority Task Scheduling Algorithm for Heterogeneous Systems
摘要
Efficient task scheduling is critical to optimizing performance and resource utilization in Heterogeneous Computing Systems (HCS). Over the years, a wide range of scheduling mechanisms have been proposed to address the task scheduling problem in HCS. However, these approaches do not consistently obtain the shortest makespan in most real scientific workflows, indicating a lack of sufficient generality. This paper proposes a novel list scheduling algorithm, Multi-factor Predictive Priority Task Scheduling (MPPTS) Algorithm, to map directed acyclic task graphs onto fully connected heterogeneous processors with the objective of minimizing schedule length (Makespan). The MPPTS algorithm comprises two phases: a task prioritization phase, which assigns priorities to tasks based on predictive metrics, and a processor selection phase, which allocates tasks to processors to optimize execution efficiency. The innovation of MPPTS lies in its ability to adaptively balance computation and communication overhead, leading to consistently low makespan and stable scheduling across diverse and large-scale workflows. This leads to more efficient task-to-processor mappings, particularly in highly heterogeneous systems with varying communication-to-computation ratios. Comprehensive experiments based on both randomly generated task graphs and real-world scientific workflow applications demonstrate that the MPPTS algorithm outperforms existing list scheduling algorithms in key performance metrics, including average makespan, speedup, standard deviation makespan, and resource efficiency.