Automatic Resource-Constrained Static Task Parallelization - A Generic Approach

Computer science, more specifically High Performance Computing (HPC)


This thesis intends to show how to efficiently exploit the parallelism present in scientific computer applications in order to enjoy the performance benefits that multiprocessors can provide, using a new automatic task parallelization methodology for compilers. The key characteristics of this research work are resource constraints and static scheduling.

Automatic Task Parallelization:

The proposed methodology includes the techniques required to decompose scientific computer programs into tasks and generate equivalent parallel code, using a generic approach that targets both different parallel languages and architectures. We apply this methodology in PIPS, a comprehensive source-to-source compilation platform.Three issues are addressed. First, since extracting task parallelism from sequential codes is a scheduling problem, an efficient, automatic scheduling algorithm called BDSC for parallelism detection has been designed and implemented; the result is a scheduled data dependence graph, called SDG, a new task graph data structure. In a second step, a new generic parallel intermediate representation extension called SPIRE has been introduced, in which parallelized code can be expressed. Finally, wrapping up the goal of automatic parallelization, a new BDSC- and SPIRE-based parallel code generator had been implemented and integrated within the PIPS compiler framework. It targets both shared anddistributed memory systems, using automatically generated OpenMP and MPI code.

Research results:
  • The BDSC scheduling algorithm. It handles simultaneously two resource constraints, namely a bounded amount of memory per processor and a bounded number of processors. These  are key parameters when scheduling tasks on actual multiprocessors.
  • SPIRE. This new and general 3-step extension methodology can be used to map any intermediate representation (IR) used in compilation platforms for representing sequential programming constructs to a parallel IR.
  • A prototype of the algorithms presented in the thesis, implemented in the PIPS source-to-source compilation framework. Performance measurements for this new parallelization approach have been gathered for five significant programs: the image and signal processing benchmarks Harris and ABF, the SPEC2001 benchmark equake, the NAS parallel benchmark IS, and the FFT, targeting both shared and distributed memory architectures. Automatic translations into two parallel languages, OpenMP and MPI, have been developed.


Dounia Khaldi is a doctor of MINES ParisTech since November 27th, 2013. Advised by François Irigoin and Corinne Ancourt at Centre de recherche en informatique (CRI) of MINES ParisTech, her research work was focused on the automatic task parallelization of sequential programs.

Dounia Khaldi obtained her engineering diploma in computer science at the Ecole supérieure d’informatique in Algiers, Algeria, in 2009. She was granted a Master Recherche, majoring in HPC (High Performance Computing), by the Université de Versailles Saint-Quentin-en-Yvelines in 2010. During her studies, she specialized in compilation, HPC and parallelism issues. How to go faster using current multiprocessors and parallel architectures was the main problem to solve. Preparing a PhD thesis was for her a life dream, which is realized at MINES ParisTech.

Dounia Khaldi chose her PhD subject because of the challenges and complexity of automatically parallelizing sequential programs. Since she was used to writing parallel programs by hand, this time the challenge was to have it automatically performed by software. She was very ambitious and motivated to work within the CRI environment, where she was influenced and taught by different brilliant researchers there. During these last three years, she used many scientific, signal and image processing benchmarks to verify and apply her approach. Current results look really exciting.