aboutsummaryrefslogtreecommitdiffstats
path: root/README
blob: 9928b3e8d95ff8d31dbe4fa8b0c205112ffb3b32 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

Projet de Système et Réseaux 2014
Alex AUVOLAT, Jean FABRE-MONPLAISIR

------------------------------------

Description du projet
=====================

Implémentation des réseaux de Kahn en OCaml pour permettre la programmation
parallèle. Trois implémentations à réaliser :

- Implémentation séquentielle (parallélisme coopératif mono-threadé)
- Implémentation basée sur les primitives Unix (fork, pipe)
- Implémentation permettant la communication en réseau


Commentaires techniques
=======================

Dans les versions séquentielle et Unix, nous avons implémenté une nouvelle
primitive : select, qui permet de faire un get sur plusieurs caneaux en même
temps et d'exécuter une fonction différente en fonction du premier canal sur
lequel un message arrive. Nous n'avons pas pris le temps d'implémenter cette
fonction dans la version fonctionnant par le réseau.

Version séquentielle
--------------------

Un processus est décrit par le type suivant :

    type 'a process = ('a -> unit) -> unit

C'est-à-dire qu'un processus renvoyant une valeur de type 'a est une fonction qui
prend comme argument sa continuation et s'exécute à ce moment-là.

Les fonctions qui exploitent le parallélisme font appel à une file de processus
en attente d'exécution : doco lance des processus en “parallèle” en mettant
les-dits processus dans la file ; get gère l'attente d'un message sur un canal
en mettant en fin de file un processus qui re-tente le get lorsque celui-ci a
échoué car le canal ne contenait aucune donnée - l'éspoir étant qu'un autre
processus se sera exécuté d'ici-là et aura envoyé un message dans le canal.

Version Unix
------------

Toutes les primitives sont fournies d'office par Unix, il n'y a donc presque
rien à faire. Les put/get sont automatiquement gérés par le noyau en ce qui
concerne la bufferisation et la mise en attente d'un processus tant qu'il n'y a
rien à lire ou qu'il n'y a plus de place pour écrire. Le lancement de processus
en parallèle (doco) exploite simplement l'appel système fork, puis waitpid pour
la syncronisation finale.

Version réseau
--------------

Publicité pour la version réseau : nous avons réussi, en mobilisant 5 machines
des salles INFO3 et INFO4 de l'ENS, à calcuer de manière naïve (c'est-à-dire
avec un algorithme exponentiel) le 53e nombre de la suite de Fibonacci, en un
temps record de 16,8 secondes. Ce nombre pouvait être calculé sur une seule
machine, ce qui prenait un peu plus d'une minute dans le cas d'une machine dont
les quatre cœurs étaient exploités (implémentation Unix). En mobilisant plus de
machines, nous pourrions sûrement améliorer encore ce temps.

L'implémentation réseau est basée sur une version simplifiée de l'implémentation
séquentielle, où un processus participant de l'exécution du réseau se contente
de lire des tâches sur stdin, de les exécuter et d'envoyer des informations sur
stdout (messages envoyés, tâches lancées par doco).

À cela se rajoute un “manager”, ou gestionnaire, qui s'occupe de multiplexer les
entrées/sorties pour dispatcher les processus disponibles aux différents
processus qui lui sont affectés.

Les appels système pour la communication étant les même pour le réseau et les
pipes (read/write), le manager peut aussi bien communiquer avec des processus
locaux qu'avec des processus distants via le réseau.

À cela nous avons rajouté un système de “pool” (pool server/pool client) qui
permet à un certain nombre de machines de se déclarer “disponnibles” pour des
calculs. Le manager peut ensuite demander à la pool de lui donner un certain
nombre de processus pour effectuer des calculs. Le pool client s'occupe
d'initaliser la connection réseau et de rediriger stdin et stdout vers le
réseau, avant de lancer le processus qui effectuera les calculs.

Les tâches (processus au sens de Kahn) sont des fermetures que l'on serialise
via la bibliothèque Marshall d'OCaml pour être transmis par le réseau. La partie
manager est indépendante de l'application que l'on fait tourner, par contre le
binaire qui effectue les calculs doit être identique sur toutes les machines
participant au calcul pour que des fermetures puissent être transmises via
Marshall sans problème.

Utilisation de la version réseau :

    tulipier$ ./poolserver.native &
    tonka$ ./poolclient.native tulipier
    tamier$ ./poolclient.native tulipier
    turnep$ ./poolclient.native tulipier
    tetragone$ ./poolclient.native tulipier
    tulipier$ time ./manager.native -pool-addr tulipier \
        -my-addr tulipier -pool-proc 16 -local-proc 4 ./example.native

(en supposant que . correspond au même dossier, monté par NFS par exemple, sur
toutes les machines)

Les temps d'exécution peuvent varier car ils sont fonction de la répartition
entre les machines des tâches qui calculent peu et communiquent beaucoup :
celles-ci ralentissent le système lorsqu'elles sont lancées sur une machine qui
n'est pas celle où tourne le manager. Nous ne pouvons avoir que peu d'influence
là-dessus puisque la répartition des processus est un processus aléatoire.