Extending IC-scheduling via the Sweep Algorithm

A key challenge when scheduling computations over the Internet is : 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 that models the computation being scheduled—namely, that the be decomposable into bipartite “building-block” s. The current paper extends the theory by developing the , 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 s that the earlier framework could not handle. Most of the newly optimally scheduled s presented here are artificial but “close” in structure to s that arise in real computations; one of the new s is a component of a large that arises in a functional Magnetic Resonance Imaging application.