2019-01286 - PhD Position F/M Automatic task-based parallelization and scheduling for OO languages by source-to-source transformations [S]

Contract type : Public service fixed-term contract

Level of qualifications required : Graduate degree or equivalent

Other valued qualifications : M.S. in Computer Science

Fonction : PhD Position

Context

The Inria CAMUS/ICube ICPS research team focus on automatic parallelization and optimization, profiling, modeling, and compilation. The team has increasing interests for the approaches used and enhanced in the high-performance community such as the task-based method.

Assignment

Scientific Context

The task-based method consists in dividing an application into interdependent sections, called tasks, and providing the dependencies between them. The dependencies allow obtaining valid parallel executions, i.e. with a correct execution order of the tasks and without any race conditions. The method has gained popularity in the high-performance computing community because it allows parallelizing with an abstraction of the hardware by delegating the task distribution and the load balancing to the dynamic schedulers. See [1] for an illustrative application that relies on the method. While all aspects related to the TB parallelization are active research topics, the method is mainly used by HPC experts because parallelizing a code must be done manually. With this in mind, the position aims in solving the challenges to bridge the gap between automatic parallelization and the task-based method.

Missions

The project aims in having an automatic task-based parallelization system for C++ code-based applications using the sequential task-flow (STF) model. In this model, a sequential code (i.e. a code that is originally not designed to run in parallel) is annotated to decide what sections to transform into tasks and how these ones access the data. From this description, a runtime system can build a graph of tasks and execute them in parallel, while respecting the data dependencies.

The transformation from an STF code to a graph of tasks is done by a runtime system. The current project will focus on the transformation from a sequential code to an STF code. To do so, a source-to-source transformation of sequential C++ source code will insert tasks and data accesses. The first step will be to consider one function/method as one task and will manage the data accesses at “object” level (one object == one data handle). Then, the research work will focus on fighting the successive pitfalls that will arise and increase the performance/degree of parallelism.

Main activities

We provide here a non-exhaustive list of possible key challenges:

  • How to manage the granularity to enable/disable tasking at runtime
  • How/when to split a function/loop into tasks
  • How to detect patterns for commutative data accesses to increase the degree of parallelism, such as in [2], or to enable speculative execution, as done manually in [3]
  • How/when to remove/delay/regroup synchronizations
  • How to schedule an automatically parallelized application, including on heterogeneous architectures using our own LAHeteroprio scheduler [4]
  • How to move to automatic distributed parallelization using a common task declaration strategies, as the one used in [5]

The significant results from past and on-going researches on automatic parallelization will give few hints and will help to parallelize computational loops, see [6,7] for example. The validation of the proposed solutions will be done on large open-source C++ projects that are currently sequential.

Technology

The source-to-source transformation system will be based on clang-LLVM. It will be developed on a modern Gitlab and proposed to the community with an open-source license. We will rely on our in-house runtime system SPETABARU to manage and execute the tasks.

References

[1] Emmanuel Agullo, Berenger Bramas, Olivier Coulaud, Eric Darve, Matthias Messner, and Toru Takahashi. Task-based FMM for heterogeneous architectures. Concurrency and Computation: Practice and Experience, 28(9):2608–2629, 2016.
[2] Emmanuel Agullo, Olivier Aumage, Berenger Bramas, Olivier Coulaud, and Samuel Pitoiset. Bridging the gap between OpenMP and task-based runtime systems for the fast multipole method. IEEE Transactions on Parallel and Distributed Systems, 28(10), 2794–2807, 2017.
[3] Increasing the Degree of Parallelism Using Speculative Execution in Task-based Runtime Systems, Berenger Bramas, 2018 (under review)
[4] Impact Study of Data Locality on Task-Based Applications Through the Heteroprio Scheduler, Berenger Bramas, 2018 (under review)
[5] Task-based fast multipole method for clusters of multicore processors, Emmanuel Agullo, Olivier Coulaud, Martin Khannouz, Luka Stanisic, Berenger Bramas, 2016, Technical report
[6] Polyhedral parallelization of binary code, Benoit Pradelle, Alain Ketterlin, Philippe Clauss, 2012, ACM Transactions on Architecture and Code Optimization (TACO), Volume 8, Number 4
[7] APOLLO: Automatic speculative POLyhedral Loop Optimizer, J. M. M. Caamaño, A. Sukumaran-Rajam, A. Baloian, M. Selva, P. Clauss, IMPACT 2017-7th International Workshop on Polyhedral Compilation Techniques (p. 8).

Skills

  • C++ (17)
  • Knowledge of compilation would be really appreciated
  • Knowledge of parallel programming/computing is an asset

 

Application deadline

May 1st, 2019(Midnight Paris time)

How to apply

The candidates are required to provide the following documents in a single pdf or ZIP file:

  • CV
  • A cover/motivation letter describing their interest in the topic
  • Degree certificates and transcripts for Bachelor and Master (or the last 5 years)
  • Master thesis (or equivalent) if it is already completed, or a description of the work in progress, otherwise
  • The publications (or web links) of the candidate, if any (it is not expected that they have any)

In addition, one letter of recommendation from the person who supervises(d) the Master thesis (or research project or internship) should be sent directly by his/her author to the prospective PhD advisor.

The advisor should send the above documents as well as the research subject and an argumentation.

Benefits package

  • Subsidized meals
  • Partial reimbursement of public transport costs
  • Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
  • Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
  • Professional equipment available (videoconferencing, loan of computer equipment, etc.)
  • Social, cultural and sports events and activities
  • Access to vocational training
  • Social security coverage

Remuneration

Salary: 1982€ gross/month for 1st and 2nd year. 2085€ gross/month for 3rd year.

Monthly salary after taxes : around 1596,05€ for 1st and 2nd year. 1678,99€ for 3rd year. (medical insurance included).