Comparative analysis of list scheduling algorithms on homogeneous multi-processors

Task Scheduling for parallel computing is a process to map the application to the multi-processors while minimize the execution time. Task scheduling is classified into static scheduling and dynamic scheduling. List scheduling is a class of static heuristic based scheduling algorithms with low complexity and good performance. Based on the principle of list scheduling algorithm with limited numbers of homogeneous multi-processors, this study analyzes the complexity and property of six typical kinds of list scheduling algorithms including HLFET, ISH, MCP, ETF, DLS and CPND. By using three types of task graphs including peer set graphs, traced graphs and random graphs, the schedule lengths of the six list scheduling algorithms are compared and analyzed. It can be concluded that the algorithms based on the critical path nodes (such as MCP, CPND) are generally better than other algorithms. The algorithms using dynamic properties (such as DLS, ETF) perform better than most of the algorithms adopting static properties.

I. Introduction

Parallel computing was firstly introduced in in 1960s and developed with the increasing demand for high performance computing. It divides one application program into multiple, interdependent task collections (known as parallel programming) and assigns them to different processors to be executed. Highly effective task scheduling is the critical technology of parallel computing. Existed researches have confirmed that the optimal scheduling of general task graphs is an NP-complete problem [1].