Design and programming of multi-threaded algorithms in Scotch

Supervisor : François PELLEGRINI (LaBRI & INRIA Bordeaux - Sud-Ouest)
E-mail :

Presentation of the proposal of internship

Many optimization problems can be modeled on the form of a constrained partitioning problem of a graph representing the initial problem to solve. To compute good-quality partitions in an acceptable time, several graph partitioning tools have been developed, such as the Scotch [1] software developed in Bordeaux within the Tadaam projet-team of Inria.

In order to handle very large graphs, many tools take advantage of shared-memory or distributed-memory parallelism, using features such as POSIX pThreads (for the former) or MPI (for the latter). Due to Amdahl's law, perfect scalability cannot be achieved. Therefore, parallelization efforts concentrate on the most time-consuming parts of the software. Version v7.0 of Scotch brought many improvements in terms of parallelization, notably regarding the multilevel framework [2], which is the most time-consuming part of the partitioning algorithms.

The main purpose of this internship is to pursue the parallelization of Scotch, by providing shared-memory, parallel versions of other commonly used algorithms. This phase of the internship will consequently start by prototyping the current version of Scotch, using the gprof tool, to identify the modules most likely to benefit from this rewriting.

The porting of the Scotch thread model onto the Windows platform may also be envisioned.

Depending on the outcome of the first phase described above, in a second phase, the internship may tackle the issue of finalizing the ScotchPy Python wrapper library for Scotch. ScotchPy, which relies on NumPy to handle number arrays, has been developed by a former intern during the covid crisis, and is close to completion. The aim is consequently to complete and release a first public version of this library, and to get feedback from its early users. A Julia wrapper is also envisioned, but is not a priority. The interest of Julia is that it handles multi-threading natively, so that users can benefit from the multi-threading capabilities of Scotch from the caller level, in terms of data locality.

Other tasks may be scheduled, depending on the evolution of the Scotch roadmap.

To sum-up: this project deals with software engineering in the context of a high-end scientific software, used by a wide academic and industrial community.

Keywords : graph, partitioning, multi-threading.

Prerequisites : A good knowledge of C programming is mandatory. Prior knowledge of parallel programming in shared memory (threads) is most welcome. Knowledge in MPI is a plus. Some knowledge of Python may be useful to address the aforementioned secondary topic.

Comments : This internship will take place at the Inria research center in Bordeaux.
In case of outstanding results, the intern may pursue their work on this project, either as a research engineer or as a PhD student.

References :
[2] For more information on the implementation of a multilevel framework in Scotch, see :