# 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.