Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems
- 7 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 375-385
- https://doi.org/10.1109/hcw.2000.843759
Abstract
The min-min algorithm is a simple algorithm. It runs fast and delivers good performance. However, the min-min algorithm schedules small tasks first, resulting in some load imbalance. We present an algorithm which improves the min-min algorithm by scheduling large tasks first. The new algorithm, segmented min-min, balances the load well and demonstrates even better performance in both makespan and running time.Keywords
This publication has 11 references indexed in Scilit:
- A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Improving search by incorporating evolution principles in parallel Tabu SearchPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling resources in multi-user, heterogeneous, computing environments with SmartNetPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The relative performance of various mapping algorithms is independent of sizable variances in run-time predictionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Parallel genetic simulated annealing: a massively parallel SIMD algorithmIEEE Transactions on Parallel and Distributed Systems, 1998
- Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based ApproachJournal of Parallel and Distributed Computing, 1997
- Real time pipelined system design through simulated annealingJournal of Systems Architecture, 1996
- On mapping signal processing algorithms to a heterogeneous multiprocessor systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Optimization by Simulated AnnealingScience, 1983
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsJournal of the ACM, 1977