Ecole Polytechnique






Cours : ``Parallélisme''
Travaux dirigés
E. Goubault & M. Martel

TD 5

5 mars 2003




Dans les exercices suivants, on va distribuer des calculs. Afin de ne pas trop ``polluer'' le réseau et les machines de toutes les salles, vous ne démarrerez des programmes et des serveurs que sur votre machine, la machine immédiatement à gauche de la votre (ou à droite selon), et immédiatement derrière vous (ou devant, selon).

1  Calcul de p

Supposons que nous voulions calculer p en parallèle par la formule suivante,

p =
ó
õ
1


0
4

1+x2
dx
   
n
S
i=1
1

n
4

1+ æ
ç
ç
è
(i-
1

2
)
1

n
ö
÷
÷
ø
2



 

Une solution est le paradigme Maître/Esclave: Un maître va lancer N esclaves chargés de calculer les sommes partielles,
Pk =
Si=k*n/N(k+1)*n/N
1

n
4

1+ æ
ç
ç
è
(i-
1

2
)
1

n
ö
÷
÷
ø
2



 
pour k=0,···,N-1.

Implémenter le calcul de p en le distribuant réellement (par RMI).

2  Méthode aux différences finies

Implémenter le code de l'équation de la chaleur en RMI. En séquentiel, cela revient à calculer pour un certain nombre d'itérations la formule suivante, sur une matrice a représentant la valeur d'une température sur un plan (discrétisé):

for (i=0;i<=N-1;i++)
  for (j=0;j<=N-1;j++)
    a[i][j]=1/4*(a[i-1][j]+a[i+1][j]+a[i][j-1]+a[i][j+1]);
On pourra commencer par en faire une implémentation utilisant les threads JAVA, ensuite on essaiera de la transformer avec RMI. Afin de simplifier l'écriture du code, on supposera que chaque processus s'occupera d'une portion égale de a de la forme a[0,...,r-1][0,...,N-1] et que donc, On supposera que les ``conditions aux limites'' c'est à dire les éléments de la forme a[0][0,...,N-1], a[N-1][0,...,N-1], a[0,...,N-1][0] et a[0,...,N-1][N-1], ont une température imposée, ici 100, alors qu'à l'instant initial, la valeur de la température à l'intérieur vaut 0.

On supposera pour simplifier que le nombre total de processus divise N, et que N est divisible par 2. On pourra par exemple afficher la température maximale à l'intérieur de chaque domaine (pour chaque processus ``esclave'').

Qu'est-ce que chaque processus doit avoir comme information à sa création? Quelles seront les synchronisations entre processus nécéssaires à la bonne résolution de l'équation de la chaleur?

En RMI, on pourra considérer chaque processus comme étant un serveur d'une itération en temps pour l'un des sous-domaines, étant donné les valeurs aux bords de ce sous-domaine. Le client sera chargé de demander à chacun des processus une itération, et ainsi de suite. En threads JAVA, on pourra soit programmer une version ``mémoire partagée'', soit une version (plus facile à transformer en RMI) qui fasse explicitement des ``envois'' et des ``réceptions'' de tranches de tableaux.

3  Simulation de processeurs en anneau

Implémenter en RMI un objet permettant de passer un message d'une machine à une autre, de telle façon à simuler les opérations de passage de message sur un réseau en anneau vues en cours. On appelera un serveur sur chaque noeud du réseau en anneau que l'on voudra simuler. A la ligne de commande, on donnera au serveur le nom de la machine successeur, et le nom de la machine prédécesseur. Chaque objet créé par ce serveur pourra exécuter les méthodes suivantes: Une façon de programmer cela est de considérer chaque objet distant s'exécutant sur un noeud comme étant un client pour le serveur du noeud suivant, et un serveur pour l'objet représentant son noeud prédécesseur.


This document was translated from LATEX by HEVEA.