HirondML2 : Migration de calcul en Objective Caml

Emmanuel Chailloux

Présentation générale

La conception de programmes répartis pose des difficultés en matière de concurrence, de sérialisation de données et de synchronisation. Bien que la nature de ces problèmes soit bien distincte, les outils théoriques <<classiques>> disponibles pour les résoudre se révèlent inadaptés lorsqu'ils intéragissent dans le cadre d'une utilisations répartie. Le projet HirondML consiste en la construction d'un modèle et d'une implantation basés sur d'autres outils et en la démonstration de leur pertinences en terme d'expressivité et de sûreté. La sûreté d'un programme réparti sera considérée comme effective si son éxécution ne provoque pas d'erreur de type et que chaque << unité de calcul >> en son sein se trouve dans un état cohérent.

Pour cela on se propose de développer un système offrant un mécanisme de migration de calculs, utilisant les fair threads pour la synchronisation de threads, sûr et efficace pour les applications réparties et les calculs parallèles pour O'Caml.

Objective Caml
Objective Caml, dévéloppé à l'Inria ( O'Caml ), est l'un des dialectes ML les plus connus. Ses qualités d'expressivité, de sûreté et d'efficacité sont appréciées par une communauté de programmeurs en nombre croissant. Pour améliorer sa diffusion on cherche à le doter d'un environneement de développement intégré portable sur les plate-formes de développement classiques (Windows, macosx, Linux).

Fair threads
Les fair threads[1] apportent un modèle coopératif simple et riche pour l'écriture d'applications concurrentes. Le modèle des fair threads est composé de schedulers et de threads. Chaque thread est attaché à un scheduler et coopère avec celui-ci. Dans tout scheduler un unique thread est actif jusqu'au prochain point de coopération. Lorsque un thread coopère avec son scheduler, le scheduler active le prochain thread. Une synchronisation est possible par la communication d'événements dans l'instant de calcul à la manière de la programmation réactive.
Les fair threads sont implantés en C, Java et Scheme (suivre le lien). Une version expérimentale et simplifiée a été conçue pour Objective Caml (suivre le lien ) pour être utilisée dans la bibliothèque hirondML de migration de calculs.

HirondML
Une des principales difficultés dans la migration de calculs provient de la synchronisation en cas de partage de donnéees dans l'environnement de calcul de la destination. Ce travail est effectué en collaboration avec Julien Verlaguet est en cours de finition

Le système HirondML [3] utilise des fair threads coopératifs à la Boussinot, implantés en Objective Caml, pour réaliser la synchronisation quand un calcul arrive à destination. L'environnement local est copié lors de la migration, mais l'environnement global (qui doit être commun) est spécifique à chaque instance de programme. Ce choix permet d'obtenir des performances raisonables, ou du moins contrôlables par le programmeur.

HirondML apporte un mécanisme de migration de code entre même version d'exécutable de programmes Objective Caml. Lors de la migration d'un calcul d'un exécutable vers un autre, HirondML copie la pile et une partie du tas correspondant aux variables locales utiles pour la poursuite du calcul. Les variables globales sont reliées à nouveau lors de l'arrivée du point de calcul. Pour cela il est nécessaire de communiquer les points de calcul entre exemplaires du même programme ayant déjà évalué toutes les variables globales du programe. On obtient ainsi la possibilité d'utiliser une copie d'une partie de l'environnement et de se relier à la partie restante.
L'implantation expérimentale utilise l'analyse de détection des variables nécessaires à un calcul du compilateur natif d'Objective Caml, une version simplifiée des fair threads pour gérer les départs et les arrivées de point de calcul, une gestion de la pile et du tas permettant d'embarquer la partie utile, et un système de déploiement sur un réseau local.

Objectifs du stage

Le premier objectif de ce stage est de réaliser une bibliothèque complète et sémantiquement correcte des Fair threads [1], [2] pour Objective Caml. Il est néanmoins possible d'utiliser le prototype existant utilisé dans HirondML1.

Le deuxième objectif est d'écrire une sémantique pour la migration de points de calcul en HirondML, en précisant les notions de capture de l'environnement local et de liaison de l'environnement global.

Le troisième objectif est de réaliser une implantation respectant cette sémantique qui utilise la nouvelle bibliothèque de Fair Threads.

Une fois ces trois points atteints, on cherchera à étendre le système pour traiter cette migration entre programmes différents. On s'interessera alors au nommage de l'environenment global et au chargement dynamique de modules, principalement du point de vue des types. La lecture des articles sur le langage Acute [4] permet d'apprécier les problèmes posés.

Profil recherché

Le volume de travail de ce stage est évalué entre 4 et 6 mois pour un étudiant de M2 qui devra pouvoir allier connaissances théoriques (avoir suivi un cours de sémantique et si possible un cours sur la concurrence) et pratiques (connaissances des langages Objective Caml et C).

Contact

Emmanuel Chailloux
Bureau 740
Equipe SPIRAL - LIP6
Université Paris 6 
104 avenue du président Kennedy 
75016 Paris


mél : Emmanuel.Chailloux@lip6.fr
web : http://www-spiral.lip6.fr/~chaillou

Références

[1]
Boussinot (F.). – Fair Threads: mixing cooperative and preemptibe threads in C. Inria research report, RR-5039 – Décembre 2003.

[2]
Serrano (M.), Boussinot (F.) et Serpette (B.) – Scheme Fair Threads – In : 6th sigplan International Conference on Principles and Practice of Declarative Programming (PPDP). – Août. 2004.

[3]
Chailloux (E.) et Verlaguet (J.). – Hirondml : Fair threads migrations for objective caml. In : Third Workshop on High-Level Parallel Programming and Applications. – Juillet 2005.

[4]
Peter Sewell, James J. Leifer, Keith Wansbrough, Francesco Zappa Nardelli, Mair Allen-Williams, Pierre Habouzit, Viktor Vafeiadis. Acute: high-level programming language design for distributed computation. In : ICFP 2005
Ce document a été traduit de LATEX par HEVEA