Abstract
The race towards more processing power between all different
hardware manufacturers has in recent years faced deep changes.
We see nowadays a huge development in the use of parallel
machines with more and more cores and increasingly complex
architectures. It seems now clear that we will witness in a near
future the development of cheap Network On Chip computers.
Executing parallel applications on such machines raises several
problems. Amongst them we take in this work interest in the
problem of scheduling a set of tasks on a set of computing
resources. Between all existing methods we can generally
distinguish on-line or off-line algorithms. On-line algorithms
like
work-stealing present the advantage to work without
informations on hardware or tasks durations but do not generally
achieve an efficient control of communications. In this book we
take interest in on-line tasks scheduling on complex platforms
where networking can impact (through congestion) performance.
More precisely, we propose several new scheduling algorithms
based on work-stealing targeting two different configurations.
In a first study, we consider applications whose dependency
graph is known in advance. By taking advantage of this
information we manage to limit the amount of data transfered and
thus to achieve high performance and even outperform the best
known off-line algorithms. Concurrently to that, we also study
possible optimisations in the case where knowledge of platform
topology is available. We show again that it is possible to use
this information to enhance performance.
Our work allows therefore to extend the application field of
scheduling algorithms towards more complex architectures and we
hope will allow a better use of tomorrow’s machine.
Keywords: parallel algorithms, work-stealing, scheduling,
platform topology, communications.
Main Outputs
Publications
Slides
Slides
Thesis in French
French thesis
