Optimal task assignment in heterogeneous distributed computing systems
- 1 July 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Concurrency
- Vol. 6 (3) , 42-50
- https://doi.org/10.1109/4434.708255
Abstract
A distributed system comprising networked heterogeneous processors requires efficient task-to-processor assignment to achieve fast turnaround time. Although reasonable heuristics exist to address optimal processor assignment for small problems, larger problems require better algorithms. The authors describe two new algorithms based on the A* technique which are considerably faster, are more memory-efficient, and give optimal solutions. The first is a sequential algorithm that reduces the search space. The second proposes to lower time complexity, by running the assignment algorithm in parallel, and achieves significant speedup. The authors test their results on a library of task graphs and processor topologies.Keywords
This publication has 12 references indexed in Scilit:
- Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1996
- Task assignment using a problem‐space genetic algorithmConcurrency: Practice and Experience, 1995
- A new mapping heuristic based on mean field annealingJournal of Parallel and Distributed Computing, 1992
- On the assignment problem of arbitrary process systems to heterogeneous distributed computer systemsIEEE Transactions on Computers, 1992
- A close look at task assignment in distributed systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Cluster partitioning approaches to mapping parallel programs onto a hypercubeParallel Computing, 1990
- Efficient computation of optimal assignments for distributed tasksJournal of Parallel and Distributed Computing, 1987
- A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax CriterionIEEE Transactions on Computers, 1985
- On the Mapping ProblemIEEE Transactions on Computers, 1981
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977