thesis/src/0_intro.tex

\chapterx*{Introduction}

%{{{ introduction "
L'informatique est employée dans de nombreux domaines, que ce soit comme sujet d'étude ou comme
outil d'application, notamment en sciences, y compris dans le cadre de démonstrations mathématiques.
L'évolution de celle-ci repose de manière croissante sur la puissance de calcul qu'apportent les
ordinateurs.
Or, jusqu'au début des années \num{2000}, la puissance d'un ordinateur dépendait sensiblement de la
fréquence du processeur qui effectue les calculs, laquelle a été confrontée à une limite physique au
delà de laquelle les fuites de courants étaient trop importantes, allant même jusqu'à faire fondre
les processeurs~\autocite{ref:namsungkim2003}.

Depuis, pour outrepasser cette limite, les processeurs se voient pourvus de cœurs de calcul de plus
en plus nombreux.
En dehors de notions élémentaires, l'utilisation de l'informatique comme outil pour résoudre des
problèmes nécessite surtout des connaissances dans le domaine du problème.
Mais l'utilisation concurrente de plusieurs cœurs de calcul introduit des difficultés propres à
l'informatique et donc une expertise que n'ont pas la plupart de ses utilisateurs, et qu'ils ne
devraient pas être contraints à maîtriser.
Ces difficultés couvrent des sujets variés, incluant la connaissance du fonctionnement du matériel,
de son interaction avec les couches logicielles les plus basses jusqu'à des principes propres à la
programmation concurrente : gestion de la communication entre les éléments concurrents ;
synchronisation du travail effectué ; implémentation de patrons de conception dédiés ; maintien de
la répétabilité malgré l'utilisation de nombres pseudo-aléatoires ; ...
Du fait de ces difficultés, une majorité de programmes sont développés sans bénéficier réellement du
potentiel du matériel à disposition.
%}}}

%{{{ solutions existantes "
Des solutions ont naturellement été étudiées, permettant d'abord l'utilisation des mêmes primitives
indépendamment de l'architecture exacte sur laquelle est déployé le programme, là où initialement
chaque système fournissait sa propre interface.
Des instructions spécifiques, mettant en place tout ce qui est nécessaire à la parallélisation, ont
été introduites, notamment au sein de certains compilateurs.
Cette technique va jusqu'à la création de langages dédiés exposant des syntaxes adaptées.
Tout cela a participé à assister les développeurs dans l'écriture de programmes s'exécutant en
parallèle sur plusieurs processeurs.

Il s'est également agit de proposer l'automatisation de la génération de programmes parallèles à
partir de leur écriture séquentielle classique.
Différentes techniques existent, dont, à nouveau, l'exploitation des compilateurs pour analyser le
code source et produire, sans que soit nécessaire une intervention de la part du développeur, un
programme dont l'exécution est
parallèle~\autocite{ref:zima1988,ref:blume1995,ref:ahmad1997,ref:fonseca2016}.
Similairement, des langages de programmation se sont mis à intégrer des constructions orientées vers
la parallélisation et plus ou moins transparentes pour le
développeur~\autocite{ref:roscoe1988,ref:loveman1993,ref:chamberlain2007,ref:rieger2019}.

Autant pour l'implémentation d'outils simplifiant la mise en œuvre de la parallélisation que pour
son automatisation, de nombreuses bibliothèques logicielles sont disponibles et permettent
d'apporter à l'existant -- langages et compilateurs -- de nouvelles
possibilités~\autocite{ref:kuchen2002a,ref:chan2004,ref:falcou2008,ref:videau2018,ref:ernstsson2018}.
Il est même possible, dans certains cas, qu'une bibliothèque logicielle (indépendante du
compilateur) agisse pratiquement aussi profondément que le peut une extension de compilateur (à
l'inverse, spécifique à celui-ci).
Ces bibliothèques, dites actives~\autocite{ref:veldhuizen1998a}, ouvrent la voie à de nouvelles
façons de proposer des outils aux développeurs.
%}}}

%{{{ besoin "
Les solutions aux problèmes de la parallélisation basées sur des bibliothèques logicielles actives
sont relativement peu nombreuses par rapport aux autres approches.
Elles sont plus contraignantes à produire qu'une extension de compilateur.
Il est notamment difficile d'en écrire une qui ne cause effectivement pas un surcoût rédhibitoire en
temps d'exécution, en mémoire utilisée ou encore en temps de compilation, comparé à une
implémentation manuelle ou à ce qui se fait au niveau des compilateurs.
Selon le cadre dans lequel la bibliothèque active est conçue, il peut également être
particulièrement difficile de déboguer.

Le C++ et ses templates, supportant une forme de métaprogrammation à la base de ce qui permet
l'élaboration de bibliothèques actives au sein de ce langage, est connu pour cela.
En partie parce que ces templates n'ont pas été pensé initialement pour cela (ils servent avant tout
à la dimension générique du langage), il est difficile de suivre ce qu'ils causent durant la
compilation.
Malgré cette limite, qui tend par ailleurs à s'amoindrir avec les évolutions du langage, cette forme
de métaprogrammation est très employée car elle permet, lorsqu'elle est bien utilisée, d'atteindre
des résultats très proches de ce que l'on obtiendrait en écrivant soi-même le code produit.
%}}}

%{{{ proposition "
Avec cette thèse, nous voulons proposer principalement deux nouveaux outils.
Le premier est un outil de parallélisation automatique, avec une bibliothèque active détectant
elle-même ce qui peut validement être exécuté en parallèle et qui génère le code correspondant.
La détection doit reposer sur des mécanismes extensibles afin de permettre l'ajout de nouvelles
règles, déterminant, à partir des accès aux variables, ce qu'il est possible de faire de chaque
instruction.
Similairement, la génération de code doit avoir la capacité de fonctionner indépendamment de la
méthode de parallélisation sous-jacente.
Pour cela, il faut donc voir la manière de paralléliser comme une simple configuration qui peut être
indiquée à la bibliothèque plutôt que comme un élément qui lui est central.
À l'inverse, le fonctionnement de la bibliothèque ne doit pas affecter négativement et
significativement la performance du programme par rapport à ce qui peut être accompli similairement
\og à la main \fg.
Cela doit en particulier être vrai lorsque son utilisation aboutit à un programme non parallélisé.

Le second outil relève, quant à lui, de la parallélisation assistée, laquelle laisse au moins à la
charge du développeur le soin de décider quelles sections du programme doivent être parallélisées
avec une deuxième bibliothèque, également active.
Pour ceci, nous proposons une nouvelle vision des squelettes algorithmiques avec davantage de
contrôle de la part du développeur.
Un but est de permettre une utilisation très flexible des squelettes algorithmiques, par exemple sur
l'aspect de la transmission des paramètres entre les différentes parties d'un squelette.
Un autre but est l'analyse des squelettes algorithmiques durant la compilation pour en déduire, par
exemple, des optimisations possibles de celui-ci ou des schémas efficaces d'exécution parallèle.
La parallélisation, particulièrement lorsqu'elle est combinée à l'utilisation de nombres
pseudo-aléatoires, rend plus difficile la préservation de la répétabilité d'un programme,
c'est-à-dire la capacité à exécuter plusieurs fois ce programme dans les mêmes conditions en
obtenant systématiquement le même résultat.
Sans répétabilité, la capacité de débogage est illusoire, et pour cette raison, nous voulons
proposer un moyen de garantir cette répétabilité grâce aux squelettes algorithmiques.
%}}}

%{{{ structure "
Ce document présente les travaux effectués au titre de cette thèse.
Pour ce faire, il est scindé en \num{5} chapitres.
\Acref{ch:par} traite de la parallélisation en partant des notions élémentaires matérielles et
logicielles et en allant jusqu'aux concepts spécifiques de plus haut niveau qui permettent de
résoudre des problèmes introduits par cette discipline.
Ce chapitre détaille ensuite différentes couches supérieures qui simplifient l'application de la
parallélisation, principalement sur les deux aspects que sont la parallélisation automatique et la
parallélisation assistée.

\Acref{ch:gnx} introduit un paradigme de programmation nommé \og généricité \fg, en particulier en
C++.
En effet, la généricité de ce langage fonctionnant durant la compilation grâce, entre autres, aux
templates, est à la base de la métaprogrammation template.
Y sont donc traitées la création et l'utilisation de templates, ainsi que leur spécialisation et les
contraintes de sélection associées à celles-ci.
Ce chapitre aborde aussi des problématiques spécifiques à cette généricité et les solutions qui y
répondent.

\Acref{ch:mp} détaille ensuite la métaprogrammation, notamment celle du C++ avec la notion de
template, les travaux effectués pour cette thèse reposant tous sur cette possibilité du langage C++.
En utilisant les notions de généricité du chapitre précédent, il présente l'implémentation de
différents algorithmes dont le déroulement s'effectue durant la compilation du programme.
Il progresse sur ce sujet jusqu'aux patrons d'expression, une technique en métaprogrammation
template permettant la représentation et l'utilisation, durant la compilation, de portions de code
source.

\Acref{ch:pfor} présente une bibliothèque active en C++ et utilisant la métaprogrammation template
pour la parallélisation automatique de boucles.
Cette proposition est expliquée en commençant par le détail des tests effectués par la bibliothèque
pour déterminer l'indépendance d'instructions et leur capacité à être exécutées en parallèle sans
créer de conflit d'accès aux données.
Ensuite, le chapitre traite de la détection des données nécessaires à l'application de ces tests,
qui repose sur des patrons d'expression, et qui permet d'acquérir une vision fine des instructions.
La génération du code éventuellement parallèle, incluant donc l'exécution des tests durant la
compilation, est subséquemment exposée.
Pour finir, l'efficacité de l'utilisation de cette bibliothèque est évaluée au moyen de mesures de
temps de compilation et d'exécution.
Cela est effectué pour différents cas et pour des codes utilisant la bibliothèque par rapport à des
codes équivalents ne l'utilisant pas.

Le \hyperref[ch:alsk]{cinquième et dernier chapitre} présente une seconde bibliothèque active,
utilisant également la métaprogrammation template du C++, cette fois-ci orientée vers la
parallélisation assistée au moyen de squelettes algorithmiques.
Ce chapitre introduit un problème de \gls{RO} et des métaheuristiques utilisées pour le résoudre.
Ces métaheuristiques sont ensuite utilisées pour illustrer les concepts généraux de squelettes
algorithmiques ainsi que ceux propres à notre proposition.
Le chapitre se poursuit avec l'étude de la répartition des tâches à exécuter en parallèle en
fonction du squelette algorithmique et de sa structure.
Le problème de la répétabilité des exécutions parallèles en tenant compte, notamment, de
l'utilisation de nombres pseudo-aléatoires est ensuite traité.
Après les premières sections qui présentent chacune un aspect de la conception des squelettes
algorithmiques en utilisant cette bibliothèque, ce chapitre montre comment ceux-ci peuvent être
utilisés en pratique, notamment par le biais d'une syntaxe alternative définissant un langage
embarqué au sein du C++.
Cette bibliothèque est testée pour résoudre des instances de \gls{TSP} et est comparée en temps
d'exécution avec des implémentations équivalentes ne l'utilisant pas.
%}}}