Yeh-Ching Chung, Chia-Cheng Liu and J.-S. Liu
Department of Information Engineering
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 . 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 , the ratio of the average communication cost to the average computation cost (CCR) of a DAG , 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.