134 lines
7.5 KiB
TeX
134 lines
7.5 KiB
TeX
%{{{ résumé "
|
|
\begin{abstract}
|
|
%{{{
|
|
L'écriture de programmes parallèles, par opposition aux programmes \og classiques \fg{} séquentiels
|
|
et n'utilisant donc qu'un processeur, est devenue une nécessité.
|
|
En effet, si jusqu'au début du millénaire la puissance de calcul des ordinateurs dépendait
|
|
principalement de la fréquence du processeur, elle est maintenant liée au nombre de cœurs de calcul
|
|
qui sont de plus en plus nombreux.
|
|
Pourtant, à cause des difficultés introduites par la parallélisation, la plupart des programmes sont
|
|
toujours écrits de manière \og classique \fg.
|
|
En particulier, il peut être compliqué de déterminer, étant donné une sous partie d'un programme, si
|
|
la parallélisation est possible, c'est-à-dire si elle n'introduira pas un changement de comportement
|
|
du programme.
|
|
Cependant, même en sachant précisément ce qui peut être parallélisé, le faire correctement est aussi
|
|
une tâche difficile.
|
|
Cette thèse présente deux approches pour simplifier l'écriture de programmes parallèles.
|
|
|
|
Nous proposons une bibliothèque active -- par métaprogrammation template, elle agit durant la
|
|
compilation -- qui acquiert des informations à propos d'une portion de programme, correspondant à
|
|
une boucle, au moyen de patrons d'expression.
|
|
Celles-ci sont utilisées pour analyser les instructions et identifier lesquelles peuvent être
|
|
exécutées en parallèle.
|
|
Cette analyse repose sur deux niveaux de connaissance : l'ensemble des variables utilisées en
|
|
distinguant les accès en lecture de ceux en écriture, et, puisqu'il s'agit souvent de tableaux, des
|
|
fonctions d'indice.
|
|
Les variables et leur mode d'accès permettent de savoir quelles instructions sont interdépendantes
|
|
tandis que les fonctions d'indice nous servent à déterminer, pour un groupe d'instructions, s'il
|
|
est possible de procéder à une exécution parallèle des itérations de la boucle.
|
|
L'objectif de cette bibliothèque est de proposer un cadre, à la fois pour les développeurs afin
|
|
d'écrire des boucles qui seront automatiquement exécutées en parallèle si cela est possible, mais
|
|
aussi à un niveau plus élevé pour intégrer de nouvelles méthodes de parallélisation ou d'autres
|
|
règles à utiliser pour l'analyse.
|
|
|
|
Nous proposons également une seconde bibliothèque, active elle aussi, orientée sur la
|
|
parallélisation assistée en utilisant la technique des squelettes algorithmiques comme interface
|
|
pour le développeur.
|
|
Celle-ci permet de représenter des algorithmes complets comme des assemblages de motifs d'exécution
|
|
: séquence de tâches ; exécution répétée d'une tâche en parallèle ; ...
|
|
En utilisant cette connaissance, nous pouvons mettre en place des choix dans la manière de répartir
|
|
les tâches exécutées en parallèle sur les différents processeurs.
|
|
Par ailleurs, nous avons choisi d'expliciter l'expression de la transmission des données entre les
|
|
tâches, contrairement à ce qui est habituellement fait.
|
|
Grâce à cela, la bibliothèque automatise notamment la transmission de paramètres qui ne doivent pas
|
|
être partagés par des tâches parallèles.
|
|
Cela nous permet en particulier de garantir la répétabilité des exécutions y compris lorsque, par
|
|
exemple, les tâches utilisent des nombres pseudo-aléatoires.
|
|
En tenant compte de la politique d'exécution choisie et des nombres de processeurs possibles, nous
|
|
réduisons la quantité nécessaire de ces paramètres ne devant pas être partagés.
|
|
Ainsi, cette seconde bibliothèque propose elle aussi un cadre de programmation à plusieurs niveaux.
|
|
Celle-ci est extensible au niveau de ses politiques d'exécution ou des motifs pour la construction
|
|
des squelettes algorithmiques.
|
|
On peut l'utiliser pour définir une variété de squelettes algorithmiques, lesquels serviront ensuite
|
|
à un développeur pour écrire des programmes dont la parallélisation sera facilitée.
|
|
%}}}
|
|
|
|
\vfill
|
|
\noindent\textbf{Mots-clés} :
|
|
métaprogrammation template ;
|
|
parallélisation assistée ;
|
|
parallélisation automatique ;
|
|
bibliothèques actives ;
|
|
squelettes algorithmiques ;
|
|
répétabilité.
|
|
\end{abstract}
|
|
%}}}
|
|
|
|
%{{{ abstract "
|
|
\begin{otherlanguage}{english}
|
|
\begin{abstract}
|
|
%{{{
|
|
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.
|
|
%}}}
|
|
|
|
\vfill
|
|
\noindent\textbf{Keywords}:
|
|
template metaprogramming;
|
|
assisted parallelisation;
|
|
automatic parallelisation;
|
|
active libraries;
|
|
algorithmic skeletons;
|
|
repeatability.
|
|
\end{abstract}
|
|
\end{otherlanguage}
|
|
%}}}
|