110 lines
5.6 KiB
Markdown
110 lines
5.6 KiB
Markdown
# About
|
|
|
|
Thesis title: using template metaprogramming to design active libraries for assisted parallelisation.
|
|
|
|
(French: *application de la métaprogrammation template à la conception de bibliothèques actives
|
|
de parallélisation assitée*)
|
|
|
|
## Download
|
|
|
|
- [Computer version](https://phd.pereda.fr/assets/thesis/alexis_pereda_thesis.pdf);
|
|
- [Print version](https://phd.pereda.fr/assets/thesis/alexis_pereda_thesis_print.pdf).
|
|
|
|
## Abstract
|
|
|
|
<div align="justify">
|
|
Hardware performance has been increasing through the addition of computing cores rather than through
|
|
increasing their frequency since the early 2000s.
|
|
This means that parallel programming is no longer optional should you need to make the best use of
|
|
the hardware at your disposal.
|
|
Yet many programs are still written sequentially: parallel programming introduces numerous
|
|
difficulties.
|
|
Amongst these, it is notably hard to determine whether a sequence of a program can be executed in
|
|
parallel, i.e. preserving its behaviour as well as its overall result.
|
|
Even knowing that it is possible to parallelise a piece of code, doing it correctly is another
|
|
problem.
|
|
In this thesis, we present two approaches to make writing parallel software easier.
|
|
|
|
We present an active library (using C++ template metaprogramming to operate during the compilation
|
|
process) whose purpose is to analyse and parallelise loops.
|
|
To do so, it builds a representation of each processed loop using expression templates through an
|
|
embedded language.
|
|
This allows to know which variables are used and how they are used.
|
|
For the case of arrays, which are common within loops, it also acquires the index functions.
|
|
The analysis of this information enables the library to identify which instructions in the loop can
|
|
be run in parallel.
|
|
Interdependent instructions are detected by knowing the variables and their access mode for each
|
|
instruction.
|
|
Given a group of interdependent instructions and the known index functions, the library decides if
|
|
the instructions can be run in parallel or not.
|
|
We want this library to help developers writing loops that will be automatically parallelised
|
|
whenever possible and run sequentially as without the library otherwise.
|
|
Another focus is to provide this to serve as a framework to integrate new methods for parallelising
|
|
programs and extended analysis rules.
|
|
|
|
We introduce another active library that aims to help developers by assisting them in writing
|
|
parallel software instead of fully automating it.
|
|
This library uses algorithmic skeletons to let the developer describe its algorithms with both its
|
|
sequential and parallel parts by assembling atomic execution patterns such as a series of tasks or a
|
|
parallel execution of a repeated task.
|
|
This description includes the data flow, that is how parameters and function returns are
|
|
transmitted.
|
|
Usually, this is automatically set by the algorithmic skeleton library, however it gives the
|
|
developer greater flexibility and it makes it possible, amongst other things, for our library to
|
|
automatically transmit special parameters that must not be shared between parallel tasks.
|
|
One feature that this allows is to ensure repeatability from one execution to another even for
|
|
stochastic algorithms.
|
|
Considering the distribution of tasks on the different cores, we even reduce the number of these
|
|
non-shared parameters.
|
|
Once again, this library provides a framework at several levels.
|
|
Low-level extensions consist of the implementation of new execution patterns to be used to build
|
|
skeletons.
|
|
Another low-level axis is the integration of new execution policies that decide how tasks are
|
|
distributed on the available computing cores.
|
|
High-level additions will be libraries using ours to offer ready-to-use algorithmic skeletons for
|
|
various fields.
|
|
</div>
|
|
|
|
Keywords: template metaprogramming; assisted parallelisation; automatic parallelisation; active libraries; algorithmic skeletons; repeatability.
|
|
|
|
## Related publications
|
|
|
|
- "Repeatability with Random Numbers Using Algorithmic Skeletons", ESM 2020 (https://hal.archives-ouvertes.fr/hal-02980472);
|
|
- "Modeling Algorithmic Skeletons for Automatic Parallelization Using Template Metaprogramming", HPCS 2019 (IEEE) [10.1109/HPCS48598.2019.9188128](https://doi.org/10.1109/HPCS48598.2019.9188128);
|
|
- "Processing Algorithmic Skeletons at Compile-Time", ROADEF 2020 (https://hal.archives-ouvertes.fr/hal-02573660);
|
|
- "Algorithmic Skeletons Using Template Metaprogramming", ICAST 2019;
|
|
- "Parallel Algorithmic Skeletons for Metaheuristics", ROADEF 2019 (https://hal.archives-ouvertes.fr/hal-02059533);
|
|
- "Static Loop Parallelization Decision Using Template Metaprogramming", HPCS 2018 (IEEE) [10.1109/HPCS.2018.00159](https://doi.org/10.1109/HPCS.2018.00159).
|
|
|
|
## Related projects
|
|
|
|
- [AlSk](https://phd.pereda.fr/dev/alsk), an algorithmic skeletons active library;
|
|
- [pfor](https://phd.pereda.fr/dev/pfor), an automatic parallelisation active library;
|
|
- [ROSA](https://phd.pereda.fr/dev/rosa), an algorithmic skeletons collection for [OR](https://en.wikipedia.org/wiki/Operations_research) algorithms;
|
|
- [TMP](https://phd.pereda.fr/dev/tmp), template metaprogramming library used to implement this library.
|
|
|
|
## Usage
|
|
|
|
To produce the `Makefile`:
|
|
```bash
|
|
mkdir build
|
|
cd build
|
|
cmake ..
|
|
```
|
|
|
|
Compilation has been tested with `texlive-full` version 2020.20210202-3.
|
|
|
|
To build the project:
|
|
```
|
|
make
|
|
```
|
|
|
|
Be patient, it takes *some* time.
|
|
|
|
Make can be run with these arguments:
|
|
- `pdf_thesis_oneside`: to build the "computer" version, including dynamic figures (default);
|
|
- `pdf_thesis_twoside`: same as oneside but better for double-page display;
|
|
- `pdf_thesis_print`: printing version (no dynamic figures, double-page and blank pages where required).
|
|
|
|
PDF files are generated in `build/pdf/`.
|