Toward Fast and Efficient Compile‐Time Task Scheduling in Heterogeneous Computing Systems
Tarek Hagras, Jan Janeček · 2005
This chapter contains sections titled: Introduction Problem Definition The Suggested Algorithm Listing Mechanism Duplication Mechanism Algorithm Complexity Analysis Heterogeneous Systems Scheduling Heuristics Fast Load Balancing (FLBf) Algorithm Heterogeneous Earliest Finish Time (HEFT) Algorithm Critical Path on a Processor (CPOP) Algorithm Experimental Results and Discussion Comparison Metrics Random Graph Generator Performance Results Applications Performance of Parents Selection Methods Performance of Machine Assignment Mechanism Summary and Discussion of Experimental Results Conclusion Reference Heterogeneous computing systems have gained importance due to their capability to execute parallel program tasks. In many cases, heterogeneous computing systems have been able to produce high performance for lower cost than a single large machine in executing parallel program tasks. However, the performance of parallel program execution on such platforms is highly dependent on the scheduling of the parallel program tasks on to the platform machines. This chapter presents a task scheduling algorithm on a bounded number of machines with different capabilities. The algorithm handles heterogeneity of both machines and communication links. The algorithm is called the Heterogeneous Critical Tasks Reverse Duplicator (HCTRD). It consists of two mechanisms, which are a lower-bound complexity listing mechanism instead of the classical list-scheduling prioritization phase and a near lower-bound machine assignment mechanism based on task-duplication. Based on the experimental study using a large set of randomly generated application graphs with various characteristics and application graphs of real world problems (such as Gaussian Elimination, and the Laplace Equation), HCTRD outperformed the other algorithms in terms of performance and complexity.