Performance Bounds on Scheduling Parallel Tasks with Communication Cost

Jiann-Fu LIN, Win-Bin SEE, Sao-Jie CHEN

Summary :

This paper investigates the problem of scheduling parallel tasks" with consideration of communication cost on an m-processor system, where processors are assumed to be identical and tasks being scheduled are independent such that they can run on more than one processor simultaneously. Once a task is processed in parallel, its finish time will be speeded up, but communication cost will also be incurred and should be taken into account. To find a schedule with minimum finish time for the parallel tasks scheduling problem is NP-hard. Therefore, in this paper, we will propose a heuristic algorithm for this kind of problem and derive its performance bounds for two different cases of applications, respectively.

• Publication: IEICE TRANSACTIONS on Information Vol.E78-D No.3 pp.263-268
• Publication Date: 1995/03/25
• Type of Manuscript: PAPER
• Category: Computer Networks

Authors

Jiann-Fu LIN
Win-Bin SEE
Sao-Jie CHEN

Keyword

scheduling,  parallel task,  communication cost,  performance bound