Conference on High Performance Computing (Supercomputing) · 1992 · 143 citations · 28 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel ComputingSchedulingAlgorithm AnalysisInstruction SchedulingParallel Algorithm DesignParallel Computing SystemsParallel Performance AnalysisPerformance OptimizationCompile-time OptimizationDistributed MemoryList SchedulingMultiprocessor SchedulingParallel SchedulingParallel Scheduling AlgorithmsResource Utilization PredictionScheduling In Multiprocessor Systems
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. >
28
Bounds on Multiprocessing Timing Anomalies
Ron Graham · SIAM Journal on Applied Mathematics · 1969 · 2.4K citations
Parallel Sequencing and Assembly Line Problems
T. C. Hu · Operations Research · 1961 · 895 citations
Management, Industrial Engineering, Operations Management +10