Soutenance mémoire
Thread noyau ou modèle d’implémentation un-à-un
Les threads noyaux sont implémentés dans le noyau du système d’exploitation. Ils sont donc gérés et supportés directement par le noyau. Du coup, le système d’exploitation connaît exactement les threads de l’application. Toutes les opérations de création, synchronisation, d’ordonnancement et de terminaison des threads noyaux passent par le système à travers un appel système au noyau. Les threads noyaux fonctionnent chacun dans le cadre de son propre espace mémoire. En sus de la table de threads, le noyau possède aussi une table de processus. Les threads noyaux sont ordonnancés par le noyau sur les processeurs. Pour les threads noyaux, le modèle correspondant est le modèle un-à-un.
Thread hybride ou modèle d’implémentation plusieurs-à-plusieurs
Il s’agit d’une combinaison des implémentations dans l’espace utilisateur et dans le noyau, le principe étant de concilier les avantages de ces deux implémentations. Les threads hybrides sont nés d’un multiplexage des threads utilisateurs sur un ou plusieurs threads noyaux. Le noyau du système d’exploitation ne connaît donc pas exactement les threads utilisateurs, mais les processus légers [38] propulseurs ou LWP (Light Weight Processus ). Autrement dit, les processus légers (LWP) sont gérés par le noyau et se chargent d’exécuter les threads utilisateurs.
L’implémentation des threads hybrides nécessite l’utilisation de deux ordonnanceurs. Le noyau ordonnance les threads noyaux et les processus légers (LWP) ordonnancent les threads utilisateurs. Les threads hybrides résultant du multiplexage de plusieurs threads utilisateurs sur un ou plusieurs threads noyaux, leurs modèles sont dits modèle plusieurs-à-plusieurs.
Limites des solutions existantes
Dans cette section, nous étudions les limites des compilateurs-paralléliseurs source-àsource Java tels que JAVAR, JOMP et CONCURRENCER.
JAVAR
JAVAR a été conçu depuis 1997 et depuis lors, il n’a pas eu d’évolution. A l’époque, le multithreading de Java n’était pas tellement évolué. Les mécanismes de synchronisation étaient rudimentaires. JAVAR est tellement limité que dés qu’une variable primitive déclarée à l’extérieur de la boucle et référencée à l’intérieur de la boucle est en mode d’accès autre qu’en lecture seule, la parallélisation est désactivée. Ce qui fait que JAVAR a une portée très limitée en ce qui concerne les applications à traiter :
• Les valeurs des variables qui sont déclarées en dehors de la boucle et qui sont invoquées à l’intérieur de la boucle doivent rester inaltérées durant toute l’exécution de la boucle.
Ce qui signifie que seules les variables primitives en mode lecture seule sont acceptées.
Autrement, la parallélisation est désactivée ;
• JAVAR n’est pas conçu pour paralléliser les applications s’exécutant en phases (par étapes et où les threads exécutent une barrière de synchronisation explicite) ;
• JAVAR utilise la synchronisation Fork/Join basique, et il y a autant de synchronisations que de régions parallèles implicites. Mais créer et détruire un thread est une opération très coûteuse. Par exemple, une application avec dix régions parallèles implicites requiert que dix opérations de création et de destruction de threads soient effectuées ;
• JAVAR n’exploite pas le parallélisme d’un programme lorsque celui-ci présente des sections indépendantes potentiellement parallélisables.
Lorsque JAVAR traite les applications basées sur la stratégie diviser-pour-régner, la seule méthode pour y parvenir est la méthode dite méthode naïve. Cette stratégie consiste à créer autant de threads que de tâches alors que le coût de création et de destruction des threads est une opération prohibitive.
Java CONCURRENCER
L’exploitation et l’utilisation de CONCURRENCER imposent l’utilisation de l’IDE Eclipse.
Ensuite, lors des transformations des inten AtomicInteger , les autres variables primitives ne sont pas prises en compte. La transformation d’un programme récursif en programme parallèle dispose d’un seul paramètre de performance qui est le Thresholdet qui est parfois difficile à utiliser dans certaines circonstances.
Conclusion
L’étude de l’état de l’art a révélé que beaucoup d’efforts on été consentis pour l’élaboration des techniques de parallélisme. Tous ces outils et compilateurs concourent tous à rendre non seulement la programmation parallèle moins propice aux erreurs, facile à utiliser, mais aussi à générer des programmes parallèles performants. Les objectifs étant les mêmes, les méthodes diffèrent d’un compilateur à un autre ou plutôt les implémentations diffèrent. Fondamentalement, en utilisant ces outils, il est possible de paralléliser des boucles d’itérations (JOMP, JAVAR), des méthodes récursives (JAVAR, Java CONCURRENCER). Toutefois, ces outils présentent chacun des limites. Ces limites nous servent de points de référence pour aborder le chapitre suivant. Ce chapitre discutera des solutions que nous avons proposées pour adresser certaines problématiques posées.
Combinaison des accès aux variables
Notre approche consiste à identifier les variables primitives invoquées à l’intérieur de la boucle à paralléliser et à déterminer les accès à ces variables. Elle consiste aussi à combiner, pour chaque variable, les opérations d’accès à l’intérieur de la boucle à paralléliser. La table suivante décrit les combinaisons possibles des opérations d’accès aux variables primitives. Lorsque la variable est accédée, nous attribuons la valeur 1 à l’accès correspondant et au cas contraire nous attribuons la valeur 0.
Elaboration des règles de transformation avec analyse de dépendance
Dans cette section, nous proposons d’élaborer des règles de transformation qui tiennent compte de l’analyse de dépendances du programme en entrée. Il s’agit d’analyser le programme en entrée, puis de procéder à son découpage suivant certains critères, ensuite de définir les conditions à respecter et enfin d’établir les règles de transformation.
Etapes avant transformation
Analyse du programme en entrée : la première étape de la conception est d’analyser le programme en entrée. Elle consiste à :
• Identifier les variables primitives invoquées à l’intérieur de la boucle ;
• Déterminer les accès des variables ;
• Analyser les dépendances des variables et des instructions.
Découpage du programme : la seconde étape consiste au découpage du programme. Les programmes découpés (slice programs ) sont un ensemble E de sous-programmes Eioù:
• Les instructions dans Ei sont directement dépendantes ou ont une dépendance transitive ;
• Tous les Eisont indépendants entre eux ;
• Dans chaque Ei, la cohérence séquentielle est respectée.
Conditions de transformation
Nous imposons comme conditions préalables aux transformations que les contraintes pour garantir la cohérence séquentielle du programme soient respectées. Donc, la transformation trouve un équilibre entre l’optimisation du code et la cohérence séquentielle. Pour des raisons d’optimisation, nos règles de transformation :
• Evitent la synchronisation redondante (ex. quand une méthode synchronisée est appelée par une autre méthode synchronisée sur le même objet) ;
• Evitent d’utiliser le même verrou pour deux Eiindépendants ;
• Réalisent un minimum de synchronisation dans le contexte de variable de réduction.
• Réalisent une privatisation de la variable sous certaines conditions ;
• Mettent en œuvre des verrous différents pour des Eidifférents ;
Dans le souci de respecter la cohérence séquentielle, nos règles de transformation :
• Evitent d’utiliser la variable dite atomicpour réaliser l’exclusion mutuelle sous certaine condition. Ce qui signifie qu’il faut éviter de remplacer la variable par une variable atomic si Eicontient plus d’une instruction parce que dans cette situation, remplacer la variable par une variable atomicne garantit pas la cohérence séquentielle ;
• Evitent d’utiliser la variable volatile pour réaliser l’exclusion mutuelle sous certaines conditions. Ce qui signifie qu’il faut éviter d’utiliser volatile si Ei contient plus d’une instruction parce que dans ce cas la variable volatile ne garantit pas la cohérence séquentielle ;
• Si Eicontient plus d’une instruction, l’exclusion mutuelle est requise.
Règles de transformation
Considérons (V,Sk,T,A,Ei,AA)tel que Vest une variable dont le type est Tà Skqui est la k ième instruction de Eiqui est un bloc d’instructions dépendantes. Nous proposons de tracer Vdans Sk et Ei dans l’optique de déterminer AA qui correspond à tous les accès de V en combinant différents Aqui sont les accès des variables. Pour la combinaison des accès A, voir la Table 5.5. Soit Nle nombre d’instructions de Ei. Nous proposons l’algorithme suivant comme algorithme principal pour déterminer nos règles de transformation.
Travaux similaires
La plupart des outils et compilateurs conçus pour la parallélisation automatique s’appuient sur l’analyse de programme statique [37]. Cependant, ces outils et compilateurs atteignent très rapidement leurs limites en termes de performances et de scalabilité.
Dans [49], le prototype proposé analyse les dépendances dynamiques du programme séquentiel Java en exécution, puis recommande à l’utilisateur les régions qui possèdent le plus de potentiel pour la parallélisation. Autrement dit, il mesure le potentiel de parallélisme d’une application.
L’approche consiste à :
• tracer les dépendances dynamiques : durant l’exécution du programme Java, à chaque instruction, tous les accès en mode écriture et en mode lecture sont tracés. De là, sont définies les relations de dépendance ;
• détecter le parallélisme : il s’agit de la construction d’un graphe pour identifier le chemin d’exécution séquentiel le plus critique et faire ressortir les différents chemins d’exécution parallèles ;
• suggérer les régions potentiellement candidates à la parallélisation.
Taskfinder [100] est un outil similaire à celui de [49] et agit sur les programmes écrits en langage C. Bridges et al. [123] mettent en œuvre la parallélisation automatique en la technique de pipelining. Avec cette technique, ils parviennent à identifier les régions favorables à la parallélisation avec traçage des dépendances des accès en mémoire. Cependant, cette technique repose sur les fonctionnalités du matériel.
Tous ces outils cités précédemment effectuent l’analyse de dépendance au niveau code intermédiaire (bytecode ou instruction machine). Or, maintenir le programme à ce niveau de code reste une tâche très pénible. Dans notre contribution, l’analyse de dépendance s’effectue au niveau code source. Ce qui offre une compréhension plus facile pour le débogage et la maintenance du code. Seulement, le champ d’application est réduit à la gestion des variables primitives. Du coup, nous gagnerons à élargir le champ en gérant les variables de référence.
Bilan
Notre première solution proposée a porté sur la gestion automatique des variables primitives référencées à l’intérieur du corps de la boucle à paralléliser. Notre approche a consisté à :
• traquer les variables primitives concernées ;
• pour chaque variable, collecter les différents accès (lecture, écriture, lecture/écriture) ;
• établir une table de combinaisons de tous les accès possibles.
Nous avons aussi posé deux cas de figure. Dans le premier cas de figure, nous avons fait fi de l’analyse de dépendance. Alors, il s’ensuit :
• Chaque entrée de la table débouche sur une règle de transformation que nous avons établie;
• Au total, quatre règles de transformations ont été établies;
• Pour chaque variable, nous lui appliquons la règle correspondante.
Dans le deuxième cas de figure, nous prenons en compte l’analyse de dépendance de données.
Alors, il s’ensuit :
• Une analyse des dépendances des variables et des instructions ;
• Le regroupement des instructions dépendantes par groupe ;
• Il en résulte n groupes (d’instructions) indépendants ;
• chaque entrée de la table des combinaisons débouche sur une règle de transformation que nous avons établie ;
• Au total, quatre règles de transformations ont été établies ;
• Pour chaque groupe d’instructions, nous lui appliquons la règle qui convient.
La section suivante introduit notre deuxième solution.
Conception du compilateur hybride : Combinaison des directives de JOMP et des annotations de JAVAR
Les compilateur-paralléliseurs source-à-source JAVAR [16] [17] et JOMP [24] [25] présentent à la fois des avantages et des limites. Toutefois, nous nous focalisons sur les limites de ces deux compilateurs. JOMP présente quelques limites non encore surmontées :
• il n’est pas indiqué pour paralléliser les méthodes récursives;
• il n’a pas de directives pour gérer explicitement les exceptions;
• il ne possède pas de directives pour exploiter les opérations atomiques;
• il ne possède pas de directives pour les opérations de type flush et atomic.
Les limites de JAVAR sont :
• Les valeurs des variables qui sont déclarées en dehors de la boucle et qui sont invoquées à l’intérieur de la boucle doivent rester inaltérées durant toute l’exécution de la boucle.
Ce qui signifie que seules les variables primitives en mode lecture seule sont acceptées.
Autrement, la parallélisation est désactivée ;
• Il n’est pas conçu pour paralléliser les applications s’exécutant en phases (par étapes et où les threads exécutent une barrière de synchronisation explicite);
• Il utilise la synchronisation Fork/Join basique, et il y a autant de synchronisations que de régions parallèles implicites. Mais, créer et détruire un thread est une opération très coûteuse. Par exemple, une application avec dix régions parallèles implicites requiert que dix opérations de création et de destruction de threads soient effectuées ;
• Il n’exploite pas le parallélisme d’un programme lorsque celui-ci présente des sections indépendantes potentiellement parallélisables.
Pour à la fois cumuler les avantages de ces deux compilateurs et surmonter certaines de leurs limites, nous proposons une solution qui consiste à combiner les annotations de JAVAR aux directives de JOMP. Le compilateur résultant est dit compilateur hybride.
Exemples d’utilisation des directives de FJComp
Les exemples suivants illustrent l’utilisation de la directive et des clauses du compilateur paralléliseur FJComp. Le programme Fibonacci permet de calculer le nième terme d’une série tandis que le programme Quicksort permet de trier un tableau d’entiers. Alors, ces deux programmes diffèrent de par leurs données à subdiviser. Fibonacci agit sur une valeur scalaire, alors que Quicksort agit sur un tableau.
|
Table des matières
CHAPITRE 1. INTRODUCTION
1.1 CONTRIBUTIONS
1.2 ORGANISATION DU DOCUMENT
CHAPITRE 2. CONTEXTE, PROBLEMATIQUES ET OBJECTIFS
2.1 CONTEXTE
2.2 PROBLEMATIQUE
2.2.1 Le thème
2.2.2 Problèmes
2.2.3 Question de recherche
2.2.4 Solutions proposées
2.2.5 Méthode
2.2.6 Bilan
2.3 OBJECTIFS
2.4 RESULTATS ATTENDUS
2.5 BILAN
CHAPITRE 3. INTRODUCTION AU MULTITHREADING, AU PARALLELISME ET PRESENTATION DE L’ARCHITECTURE C.M.P
3.1 IMPLEMENTATIONS ET MODELES DES THREADS
3.1.1 Thread utilisateur ou modèle d’implémentation plusieurs-à-un
3.1.2 Thread noyau ou modèle d’implémentation un-à-un
3.1.3 Thread hybride ou modèle d’implémentation plusieurs-à-plusieurs
3.1.4 Bilan
3.2 PRESENTATION DES MODELES DE THREADS
3.3 LES THREADS JAVA
3.4 SYNCHRONISATION DES THREADS JAVA
3.4.1 Le moniteur de Java
3.4.2 Le mot clé synchronized de Java
3.4.3 La classe java.util.concurrent.CyclicBarrier de Java
3.4.4 Les classes du package java.util.concurrent.atomic de Java
3.4.5 Le mot clé volatile de Java
3.4.6 Remarques importantes sur la synchronisation des threads en Java
3.5 LE PARALLELISME DES APPLICATIONS
3.5.1 Les paradigmes du parallélisme
3.5.2 Les facteurs de performance du parallélisme
3.5.3 Les mesures de performance d’un programme parallèle
3.5.4 Les algorithmes de répartition d’itérations
3.5.5 Les variables dans le parallélisme de boucle
3.5.6 Bilan
3.6 PRESENTATION DE L’ARCHITECTURE DES PROCESSEURS MULTI-CŒURS
3.6.1 Multithreading Simultané (S.M.T)
3.7 BILAN
CHAPITRE 4. ETUDE DES COMPILATEURS-PARALLELISEURS EN JAVA
4.1 INTRODUCTION
4.2 REVUE DU PARALLELISME SMPET CMPEN JAVA
4.3 JAVA RESTRUCTURING COMPILER OU JAVAR
4.3.1 Annotations de JAVAR
4.3.1.1 Parallélisme de boucle
4.3.1.2 Parallélisme de méthode
4.3.1.3 Exemples
4.3.2 Compilation avec JAVAR
4.4 JOMP
4.4.1 Concepts généraux
4.4.2 Principes de fonctionnement
4.4.3 Construction de la région parallèle
4.4.4 Partage de travail (work-sharing) et parallélisme de boucle
4.4.5 Synchronisation
4.4.6 Exemples d’utilisation des directives de JOMP
4.4.7 Compilation avec JOMP
4.5 FRAMEWORK FORK/JOIN
4.5.1 La stratégie dite vol-de-travail (work-stealing)
4.6 JAVA CONCURRENCER
4.7 LA PROGRAMMATION PARALLELE “A LA MAIN”:CAS DE QUICKSORT
4.8 LIMITES DES SOLUTIONS EXISTANTES
4.8.1 JAVAR
4.8.2 JOMP
4.8.3 Java CONCURRENCER
4.9 CONCLUSION
CHAPITRE 5. CONCEPTION DES COMPILATEURS-PARALLELISEURS
5.1 INTRODUCTION
5.2 NOTATIONS FORMELLES DE JAVACC
5.2.1 Production BNF
5.2.2 Production d’expression régulière
5.3 GESTION AUTOMATIQUE DES VARIABLES PRIMITIVES
5.3.1 Le modèle de mémoire de Java
5.3.2 Analyse de dépendance
5.3.2.1 Les dépendances de contrôle
5.3.2.2 Les dépendances de données
5.3.2.3 Les dépendances de paramètres et d’appel
5.3.2.4 Découpage de programme ou program slicing
5.3.3 Les outils de dépendance de programme de Java
5.3.4 Notation formelle des accès aux variables en Java
5.3.4.1 Accès en lecture
5.3.4.2 Accès en écriture
5.3.4.3 Accès en lecture/écriture
5.3.4.4 Variable de réduction
5.3.5 Combinaison des accès aux variables
5.3.6 Elaboration des règles de transformation sans analyse de dépendance
5.3.7 Elaboration des règles de transformation avec analyse de dépendance
5.3.7.1 Etapes avant transformation
5.3.7.2 Conditions de transformation
5.3.7.3 Règles de transformation
5.3.8 Travaux similaires
5.3.9 Bilan
5.4 CONCEPTION DU COMPILATEUR HYBRIDE: COMBINAISON DES DIRECTIVES DE JOMPET DES ANNOTATIONS DE JAVAR
5.4.1 Analyse comparative de JOMP et de JAVAR
5.4.2 Conception du compilateur hybride
5.4.3 Bilan
5.5 CONCEPTION DU COMPILATEUR-PARALLELISEUR FJCOMP
5.5.1 Le framework Fork/Join de Java
5.5.2 Elaboration des directives de compilation de FJComp
5.5.3 Exemples d’utilisation des directives de FJComp
5.5.4 Travaux similaires
5.5.5 Bilan
5.6 CONCLUSION
CHAPITRE 6. IMPLEMENTATION DES COMPILATEURS PARALLELISEURS
6.1 GENERATEUR DE COMPILATEUR JAVACC
6.2 IMPLEMENTATION DE PJAVAR
6.2.1 Elaboration du Champ lexical de PJAVAR
6.2.2 Elaboration des expressions syntaxiques de PJAVAR
6.2.3 Construction de l’arbre syntaxique abstrait
6.2.4 Génération du code
6.2.5 Empaquetage du compilateur PJAVAR
6.3 IMPLEMENTATION DU COMPILATEUR HYBRIDE
6.3.1 Empaquetage du compilateur hybride
6.4 IMPLEMENTATION DE FJCOMP
6.4.1 Elaboration du champ lexical de FJComp
6.4.2 Elaboration des expressions syntaxiques de FJComp
6.4.3 Construction de l’arbre syntaxique abstrait
6.4.4 Génération du code
6.4.5 Empaquetage du compilateur FJComp
6.5 BILAN
CHAPITRE 7. APPLICATIONS DES COMPILATEURS-PARALLELISEURS
7.1 APPLICATION DE PJAVARAU PROGRAMME DE CALCUL DE PI
7.1.1 Insertion des annotations de PJAVAR
7.1.2 Compilation avec PJAVAR
7.1.3 Programme parallèle généré par PJAVAR
7.1.4 Exécution du programme parallèle généré par PJAVAR
7.2 APPLICATION DES REGLES DE TRANSFORMATION AVEC ANALYSE DE DEPENDANCE
7.2.1 Programme incorrectement synchronisé généré par JOMP
7.2.2 Transformation du programme parallèle de ArrayOperation incorrectement
synchronisé en un programme parallèle correctement synchronisé
7.2.3 Exécution du programme parallèle de ArrayOperation correctement synchronisé
7.3 APPLICATION DE NOTRE COMPILATEUR HYBRIDE A L’ALGORITHME DE TRI DE MATRICE
7.3.1 Algorithme du Tri de Matrice
7.3.2 Compilation de MatrixMergesort.javar avec le compilateur hybride
7.3.3 Exécution du programme parallèle MatrixMergesort.java généré par PJAVAR
7.4 APPLICATION DE FJCOMP AU PROGRAMME DE FIBONACCI
7.4.1 Programme séquentiel de Fibonacci avec insertion des directives de FJComp
7.4.2 Compilation de Fibonacci.fj avec FJComp
7.4.3 Programme parallèle de Fibonacci généré par FJComp
7.4.4 Exécution du programme parallèle Fibonacci.java généré par FJCOMP
7.5 BILAN
CHAPITRE 8. EXPERIMENTATIONS, DISCUSSIONS ET VALIDATION
8.1 PRESENTATION DE NOS ENVIRONNEMENTS DE TEST
8.2 EXPERIMENTATIONS DE PJAVAR
8.2.1 Présentation et Discussion des résultats expérimentaux
8.3 EXPERIMENTATIONS DES PROGRAMMES PARALLELES JOMPTRANSFORMES “MANUELLEMENT”SUIVANT LES REGLES DE TRANSFORMATION
8.3.1 Présentation des résultats expérimentaux
8.3.2 Discussions des résultats expérimentaux
8.4 PERFORMANCES DU COMPILATEUR HYBRIDE
8.4.1 Présentation des résultats expérimentaux
8.4.2 Discussion des résultats expérimentaux
8.5 EXPERIMENTATIONS DE FJCOMP
8.5.1 Résultats expérimentaux
8.5.2 Discussions des résultats expérimentaux
8.6 VALIDATION
CHAPITRE 9. CONCLUSION
9.1 EVALUATION
9.2 PERSPECTIVES
BIBLIOGRAPHIE
WEBOGRAPHIE
LISTE DE NOS PUBLICATIONS
RESUME
ABSTRACT
ANNEXES
