Performance Comparison of Algorithms for Static Scheduling of DAGs to Multiprocessors1
Ishfaq Ahmad, Yu‐Kwong Ricky Kwok, Min‐You Wu · 1998
. In this paper, we evaluate and compare algorithms for scheduling and clustering. These algorithms allocate a parallel program represented by an edge-weighted directed acyclic graph (DAG), also called a task graph or macro-dataflow graph, to a set of homogeneous processors, to minimize the completion time. We examine several such classes of such algorithms and compare the performance of a class of algorithms known as the arbitrary processor network (APN) scheduling algorithms. We discuss the design philosophies and principles behind these algorithms and assess their merits and deficiencies. Experimental results have been obtained by testing the algorithms with a large number of test cases. Global and pair-wise comparisons are made within each group whereby these algorithms are ranked according to their performance. 1. Introduction Scheduling and mapping of computations onto the processors is one of the crucial components of a parallel processing environment. Since the sched...