Mise en oeuvre parallèle des langages fonctionnels paresseux: Une approche basée sur la propagation abstraite des demandes

Les langages fonctionnels sont souvent présentés comme une alternative intéressante pour la programmation des machines parallèles. Pour que ces langages soient utiles à la programmation de telles machines, il doit être possible de générer suffisament de parallélisme pour utiliser efficacement les ressources de la machine. Dans le cas des langages fonctionnels paresseux, ceci nécessite l'utilisation d'une forme d'analyse à la compilation appelée "analyse de stricticité": une telle analyse permet de détecter les expressions dont l'évaluation n'a pas besoin d'être gelée/suspendue, générant ainsi du parallélisme.

Dans cette présentation, une approche parallèle de la mise en oeuvre des langages fonctionnels paresseux sera introduite. Cette approche, basée sur le modèle parallèle d'exécution associé aux graphes de flux de données, utilise une forme d'analyse de stricticité appelée "propagation abstraite des demandes". La propagation de demandes peut être formalisée par le biais d'une sémantique dénotationnelle non-standard (propagation exacte) et d'une interpretation abstraite associée (propagation abstraite). Ceci permet de considérer la propagation de demandes comme une abstraction du processus de calcul de l'"inverse" d'une fonction, i.e., permet de déterminer les entrées devant être fournies de facon à produire un certain résultat.

La propagation abstraite des demandes a été incorporée dans un compilateur pour une version paresseuse de Id, langage initialement conçu pour les machines à flux de données dynamiques. Diverses expériences ont été effectuées pour déterminer l'impact de la "paresse" sur le parallélisme. Ces résultats expérimentaux seront brièvement présentés, résultats montrant que paresse et parallélisme sont peu compatibles.

Pour obtenir les acétates

Cliquez ici pour obtenir les acétates (postscript).