Task scheduling on a hypercube with link contentions
- 31 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 363-368
- https://doi.org/10.1109/ipps.1993.262907
Abstract
The authors propose a new task scheduling algorithm, which takes communication delays and link contentions into account to meet the requirements of a communication model of a hypercube. It assigns a priority which includes communication delays to each task and selects the processor where the task will be allocated in order to minimize link contentions. Evaluation has been carried out by using randomly generated graphs. The results show that almost linear speed-up is obtained when the number of tasks is 1024 and the number of processors ranges between 2 and 32. A ratio of communication time to processing time (C/P), which indicates the difficulty of scheduling task graphs with communication, is introduced and verifies the effectiveness of the proposed algorithm.Keywords
This publication has 6 references indexed in Scilit:
- System effects of interprocessor communication latency in multicomputersIEEE Micro, 1991
- Lower bound on the number of processors and time for scheduling precedence graphs with communication costsIEEE Transactions on Software Engineering, 1990
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- Complexity of Scheduling under Precedence ConstraintsOperations Research, 1978