loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2003 International Conference on Parallel Processing (ICPP'03)
Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid
Kaohsiung, Taiwan
October 06-October 09
ISBN: 0-7695-2017-0
Noriyuki Fujimoto, Osaka University
Kenichi Hagihara, Osaka University
The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the computing power of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid. In this paper, a novel criterion of a schedule is proposed. The proposed criterion is called total processor cycle consumption, which is the total number of instructions the grid could compute until the completion time of the schedule. Moreover, for the criterion, this paper gives a (1 + \frac{{m(\log \_(m - 1) + 1)}} {n})-approximation algorithm for scheduling n idependent coarse-grained tasks with the same length onto a grid with m processors. The proposed algorithm does not use any prediction information on the performance of underlying resources. This result implies a non-trivial result that the computing power consumed by a parameter sweep application can be limited in such a case within (1 + \frac{{m(\log \_(m - 1) + 1)}} {n}) times that required by an optimal schedule, regardless how the speed of each processor varies over time.
Citation:
Noriyuki Fujimoto, Kenichi Hagihara, "Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid," icpp, pp.391, 2003 International Conference on Parallel Processing (ICPP'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.