Computer Science Colloquium

Designing parallel algorithms on heterogeneous platforms (such as networks of different-speed workstations and clusters of such networks) turns out to be surprisingly difficult. Scheduling, load-balancing and data allocation, which were already difficult tasks in the context of equal-speed processors, all become quite complicated when heterogeneity comes into the playground. Even a simple kernel such as matrix multiplication leads to NP-hard problems.

We survey the design of a few parallel algorithms for distance transforms, matrix multiplication, LU decomposition, and master-slave tasking. We state several optimization problems, most of them> shown to be NP-complete, but we also introduce efficient data-allocation heuristics, some of which we are able to guarantee by approximation factors.Finally we state several open problems.

Joint work with Olivier Beaumont, Vincent Boudet, Arnaud Legrand and Fabrice Rastello, all with the ReMaP team at LIP, ENS Lyon.

Yves Robert is a full professor in the Computer Science Laboratory LIP at ENS Lyon. He is the author of three books, more than 80 papers published in international journals, and more than 90 papers published in international conferences. His main research interests are parallel algorithms for distributed memory architectures and automatic compilation/parallelization techniques. He is an associate editor for IEEE Trans. Parallel and Distributed Systems.