Scheduling large jobs by abstraction refinement

Thomas A. Henzinger, Vasu Singh, Thomas Wies, Damien Zufferey

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


The static scheduling problem often arises as a fundamental problem in real-time systems and grid computing. We consider the problem of statically scheduling a large job expressed as a task graph on a large number of computing nodes, such as a data center. This paper solves the large-scale static scheduling problem using abstraction refinement, a technique commonly used in formal verification to efficiently solve computationally hard problems. A scheduler based on abstraction refinement first attempts to solve the scheduling problem with abstract representations of the job and the computing resources. As abstract representations are generally small, the scheduling can be done reasonably fast. If the obtained schedule does not meet specified quality conditions (like data center utilization or schedule makespan) then the scheduler refines the job and data center abstractions and, again solves the scheduling problem. We develop different schedulers based on abstraction refinement. We implemented these schedulers and used them to schedule task graphs from various computing domains on simulated data centers with realistic topologies. We compared the speed of scheduling and the quality of the produced schedules with our abstraction refinement schedulers against a baseline scheduler that does not use any abstraction. We conclude that abstraction refinement techniques give a significant speed-up compared to traditional static scheduling heuristics, at a reasonable cost in the quality of the produced schedules. We further used our static schedulers in an actual system that we deployed on Amazon EC2 and compared it against the Hadoop dynamic scheduler for large MapReduce jobs. Our experiments indicate that there is great potential for static scheduling techniques.

Original languageEnglish (US)
Title of host publicationEuroSys'11 - Proceedings of the EuroSys 2011 Conference
Number of pages14
StatePublished - 2011
Event6th ACM EuroSys Conference on Computer Systems, EuroSys 2011 - Salzburg, Austria
Duration: Apr 10 2011Apr 13 2011

Publication series

NameEuroSys'11 - Proceedings of the EuroSys 2011 Conference


Other6th ACM EuroSys Conference on Computer Systems, EuroSys 2011


  • Abstraction refinement
  • Data centers
  • Scheduling

ASJC Scopus subject areas

  • Control and Systems Engineering


Dive into the research topics of 'Scheduling large jobs by abstraction refinement'. Together they form a unique fingerprint.

Cite this