New Challenges in Scheduling Theory

October 21 - 27, 2012 --- Centre CNRS "La Villa Clythia", Frejus, France

Task-graph scheduling to minimize memory

SpeakerLoris Marchal

As the cost of floating-point operations decreases compared to the cost of storing and moving data, the classical makespan metric may become irrelevant, and new metrics such as memory cost or number of input/output (I/O) operations may arise. We revisit the problem of scheduling task-graphs whose tasks require large I/O files. Our objective is to minimize the memory needed for their processing, if the available memory is smaller than needed, or to minimize the amount of I/O in an out-of-core execution. In this talk, we will review some previous studies that date back to the 1980's for the sequential processing of tree-shaped task-graphs, as well as recent attempts to extend these results to other classes of graphs and to parallel processing.