Béatrice MARKHOFF 

"Contribution à la définition d'un modèle de calcul fonctionnel parallèle"

Mots clés :

programmation fonctionnelle parallèle, flots de données, analyse de caractère strict, G-machine, réduction de graphes distribuée, réseau de processus communicants, protocoles distribués.

Résumé en 6 pages

Introduction

Programmation parallèle en KAP2L

Principes de la compilation vers un réseau de G-machines : NG-machine pour Network G-machine)

Fonctionnement parallèle et distribué de la NG-machine

Conclusion

Références

1. Introduction

Pour programmer plus aisément les machines parallèles il faut disposer d’un modèle de calcul parallèle performant dans ses deux composants, le modèle de programmation et le modèle d’exécution [BOU 93]. Le premier, représenté par le langage de programmation, offre une vue macroscopique du calcul : il doit être informatif, dans le sens où la correction des programmes doit être aisément vérifiable. Le deuxième, incarné par le langage intermédiaire cible du compilateur, utilise les paramètres physiques de la machine pour obtenir une exécution efficace, dans le sens où le temps et l’utilisation des ressources sont optimisés. La qualité d'un modèle de calcul s'accroît avec celle du compromis qu'il réalise entre informativité et efficacité.

L'amélioration de ce compromis est particulièrement complexe dans le monde parallèle, du fait de la diversité des modèles et des architectures.

Du point de vue programmation, on distingue deux classes de parallélisme : d’une part le parallélisme de contrôle, où les flots de contrôle à exécuter en parallèle doivent être spécifiés ainsi que leurs interactions (communications / synchronisations), et d’autre part le parallélisme de données, où un programme est une combinaison séquentielle d’opérations appliquées en parallèle sur des structures de données distribuées. Par ailleurs, les deux modèles de programmation classiques, impératif et applicatif, se retrouvent dans les langages parallèles. Parmi les seconds, plus informatifs grâce au principe de substitution, les langages fonctionnels offrent des exécutions relativement plus efficaces que les langages logiques, mais en général moins efficaces que les langages impératifs [GEL 96].

Concernant les architectures, outre les quantités de flots de contrôle et de flots de données traités par le calculateur (classification de Flynn [FLY 66] : SISD, MISD, SIMD et MIMD), divers critères les distinguent : la configuration de la mémoire, qui peut être partagée ou distribuée, les caractéristiques du réseau de communication (bus, commutateur, grille, arbre…), et celles des processeurs (du processeur très élémentaire d'une "Connection Machine" au processeur de type station de travail) [COS 94]. Les architectures MIMD s'imposent pour des raisons économiques : étant construites à partir de composants standards (processeurs, mémoires, cartes d'entrée/sortie…) elles sont moins chères, et plus aptes à bénéficier des évolutions des ces composants.

• Nous avons choisi comme modèle d’exécution le MIMD à mémoire distribuée : il correspond au modèle théorique des réseaux de processus communicant par échange de messages.
• Nous avons choisi le modèle de programmation fonctionnel pour son informativité. L’exécution de programmes fonctionnels à base de flots se modélise par les réseaux de Kahn [KAH 74, BOU 92].

Nos propositions sont les suivantes :

• Pour l’informativité, nous définissons un noyau de langage fonctionnel à base de flots.
• Nous y introduisons un parallélisme de contrôle par le biais d’une annotation parallèle ("||") placée sur une application. Cela établit un pipeline entre le calcul des flots arguments et celui de l'application. Par ailleurs, deux arguments indépendants sont calculés simultanément.
• Pour l’efficacité, chaque processus du réseau s'implante comme une G-machine [AUG 89b] [PEY 87], formant la NG-machine (Network of G-machines), qui est un réseau de G-machines.

Dans cette synthèse, je présente en section 2 le style de programmation parallèle permise par le noyau de langage Kap²l. Je décris en section 3 les principes de la compilation, et en section 4, son résultat : une NG-machine.

Retour au sommaire

2. Programmation parallèle en Kap²l

Le noyau de langage Kap²l est fonctionnel "orienté flots", un flot étant une structure ordonnée d'éléments de même type, à accès séquentiel ([SKE 91], [CAS 96]). Le programmeur définit des réseaux de processus, suivant le modèle des réseaux de processus séquentiels de Kahn [BOU 92].

2.1 Processus et réseau de processus

Une fonction représente un processus à part dès lors qu’elle a au moins un argument de type flot et que son application est annotée du symbole parallèle "||". Le calcul de l’argument est pris en charge par un processus distinct, et une communication de producteur à consommateur s’établit entre les deux processus, pour que les valeurs successives de l’argument parviennent à la fonction.

Dans l'exemple Figure 1, la fonction P qui multiplie par 2 son argument est réduite par un processus indépendant, tandis qu'un autre processus est chargé du calcul du flot Nat des entiers naturels : celui-ci commence par le premier élément du flot constante 0, et l'élément suivant est le résultat de la somme des deux flots Nat et 1. Les opérations arithmétiques ou logiques telles que la somme s’effectuent terme à terme.

Le mot clef "rec" indique une définition par récurrence des éléments du flot résultat : une variable telle que Nat dénote une boucle dans le réseau, étant donné que ses premiers éléments servent au calcul des suivants. Le réseau décrit par ce programme est à droite en figure 1 : il produit en résultat d'abord 0, puis 2, etc., soit la suite croissante des nombres pairs.

Let rec Nat = 0 : (Nat + 1) in Let P(x) = 2 * x in P||(Nat)

Figure 1. Un programme KAP²L et le réseau correspondant

2.2 Parallélisme

Le parallélisme pipeline est évident dans l’algorithme (classique) du crible d’Eratosthène ; le programme en figure 2 implante cet algorithme en définissant le flot des nombres premiers, Primes, à partir de :

• Onat le flot des entiers naturels impairs à partir de 3,
• Filter la fonction qui supprime du flot s les éléments multiples de n,
• Sieve la fonction qui construit le crible, en créant les filtres successifs.

Let rec Onat = 3 : (Onat + 2) in

Let Filter(s, n) = if (s mod n) <> 0 then s fi in

Let Sieve(x) = x : (Sieve||(Filter(Tl(x), Hd(x)))) in

Let Primes = 2 : (Sieve||(Onat)) in Primes

Figure 2. Programme du crible d'Eratosthène

Le flot Primes des nombres premiers commence par 2, et son reste est le résultat de l’application de Sieve au flot Onat ; l’annotation "||" dans la définition de Primes a pour effet de faire calculer Onat séparément. Celle qui apparaît dans le corps de Sieve crée dynamiquement les filtres, en les organisant en pipeline, voir figure 3.

Figure 3. réseaux du crible d’Eratosthène

Lorsque les calculs de deux arguments sont indépendants, ils peuvent être pris en charge par des processus distincts. C’est alors un parallélisme collatéral.

2.3 Syntaxe de Kap²l

<Kexpr>::= Constant (flots constants d’entiers ou de booléens)

| Ident (variables)

| Ident [||] (<Kexpr>+) (applications annotées ou non)

| Let <Def> in <Kexpr> (blocs)

| <Kexpr>: (<Kexpr>) | Hd(<Kexpr>) | Tl(<Kexpr>) (constructeurs)

| If <Kexpr> Then <Kexpr> [Else <Kexpr>] fi (conditionnelles)

| [<Kexpr>] op <Kexpr> (opérations arithmétiques et logiques)

<Def>::= Ident (Ident+) = <Kexpr> | [rec] Ident = <Kexpr> (définitions)

Figure 4. syntaxe de Kap²l

Kap²l est limité aux fonctions du premier ordre, et la seule structure de données manipulée est le flot infini.

Comme le montrent les exemples précédents, tous les opérateurs, y compris les conditionnelles, s'appliquent sur des flots et retournent un flot. L'opérateur Followed-by (":") s'applique sur deux flots et retourne le flot composé du premier élément du premier argument, suivi du deuxième argument complet. L'opérateur Hd retourne le flot constant formé de la valeur du premier élément de son argument. L'opérateur Tl retourne son argument sans son premier élément.

2.4 Sémantique du calcul parallèle basé sur les flots

Du point de vue dénotationnel, ce calcul parallèle correspond à la sémantique proposée par Gilles Kahn [KAH 74]. Nous avons par ailleurs développé et implanté sous Centaur [CEN 92] une sémantique parallèle opérationnelle asynchrone, dite "à petit pas", pour tester nos programmes. En l'absence d'annotation, la réduction se déroule selon l'ordre normal, et en cas d'annotation, un ordre concurrent est défini entre les processus de réduction parallèle.

Avec l'ordre normal, seuls les éléments de l'argument utiles à l'application sont effectivement calculés, mais avec l'évaluation parallèle, lorsqu'on confie le calcul de l'argument à un processus indépendant, une non-terminaison peut résulter du calcul d'éléments non évalués par l'ordre normal. On donne en figure 5 un exemple de programme défini sans annotation parallèle —le résultat est la suite croissante des entiers naturels— mais indéfini en cas d'application parallèle —car le calcul de x ne peut aboutir—. L'analyse statique développée pour détecter automatiquement ces cas de figure est une analyse de caractère strict [PEY 87] adaptée au contexte des flots infinis.

Let rec x=x:(0:(Tl(x)+1)) in

Let f(y)=Tl(y) in F||(x)

Figure 5. Impact du parallélisme sur le résultat

Retour au sommaire

3. Principes de la compilation

La compilation reprend les principes utilisés pour la G-Machine, machine abstraite de réduction paresseuse de graphes de super-combinateurs [AUG 89b] [PEY 87] (décrite au paragraphe 4 de cette synthèse).

Nous avons adapté la démarche aux flots infinis, en introduisant en particulier des calculs statiques dont le résultat influence le comportement distribué du réseau de machines de réduction. Les étapes de la compilation sont les suivantes :

• traduction de KAP2L vers le lambda-calcul enrichi,
  Les fonctions sont curryfiées, l'annotation parallèle sur une application (f||(x1, …, xn)) est distribuée sur les arguments : f ||x1 … ||xn. Les définitions sont traduites en "letrec"…
• extraction des lambdas, ce qui produit les super-combinateurs,
• analyse de caractère strict, qui ajoute des annotations sur les paramètres formels stricts et les paramètres effectifs non-stricts
• comptage des "consommateurs" des expressions parallèles,
  Ce comptage permet de déterminer le nombre de consommations de chaque valeur produite par tout processus du réseau. Ce nombre sert dans le protocole de communication (cf. § 4.3).
• génération de code, qui consiste en un ensemble de séquences de G-code, rassemblées dans le graphe initial de la machine distribuée.

Retour au sommaire

4. Machine de réduction de graphes parallèle et distribuée

La NG-machine est un réseau de processus séquentiels communicants. Chaque processus évalue une partie du graphe du programme qu’il détient en propre, à l'instar d'une G-machine.

Une G-Machine se définit en termes de transitions entre états. L’état est formé de quatre composants :

• S la pile d’évaluation courante,
• G le graphe en cours de réduction,
• D la pile de sauvegarde des contextes et
• C la séquence d’instructions de G-code à exécuter.

Une transition correspond à l’exécution d’une instruction de G-code. Les instructions de calcul font évoluer la séquence de code, la pile et le graphe. Les instructions de contrôle gèrent en plus les contextes. Par exemple une instruction EVAL sur un nœud d’application @ e1 e2 initie une évaluation dans un nouveau contexte, en ayant sauvegardé le contexte courant dans la pile de sauvegarde D [AUG 89b].

Pour ce qui est de la NG-machine, chaque processus réduit son graphe local en utilisant des flots de valeurs calculées par d’autres, et en mettant son flot de résultats à la disposition de ses consommateurs. L'état de chaque composant comprend l'état d'une G-machine, avec en plus quatre éléments destinés au calcul distribué :

• M l'identificateur du processus,
• F la liste des processus qu'il a créés (ses " fils "),
• O sa sortie,
• et R la liste des requêtes émises par les processus consommateurs de son flot de résultats.

Il existe dans le graphe un nouveau type de nœud appelé INPUT, qui représente un flot de valeurs calculées par un autre processus.

La NG-machine évolue de deux manières :

• soit par exécution parallèle des transitions locales à chaque processus,
• soit par exécution synchrone de  plusieurs transitions mettant en jeu plusieurs processus : créations, communications, ou terminaisons.

De nouvelles instructions de G-code implantent les interactions entre processus :

• instruction CREATE pour la création d'un nouveau processus de réduction,
• instruction END pour la fin d’un calcul,
• instruction EVAL sur un nœud INPUT, pour une demande de valeurs à un processus,
• instruction WAIT pour la suspension du calcul local,
• instruction SEND pour l’envoi de valeurs.

Dans la suite, nous présentons trois points essentiels dans le fonctionnement de la NG-machine: les calculs locaux, la création de processus (engendrée par l'évaluation d'une application parallèle) et la gestion des communications.

4.1. Calculs locaux

Chaque processus évalue l'expression pointée par le sommet de pile jusqu'à une constante de tête (instruction EVAL), puis il alimente son flot de sortie avec cette constante (instruction SEND) et reprend ce cycle d'évaluation sur le reste de l'expression. Par rapport au fonctionnement de la G-machine, il y a deux changements importants :

• l'introduction de nouvelles transitions pour les nœuds de communication INPUT,
• l'implantation dans le G-code des opérateurs sur flots propres à Kap²l.

4.2. Création de processus

La compilation d'une application parallèle engendre les actions suivantes en G-code :

• construction du graphe de l'argument, et dépôt d’un pointeur vers sa racine en sommet de pile,
• création d'un nouveau processus pour évaluer ce sous-graphe (instruction CREATE),
• construction du graphe de la fonction,
• création du nœud d'application de la fonction sur le résultat de la création du processus (un nœud INPUT).

Ainsi, l'exécution de l'instruction CREATE conduit à remplacer dans le graphe local la racine du sous-graphe par un nœud INPUT référençant le nouveau processus. C'est à travers ce nœud INPUT que le processus courant obtiendra les valeurs produites par le processus créé.

4.3. Communications

Les communications ont pour but la transmission des valeurs calculées par un processus vers les processus qui les utilisent. Cette transmission se fait à la demande : l'évaluation d'un nœud INPUT induit une requête, et chaque processus gère un service des requêtes. Le service des requêtes est prioritaire sur la réduction locale. Cela se traduit dans le système de transitions par le fait que les règles de transition du calcul local ne s'appliquent que lorsque la liste des requêtes R de l'état local est vide.

Le service des requêtes est la partie la plus importante du protocole de communication. Il s’appuie sur la structure de données o de l'état local d'un processus. Les valeurs produites y sont stockées. Les requêtes émises par des consommateurs de ces valeurs sont traitées de la manière suivante :

• Dès qu’il y a une requête, le processus ne peut plus appliquer de transition locale.
• Si une requête arrive alors que le processus sert un consommateur, elle est stockée : les requêtes sont traitées dans l’ordre de leur arrivée.
• Lors d'une requête, toutes les valeurs disponibles sont envoyées au consommateur.
• S'il n'y a pas de valeur disponible, le service ne peut être effectué et la requête est mise en attente de façon à permettre le calcul local. Elle sera servie dès qu'une valeur sera produite.
• S'il y a des valeurs disponibles, le traitement consiste à :
  • déterminer les valeurs à envoyer,
  • comptabiliser les nouvelles consommations de ces valeurs,
  • transmettre les valeurs.

Ce protocole de communication est bâti sur le modèle classique "producteur-consommateur", sachant qu'ici le producteur connaît le nombre de consommateurs, ce qui permet d'utiliser un tampon de taille bornée pour le stockage des valeurs produites.

Retour au sommaire

5. Conclusion

La NG-machine a été testée selon deux directions :

• avec CENTAUR (outil de prototypage basé sur la logique naturelle) [CEN 92], pour expérimenter sur des exemples et valider les règles.
  Pour ce faire, l'état de la NG-machine et ses transitions ont été modélisés, et une simulation d’exécution parallèle a été mise au point [BAR 95].
• avec SPIN (outil de simulation de protocoles distribués) [HOL 93], pour valider le protocole de communication. Le système distribué que constitue la NG-machine a été isolé du système de transitions complet, et ses propriétés de vivacité (pas d'interblocage) et de sûreté des communications (pas de perte, conservation de l'ordre des données) ont été vérifiées sur un échantillon d’exemples [CAN 96].

Il est clair que la part de calcul consacrée à la gestion du parallélisme est faible, puisque les processus sont indépendants et communiquent par transmission de messages. Chacun dispose de son ramasse-miettes local, on évite donc l'inconvénient d'un système global qui bloque tous les processus. La configuration du réseau est dynamique, puisqu'il y a création de processus au cours du calcul. En revanche, puisqu'ils calculent des flots de valeurs, les processus créés participent au calcul jusqu'à sa fin globale ("durée de vie" importante).

Cette machine abstraite parallèle et distribuée est bâtie selon un principe différent des parallélisations de la G-machine (<n,G>-machine [AUG 89a], Gaml [MAR 91], HDG-machine [KIN 91]…) : ces approches introduisent dans la réduction paresseuse de graphes de super-combinateurs un modèle d’exécution parallèle du type "ferme de processus", lesquels exécutent des tâches mises en attente dans une structure partagée. Il y a donc nécessité de mémoire partagée, physique ou virtuelle. Par ailleurs, ces tâches consistent en la réduction ponctuelle d’expressions, ce qui se révèle souvent trop simple par rapport au coût du parallélisme. Dans la conclusion de [PEY 91], trois arguments principaux sont avancés en faveur du parallélisme fonctionnel qui consiste à "adapter" la G-machine à une cible parallèle :

• la réduction de graphe est une activité décentralisée, le graphe étant une structure de donnée distribuée,
• des réductions simultanées peuvent avoir lieu au sein du graphe sans influence sur le résultat,
• toutes les communications et synchronisations peuvent s’effectuer via le graphe.

Le deuxième argument correspond au constat fondamental en programmation fonctionnelle parallèle : il n’y a pas d’ordre total (séquentiel) imposé dans le l-calcul. Le premier argument est également important, et pourtant mal exploité par les machines citées, dans la mesure où le troisième argument est mis en œuvre par mémoire partagée. Dans la NG-machine, le graphe et ses transformations servent effectivement de cadre aux synchronisations et communications, mais selon un modèle distribué de processus communicants.

Le modèle de programmation supporté par KAP²L préserve l'informativité de la programmation fonctionnelle grâce à l’analyse de caractère strict. Néanmoins, étant donné que la programmation à base de flots n’est pas guère intuitive, nous envisageons ce noyau de langage comme un niveau intermédiaire, atteint par une chaîne de transformations à partir d'un langage fonctionnel de plus haut niveau. Nous avons travaillé sur ce point avec Françoise Bellegarde [BEL 95].

Enfin, la NG-machine représente un compromis entre deux axes majeurs de l'implémentation parallèle de langages fonctionnels : le dataflow et la réduction de graphes.

• Par rapport au premier, nous rendons le contrôle aux processus.
• Par rapport au second nous structurons le parallélisme à l'aide de flots de données.

Retour au sommaire

Références

[AUG 89a] L. Augustsson, T. Johnsson Parallel Graph Reduction with the <n, G>-machine Proceedings of the 1989 Conference on Functional Programming Languages and Computer Architecture, 1989.

[AUG 89b] L. Augustsson, T. Johnsson The Chalmers Lazy-ML Compiler, The Computer Journal, Vol. 32, No. 2, pages 127-141, 1989.

[BAR 95] B. Barbier Réduction de graphes distribuée, rapport de DEA n°1854, Fac. des sciences, Université de Franche-Comté, 1995.

[BEL 95] F. Bellegarde ASTRE: Towards a Fully Automated Program Transformation System, Proc. of RTA'95 conference.

[BOU 92] F. Boussinot Réseau de processus réactifs, Rapport de recherche INRIA, n°1588, 1992.

[BOU 93] L. Bougé Le modèle de programmation à parallélisme de données : une perspective sémantique, Techniques et Science Informatiques, Volume 12, n°5, 1993, pages 541-562.

[CAS 96] P. Caspi, M. Pouzet Synchronous Kahn Networks ACM SIGPLAN International Conference on Functional Programming (ICFP'96), Philadelphia, May 1996.

[CAN 96] C. Canipel et S. Farnier, Vérification d'un protocole de communication à l'aide de SPIN, rapport interne du LIB (DESS), Université de Franche-Comté, 1996.

[CEN 92] CENTAUR1.2: manuel de référence, SemaGroup, 1992.

[COS 94] M. Cosnard, F. Desprez Quelques architectures de nouvelles machines, Calculateurs parallèles n° 21, Mars 1994.

[FLY 66] M.J. Flynn Some computer organizations and their effectiveness, IEEE Trans. on Computers, C-21, 9, 1972, pages 948-960.

[GEL 96] W. Gellerich, M.M. Gutzmann Parallel Programming Languages - A Classification of Design Approaches, IEEE Conference on Parallel and Distributed Computing Systems, Dijon, septembre 1996.

[KAH 74] G. Kahn The semantics of a simple language for parallel programming Proc. of IFIP Congress, 1974.

[KIN 91] H. Kingdom, D. Lester, G. L. Burn The HDG_machine, a highly distributed graph reducer for a transputer network, The Computer Journal, Vol. 34, No 4, pages 290-302, 1991.

[MAR 91] L. Maranget GAML: a Parallel Implementation of Lazy ML Proceedings of the 1991 Conference on Functional Programming Languages and Computer Architecture, 1991.

[PEY 87] S. L. Peyton Jones Implementation of Functional Programming Languages, Prentice-Hall 1987.

[PEY 91] S. L. Peyton Jones, D. Lester Implementing functional languages, Prentice-hall Int.series in computer sc. 1991

[SKE 91] S. K. Skedzielewski Sisal, pages 105-158, dans Parallel Functional Languages and Compilers. B. K. Szymanski Ed., ACM Press, 1991.

Retour au sommaire