Sémantique et mise en oeuvre parallèle d'un langage fonctionnel indulgent

La compilation d'un langage de programmation vers une machine parallèle multi-processeurs n'est pas une tâche facile. Un des éléments importants, comme pour la génération de code vers une machine normale, est de déterminer où se termine la tâche du programmeur et où commence celle du compilateur. Dans le cas de machines parallèles, ceci implique que l'on doit déterminer comment identifier ce qui peut être exécuté en parallèle et ce qui ne peut pas l'être. On peut faire la distinction entre deux types de parallélisme: explicite et implicite. Le parallélisme explicite est celui spécifié par le programmeur à l'aide d'annotations ou à l'aide de structures de contrôle parallèles alors que le parallélisme implicite est celui extrait par le compilateur sans que le programmeur n'ait à le spécifier explicitement. Dans ce mémoire, c'est ce dernier type de parallélisme (implicite) qui sera examiné dans le contexte d'un langage fonctionnel.

Ce mémoire vise à décrire le parallélisme qu'un compilateur pourrait extraire d'un programme écrit en pH, un langage parallèle dérivé de Haskell et Id. Pour rendre cette description claire et précise, nous allons utiliser une méthode formelle afin de décrire le comportement de notre langage. Nous avons choisi une algèbre de processus, le pi-calcul, comme langage formel, puisque ce genre de langage sémantique a été conçu expressément pour modéliser le parallélisme, les communications et synchronisations entre processus. La description sémantique résultante devrait pouvoir être facilement mise en oeuvre sur une architecture MIMD avec des processeurs multi-contextes puisqu'une telle architecture supporte des processus de granularité fine. Notons que la sémantique résultante va mettre en oeuvre le principe d'évaluation indulgente qui permet d'extraire un maximum de parallélisme d'un langage fonctionnel.

Afin de valider notre description sémantique, un interpréteur concurrent de pi-calcul a été développé. Cet interpréteur, qui utilise les fils d'exécution du langage Java afin de représenter l'évaluation concurrente de différents processus, a aussi été instrumenté afin de produire des profils de parallélisme et ainsi comparer diverse formes d'évaluation parallèle d'un programme (strict, indulgent et paresseux).