loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008)
Extending IC-Scheduling via the Sweep Algorithm
February 13-February 15
ISBN: 978-0-7695-3089-5
Earlier work has developed the rudiments of a scheduling theory for computations having intertask dependencies---modeled via dags---for Internet-based computing.??The goal of the schedules produced is to render tasks eligible for execution as fast as possible, with the aim of: ($a$) utilizing clients' computational resources??well, by always having work to allocate to an available??client; ($b$) lessening the likelihood of a computation's stalling for lack of eligible tasks. Simulation studies suggest that this goal does accelerate computation over the Internet.??The theory crafts a schedule for a dag $\g$ by "parsing'' $\g$ (if possible) into connected building-block dags that one can "compose'' to form $\g$ and then analyzing the scheduling dependencies among these building blocks.??The current paper extends the theory by developing the {\em Sweep Algorithm}, a tool that allowsone to: ($1$) schedule using building blocks that are not necessarily connected, and ($2$) craft schedules that interleave the execution of subdags that have no interdependencies.??The augmented scheduling algorithms allow one to craft optimal schedules for previously unschedulable dags.??Examples presented include artificial dags that are "close'' to ones arising in real computations, as well as a component of a dag that arises in a functional MRI application.
Index Terms:
IC-Scheduling Theory, Internet-based computing, gridcomputing, globalcomputing, schedulingDAGs
Citation:
Gennaro Cordasco, Grzegorz Malewicz, Arnold L. Rosenberg, "Extending IC-Scheduling via the Sweep Algorithm," pdp, pp.366-373, 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.