Extending IC-Scheduling via the Sweep Algorithm

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 Q by "parsing" Q (if possible) into connected building-block dags that one can "compose " to form Q and then analyzing the scheduling dependencies among these building blocks. The current paper extends the theory by developing the Sweep Algorithm, a tool that allows one 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.