Stretch out and compact

Workflow scheduling with resource abundance

Young Choon Lee, Albert Y. Zomaya

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

22 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2013
EditorsPavan Balaji, Dick Epema, Thomas Fahringer
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages219-226
Number of pages8
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2013 - Delft, Netherlands
Duration: 13 May 201316 May 2013

Other

Other13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2013
CountryNetherlands
CityDelft
Period13/05/1316/05/13

Fingerprint Dive into the research topics of 'Stretch out and compact: Workflow scheduling with resource abundance'. Together they form a unique fingerprint.

  • Cite this

    Lee, Y. C., & Zomaya, A. Y. (2013). Stretch out and compact: Workflow scheduling with resource abundance. In P. Balaji, D. Epema, & T. Fahringer (Eds.), Proceedings - 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2013 (pp. 219-226). [6546096] Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/CCGrid.2013.55