Propriétés de correction séquentielle dans un langage parallèle à mémoire partagée

Les modèles de programmation parallèle

Il existe plusieurs formes de parallélisme. Nous pouvons les envisager par l’aval, en considérant les formes d’architecture de machines parallèles, ou bien les considérer par l’amont, à travers des modèles de programmation paral lèle. Nous inspirant de la classification de Flynn [40], nous distinguons trois formes d’architecture parallèle, correspondant assez étroitement à trois modèles de programmation parallèle. Nous allons les esquisser tout d’abord, avant d’évoquer ensuite qu’il est parfois possible et intéressant de concevoir un programme dans un certain modèle de programmation, puis de le compiler vers une machine cible participant d’un autre modèle.

Le modèle de programmation à paral lélisme de données. Dans ce modèle, des instructions s’exécutant de manière strictement séquentielle accèdent chacune à tout un ensemble de données à la fois, par exemple à tout un tableau, traitant ces données en parallèle. C’est dans ce modèle de programmation que se place le calcul vectoriel. Le langage Fortran HPF [14], par exemple, se réclame de ce modèle de programmation. Ce modèle est le plus simple, car le contrôle y reste séquentiel. Cependant, la classe d’algorithmes pour laquelle il est eficace est restreinte. L’architecture de machine correspondante est dite SIMD (Single Instruction stream Multiple Data stream).

Les deux autres modèles de programmation parallèle que nous allons évoquer maintenant sont les modèles à paral lélisme de contrôle : sur les architectures qui y correspondent, plusieurs flots d’instructions peuvent s’exécuter simultanément, sur plusieurs processeurs . Ces formes d’architecture sont dites MIMD (Multiple Instruction stream Multiple Data stream)

Le modèle distribué à passage de messages correspond à l’architecture parallèle à mémoire distribuée MIMD DM (MIMD Distributed Memory), dans laquelle plusieurs processeurs dotés chacun d’une mémoire locale, communiquent par l’envoi et la réception de messages. Ce modèle de programmation parallèle est le plus complexe à utiliser, plaçant sur le programmeur la charge de la coordination et de l’échange de données par l’envoi et la réception explicites de messages entre des unités distinctes. Ce modèle de programmation est représenté notamment par les bibliothèques PVM [16] et MPI [15]. Ce modèle est potentiellement le plus efficace mais la programmation peut s’y révéler dificile pour des applications complexes.

Le modèle asynchrone à mémoire partagée. Dans l’architecture qui y correspond, l’architecture paral lèle à mémoire partagée MIMD SM (MIMD Shared Memory), plusieurs processeurs s’exécutant en parallèle échangent des données avec une mémoire commune. Cette architecture est celle des multiprocesseurs à mémoire réelle partagée, machines très répandues, dotées d’un petit nombre de processeurs. Le modèle de programmation correspondant occupe, quant à sa dificulté de mise en oeuvre, une position intermédiaire entre les deux autres modèles précédemment mentionnés. C’est à ce modèle de programmation que nous al lons nous intéresser dans le présent travail.

Sur les sémantiques du parallélisme

L’utilisation de la programmation parallèle pose différents problèmes. Par exemple, apparaît le problème de l’eficacité de la parallélisation : comment concevoir notre programme parallèle, ou le charger en machine, pour que, exploitant au mieux les possibilités de cette dernière, il fournisse ses résultats le plus vite possible ? Mais, plus fondamentalement, se pose le problème de la correction (au sens de : caractère correct correctness en anglais) d’un programme parallèle : comment spécifier la sémantique souhaitée de ce programme, c’est-à-dire le comportement que l’on en attend quant aux calculs effectués et aux résultats obtenus ? Lors de l’exécution d’un programme séquentiel, sa sémantique est assez bien caractérisée conceptuellement, et modélisée sans ambiguïté dans son principe. Les exécutions d’instructions individuelles s’y opèrent suivant un ordre temporel strict chaque instruction termine son exécution avant que l’instruction suivante commence la sienne , et dans un environnement donné (c’est-à-dire un état de la mémoire). Par exemple, pour les langages impératifs séquentiels, la sémantique opérationnel le modélise comment une exécution d’une instruction fait passer l’environnement d’un état à un autre, les transitions entre états étant régies par des règles formelles ([39], par exemple) Le modèle à parallélisme de données a une sémantique analogue, en fin de compte, à la sémantique séquentielle : comme nous l’avons mentionné, en effet, le contrôle y reste séquentiel.

Dans les modèles à parallélisme de contrôle, au contraire, les choses apparaissent beaucoup plus compliquées. Dès lors, en effet, que plusieurs processus s’exécutent simultanément, interférant avec des environnements de mémoire éventuellement distincts, leur sémantique est beaucoup moins claire. Par exemple, il apparaît un indéterminisme fondamental (tenant au fait que les processus sont autorisés, a priori, à s’exécuter à des vitesses diférentes) qui n’existe pas au même titre dans le cas d’un programme séquentiel. La modélisation du comportement de programmes à parallélisme de contrôle a fait l’ob jet de plusieurs travaux. En 1978, Hoare a introduit le modèle des processus séquentiels communicants (Communicating Sequential Processes, ou CSP) [23], dans lequel les processus communiquent par envoi et réception de messages CSP est donc plus particulièrement adapté au modèle à mémoire distribuée. Dans CSP, les messages sont synchrones, en ce sens qu’un message ne peut être émis que si son destinataire est prêt à le recevoir (rendez vous), par opposition au cas asynchrone où le processus émetteur n’a pas besoin d’attendre (en suspendant son exécution) la réception de son message le modèle que nous allons considérer comporte un tel mode asynchrone de communication entre processus. En 1980, Milner développa un calcul algébrique permettant de décrire de manière abstraite le parallélisme et le non-déterminisme (Calculus for Communicating Systems, ou CCS), développement qui déboucha ensuite sur le calcul (1989) ([29], par exemple). On a dit que le -calcul est aux langages parallèles ce que le -calcul est aux langages fonctionnels .

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
2 Le langage étudié
2.1 Le langage
2.2 Le modèle d’exécution
2.3 La correction séquentielle. La notion d’équivalence sémantique
3 Dépendances et précédences
3.1 Le prédicat d’exécution séquentielle
3.2 Dépendances
3.3 Précédences
3.3.1 Expression des précédences de contrôle
3.3.2 Combiner précédences de contrôle et de synchronisation
3.3.3 Les précédences de synchronisation
4 Quelques résultats préliminaires
4.1 Approximations conservatrices des prédicats
4.2 Un lemme sur le prédicat d’exécution
4.3 Une notion de date d’exécution
4.4 L’exécution monoprocessus ordonnée
5 Le théorème d’équivalence sémantique
6 Applications du théorème
6.1 L’application développée au CERMICS
6.2 Quelques considérations de complexité
6.3 L’idée d’exécution séquentielle « test »
6.4 Le traitement incrémental des non-préservations de dépendances
7 Extensions possibles
7.1 Les synchronisations à passage de références
7.2 Les sections critiques
8 Conclusion