Scotch
Supervisor : François PELLEGRINI (LaBRI & INRIA Bordeaux - Sud-Ouest)
E-mail : francois.pellegrini@u-bordeaux.fr
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 :
[1] https://gitlab.inria.fr/scotch/scotch/
[2] For more information on the implementation of a multilevel framework in Scotch,
see : http://tel.archives-ouvertes.fr/docs/00/54/05/81/PDF/hdr.pdf