Exploiting hierarchical task submission within sparse direct solvers

The goal of the internship will be to evaluate the usage of the hierarchical tasks programing model from the StarPU runtime system within the sparse direct solver PaStiX.

Over the past few years, parallel sparse direct solvers have made significant progress [1]. They are now able to solve efficiently real-life three-dimensional problems having in the order of several millions of equations. The ongoing hardware evolution exhibits an escalation in the number, as well as in the heterogeneity, of the computing resources.

PaStiX [2] is a parallel sparse direct solver, based on a dynamic scheduler for modern hierarchical architectures and developped in the Inria TOPAL team. Recently, to support modern heterogeneous architectures and low-rank compression formats, the library has been completely rewritten to better integrate support for runtime systems [3]. One of the main issue when using task-based runtime systems and sparse direct solver is the management of the task granularity. Indeed, the largely varying sizes in sparse solvers induce heterogenity in the computations and a potentially large task submission overhead.

Over the last three years, a new paradigm model has been developped in the StarPU runtime system in the context of G. Lucas’s PhD. This new model proposes to submit tasks in a hierachical fashion which allows the developper and/or the runtime system to dynamically split tasks into smaller ones, or to keep them as large tasks. It also allows for a finer management of the number of tasks submitted in the system by delaying the submission of subgraph when needed.

The goal of the internship will be to investigate how hierachical task submission can be exploited in the PaStiX solver to reduce the task submission overhead, but also to improve dynamically the task granularity based on the problem size and the targetted architecture.

In this context, the internship student will need to interact with both teams: TOPAL who develop PaStiX and Storm who develop StarPU to reach the internship objectives. The results may be validated with a publication in a conference.


sparse direct solver, task-based runtime system


  • MPI and multi-threaded programming
  • Basics in linear algebra

Contacts :

Lieu du stage :

  • Inria Bordeaux - Sud-Ouest


[1] Anshul Gupta. Recent progress in general sparse direct solvers. Lecture Notes in Computer Science, 2073:823–840, 2001.

[2] Pascal Hénon, Pierre Ramet, and Jean Roman. PaStiX: A High-Performance Parallel Direct Solver for Sparse Symmetric Definite Systems. Parallel Computing, 28(2):301-321, January 2002.

[3] Xavier Lacoste, Pierre Ramet, Mathieu Faverge, Yamazaki Ichitaro, and Jack Dongarra. Sparse direct solvers with accelerators over DAG runtimes. Research Report RR-7972, INRIA, 2012.