Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] |

Applications and Performance Analysis of

An Optimization Approach for List Scheduling Algorithms on

Distributed Memory Multiprocessors

**Yeh-Ching Chung, Chia-Cheng Liu and J.-S. Liu**

Feng Chia University

Taichung, Taiwan 407, R.O.C.

We have proposed an optimization approach, the *bottom-up top-down duplication* heuristic (BTDH), for static scheduling of *directed-acyclic graphs* (DAGs) on *distributed memory multiprocessors* [5]. In this paper, we discuss the applications of BTDH for *list scheduling algorithms *(LSAs). There are two ways to use BTDH with LSAs. (1) BTDH can be used with an LSA to form a new scheduling algorithm (LSA/BTDH). (2) It can be used as a pure optimization algorithm for an LSA (LSA-BTDH). We have applied BTDH to two well-known LSAs, the *highest level first with estimated time* (HLFET) and the *earlier task first* (ETF) heuristics. Extensive simulation bas been conducted to study the performance of BTDH for LSAs. Three Parameters, *graph parallelism* (GP) of a DAG [19], the ratio of the average communication cost to the average computation cost (CCR) of a DAG [5], and the processor number (PN) of a distributed memory multiprocessor, have been simulated. From the simulation, we have the following conclusions. (I) Given a DAG, the GP of a DAG can accurately predict the number of processors to be used such that a good scheduling length and good resource utilization (or efficiency) can be achieved simultaneously. (II) In terms of speedups, in general, we have LSA/BTDH ¡Ù LSA-BTDH ¡Ù ETF ¡Ù HLFET. Experimental results of scheduling FFT programs on an NCUBE-2 are also presented. The results confirm our simulation results and show that the speedups of LSA/BTDH and LSA/BTDH are better than the speedups of LSAs.

Keywords: list scheduling algorithm, heuristic, graph parallelism, directed-acyclic graph, distributed memory multiprocessor

Received July 6, 1993; revised September 30, 1994.

Communicated by Wen-Tsuen Chen.