loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Second International Symposium on Parallel and Distributed Computing
Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid
Ljubljana, Slovenia
October 13-October 14
ISBN: 0-7695-2069-3
Noriyuki Fujimoto, Osaka University, Japan
Kenichi Hagihara, Osaka University, Japan
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 speed of each processor 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 contrast, recently the authors proposed the computing power consumed by a scheduling as a criterion of the schedule. For the criterion, this paper gives a (1 + \frac{{L_{cp} (n) \cdot m(\log _e (m - 1) + 1)}} {n})-approximation algorithm for scheduling precedence constrained coarse-grained tasks with the same length onto a grid where n is the number of tasks, m is the number of processors, and Lcp(n) is the length of the critical path of the task graph. The proposed algorithm does not use any prediction information on the performance of underlying resources. Lcp(n) is usually a sublinear function of n. So, the above performance guarantee converges to one as n grows. This result implies a non-trivial result that the computing power consumd by an application on a grid can be limited within (1 + \frac{{L_{cp} (n) \cdot m(\log _e (m - 1) + 1)}} {n}) times that required by an optimal schedule in such a case.
Citation:
Noriyuki Fujimoto, Kenichi Hagihara, "Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid," ispdc, pp.80, Second International Symposium on Parallel and Distributed Computing, 2003
Usage of this product signifies your acceptance of the Terms of Use.