loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008)
On Non-Approximability of Coarse-Grained Workflow Grid Scheduling
May 07-May 09
ISBN: 978-0-7695-3125-0
Scheduling a scientific workflow onto a computational grid is considered. A computational grid can be regarded as a heterogeneous parallel machine such that the speed of each processor varies over time. A scientific workflow can be modeled as a DAG of tasks. This paper focuses on a coarse-grained workflow. So, any communication delay between tasks is negligible because computation time of every task is much longer than the corresponding communication delay.??Hence, in this paper, a coarse-grained workflow grid scheduling problem (WSP for short) is defined as an extension of the classical precedence constrained scheduling problem over a uniform parallel machine with processor speed fluctuation. The objective of our problem is to minimize the makespan of a schedule. It is known that no approximation algorithm exist if a grid has a very long period with zero spare computing power. However, such situation seems to be unrealistic. This paper gives a proof that, unless P=NP, WSP is not approximable within a factor of 1.5 even if accurate performance prediction is possible, all processors have the same peak speed, and??speed of every processor at any time is restricted to either 50% or 100% of the peak speed. Since the quite restricted problem is not approximable, any more general problem such that accurate performance prediction is impossible and/or processor speed fluctuation pattern isnot restricted is also not approximable. So, the proof implies that WSP is not approximable within a factor of 1.5 in realistic grid environment unless P=NP.
Index Terms:
grid computing, workflow, scheduling, non-approximability
Citation:
Noriyuki Fujimoto, "On Non-Approximability of Coarse-Grained Workflow Grid Scheduling," ispan, pp.127-132, The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.