Research topics

During my PhD., my research interests included parallel computing and scheduling, like steady-state scheduling. We have numbers of tasks to process, a parallel platform (like a cluster or a computing grid) to handle them, and the problem is to define a good mapping of these tasks to the processors, to optimize the total computation time, or similar objective value.

My PhD is available online, as well as the slides of the defense presentation.

Divisible load scheduling

The Divisible Load Theory (DLT) addresses the problem of scheduling a large amount of identical, fine-grain computations on a parallel platform, typically a master-worker platform. These computations have to be perfectly parallel, without any inter-task dependences, and we assume that we can split them in chunks of arbitrary sizes. Widespread by Bharadwaj, Ghose, Mani, and Robertazzi, ten years ago, this model is a simple relaxation of the original scheduling problem, allowing many variants of it to be tractable. The model remains tractable even if we use fully heterogeneous platforms. However, this model shows its limits as soon as we add latencies or return messages, most of the problems being NP-complete.

Steady-state scheduling

Usually, we aim to minimize the makespan, i.e. the total computation time. In Steady-State scheduling, we assume that we have a great number of copies of the same task graph (a directed acyclic graph, DAG), and we focus on the heart of the scheduling, searching for a periodic scheme, without optimizing the initialization or the terminaison of the schedule. The whole set of constraints defining a multi-allocations scheme can be expressed as a rational linear program. However, looking for the best mono-allocation schedule is a harder problem, even if the solution can be by far easier to implement.

Stochastic scheduling and Petri nets

Let us consider linear workflows (or pipelines), each stage being mapped on several processors. Each instance is distributed to processors in a round-robin fashion. Even if this mapping is rather simple, the quality of it, defined by its average throughput, is hard to determine. Nonetheless, its quality can be assessed if we model it by a Timed Petri Net. Finally, TPNs allow us to handle the more general problem of dynamic platform, representing the use of a computational grid shared by several users if we assume that the communication and computation times follow common distribution laws.