Graph Partitioning and its application to MPI (message passing interface)

Details

Supervisors

Hendrickx, Julien

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

This thesis lies at the crossroad of graph theory and high performance computing. The rise of increasingly bigger supercomputers has made the distributed computing paradigm more prominent than ever before. The Message Passing Interface (MPI) provides a standard describing how we can take advantage of distributed computing to unleash the full power of these machines. But even the best system in the world is subject to a simple physical limit : the time it takes for data to travel. In this work, we model distributed computing applications as a graph in which vertices are processes and edges represent the communications in between processes. We then use graph partitioning techniques to group processes on the same node of the supercomputer. In that regard, we attempt to minimize the total communication time of the application. We develop a library for this purpose and apply it to minimize the communication time of FLUPS, a scientific application solving 3D Poisson equations through FFTs. We find that our library is able to reduce the overall runtime of FLUPS by up to 20% on Lucia, a Belgian supercomputer. We believe the results obtained on FLUPS can be obtained for other type of software such as finite-difference solvers.