Extending IC-scheduling via the Sweep Algorithm

A key challenge when scheduling computations over the Internet is temporal unpredictability: remote “workers” arrive and depart at unpredictable times and often provide unpredictable computational resources; the time for communication over the Internet is impossible to predict accurately. In response, earlier research has developed the underpinnings of a theory of how to schedule computations having intertask dependencies in a way that renders tasks eligible for execution at the maximum possible rate. Simulation studies suggest that such scheduling: (a) utilizes resource providers’ computational resources well, by enhancing the likelihood of having work to allocate to an available client; (b) lessens the likelihood of a computation’s stalling for lack of tasks that are eligible for execution. The applicability of the current version of the theory is limited by its demands on the structure of the dag that models the computation being scheduled—namely, that the dag be decomposable into connected bipartite “building-block” dags. The current paper extends the theory by developing the Sweep Algorithm, which takes a significant step toward removing this restriction. The resulting augmented suite of scheduling algorithms allows one to craft optimal schedules for a large range of dags that the earlier framework could not handle. Most of the newly optimally scheduled dags presented here are artificial but “close” in structure to dags that arise in real computations; one of the new dags is a component of a large dag that arises in a functional Magnetic Resonance Imaging application.