Stretch out and compact: Workflow scheduling with resource abundance

Resource abundance is apparent in today's multicore era. Workflow applications common in science and engineering can take great advantage of such ample resource capacity. Yet, existing workflow scheduling algorithms have been mostly designed on the traditional and contrasting premise of scarce resource capacity relative to what applications require. In this paper, we address the problem of workflow scheduling exploiting resource abundance not only for performance, but also for resource efficiency. We first present the critical-path-first scheduling algorithm, which efficiently stretches out the schedule to proactively preserve critical path length, the shortest possible time of completion. We then develop an algorithm to compact the schedule for resource efficiency. The schedule is compacted by rearranging tasks making use of idle/inefficiency slots present in the schedule due to precedence constraints (synchronization). We have compared the performance of our scheduling algorithm with three previous algorithms and evaluated the efficacy of our schedule compaction algorithm by applying it to those four scheduling algorithms including our own. Experiments were conducted in a simulated environment with various real-world scientific workflows. Results show that our scheduling algorithm achieves a great performance to resource usage ratio. Further, our schedule compaction algorithm reduces resource usage by 33% on average ranging from 11.3% to 90.7% with no makespan increases.