Title :
Link contention-constrained scheduling and mapping of tasks and messages to a network of heterogeneous processors
Author :
Kwok, Yu-Kwong ; Ahmad, Ishfaq
Author_Institution :
Dept. of Electr. & Electron. Eng., Hong Kong Univ., Hong Kong
Abstract :
In this paper, we consider the problem of scheduling and mapping precedence-constrained tasks to a network of heterogeneous processors. In such systems, processors are usually physically distributed, implying that the communication cost is considerably higher than in tightly coupled multiprocessors. Therefore, scheduling and mapping algorithms for such systems must schedule the tasks as well as the communication traffic by treating both the processors and communication links as important resources. We propose an algorithm that achieves these objectives and adapts its tasks scheduling and mapping decisions according to the given network topology. Just like tasks, messages are also scheduled and mapped to suitable links during the minimization of the finish times of tasks. Heterogeneity of processors is exploited by scheduling critical tasks to the fastest processors. Our extensive experimental study has demonstrated that the proposed algorithm is efficient, robust, and yields consistent performance over a wide range of scheduling parameters
Keywords :
minimisation; network topology; parallel algorithms; processor scheduling; telecommunication links; telecommunication traffic; communication links; link contention-constrained scheduling; minimization; network of heterogeneous processors; precedence-constrained tasks; scheduling parameters; tasks mapping; tightly coupled multiprocessors; Application software; Computer science; Contracts; Councils; Dynamic scheduling; Large-scale systems; Network topology; Processor scheduling; Routing; Scheduling algorithm;
Conference_Titel :
Parallel Processing, 1999. Proceedings. 1999 International Conference on
Conference_Location :
Aizu-Wakamatsu City
Print_ISBN :
0-7695-0350-0
DOI :
10.1109/ICPP.1999.797444