A Novel List Scheduling Algorithm for Heterogeneous Sysatems Utilizing Predictive Optimistic Cost Matrix

Heterogeneous computing, as a specialized form of parallel and distributed computing, has garnered significant attention in both academic and industrial spheres in recent years. The efficiency of task execution in heterogeneous computing systems is primarily determined by the effectiveness of the task scheduling algorithms employed. However, most existing algorithms tend to converge towards local optima, often overlooking the complex factors that influence scheduling performance. In this paper, we propose a novel list-based heuristic static scheduling algorithm, called Heterogeneous Predictive Optimal Cost Scheduling (HPOC). The algorithm proposes the Predictive Optimisation Cost Matrix (POCM). This takes into account a wider set of factors affecting scheduling performance and helps to mitigate local optimum bias in scheduling results. Additionally, the task out-degree weight (OW) is used to calculate task scheduling priorities. This ensures that tasks with a significant impact on the overall scheduling performance are given a higher priority. Experimental evaluations on both random and real-world application graphs demonstrate that the HPOC algorithm outperforms existing algorithms in terms of both scheduling length and speedup ratios.