A Bottom-Up Approach to Task Scheduling on Distributed Memory Multiprocessors
- 1 August 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 151-154
- https://doi.org/10.1109/icpp.1994.14
Abstract
This paper presents a new approach to statically schedule parallel programs modeled as Directed Acyclic Graphs (DAGs) on various distributed memory multi-processor topologies represented as processor graphs to reduce the overall execution time of the program. The scheduler factors in the processor topology, communication delays and delays due to channel conflicts for scheduling. Our scheme differs dramatically from existing schedulers in that tasks of the DAG are scheduled bottom up. Experimental results presentedfor message switched systems using the hypercube and torus topologies show the effectiveness of our scheme. Our scheme can also be adapted for other topologies and routing schemes such as wormhole routing and circuit switching.Keywords
This publication has 11 references indexed in Scilit:
- Task scheduling on a hypercube with link contentionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Mapping to reduce contention in multiprocessor architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A universal approach for task scheduling for distributed memory multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling task graphs onto distributed memory multiprocessors under realistic constraintsPublished by Springer Nature ,1994
- A generalized scheme for mapping parallel algorithmsIEEE Transactions on Parallel and Distributed Systems, 1993
- A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessorsJournal of Parallel and Distributed Computing, 1992
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- A Mapping Strategy for Parallel ProcessingIEEE Transactions on Computers, 1987
- A Shortest Tree Algorithm for Optimal Assignments Across Space and Time in a Distributed Processor SystemIEEE Transactions on Software Engineering, 1981
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961