Projet CARAML (ACI) : Objective Caml Flight
Description d'un Prototype

Emmanuel Chailloux1

 
1: Equipe Preuves, Programmes et Systèmes (UMR 7126),
Emmanuel.Chailloux@pps.jussieu.fr
http://www.pps.jussieu.fr/~emmanuel

version du Date: 2003/04/23 15:50:19

Introduction

Ce document présente un prototype d'une extension data-parallèle du langage Objective Caml. Une première version, appelée Caml-FLight, de cette extension a été réalisée pour le langage Caml-Light en 1995/96. L'implantation de Caml-FLight nécéssitait de modifier les sources du compilateur Caml-Light. Elle n'a pu suivre les différentes évolutions du langage Caml-Light devenu maintenant Objective Caml. Le prototype présenté dans ce document tente d'implanter les mêmes fonctionalités de Caml-FLight pour Objective Caml en utilisant le préprocesseur camlp4 permettant ainsi de ne pas modifier le compilateur original Objective Caml pour garantir l'évolution de l'extension, maintenant appelée Objective Caml-Flight, pour les prochaines moutures de langage Objective Caml.
On rappelle tout d'abord les principes de Caml-FLight. On décrit ensuite les outils fournis avec les distributions récentes d'Objective Caml qui facilitent l'implantation de telles extensions.

1   L'ancêtre Caml-FLight

Le texte de cette section est tiré de [1] :

1.1   Adressage

Les processus qui exécutent le calcul sont numérotés de 0 à nodes - 1. La valeur de nodes est commune à tous les processus. La constante local a la valeur de l'adresse du processus, cette valeur est unique et constante pour chacun des nodes processus.

L'intérêt d'un mode d'adressage linéaire est d'être indépendant de l'architecture du réseau ou de la machine. L'écriture d'applications portables en est facilité, au compilateur de s'adapter à la topologie du réseau ou de la machine cible.

1.2   Syntaxe

Les deux constantes de localisation font partie de la nouvelle syntaxe. Deux nouvelles instructions sont ajoutées au langage Caml-Light. Si on suppose qu'une expression Caml-Light est nommée Expr et est fonction de Simple_Expr, l'extension de la syntaxe est la suivante :
2.0in 

Expr ::= Simple_expr
      ...
      | sync Expr
      | get ( Expr , Expr )

Simple_expr ::= ...
      | local | nodes
140.pt get(e1,e2) correspond à la demande de calcul, de l'expression e2, délocalisé sur le processeur d'adresse e1. sync(e) autorise les communications dans l'environnement (voir en 1.4) cons truit à l'entrée d'un sync pour le calcul de l'expression. Il n'y a pas de get en dehors d'un sync.

1.3   Typage

Deux nouvelles règles de typage sont introduites pour les nouvelles instructions.

2.in
G |- e : t
G |- sync(e) : t
140.pt Le type d'une opération parallèle sync d'une expression est le type de cette expression.
   

2.in
G |- e1 : int   G |- e2 : t     V(t)=f
G |- get(e1,e2) : t
140pt Le type d'une communication est celui de l'expression à calculer. V(t) est l'ensemble des variables de type de t, il doit être vide (i.e. le get est monomorphe).

Les deux constantes de localisation, local et nodes, sont de type int.

1.4   Blocs de synchronisation, environnements et communications

Il n'y a de communication possible qu'à l'intérieur d'un sync. À l'entrée du w-ième sync par un processus, l'environnement courant est conservé : il s'agit de l'environnement de communication de la vague w. L'environnement de communication sert à l'évaluation des requêtes (produites par get) pouvant parvenir au processus. Pour cela, l'environnement de calcul ne pourra plus par la suite être modifié dans le corps de sync avant un autre get, i.e. qu'il ne peut pas être augmenté, ni modifié sans interdire l'utilisation subséquente de get. Cela empêche toute nouvelle déclaration, le filtrage et (bien entendu) les modifications physiques avant l'occurrence d'un get dans le corps de sync. Cette restriction est particulièrement forte pour les filtrages à un seul cas1, mais est indispensable pour la cohérence de l'environnement dans tous les autres cas. Comme l'exécution des copies du programme est asynchrone, il est possible que certains processus soient entrés dans un sync donné et d'autres non. Si une requête est envoyée à un processus non synchronisé, alors celle-ci doit attendre que le processus en question arrive dans ce bloc de synchonisation. De plus, un processus ne peut communiquer avec un autre que si les deux évaluent le même sync à la même vague. Pour amoindrir les attentes et accepter des programmes avec décalage temporel, Caml-FLight autorise les calculs à des vagues différentes en introduisant le mécanisme de profondeur d'asynchronisme.

1.5   Profondeur d'asynchronisme

Si on considère sync comme étant une barrière de synchronisation, tous les processus doivent s'attendre avant de débuter l'évaluation du corps du sync. Cette situation, essentielle dans les langages impératifs, est ici inutile puisque get accède un environnement composé essentiellement de valeurs (en excluant les valeurs mutables).

Pour relâcher cette contrainte, un paramètre entier est donné au lancement de l'évaluation : la profondeur d'asynchronisme. Si ce paramètre vaut p et que le processus le plus lent est à la vague w, le plus rapide ne pourra dépasser la vague w+p. Pour réaliser cette désynchronisation, les processus peuvent sauvegarder un total de p+1 ECs. De cette manière, un processus qui ne communique pas à une vague donnée peut continuer son évaluation plutôt que d'attendre à ne rien faire. On doit par contre connaître le moment où tous les processus ont terminé une vague donnée afin de libérer l'EC associé à cette vague, et ainsi permettre l'évolution du calcul. La profondeur d'asynchronisme agit ni plus ni moins comme une barrière de synchronisation à largeur variable : un processus trop ``rapide'' (ce qui arrive quand la charge est mal répartie) sera bloqué s'il atteint la vague maximale permise, son calcul ne pouvant reprendre qu'à la <<mort>> de la plus vielle vague.

La vague w correspond au w-ième bloc de synchronisation rencontré par un processus, il existe donc un environnement de communication (EC) par vague par processus. L'union des nodes ECs d'une vague donnée forme l'environnement global de communication (EGC). L'EGC de la vague w doit être préservé tant que tous les processus n'ont pas atteint la vague w+1.

La profondeur d'asynchronisme permet d'amoindrir les temps d'attente en permettant (quand le programme s'y prête) d'obtenir un effet pipeline entre les processus.

1.6   Exceptions et communications

On ne s'intéresse qu'aux exceptions se déclenchant dans un sync. Deux cas sont possibles, soit l'exception est déclenchée localement, soit elle est déclenchée dans un get (i.e. sur un processus distant). Dans le premier cas, si l'exception est traitée dans le corps du sync, tout se passe comme d'habitude. Si ce n'est pas le cas, l'exception s'échappe en provoquant prématurément la fin de la vague en cours (voir ??). Si l'exception se produit à distance, dans la partie droite d'un get, celle-ci revient à l'appelant, qui déclenche celle-ci chez lui. L'exception rebrousse ainsi chemin (car un get peut en contenir un autre) jusqu'à ce qu'elle regagne le processus ayant initié la chaîne de get. On se retrouve ultimement dans le premier cas de l'exception locale.

1.7   Limitations de Caml-FLight

Un certain nombre de limitations existe dans l'implantation de Caml-FLight. La liste suivante les indique :

2   Les outils utilisés

L'évolution du langage Caml-Light vers Objective Caml s'est effectuée par étapes sur les points suivants : On utilise pour cette extension les traits suivants : Tous ces (nouveaux) traits simplifient grandement l'implantation de l'extension.
À partir de la version 3.04 du langage Objective Caml [4] le préprocesseur camlp4 [5] est inclus dans la distribution. camlp4 permet de définir de nouvelles grammaires et de les étendre. Comme la grammaire de Objective Caml est fournie avec cet outil il est alors possible de l'étendre.

3   Le prototype

Le prototype Objective Caml-Flight se décompose principalement en trois fichiers Objective Caml et un fichier shell : L'ensemble de ces fichiers fait moins de 1000 lignes de code.
À aucun moment le compilateur Objective Caml n'est modifié. Ceci est un gage de pérénité de l'extension.

Au final, on obtient les commandes suivantes :

3.1   Principes d'implantation

Un programme Objective Caml-Flight est réécrit automatique en un programme Objective Caml (on peut voir le résultat par la commande ocamlfp).

instances de programme
Une fois l'exécutable construit, celui-ci est lancé sur différentes machines. Chaque <<instance>> de ce programme connait : Une instance de programme est alors composée de deux processus légers : un thread du programme séquentiel et un thread de serveur de requêtes accessible aux autres instances. Le protocole de base utilisé est TCP/IP. À chaque réception d'une requête, un nouveau processus léger est lancé pour effectuer le calcul demandé. Une fois celui-ci terminé (ou interrompu par une exception) la valeur calculée (ou l'exception) est transmise au demandeur.

envoi de requêtes
Les requêtes correspondent à l'exécution d'un get dans l'environnement distant d'un même bloc de synchronisation. L'information transmise est simple. Elle correspond aux informations suivantes : Au processus receveur d'effectuer le calcul.

répondre à une requête
Le processus receveur d'une requête de calcul, celui-ci doit l'effectuer dans l'environnement de calcul du bloc de synchronisation correspondant à la requête. A l'entrée du bloc de synchronisation, les différentes requêtes possibles get e from i2 définies dans ce bloc sont stockées sous la forme d'une fermeture : fun () -> e dans un tableau des requêtes du bloc. Quand une requête doit être traitée, un thread de calcul est lancé correspondant à l'application de cette fermeture sur la valeur (). Si le calcul se termine la valeur résultat est transmis au demandeur. En cas de déclenchement d'une exception durant le calcul, celle est transmise au demandeur qui la déclenche localement. Pour savoir si le processus receveur est bien dans le même bloc de synchronisation du demandeur et quelle fermeture doit être exécutée, les différents sync et get sont numérotés. Pour limiter les attentes entre blocs de synchronisation, il est possible de définir une profondeur d'asynchronisme pour chaque processus. Celle-ci permet de conserver les environnements de synchronisation des n derniers sync rencontrés. De cette manière il n'est plus nécessaire d'attendre que tous les processus soient synchronisés à la sortie du bloc courant de synchronisation.

environnement de communication
L'environnement de communication, dans un bloc de synchronisation, pour chaque fermeture correspondant à une requête est calculé à l'entrée d'un sync. Pour chaque requête get d'un même sync cet environnement doit rester le même, en particulier en cas d'effets de bord sur des valeurs de cet environnement. Ce cas peut arriver de par les expressions à l'intérieur de ce sync ou à l'extérieur du sync si la profondeur d'asynchronisme est supérieure à 1. Il est délicat d'effectuer une analyse de flots sur l'ensemble des programmes pour détecter ces effets de bord. Pour figer ces environnements, on utilise le module Marshal dont la fonction to_string de type 'a ® string linéarise une valeur Objective Caml sous forme d'une chaîne de caractères. La fonction from_string de type string ® 'a effectue l'opération inverse. On utilise to_string pour stocker dans un tableau de chaînes de caractères, à l'entrée d'un sync, les fermetures associées aux différents get du bloc de synchronisation. L'environnement de la fermeture stockée ne peut plus être modifié dans sa version chaîne de caractères. Quand une demande de calcul est reçue, celle-ci indique le numéro du get désiré (i), alors la fonction from_string est appliquée à la chaîne de caractères d'indice i ce qui restaure la fermeture avec une copie de son environnement. De cette manière l'environnement de calcul du get n'a pas pu être modifié.

type des requêtes
Pour pouvoir coder les fermetures correspondant aux requêtes dans une même structure linéaire elles sont vues de même type : unit ® 'a.

3.2   Module Flight

Un programme Objective Caml-Flight doit être lié avec le module Flight. Les tâches de ce module sont : Les données globales suivantes sont déclarées dans le module Flight : numéro du processus, nombre de processus, profondeur d'asynchronisme. Ces valeurs sont transmises sur la ligne de commande de l'exécutable.

3.3   Extension de syntaxe

On ajoute une règle pour les expressions du langage correspondant aux blocs de synchronisation : 
  expr :
    [ [ "sync"; "("; c = sync_expr; ")" -> ...
en introduisant une nouvelle classe d'expressions (sync_expr) pour les expressions à l'intérieur d'un bloc de synchronisation. Ces sync_expr sont des expressions Objective Caml qui n'introduisent pas de nouvelles variables (c'est-à-dire n'augmentent pas l'environnement de calcul d'un bloc de synchronisation). On élimine principalement les déclarations locales, le filtrage de motif, les lambda-asbtractions, les boucles for. On leur ajoute l'expression de calcul distant get suivante : 
    | "sync_expr1"
        [ "get"; e = sync_expr; "from";  n = sync_expr -> ...
Syntaxiquement un get ne peut pas être à l'extérieur d'un sync.

3.4   Démarage des tâches

Les différentes versions du même programme sont lancées par le shell script monitor. Ses trois premiers arguments correspondent au nom de l'exécutable, le premier numéro de port et la taille de la profondeur d'asynchronisme. Les arguments qui suivent sont les noms des différentes machines où s'exécuteront le programme. Ces programmes sont lancés par une commande ssh (ou rsh). Une fois tous ces programmes démarés, ce lancement étant validé par l'utilisateur, le programme start envoie à chaque instance du programme les informations sur les autres instances par le programme Objective Caml start. Ces programmes ne s'arreteront que lorsque toutes

4   Exemple

L'exemple suivant est plus un jeu de test qu'une application réelle, mais il permet de comprendre les transformations de programme effectués sur un cas simple. Un programme Objective Caml-Flight commence par l'ouverture du module Flight et se termine par l'expression close_Flight();; qui attend que tous les processus soient sortis de la vague.

for.ml
: chaque processus initialise un vecteur v par des valeurs en fonction de son numéro de noeud. Ensuite le processus 0 demande à chaque processus la valeur du vecteur pour sa position et l'affecte au vecteur du processus 0.

(* open Flight;; *)

let v = Array.init Flight.nodes (fun i-> Flight.nodes * i + Flight.local)
in
  for i=0 to Flight.nodes-1
  do
    let r =  sync ( if Flight.local == 0
             then get v.(i) from i
             else v.(i) )
    in v.(i) <- r
  done;
  Printf.printf "Processus %d: valeur du tableau: " Flight.local;
  flush stdout;
  for i = 0 to (Flight.nodes-1)
  do
    Printf.printf "%d " v.(i);
    flush stdout;
  done;
  Printf.printf "\n";
  flush stdout;;

Flight.close_Flight();;
La transformation de ce programme donne : 
(* open Flight;; *)

let _ =
  let v =
    Array.init Flight.nodes (fun i -> Flight.nodes * i + Flight.local)
  in
  for i = 0 to Flight.nodes - 1 do
    let r =
      Flight.env_buffer := [];
      begin
        Flight.save_closure
          (Marshal.to_string (fun () -> v.(i)) [Marshal.Closures]);
        let ___fun_sync () =
          if Flight.local == 0 then
            if i == Flight.local then v.(i) else Flight.drequest i 1
          else v.(i)
        in
        match Flight.sync_type.(0), Flight.sync_type.(1) with
          0, 0 ->
            Flight.begin_sync 1;
            let ___res_sync =
              try ___fun_sync () with
                Flight.RemoteExn e -> raise e
              | e -> raise e
            in
            Flight.end_sync (); ___res_sync
        | ___s, ___g ->
            if ___s == 1 && ___g == 0 || ___g == 1 then ___fun_sync ()
            else raise Flight.NestedSync
      end
    in
    v.(i) <- r
  done;
  Printf.printf "Processus %d: valeur du tableau: " Flight.local;
  flush stdout;
  for i = 0 to Flight.nodes - 1 do
    Printf.printf "%d " v.(i); flush stdout
  done;
  Printf.printf "\n";
  flush stdout

let _ = Flight.close_Flight ()
Seule la partie dans le sync est modifiée.

Pour créer un exécutable, on utilise un des deux compilateurs fournis. 
$ ./nocfc -o for.exe -thread unix.cma threads.cma flight.cmo for.ml

$ ./nocfopt -o for.exe -thread unix.cmxa threads.cmxa flight.cmx 
for.ml -cclib -lthreads -cclib -lunix -cclib -lpthread
Pour l'exécutation la commande monitor est utilisée. Dans l'exemple suivant l'exécutable for.bc est lancé quatre fois sur la machine chrome à partir du port 3001 avec une profondeur d'asynchronisme de 3 : 
$ ./monitor for.bc 3000 3 chrome chrome chrome chrome
Le moniteur attend une confirmation manuelle une fois que tous les processus serveur sont démarrés. 
press enter to start...
Processus 0: serveur demarré
Processus 2: serveur demarré
Processus 1: serveur demarré
Processus 3: serveur demarré
A ce moment là, la commande start communique les informations nécessaires à tous les processus lancés. 
Sortie normale
et les calculs peuvent commencer. Voici la trace pour for.bc: 
Processus 0: synchronisation...
Processus 2: synchronisation...
Processus 1: synchronisation...
Processus 3: synchronisation...
Processus 2: je surf sur la vague 1
Processus 2: synchronisation...
Processus 2: je surf sur la vague 2
Processus 2: synchronisation...
Processus 2: je surf sur la vague 3
Processus 2: synchronisation...
Processus 1: je surf sur la vague 1
Processus 1: synchronisation...
Processus 1: je surf sur la vague 2
Processus 1: synchronisation...
Processus 1: je surf sur la vague 3
Processus 1: synchronisation...
Processus 3: je surf sur la vague 1
Processus 3: synchronisation...
Processus 3: je surf sur la vague 2
Processus 3: synchronisation...
Processus 3: je surf sur la vague 3
Processus 3: synchronisation...
Processus 0: je surf sur la vague 1
Processus 0: synchronisation...
Processus 0: je surf sur la vague 2
Processus 0: je demande le get 1 de la vague 2 au processus 1
Processus 1: le processus 0 me demande le get 1 de la vague 2
Processus 1: j'envoi au processus 0 la valeur du get 1 de la vague 2
Processus 0: je recupère la valeur demandée au processus 1
Processus 0: synchronisation...
Processus 0: je surf sur la vague 3
Processus 0: je demande le get 1 de la vague 3 au processus 2
Processus 2: le processus 0 me demande le get 1 de la vague 3
Processus 2: j'envoi au processus 0 la valeur du get 1 de la vague 3
Processus 0: je recupère la valeur demandée au processus 2
Processus 0: synchronisation...
Processus 0: je surf sur la vague 4
Processus 2: je surf sur la vague 4
Processus 1: je surf sur la vague 4
Processus 2: valeur du tableau: 2 6 10 14 
Processus 2: j'ai fini, mais j'attend les autres...
Processus 1: valeur du tableau: 1 5 9 13 
Processus 1: j'ai fini, mais j'attend les autres...
Processus 3: je surf sur la vague 4
Processus 3: valeur du tableau: 3 7 11 15 
Processus 3: j'ai fini, mais j'attend les autres...
Processus 0: je demande le get 1 de la vague 4 au processus 3
Processus 3: le processus 0 me demande le get 1 de la vague 4
Processus 3: j'envoi au processus 0 la valeur du get 1 de la vague 4
Processus 2: voila!
Processus 1: voila!
Processus 0: je recupère la valeur demandée au processus 3
Processus 0: valeur du tableau: 0 5 10 15 
Processus 0: j'ai fini, mais j'attend les autres...
Processus 3: voila!
Processus 0: voila!

Conclusion

Par rapport à l'implantation d'origine Caml-FLight, cette nouvelle version a le grand avantage d'être simple. Elle n'implante pas toutes les fonctionalités, en particulier il n'est pas possible d'utiliser syntaxiquement un get à l'extérieur d'un sync. Néanmoins elle autorise les effets de bord à l'intérieur d'une requête, l'environnement de communicaiton est reconstruit à chaque requête. Le prototype utilise le protocole TCP/IP (à la place de UDP/IP) ce qui simplifie sa mise en oeuvre quitte à consommer des ressources du système. Il manque d'autre part un véritable moniteur qui permette le lancement automatique des tâches et la récupération des affichages de chaque processus. L'intérêt principal de ce prototype est de montrer l'utilisation des nouveaux outils d'Objective Caml pour la réalisation d'extension parallèles à ce langage.

Remerciements

Bruno Baia et Clément Garrigou ont implanté la première version d'OCF [6] dans le cadre d'un TER de maîtrise de Paris 6. Grâce à la qualité de leur travail, celui-ci a pu être repris par la suite.

Références

[1]
Emmanuel Chailloux and Christian Foisy, Caml-FLight : implantation et applications Journées Francophones des Langages Applicatifs INRIA, 1995

[2]
, Julie Vachon,

[3]
Emmanuel Chailloux, Pascal Manoury and Bruno Pagano, ``Développement d'applications avec Objective Caml'', O'Reilly, Apr, 2000, Paris.

[4]
Xavier Leroy et al, ``Objective Caml system 3.04 : Documentation and user's manual'', Documentation INRIA disponible sur le site ``http://caml.inria.fr'', 2001.

[5]
Daniel de Rauglaudre, ``camlp4 : '' Documentation INRIA disponible sur le site ``http://caml.inria.fr'', 2001.

[6]
Bruno Baia and Clément Garrigou, rapport de TER (maitrise), juin 2001.
1
Typiquement, le programme suivant est correct, mais sera rejeté par le compilateur Caml-FLight :
2.6in let f e =
sync( match e with (x,y) ®
if local < nodes-1
then get(local+1,x+y)
else 0) ;; 		95pt En effet, le filtrage de l'expression e augmente l'environnement de calcul des variables x et y.
2
la syntaxe du get a légèrement changé par rapport à l'ancêtre
Ce document a été traduit de LATEX par HEVEA.