Task scheduling on a hypercube with link contentions

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.