The PT-Scotch project: purpose, algorithms, current results
Résumé
Graph partitioning is an ubiquitous technique which has applications in many fields of computer science and engineering. It is mostly used to help solving domain-dependent optimization problems modeled in terms of weighted or unweighted graphs, where finding good solutions amounts to computing, eventually recursively in a divide-and-conquer framework, small vertex or edge cuts that balance evenly the weights of the graph parts. Because there always exists large problem graphs which cannot fit in the memory of sequential computers and cost too much to partition, parallel graph partitioning tools have been developed. PT-Scotch is another attempt to provide a simple and efficient library for parallel graph partitioning and ordering. Its goal is to provide efficient parallel tools to partition graphs with sizes up to several billion vertices, distributed over a thousand processors. This deliberately ambitious goal aims at tackling frontally scalability and efficiency issues. As for many algorithmic problems, preserving the quality of produced solutions when going parallel is a hard task, because state-of-the-art algorithms used in this context, such as Fiduccia-Mattheyses-like local optimization algorithms, are intrinsically sequential. This talk will emphasize on the algorithmic challenges induced by parallelism for graph partitioning, by first exposing the sequential framework, and then the parallel solutions that we devised for several of its key algorithms.