CR-07 : Scheduling

(This course will be delivered in English on demand)

Scheduling is sub-part of Operation Research, which aims at allocating resources to tasks, and organize their processing, so as to optimize a given objective (which could be total execution time, throughput, etc). In this course, we will study the scheduling problems which appears in computer systems, and in particular on parallel computing platforms.

We will first present the classical scheduling problems and techniques, and gradually introduce models which account for the characteristics of modern computing platforms, and at the same time allow to keep optimization problems tractable. Then, we will present specific objectives for these platforms, as well as the techniques
employed to solve corresponding problems.

Tentative outline:

  1. Classical approaches in scheduling
    • introduction and classical problem (list scheduling, Smith ratio, etc.)
    • application modeling (task graphs, flow-shop, moldable tasks, etc.
    • NP-completeness, approximation algorithms
    • online and non-clairvoyant scheduling
  2. Towards a more realistic model for computing platforms
    • introduction of communication costs
    • divisible load scheduling
    • steady-state scheduling
    • interference-aware scheduling
  3. New objectives and techniques in scheduling
    • fault tolerance and robustness
    • energy-aware scheduling
    • multi-organisation scheduling
    • game theory
    • stochastic approach
    • multi-criteria scheduling

All techniques will be illustrated through case studies.

Evaluation. The evaluation will consist in article analysis and presentation. Some classes will allow the student to practice reading articles and commenting on them.

Pre-requisite: Parallel Algorithm course in M1 (desirable but not essential); for motivated students, studying thoroughly a few chapters of the corresponding book should be enough.

Instructors

  • Loris Marchal, CR CNRS
  • Frédéric Vivien, DR INRIA