Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors

The authors discuss applications of BTDH (bottom-up top-down duplication heuristic) to list scheduling algorithms (LSAs). There are two ways to use BTDH for LSAs. BTDH can be used with an LSA to form a new scheduling algorithm (LSA/BTDH), and it can be used as a pure optimization algorithm for an LSA (LSA-BTDH). BTDH has been applied with two well-known LSAs: the highest level first with estimated time (HLFET) and the earlier task first (ETF) heuristics. Simulation results show that, given a directed acyclic growth (DAG), the graph parallelism of the DAG can accurately predict the number of processors to be used such that a good scheduling length and a good resource utilization (or efficiency) can be achieved simultaneously. In terms of speedups, LSA/BTDH >or= LSA-BTDH >or= ETF >or= HLFET. Experimental results of scheduling FFT programs, which are written in a single program multiple data (SPMD) programming approach, on NCUBE-2 are also presented. The results confirm the simulation results and show that the speedups of LSA/BTDH and LSA-BTDH are better than the speedups of LSAs. >