Parallélisme et Distribution

Eric Goubault
Commissariat à l'Energie Atomique

Chapter 1  Avant-Propos

Références

Chapter 2  Introduction

2.1  Une classification des machines parallèles

2.1.1  Machine SISD

int A[100];
...
for (i=1;100>i;i++)
   A[i]=A[i]+A[i+1];

2.1.2  Machine SIMD

       INTEGER I,J,A(32,1000)
CMF$   LAYOUT A(:NEWS,:SERIAL)
       ...
       FORALL (I=1:32,J=1:1000) 
     $    A(I:I,J:J)=A(I:I,J:J)+A(I:I,(J+1):(J+1))

---

Figure 2.1: Répartion d'un tableau sur les processeurs d'une machine SIMD typique.

---

2.1.3  Machine MISD

FOR  i:=1 to n DO
   R(a+b*i):=A(a'+b'*i)+B(a''+b''*i);

2.1.4  Machine MIMD

• (1) Mémoire partagée (Sequent etc.)
  
• (2) Mémoire locale + réseau de communication (Transputer, Connection Machine) - Système réparti

Mémoire Partagée:

---

Figure 2.2: Architecture simplifiée d'une machine à mémoire partagée.

---

• Barrières de synchronisation (voir section 5.5),
• Sémaphores : deux opérations P et V (voir section 5.4),
• Verrou (mutex lock) : sémaphore binaire qui sert à protéger une section critique (voir section 5.4.1),
• Moniteurs : construction de haut niveau, verrou implicite (voir section 5.3),
• etc.

Mémoire distribuée

• Appel de procédure à distance (RPC) :
  • réponse synchrone
  • réponse asynchrone
• Envoi/Réception de message asynchrone (tampon de taille limitée ou non), point à point, ou vers des groupes de processus; par active polling ou gestion à l'arrivée par une procédure handler. L'``active polling'' ou attente active désigne la façon qu'un processus attendant un message a de demander périodiquement si celui-ci est arrivé, pour effectuer son traitement. C'est une méthode consommatrice de CPU, qui n'est donc pas très efficace. La plupart des primitives de communication asynchrones offrent la possibilité d'appeler directement une fonction utilisateur ``handler'' à l'arrivée d'un message, ce qui permet au processus demandeur d'effectuer d'autres opérations, avant d'être interrompu par l'appel à ce ``handler'' de communication.
• Envoi/Réception de message synchrone : rendez-vous. Le modèle synchrone ou bloquant est le plus simple, et nous verrons dans le TD 6 un modèle théorique particulièrement adapté au raisonnement dans ce cas, il s'agit de l'algèbre de processus CCS, sorte de langage jouet décrivant les coordinations possibles de processus.
• Mélange des deux derniers cas.

---

2cm

Figure 2.3: Architecture Client/Serveur (RPC).

---

2.1.5  Gain d'efficacité

2.2  Contrôle d'une machine parallèle

• (1) On dispose d'un language séquentiel: le compilateur parallélise (Fortran...),
  
• (2) On a une extension d'un langage séquentiel (par exemple, PVM, MPI) ou un langage dédié avec des constructions parallèles explicites (Parallel C, Occam...)

• La création de parallélisme,
  • Itération simultanée sur tous les processeurs (FOR parallèle de Fortran ou FORALL),
  • Définition d'un ensemble de processus (COBEGIN),
  • Création de processus (FORK de Unix).
• Contrôler les tâches parallèles,
  • Synchronisation (Rendez-vous d'Ada),
  • Passage de messages (synchrones/asynchrones, broadcast,...),
  • Sections critiques (gestion de la mémoire partagée),
  • Arrêt d'une exécution parallèle (COEND, WAIT d'Unix).

Chapter 3  Threads Java

3.1  Introduction aux threads

3.2  Les threads en JAVA

3.2.1  Création

---

class Compte extends Thread { int valeur; Compte(int val) { valeur = val; } public void run() { try { for (;;) { System.out.print(valeur + " "); sleep(100); } } catch (InterruptedException e) { return; } } public static void main(String[] args) { new Compte(1).start(); new Compte(2000).start(); } }

Figure 3.1: Classe Compte programmée par extension de la classe Thread.

---

> java Compte
1 2000 1 2000 1 1 2000 1
^C
>

public void run();

public Thread(Runnable target);

---

class Compte implements Runnable { int valeur; Compte(int val) { valeur = val; } public void run() { try { for (;;) { System.out.print(valeur + " "); sleep(100); } } catch (InterruptedException e) { return; } } public static void main(String[] args) { Runnable compte1 = new Compte(1); Runnable compte2 = new Compte(2000); new Thread(compte1).start(); new Thread(compte2).start(); } }

Figure 3.2: Classe Compte programmée par implémentation de l'interface Runnable.

---

3.2.2  Partage des variables

---

public class UnEntier { int val; public UnEntier(int x) { val = x; } public int intValue() { return val; } public void setValue(int x) { val = x; } }

Figure 3.3: La classe UnEntier.

---

3.2.3  Quelques fonctions élémentaires sur les threads

---

class Compte3 extends Thread { int valeur; Compte3(int val) { valeur = val; } public void run() { try { for (;;) { System.out.print(valeur + " "); sleep(100); } } catch (InterruptedException e) { return; } } public static void printThreads() { Thread[] ta = new Thread[Thread.activeCount()]; int n = Thread.enumerate(ta); for (int i=0; i<n; i++) { System.out.println("Le thread "+ i + " est " + ta[i].getName()); } } public static void main(String[] args) { new Compte3(1).start(); new Compte3(2000).start(); printThreads(); } }

Figure 3.4: Nouvelle implémentation de la classe Compte.

---

% java Compte3
1 2000 Le thread 0 est main
Le thread 1 est Thread-2
Le thread 2 est Thread-3
1 2000 1 2000 1 2000 1 2000 2000 
1 1 2000 2000 1 1 2000 2000 1 1 
2000 2000 1 1 2000 2000 1 1 2000 
2000 1 1 2000 2000 1 1 ^C
%

3.3  Eléments avancés

• l'état initial, comprenant tous les instants entre sa création (par un constructeur) et l'invocation de sa méthode start().
• l'état prêt, immédiatement après que la méthode start ait été appelée.
• l'état bloqué représentant les instants où le thread est en attente, par exemple d'un verrou, d'un socket, et également quand il est suspendu (par la méthode sleep(long) qui suspend l'exécution du thread pendant un certain temps exprimé en nanosecondes, ou suspend). On repasse à l'état prêt (ou exécution) quand le verrou est de nouveau disponible, ou quand a été fait resume, notify etc.
• l'état terminaison, quand sa méthode run() se termine ou quand on invoque la méthode stop() (à éviter si possible, d'ailleurs cette méthode n'existe plus en JAVA 2).

---

public class ... extends Thread { ... public void stop() { t.shouldRun=false; try { t.join(); } catch (InterruptedException e) {} } }

Figure 3.5: Utilisation typique de join.

---

3.3.1  Priorités

setDaemon(Boolean on);
boolean isDaemon();

3.3.2  Ordonnancement des tâches JAVA

3.3.3  Les groupes de processus

new Thread(ThreadGroup group, Runnable target);
new Thread(ThreadGroup group, String name);
new Thread(ThreadGroup group, Runnable target, String name);

ThreadGroup Groupe = new ThreadGroup("Mon groupe");
Thread Processus = new Thread(Groupe, "Un processus");
...
ThreadGroup MonGroupe = Processus.getThreadGroup();

Groupe.getParent();
Groupe.getName();
Groupe.activeCount();
Groupe.activeGroupCount();
Groupe.enumerate(Thread[] list);
Groupe.enumerate(Thread[] list, boolean recurse);
Groupe.enumerate(ThreadGroup[] list);
Groupe.enumerate(ThreadGroup[] list, boolean recurse);

1

C'est pourquoi il faut toujours encapsuler ces appels dans un bloc try ... catch(InterruptedException e)

Chapter 4  Modèle PRAM

4.1  Introduction

• d'une suite d'instructions à exécuter plus un pointeur sur l'instruction courante,
• d'une suite non bornée de processeurs parallèles,
• d'une mémoire partagée par l'ensemble des processeurs.

• EREW (Exclusive Read Exclusive Write): seul un processeur peut lire et écrire à un moment donné sur une case donnée de la mémoire partagée.
• CREW (Concurrent Read Exclusive Write): plusieurs processeurs peuvent lire en même temps une même case, par contre, un seul à la fois peut y écrire. C'est un modèle proche des machines réelles (et de ce que l'on a vu à propos des threads JAVA).
• CRCW (Concurrent Read Concurrent Write): c'est un modèle étonnament puissant et assez peu réaliste, mais qu'il est intéressant de considérer d'un point de vue théorique. Plusieurs processeurs peuvent lire ou écrire en même temps sur la même case de la mémoire partagée. Il nous reste à définir ce qui se passe lorsque plusieurs processeurs écrivent au même moment; on fait généralement l'une des trois hypothèses suivantes:
  • mode consistant: tous les processeurs qui écrivent en même temps sur la même case écrivent la même valeur.
  • mode arbitraire: c'est la valeur du dernier processeur qui écrit qui est prise en compte.
  • mode fusion: une fonction associative (définie au niveau de la mémoire), est appliquée à toutes les écritures simultanées sur une case donnée. Ce peut être par exemple, une fonction maximum, un ou bit à bit etc.

4.2  Technique de saut de pointeur

for each processor i in parallel {
  y[i] = x[i]; 
}
while (exists object i s.t. next[i] not nil) {
  for each processor i in parallel {
    if (next[i] not nil) {
      y[next[i]] =_next[i] op_next[i](y[i],y[next[i]]);
      next[i] =_i next[next[i]];
    }
  }
}

• op_j pour préciser que l'opération op s'effectue sur le processeur j.
• =_j pour préciser que l'affectation est faite par le processeur j.

---

Figure 4.1: Technique du saut de pointeur.

---

y[i] =_i op_i(y[i],y[next[i]]);

y[next[i]] =_next[i] op_next[i](y[i],y[next[i]]);

for each processor i in parallel 
  A[i] = B[i];

for each processor i in parallel
  temp[i] = B[i];
for each processor i in parallel
  A[i] = temp[i];

d[i] = d[i]+d[next[i]];

temp[i] = d[next[i]];
d[i] = d[i]+temp[i];

public class SommePartielle extends Thread {

    int pos,i;
    int t[][];
    
    SommePartielle(int position,int tab[][]) {
      pos = position;
      t=tab;
    }

    public void run() {
      int i,j;
        
      for (i=1;i<=3;i++) {
        j = pos-Math.pow(2,i-1);
        if (j>=0) { 
          while (t[j][i-1]==0) {} ; // attendre que le resultat soit pret
          t[pos][i] = t[pos][i-1]+t[j][i-1] ; 
          } else {
        t[pos][i] = t[pos][i-1] ;
      };
    };
  }
}

import java.util.* ;

public class Exo3 {

    public static void main(String[] args) {
        int[][] tableau = new int[8][4];
        int i,j;
        Random r = new Random();
        
        for (i=0;i<8;i++) {
            tableau[i][0] =  r.nextInt(8)+1 ;
            for (j=1;j<4;j++) {
                tableau[i][j]=0;
            };
        };
        
        for (i=0;i<8;i++) {
            new SommePartielle(i,tableau).start() ;
        };
                
        for (i=0;i<8;i++) {
           while (tableau[i][3]==0) {} ;
        };
        
        for (i=0;i<4;i++) {
            System.out.print("\n");
            for (j=0;j<8;j++) {
                System.out.print(tableau[j][i]+" ");
            };
        };        
        System.out.print("\n");
    }
}

4.3  Circuit Eulerien

• int numero : numéro unique associé à chaque noeud,
• int profondeur : valeur à calculer,
• arbre_binaire pere : père du noeud courant de l'arbre,
• arbre_binaire fg,fd : fils gauche et droit du noeud courant dans l'arbre.

actif[0] = true; 
continue = true;
p = 0; /* p est la profondeur courante */

forall j in [1,n-1]
  actif[j] = false;

while (continue == true)
  forall j in [0,n-1] such that (actif[j] == true) {
    continue = false;
    prof[j] = p;
    actif[j] = false;
    if (fg[j] != nil) {
      actif[fg[j]] = true;
      continue = true; 
      p++; }
    if (fd[j] != nil) {
      actif[fd[j]] = true;
      continue = true; 
      p++; }

---

Figure 4.2: Un arbre binaire assez quelconque.

---

• successeur[3i] = 3fg[i] si fg[i] est différent de null et successeur[3i] = 3i+1 sinon.
• successeur[3i+1] = 3fd[i] si fd[i] est différent de null et successeur[3i+1] = 3i+2 sinon.
• successeur[3i+2] = 3pere[i]+2

4.4  Théorèmes de simulation

for each i from 1 to n in parallel 
  m[i] = TRUE;
for each i, j from 1 to n in parallel
  if (A[i] < A[j])
    m[i] = FALSE;
for each i from 1 to n in parallel
  if (m[i] == TRUE)
    max = A[i];

res = FALSE;
for each i in parallel {
  if (e == e[i])
    res = TRUE;

Théorème

---

Figure 4.3: Codage d'un algorithme CRCW sur une PRAM EREW

---

Théorème (Brent)

for (k=m-1; k>=0; k--) 
  for each j from 2^k to 2^(k+1)-1 in parallel
    A[j] = max(A[2j],A[2j+1]);

Proposition

4.5  Tris et réseaux de tris

---

Figure 4.4: Un comparateur.

---

---

Figure 4.5: Réseau de tri pair-impair pour n=8.

---

Chapter 5  Coordination de processus

5.1  Problème

---

public class Compte { private int valeur; Compte(int val) { valeur = val; } public int solde() { return valeur; } public void depot(int somme) { if (somme > 0) valeur+=somme; } public boolean retirer(int somme) throws InterruptedException { if (somme > 0) if (somme <= valeur) { Thread.currentThread().sleep(50); valeur -= somme; Thread.currentThread().sleep(50); return true; } return false; } }

Figure 5.1: Opérations simples sur un compte bancaire.

---

---

public class Banque implements Runnable { Compte nom; Banque(Compte n) { nom = n; } public void Liquide (int montant) throws InterruptedException { if (nom.retirer(montant)) { Thread.currentThread().sleep(50); Donne(montant); Thread.currentThread().sleep(50); } ImprimeRecu(); Thread.currentThread().sleep(50); } public void Donne(int montant) { System.out.println(Thread.currentThread(). getName()+": Voici vos " + montant + " euros."); } public void ImprimeRecu() { if (nom.solde() > 0) System.out.println(Thread.currentThread(). getName()+": Il vous reste " + nom.solde() + " euros."); else System.out.println(Thread.currentThread(). getName()+": Vous etes fauches!"); } public void run() { try { for (int i=1;i<10;i++) { Liquide(100*i); Thread.currentThread().sleep(100+10*i); } } catch (InterruptedException e) { return; } } public static void main(String[] args) { Compte Commun = new Compte(1000); Runnable Mari = new Banque(Commun); Runnable Femme = new Banque(Commun); Thread tMari = new Thread(Mari); Thread tFemme = new Thread(Femme); tMari.setName("Conseiller Mari"); tFemme.setName("Conseiller Femme"); tMari.start(); tFemme.start(); } }

Figure 5.2: Un automate bancaire.

---

% java Banque
Conseiller Mari: Voici vos 100 euros.
Conseiller Femme: Voici vos 100 euros.
Conseiller Mari: Il vous reste 800 euros.
Conseiller Femme: Il vous reste 800 euros.
Conseiller Mari: Voici vos 200 euros.
Conseiller Femme: Voici vos 200 euros.
Conseiller Femme: Il vous reste 400 euros.
Conseiller Mari: Il vous reste 400 euros.
Conseiller Mari: Voici vos 300 euros.
Conseiller Femme: Voici vos 300 euros.
Conseiller Femme: Vous etes fauches!
Conseiller Mari: Vous etes fauches! ...

• S est un ensemble d'états,
• i Î S est l'``état initial'',
• E est un ensemble d'étiquettes,
• Tran Í S × E × S est l'ensemble des transitions. On représente plus communément une transition (s,t,s') Î Tran par le graphe:
  s ®^t s'

• (x=expr;block,r) ®^x=expr (block,r[x® [ [ expr ] ](r)])
  où [ [ expr ] ] (r) dénote la valeur entière résultat de l'évaluation de l'expression expr dans l'environnement r (on ne donne pas les règles formelles évidentes qui donnent un sens précis à cela).
• (if t then b₁ else b₂; b₃,r) ®^then (b₁; b₃,r)
  si [ [ t ] ] (r) = vrai sinon
  (if t then b₁ else b₂; b₃,r) ®^else (b₂; b₃,r)
• (while t b₁; b₂,r) ®^while (b₁;while t b₁; b₂,r)
  si [ [ t ] ] (r) = vrai sinon
  (while t b₁; b₂,r) ®^while (b₂,r)

• A chaque P_j on associe par [ [ . ] ] défini plus haut un système de transition (S_j,i_j,E_j,Tran_j),
• On définit (S,i,E,Tran)=[ [ P₁ | ... | P_n ] ] par:
  • S=S₁ × ... × S_n,
  • i=(i₁,...,i_n),
  • E=E₁ È ... È E_n,

  • Tran=

    {

    (s1,...,sj,...,sn) ®tj (s1,...,sj',...,sn) où sj ®tj sj' Î Tranj

    }

• S=S₁ × ... × S_n × S_g, avec S_g=VP ® ZZ
• la sémantique de l'affectation d'une variable globale modifie S_g et non le S_i particulier du processus en question.

5.2  Une solution: synchronized

public synchronized boolean retirer(int somme)

% java Banque
Conseiller Mari: Voici vos 100 euros.
Conseiller Femme: Voici vos 100 euros.
Conseiller Mari: Il vous reste 800 euros.
Conseiller Femme: Il vous reste 800 euros.
Conseiller Mari: Voici vos 200 euros.
Conseiller Mari: Il vous reste 400 euros.
Conseiller Femme: Voici vos 200 euros.
Conseiller Femme: Il vous reste 400 euros.
Conseiller Mari: Voici vos 300 euros.
Conseiller Femme: Il vous reste 100 euros.
Conseiller Mari: Il vous reste 100 euros.
Conseiller Femme: Il vous reste 100 euros.
Conseiller Mari: Il vous reste 100 euros...

   synchronized(obj) {
      BLOCK }

5.3  Moniteurs

5.4  Sémaphores

5.4.1  Sémaphores binaires

---

public class Semaphore { int n; String name; public Semaphore(int max, String S) { n = max; name = S; } public synchronized void P() { if (n == 0) { try { wait(); } catch(InterruptedException ex) {}; } n--; System.out.println("P("+name+")"); } public synchronized void V() { n++; System.out.println("V("+name+")"); notify(); } }

Figure 5.3: Implémentation de sémaphores.

---

---

public class essaiPV extends Thread { static int x = 3; Semaphore u; public essaiPV(Semaphore s) { u = s; } public void run() { int y; // u.P(); try { Thread.currentThread().sleep(100); y = x; Thread.currentThread().sleep(100); y = y+1; Thread.currentThread().sleep(100); x = y; Thread.currentThread().sleep(100); } catch (InterruptedException e) {}; System.out.println(Thread.currentThread(). getName()+": x="+x); // u.V(); } public static void main(String[] args) { Semaphore X = new Semaphore(1,"X"); new essaiPV(X).start(); new essaiPV(X).start(); } }

Figure 5.4:

---

% java essaiPV
Thread-2: x=4
Thread-3: x=4

% java essaiPV
P(X)
Thread-2: x=4
V(X)
P(X)
Thread-3: x=5
V(X)

5.4.2  Un peu de sémantique

• On rajoute dans l'ensemble d'états S du système de transitions une composante nouvelle qui est une fonction k: VARIABLE ® {0,1}. Donc S=(S₁,...,S_n,S_g,k). Cette fonction k représente le fait qu'une variable est verrouillée par un processus ou non,
• i=(P₁,...,P_n,k₀) où k₀ est la fonction qui donne uniformément 1 (aucune variable n'est encore verrouillée),
• E contient maintenant les nouvelles actions Px et Vx pour toutes les variables x du programme,
• On a de nouvelles transitions dans Tran de la forme:
  (b₁,...,Px;b_j,...,b_n,k) ®^Px (b₁,...,b_j,...,b_n,k')
  si k(x)=1; et alors k'(y)=k(y) pour tout y ¹ x et k'(x)=0, et,
  (b₁,...,Vx;b_j,...,b_n,k) ®^Vx (b₁,...,b_j,...,b_n,k')
  avec k'(y)=k(y) pour tout y ¹ x et k'(x)=1.

A=Pa;Pb;Va;Vb
B=Pb;Va;Vb;Va

5.4.3  Un complément sur la JVM

• les actions qu'un thread peut exécuter sont:
  • use transfère le contenu de la copie locale d'une variable à la machine exécutant le thread.
  • assign transfère une valeur de la machine exécutant le thread à la copie locale d'une variable de ce même thread.
  • load affecte une valeur venant de la mémoire principale (après un read, voir plus loin) à la copie locale à un thread d'une variable.
  • store transfère le contenu de la copie locale à un thread d'une variable à la mémoire principale (qui va ainsi pouvoir faire un write, voir plus loin).
  • lock réclame un verrou associé à une variable à la mémoire principale.
  • unlock libère un verrou associé à une variable.
• les actions que la mémoire principale (la JVM) peut exécuter sont:
  • read transfère le contenu d'une variable de la mémoire principale vers la mémoire locale d'un thread (qui pourra ensuite faire un load).
  • write affecte une valeur transmise par la mémoire locale d'un thread (par store) d'une variable dans la mémoire principale.

---

class Essai1 extends Thread { public Essai1(Exemple1 e) { E = e; } public void run() { E.F1(); } private Exemple1 E; } class Essai2 extends Thread { public Essai2(Exemple1 e) { E = e; } public void run() { E.G1(); } private Exemple1 E; } class Lance { public static void main(String args[]) { Exemple1 e = new Exemple1(); Essai1 T1 = new Essai1(e); Essai2 T2 = new Essai2(e); T1.start(); T2.start(); System.out.println("From Lance a="+e.a+" b="+e.b); } }

Figure 5.5: Classe Essai1.

---

---

class Exemple1 { int a = 1; int b = 2; void F1() { a = b; } void G1() { b = a; } }

Figure 5.6: Classe Exemple1.

---

---

class Exemple2 { int a = 1; int b = 2; synchronized void F2() { a = b; } synchronized void G2() { b = a; } }

Figure 5.7: Classe Exemple2

---

> java Lance
a=2 b=2

> java Lance
a=1 b=1

> java Lance
a=2 b=1

5.4.4  Quelques grands classiques

---

public class Phil extends Thread { Semaphore LeftFork; Semaphore RightFork; public Phil(Semaphore l, Semaphore r) { LeftFork = l; RightFork = r; } public void run() { try { Thread.currentThread().sleep(100); LeftFork.P(); Thread.currentThread().sleep(100); RightFork.P(); Thread.currentThread().sleep(100); LeftFork.V(); Thread.currentThread().sleep(100); RightFork.V(); Thread.currentThread().sleep(100); } catch (InterruptedException e) {}; } } public class Dining { public static void main(String[] args) { Semaphore a = new Semaphore(1,"a"); Semaphore b = new Semaphore(1,"b"); Semaphore c = new Semaphore(1,"c"); Phil Phil1 = new Phil(a,b); Phil Phil2 = new Phil(b,c); Phil Phil3 = new Phil(c,a); Phil1.setName("Kant"); Phil2.setName("Heidegger"); Phil3.setName("Spinoza"); Phil1.start(); Phil2.start(); Phil3.start(); } }

Figure 5.8: Implémentation des trois philosophes.

---

% java Dining
Kant: P(a)
Heidegger: P(b)
Spinoza: P(c)
^C

A=Pa;Pb;Va;Vb
B=Pb;Pc;Vb;Vc
C=Pc;Pa;Vc;Va

---

Figure 5.9: Le graphe de requêtes pour n philosophes.

---

---

Figure 5.10: Graphe d'avancement des 3 philosophes

Figure 5.11: Point mort des 3 philosophes

---

A=Px;Py;Pz;Vx;Pw;Vz;Vy;Vw
B=Pu;Pv;Px;Vu;Pz;Vv;Vx;Vz
C=Py;Pw;Vy;Pu;Vw;Pv;Vu;Vv

---

Figure 5.12: Graphe de requêtes pour l'exemple Lipsky/Papadimitriou.

---

---

Figure 5.13: Graphe de processus pour le terme de Lipsky et Papadimitriou.

---

P1=Pa2;Pa1;Va2;Va1
P2=Pa2;Pa3;Va2;Va3
...
P2k=Pa2k;Pa(2k+1);Va2k;Va(2k+1)
P(2k+1)=Pa(2k+2);Pa(2k+1);Va(2k+2);Va(2k+1)

---

Figure 5.14: Le nouveau graphe de requêtes.

---

5.4.5  Sémaphores à compteur

---

public class essaiPVsup extends Thread { static int x = 3; Semaphore u; public essaiPVsup(Semaphore s) { u = s; } public void run() { int y; u.P(); try { Thread.currentThread().sleep(100); y = x; Thread.currentThread().sleep(100); y = y+1; Thread.currentThread().sleep(100); x = y; Thread.currentThread().sleep(100); } catch (InterruptedException e) {}; System.out.println(Thread.currentThread(). getName()+": x="+x); u.V(); } public static void main(String[] args) { Semaphore X = new Semaphore(2,"X"); new essaiPVsup(X).start(); new essaiPVsup(X).start(); } }

Figure 5.15: Utilisation de sémaphores à compteur.

---

% java essaiPVsup
Thread-2: P(X)
Thread-3: P(X)
Thread-2: x=4
Thread-2: V(X)
Thread-3: x=4
Thread-3: V(X)

---

public class essaiPVsup2 extends Thread { static String[] x = {null,null}; Semaphore u; public essaiPVsup2(Semaphore s) { u = s; } public void push(String s) { x[1] = x[0]; x[0] = s; } public String pop() { String s = x[0]; x[0] = x[1]; x[1] = null; return s; } public void produce() { push(Thread.currentThread().getName()); System.out.println(Thread.currentThread(). getName()+": push"); } public void consume() { pop(); System.out.println(Thread.currentThread(). getName()+": pop"); } public void run() { try { u.P(); produce(); Thread.currentThread().sleep(100); consume(); Thread.currentThread().sleep(100); u.V(); } catch(InterruptedException e) {}; } public static void main(String[] args) { Semaphore X = new Semaphore(2,"X"); new essaiPVsup2(X).start(); new essaiPVsup2(X).start(); new essaiPVsup2(X).start(); } }

Figure 5.16: Producteur/consommateur, avec des sémaphores à compteur.

---

% java essaiPVsup2
Thread-2: P(X)
Thread-2: push
Thread-3: P(X)
Thread-3: push
Thread-2: pop
Thread-3: pop
Thread-2: V(X)
Thread-3: V(X)
Thread-4: P(X)
Thread-4: push
Thread-4: pop
Thread-4: V(X)

5.5  Barrières de synchronisation

---

public class Barrier { private int threads2Wait4; private InterruptedException iex; public Barrier(int nThreads) { threads2Wait4 = nThreads; } public synchronized int waitForRest() throws InterruptedException { int threadNum = --threads2Wait4; if (iex != null) throw iex; if (threads2Wait4 <= 0) { notifyAll(); return threadNum; } while (threads2Wait4 > 0) { if (iex != null) throw iex; try { wait(); } catch(InterruptedException ex) { iex = ex; notifyAll(); } } return threadNum; } public synchronized void freeAll() { iex = new InterruptedException("Barrier Released by freeAll"); notifyAll(); } }

Figure 5.17: Implémentation d'une barrière de synchronisation en JAVA.

---

---

public class ProcessIt implements Runnable { String[] is; Barrier bpStart, bp1, bp2, bpEnd; public ProcessIt(String[] sources) { is = sources; bpStart = new Barrier(sources.length); bp1 = new Barrier(sources.length); bp2 = new Barrier(sources.length); bpEnd = new Barrier(sources.length); for (int i=0;i<is.length; i++) { (new Thread(this)).start(); } } public void run() { try { int i = bpStart.waitForRest(); doPhaseOne(is[i]); bp1.waitForRest(); doPhaseTwo(is[i]); bp2.waitForRest(); doPhaseThree(is[i]); bpEnd.waitForRest(); } catch(InterruptedException ex) {}; } public void doPhaseOne(String ps) { } public void doPhaseTwo(String ps) { } public void doPhaseThree(String ps) { } static public void main(String[] args) { ProcessIt pi = new ProcessIt(args); } }

Figure 5.18: Essai des barrières de synchronisation.

---

5.6  Un exemple d'ordonnancement: séquentialisation

---

public class Ticket { String nom;} public class Requete extends Thread { Ticket Aller; Ticket Aller2; Semaphore u; Semaphore v; public Requete(Ticket t, Ticket s, Semaphore x, Semaphore y) { Aller = t; Aller2 = s; u = x; v = y; } public void run() { try { u.P(); Thread.currentThread().sleep(100); if (Aller.nom == null) Aller.nom = Thread.currentThread(). getName(); Thread.currentThread().sleep(100); u.V(); } catch (InterruptedException e) {}; try { v.P(); Thread.currentThread().sleep(100); if (Aller2.nom == null) Aller2.nom = Thread.currentThread(). getName(); Thread.currentThread().sleep(100); v.V(); } catch (InterruptedException e) {}; } } public class Serial { public static void main(String[] args) { Semaphore a = new Semaphore(1,"a"); Semaphore b = new Semaphore(1,"b"); Ticket s = new Ticket(); Ticket t = new Ticket(); Requete Bill = new Requete(s,t,a,b); Requete Tom = new Requete(t,s,b,a); Bill.setName("Bill"); Tom.setName("Tom"); Bill.start(); Tom.start(); try { Tom.join(); Bill.join(); } catch(InterruptedException e) {}; System.out.println("Le premier billet Paris->New York est au nom de: "+s.nom); System.out.println("Le deuxieme billet New York->Paris est au nom de: "+t.nom); } }

Figure 5.19: Base de donnée de billets d'avions.

---

% java Serial
Bill: P(a)
Tom: P(b)
Bill: V(a)
Tom: V(b)
Bill: P(b)
Tom: P(a)
Bill: V(b)
Tom: V(a)
Le premier billet Paris->New York est au nom de: Bill
Le deuxieme billet Paris->New York est au nom de: Tom

---

public void run() { try { u.P(); v.P(); Thread.currentThread().sleep(100); if (Aller.nom == null) Aller.nom = Thread.currentThread(). getName(); Thread.currentThread().sleep(100); Thread.currentThread().sleep(100); if (Aller2.nom == null) Aller2.nom = Thread.currentThread(). getName(); Thread.currentThread().sleep(100); u.V(); v.V(); } catch (InterruptedException e) {}; }

Figure 5.20: Une politique d'ordonnancement séquentialisable pour la base de données de billets d'avion.

---

% java Serial2
Bill: P(a)
Bill: P(b)
Bill: V(a)
Bill: V(b)
Tom: P(b)
Tom: P(a)
Tom: V(b)
Tom: V(a)
Le premier billet Paris->New York est au nom de: Bill
Le deuxieme billet Paris->New York est au nom de: Bill

% java Serial2
Bill: P(a)
Tom: P(b)
^C

Chapter 6  Algorithmes d'exclusion mutuelle (mémoire partagée)

6.1  Peut-on se passer de synchronized?

• (A) si un thread se trouve en section critique, tout autre thread doit être en train d'exécuter une section non-critique.
• (B) supposons qu'un groupe de threads I exécute du code dans une section non-critique, et ne requiert pas encore d'accéder à une section critique. Supposons maintenant que tous les autres processus (groupe J) requièrent l'accès à une section critique, mais qu'ils n'en ont pas encore obtenu la permission. Alors le processus qui doit rentrer en section critique doit appartenir à J, et cette permission ne doit pas pouvoir être reportée indéfiniment.
• (C) un thread qui demande à entrer en section critique obtiendra toujours d'y rentrer au bout d'un temps fini (c'est une propriété d'équité qui permet d'éviter la famine d'un ou plusieurs processus).

public class CS1 extends Thread {
    Thread tour = null;
    ...
}

public void AttendtonTour()

public void RendlaMain()

    public void run() {
        while(true) {
            AttendtonTour();
            System.out.println("C'est le tour de "+
                       Thread.currentThread().getName());
            RendlaMain();
        }
    }

---

public class CS1 extends Thread { volatile Thread tour = null; public void AttendtonTour() { while (tour != Thread.currentThread()) { if (tour == null) tour = Thread.currentThread(); try { Thread.sleep(100); } catch (Exception e) {} } } public void RendlaMain() { if (tour == Thread.currentThread()) tour = null; } public void run() { while(true) { AttendtonTour(); System.out.println("C'est le tour de "+ Thread.currentThread().getName()); RendlaMain(); } } public static void main(String[] args) { Thread Un = new CS1(); Thread Deux = new CS1(); Un.setName("UN"); Deux.setName("DEUX"); Un.start(); Deux.start(); } }

Figure 6.1: Une tentative d'algorithme d'exclusion mutuelle.

---

6.2  Premiers algorithmes?

---

public class Algorithme1 extends ExclusionMutuelle { public Algorithme1() { turn = 0; } public void Pmutex(int t) { while (turn != t) Thread.yield(); } public void Vmutex(int t) { turn = 1-t; } private volatile int turn; }

Figure 6.2: Une autre tentative d'algorithme d'exclusion mutuelle.

---

---

public abstract class ExclusionMutuelle { public static void Critique() { try { Thread.sleep((int) (Math.random()*3000)); } catch (InterruptedException e) { } } public static void nonCritique() { try { Thread.sleep((int) (Math.random()*3000)); } catch (InterruptedException e) { } } public abstract void Pmutex(int t); public abstract void Vmutex(int t); }

Figure 6.3: Simulation des sections critiques et non-critiques.

---

---

public class Tache extends Thread { public Tache(String n,int i,ExclusionMutuelle s) { name = n; id = i; section = s; } public void run() { while (true) { section.Pmutex(id); System.out.println(name+" est en section critique"); ExclusionMutuelle.Critique(); section.Vmutex(id); System.out.println(name+" est sorti de la section critique"); ExclusionMutuelle.nonCritique(); } } private String name; private int id; private ExclusionMutuelle section; }

Figure 6.4: Thread appelant les algorithmes d'exclusion mutuelle.

---

---

public class Test { public static void main(String args[]) { ExclusionMutuelle alg = new Algorithme1(); Tache zero = new Tache("Tache 0",0,alg); Tache un = new Tache("Tache 1",1,alg); zero.start(); un.start(); } }

Figure 6.5: Lancement de deux tâches en parallèle.

---

---

public class Algorithme2 extends ExclusionMutuelle { public Algorithme2() { flag[0] = false; flag[1] = false; } public void Pmutex(int t) { int other; other = 1-t; flag[t] = INIT; while (flag[other] == true) Thread.yield(); } public void Vmutex(int t) { flag[t] = false; } private volatile boolean[] flag = new boolean[2]; }

Figure 6.6: Deuxième tentative d'implémentation d'un algorithme d'exclusion mutuelle.

---

---

public class Algorithme4 extends ExclusionMutuelle { public Algorithme4() { flag[0] = false; flag[1] = false; } public void Pmutex(int t) { int other; other = 1-t; flag[t] = true; while (flag[other] == true) { flag[t] = false; while (flag[other]) Thread.yield(); flag[t] = true; } public void Vmutex(int t) { flag[t] = false; } private volatile boolean[] flag = new boolean[2]; }

Figure 6.7: Autre tentative d'algorithme d'exclusion mutuelle.

---

6.3  Algorithme de Dekker

---

public class Dekker extends ExclusionMutuelle { public Dekker() { flag[0] = false; flag[1] = false; turn = 0; } public void Pmutex(int t) { int other; other = 1-t; flag[t] = true; while (flag[other] == true) { if (turn == other) { flag[t] = false; while (turn == other) Thread.yield(); flag[t] = true; } } } public void Vmutex(int t) { turn = 1-t; flag[t] = false; } private volatile int turn; private volatile boolean[] flag = new boolean[2]; }

Figure 6.8: Algorithme de Dekker.

---

---

public class Hyman extends ExclusionMutuelle { public Hyman() { flag[0] = false; flag[1] = false; turn = 0; } public void Pmutex(int t) { int other = 1-t; flag[t]= true; while (turn==other) { while (flag[other]) Thread.yield(); turn = t; } } public void Vmutex(int t) { flag[t] = false; } private volatile int turn; private volatile boolean[] flag = new boolean[2]; }

Figure 6.9: Algorithme faux d'Hyman.

---

6.4  Algorithme de Peterson

---

public class Peterson extends ExclusionMutuelle { public Peterson() { flag[0] = false; flag[1] = false; turn = 0; } public void Pmutex(int t) { int other; other = 1-t; flag[t] = true; turn = t; while (flag[other] && (turn == t)) Thread.yield(); } public void Vmutex(int t) { flag[t] = false; } private volatile int turn; private volatile boolean[] flag = new boolean[2]; }

Figure 6.10: Algorithme de Peterson.

---

• { p[x¬ u] } x=u { p }

• { p1 }

  (

  if B then {p2} I1 {q2} else {p3}I2 {q3}

  )

  { q1 }

  si on a,

  p1 Ù B Þ p2

  p1 Ù ¬ B Þ p3

  {p2} I1 {q2}

  {p3}I2{q3}

  q2 Þ q1

  q3 Þ q1

• {p1} while B

  {

  {p2} C {q2}

  }

  {q1}

  si on a,

  p1 Ù B Þ p2

  p1 Ù ¬ B Þ q1

  {p2} C {q2}

  q2 Ù B Þ p2

  q2 Ù ¬ B Þ q1

{ x=x0 et y=y0 }
q = 0;
while (x >= y) {
  {x=x0-qy0 et y=y0}
  q = q+1;
  {x=x0-(q-1)y0 et y=y0}
  x = x-y;
  {x=x0-qy0 et y=y0}
}
{x=x0-qy0 et x<y et y=y0}

{ x=x0 et y=y0 et c=0}
q = 0;
{ x=x0 et y=y0 et c=1}
while (x >= y) {
  {x=x0-qy0 et y=y0 et c=2}
  q = q+1;
  {x=x0-(q-1)y0 et y=y0 et c=3}
  x = x-y;
  {x=x0-qy0 et y=y0 et c=4}
}
{x=x0-qy0 et x<y et y=y0 et c=5}

---

{ non flag[0] } flag[0]=true; after[0]=false; { flag[0] et non after[0] } turn=0; after[0]=true; { inv: flag[0] et after[0] et I } while (flag[1] && (turn==0)) { flag[0] et after[0] et I } Thread.yield(); { flag[0] et after[0] et (flag[1] et (non(after[1]) ou turn=1)) } [ Section Critique CS1] { flag[0] } flag[0]=false;

Figure 6.11: Assertions pour la preuve de l'algorithme de Peterson.

---

---

{ non flag[1] } flag[1]=true; after[1]=false; { flag[1] et non after[1] } turn=1; after[1]=true; { inv: flag[1] et after[1] et I } while (flag[0] && (turn==0)) do { flag[1] et after[1] et I } Thread.yield(); { flag[1] et after[1] et (flag[0] et (non(after[0]) ou turn=0)) } [ Section Critique CS2] { flag[1] } flag[1]=false;

Figure 6.12: Assertions pour la preuve de l'algorithme de Peterson.

---

pre(CS1) = flag[0] et after[0] et (flag[1] et (non(after[1]) 
                                           ou (turn=1)))

flag[1]=true; after[1]=false;

turn=1; after[1]=true;

{ pre(CS1) } flag[1]=true; after[1]=false; { pre(CS1) }

{ pre(CS1) } turn=1; after[1]=true; { pre(CS1) }

pre(CS1) et pre(CS2) implique (turn=0 et turn=1)

non(pre(CS1) et pre(CS2))

---

public class PetersonN extends ExclusionMutuelle { public PetersonN(int nb) { int i; nproc = nb; turn = new int[nproc-1]; flag = new int[nproc]; for (i=0; i < nproc; i++) { flag[i] = -1; } } public void Pmutex(int t) { int j, k; boolean cond; for (j=0; j < nproc-1; j++) { flag[t] = j; turn[j] = t; cond = true; for (k=0; (k < nproc) && (k != t); k++) cond = cond || (flag[k] >= j); while (cond && (turn[j] == t)) Thread.yield(); } } public void Vmutex(int t) { flag[t] = -1; } private volatile int[] turn; private int nproc; private volatile int[] flag; }

Figure 6.13: Algorithme de Peterson pour plus de deux tâches.

---

---

public class TestN { public final static int nb = 5; public static void main(String args[]) { int i; Tache[] liste; liste = new Tache[nb]; ExclusionMutuelle alg = new PetersonN(nb); for (i=0; i < nb; i++) { liste[i] = new Tache("Tache "+i,i,alg); liste[i].start(); } } }

Figure 6.14: Classe pour tester des algorithmes d'exclusion mutuelle pour plus de deux processus.

---

Chapter 7  Problèmes d'ordonnancement

7.1  Introduction

7.2  Nids de boucles

for (i=1;i<=N;i++) {
  for (j=i;j<=N+1;j++)
    for (k=j-i;k<=N;k++) {
      S1;
      S2;
    }
  for (r=1;r<=N;r++)
    S3;
}

7.3  Dépendance des données

7.3.1  Définitions

• Dépendance de flot de S(I) vers T(J): si un emplacement mémoire commun est en écriture pour S(I) et en lecture pour T(J)
• Dépendance anti de S(I) vers T(J): si un emplacement mémoire commun est en lecture pour S(I) et en écriture pour T(J)
• Dépendance de sortie de S(I) vers T(J): si un emplacement mémoire commun est en écriture pour S(I) et en écriture pour T(J)

for (i=1;i<=N;i++)
  for (j=1;j<=N;j++)
    a(i+j) = a(i+j-1)+1;

---

Figure 7.1: Dépendances flot, anti et de sortie.

---

7.3.2  Calcul des dépendances

• f(I)=g(J) Û i'+j'=i+j-1
• S(i',j') <_seq S(i,j) Û ( (i'£ i-1) ou (i=i' et j'£ j-1) )

7.3.3  Approximation des dépendances

• Sommets: instances S_i(I), 1 £ i £ s et I Î D_Si
• Arcs: S(I) ® T(J) pour chaque dépendance

• lecture a(i+j-1)-écriture a(i+j): ensemble de distance {(1,-2)}
• écriture a(i+j)-lecture a(i+j-1): ensemble de distance {(1,0),(0,1)}
• écriture a(i+j)-écriture a(i+j): ensemble de distance {(1,-1)}

• Sommets: instructions S_i (1 £ i £ s)
• Arcs: e: S ® T si il existe au moins un arc S(I) ® T(J) dans le GDE
• Etiquette: w(e) décrivant un sous-ensemble D_e de ZZ^n_S,T

• l(e)=¥ si S(I)® T(J) avec J - I=0
• l(e) Î [1,n_S,T] si S(I) ® T(J), et la première composante non nulle de J-I est la l(e)^ieme composante

for (i=2;i<=N;i++) {
  S1: s(i) = 0;
  for (j=1;j<i-1;j++) 
    S2: s(i) = s(i)+a(j,i)*b(j);
S3:  b(i) = b(i)-s(i);
}

---

Figure 7.2: GDRN

---

• on note z+ pour une composante si toutes les distances sur cette composante ont au moins la valeur z
• on note z- pour une composante si toutes les distances sur cette composante ont au plus la valeur z
• on note + à la place de 1+, - à la place de -1-
• on note * si la composante peut prendre n'importe quelle valeur
• on note z si la composante a toujours la valeur z

---

Figure 7.3: GRDV

---

7.4  Transformations de boucles

• Allen et Kennedy (basé sur le GDRN) : effectue des distributions de boucles
• Lamport : transformations unimodulaires (basé sur le GDRV), c'est à dire, torsion, inversion et permutation de boucles

7.4.1  Distribution de boucles

for (i=...) {
  S1;
  S2;
}

for (i=...)
  S1;
for (i=...)
  S2;

for (i=...)
  S2;
for (i=...)
  S1;

7.4.2  Fusion de boucles

forall (i=1;i<=N;i++)
 D[i]=E[i]+F[i];
forall (j=1;j<=N;j++)
 E[j]=D[j]*F[j];

forall (i=1;i<=N;i++)
 {
  D[i]=E[i]+F[i];
  E[i]=D[i]*F[i];
 }

7.4.3  Composition de boucles

forall (j=1;j<=N;j++)
 forall (k=1;k<=N;k++)
  ...

forall (i=1;i<=N*N;i++)
 ...

7.4.4  Echange de boucles

for (i=1;i<=N;i++)
 for (j=2;j<=M;j++)
  A[i,j]=A[i,j-1]+1;

for (j=2;j<=M;j++)
 A[1:N,j]=A[1:N,j-1]+1;

7.4.5  Déroulement de boucle

for (i=1;i<=100;i++)
 A[i]=B[i+2]*C[i-1];

for (i=1;i<=99;i=i+2)
 {
  A[i]=B[i+2]*C[i-1];
  A[i+1]=B[i+3]*C[i];
 }

7.4.6  Rotation de boucle [skewing]

for (i=1;i<=N;i++)
 for (j=1;j<=N;j++)
  a[i,j]=(a[i-1,j]+a[i,j-1])/2;

for (k=2;k<=N;k++)
  forall (l=2-k;l<=k-2;l+=2)
    a[(k-l)/2][(k+l)/2] = a[(k-l)/2-1][(k+l)/2]+a[(k-l)/2][(k+l)/2-1];
for (k=1;k<=N;k++)
  forall (l=k-N;l<=N-k;l+=2)
    a[(k-l)/2][(k+l)/2] = a[(k-l)/2-1][(k+l)/2]+a[(k-l)/2][(k+l)/2-1];

7.4.7  Exemple de parallélisation de code

x[n]=b[n]/U[n,n];
for (i=n-1;i>=1;i--)
{  
x[i]=0;
for (j=i+1;j<=n;j++)
     L: x[i]=x[i]+U[i,j]*x[j];
     x[i]=(b[i]-x[i])/U[i,i];
     }

---

Figure 7.4: Graphe de dépendances de la remontée LU

---

H': forall (i=1;i<=n-1;i++)
       x[i]=b[i];
T': x[n]=b[n]/U[n,n];
H:  for (t=1;t<=n-1;t++)
     forall (i=1;i<=n-t;i++)
      L: x[i]=x[i]-x[n-t+1]*U[i],n-t+1];
     T: x[n-t]=x[n-t]/U[n-t,n-t];

7.5  Algorithme d'Allen et Kennedy

• Commencer avec k=1
• Supprimer dans le GDRN G toutes les arêtes de niveau inférieur à k
• Calculer les composantes fortement connexes (CFC) de G
• Pour tout CFC C dans l'ordre topologique:
  • Si C est réduit à une seule instruction S sans arête, alors générer des boucles parallèles dans toutes les dimensions restantes (i.e. niveaux k à n_S) et générer le code pour S
  • Sinon, l=l_min(C), et générer des boucles parallèles du niveau k au niveau l-1, et une boucle séquentielle pour le niveau l. Puis reboucler l'algorithme avec C et k=l+1

for (i=1;i<=N;i++) 
  for (j=1;j<=N;i++) {
    S1: a(i+1,j+1) = a(i+1,j)+b(i,j+2);
    S2: b(i+1,j) = a(i+1,j-1)+b(i,j-1);
    S3: a(i,j+2) = b(i+1,j+1)-1;
  }

• Flot S1 ® S1, variable a, distance (0,1),
• Flot S1 ® S2, variable a, distance (0,2),
• Flot S2 ® S1, variable b, distance (1,-2),
• Flot S2 ® S2, variable b, distance (1,1),
• Anti S1 ® S3, variable a, distance (1,-2),
• Anti S2 ® S3, variable a, distance (1,-3),
• Anti S3 ® S2, variable b, distance (0,1),
• Sortie S1 ® S3, variable a, distance (1,-1).

---

Figure 7.5: GDRN

---

---

Figure 7.6: GDRN

---

for (i=1;i<=N;i++) {
  for (j=1;j<=N;j++) 
    S1: a(i+1,j+1) = a(i+1,j)+b(i,j+2);
  forall (j=1;j<=N;j++)
    S3: a(i,j+2) = b(i+1,j+1)-1;
  forall (j=1;j<=N;j++)
    S2: b(i+1,j) = a(i+1,j-1)+b(i,j-1);
}

Chapter 8  Communications et routage

8.1  Généralités

8.2  Routage

---

Figure 8.1: Comparaison CC, WH et SF

---

8.3  Algorithmique sur anneau de processeurs

8.3.1  Hypothèses

---

Figure 8.2: Architecture en anneau

---

8.3.2  Problème élémentaire: la diffusion

broadcast(k,adr,L) { // emetteur initial=k
  q = my_num();
  p = tot_proc_num();
  if (q == k) 
    (1) send(adr,L);       
  else
    if (q == k-1 mod p)
      (2) receive(adr,L);  
    else {
      (3) receive(adr,L);  
      (4) send(adr,L);      
    } 
}

---

Figure 8.3: Exécution de la diffusion sur un anneau au temps 0.

---

---

Figure 8.4: Exécution de la diffusion sur un anneau au temps b+Lt.

---

---

Figure 8.5: Exécution de la diffusion sur un anneau au temps i(b+Lt) (i<p-1).

---

---

Figure 8.6: Exécution de la diffusion sur un anneau au temps (p-1)(b+Lt).

---

8.3.3  Diffusion personnalisée

scatter(k,adr,L) {
  q = my_num();
  p = tot_proc_num();
  if (q == k) {
    adr = adr[k];
    for (i=1;i<p;i=i+1)
      send(adr[k-i mod p],L); }
  else 
    (1) receive(adr,L);
  for (i=1;i<k-q mod p;i = i+1) {
    (2) send(adr,L); 
    (3) receive(temp,L);
    adr = temp; } }

---

Figure 8.7: Exécution de la diffusion personnalisée au temps 0.

---

---

Figure 8.8: Exécution de la diffusion personnalisée au temps b+Lt.

---

---

Figure 8.9: Exécution de la diffusion personnalisée au temps i(b+Lt).

---

---

Figure 8.10: Exécution de la diffusion personnalisée au temps (p-1)(b+Lt).

---

8.3.4  Echange total

all-to-all(my_adr,adr,L) {
  q = my_num();
  p = tot_proc_num();
  adr[q] == my_adr;
  for (i=1;i<p;i++) {
    send(adr[q-i+1 mod p],L);
    receive(adr[q-i mod p],L);
  }
}

8.3.5  Diffusion pipelinée

broadcast(k,adr,L) {
  q = my_num();
  p = tot_proc_num();
  if (q == k)
    for (i=1;i<=r;i++) send(adr[i],L/r);
  else
    if (q == k-1 mod p)
      for (i=1;i<=r;i++) receive(adr[i],L/r);
    else {
      receive(adr[1],L/r);
      for (i=1;i<r;i++) {
        send(adr[i],L/r);
        receive(adr[i+1],L/r); } } }

8.4  Election dans un anneau bidirectionnel

• Les n processeurs sont numérotés de P₀ jusqu'à P_n-1. Par abus de notation, on ne décrira pas les indices des processeurs modulo n. Ainsi, par exemple, P_n est identifié à P₀.
• Chaque processeur P_i peut envoyer un message send(adr,L,sens) dont le contenu se trouve dans sa mémoire locale à l'adresse adr, et consiste en L entiers. La nouveauté est que P_i peut envoyer vers son voisin P_i+1, en faisant sens=+, mais aussi vers P_i-1, en faisant sens=-.
• De même, la réception s'écrira maintenant recv(adr,L,sens). Un recv(adr,L,+) sur P_i+1 réceptionnera le message émis par P_i, qui aura fait send(adr,L,+) (et de façon similaire pour le -).
• On va maintenant supposer que les processus ne connaissent pas leur indice, et donc pas ceux de leurs voisins non plus. Le processeur P_i n'a au départ dans sa mémoire locale qu'un entier pid_i représentant son identificateur, et un autre entier leader initialement à zéro. Chaque pid_i est unique, c'est-à-dire que pid_i=pid_j implique i=j. Le but de l'algorithme d'élection est qu'un seul processus termine avec leader=1.
• On prend une hypothèse d'exécution synchrone: tous les codes seront écrits en mode SPMD, c'est-à-dire que le même code sera exécuté par tous les processeurs, et tous les send (respectivement recv) seront exécutés exactement au même moment, que l'on appellera étape: pour simplifier, on ne comptera que le nombre de recv. Un processeur est à l'étape k s'il a effectué exactement k recv. Cela implique donc que ni les send ni les recv ne sont bloquants, par contre, si on n'a envoyé aucun message à un processus P_i, alors recv fait sur P_i renverra le booléen faux (false), sinon, il renvoie le booléen vrai (true).

8.4.1  Algorithme de Le Lann, Chang et Roberts (LCR)

LCR() {
  send(pid,1,+);
  while (recv(newpid,1,+)) {
    if (newpid==pid)
      leader = 1;
    else if (newpid>pid)
           send(newpid,1,+);
  }
}

8.4.2  Algorithme de Hirschberg et Sinclair (HS)

• Chaque processeur P_i opère par phases, que l'on numérote à partir de 0.
• A chaque phase l, le processeur P_i envoie des tokens contenant son identificateur dans les deux sens possibles, sur l'anneau.
• Ceux-ci vont parcourir une distance (nombre de noeuds traversés sur l'anneau) de 2^l au maximum (sous-phase d'envoi), avant d'essayer de revenir à leur emetteur P_i (sous-phase de retour).
• Si les deux tokens reviennent, P_i continue avec la phase l+1.
• Quand l'identificateur pid_i, émis par P_i, est dans la sous-phase d'envoi, et est réceptionné par P_j, alors,
  • si pid_i < pid_j alors P_j ne fait rien,
  • si pid_i > pid_j alors P_j continue à renvoyer (dans la sous-phase envoi ou retour, selon la distance déjà effectuée par le message pid_i) le token contenant pid_i,
  • si pid_i = pid_j alors P_j devient leader.
• Dans la sous-phase retour, tous les processeurs relaient les tokens normalement.

• les tokens sont représentés par une classe JAVA token contenant un constructeur token(int phase, int message) (phase est le numéro de phase à la création du token); on supposera qu'un token est de taille L donnée,
• token incr(token x) incrémente la distance parcourue par le token x,
• boolean retour(token tok) renvoie true si le message encapsulé dans tok a fini la sous-phase envoi, false sinon (par rapport au numéro de phase encapsulé),
• int valeur(token x) renvoie le message (entier) encapsulé par le token x.

HS() {
  boolean leader, continuephase;
  int l;
  token plus, moins;
  l = 0;
  leader = false;
  
  continuephase = true;

  while (continuephase) {
    send(token(l,pid),L,+);
    send(token(l,pid),L,-);
    continuephase = false;

    while () {
      if (recv(plus,L,+)) {
        if (not retour(plus)) {
          if (valeur(plus) > pid) {
            plus = incr(plus);
            if (retour(plus))
              send(plus,L,-);
            else
              send(plus,L,+);
          }
          else if (valeur(plus) == pid) {
                 leader = true;
                 System.exit(0);
               }
        }
       else
         if (valeur(plus) == pid) {
           l = l+1;
           continuephase = true;
         }
         else 
           send(incr(plus),L,-);

      if (recv(moins,L,-)) {
        if (not retour(moins)) {
          if (valeur(moins) > pid) {
            plus = incr(moins);
            if (retour(moins))
              send(moins,L,+);
            else
              send(moins,L,-);
          }
          else if (valeur(moins) == pid) {
                 leader = true;
                 System.exit(0);
               }
        }
       else
         if (valeur(moins) == pid) {
           l = l+1;
           continuephase = true;
         }
         else 
           send(incr(moins),L,+);
      }
  }
}

8.5  Communications dans un hypercube

8.5.1  Chemins dans un hypercube

8.5.2  Plongements d'anneaux et de grilles

• xG énumère les éléments de G en rajoutant x en tête de leur écriture binaire,
• G^rev énumère les éléments de G dans l'ordre renversé,
• | est la concaténation (de ``listes'' de mots binaires).

• G₁={0,1},
• G₂={00,01,11,10},
• G₃={000,001,011,010,110,111,101,100},
• G₄={0000,0001,0011,0010,0110,0111,0101,0100,1100,
  
            1101,1111,1110,1011,1010,1001,1000}.

---

Figure 8.11: Plongement d'un anneau dans un hypercube.

---

8.5.3  Diffusion simple dans l'hypercube

---

Figure 8.12: Un arbre couvrant pour un 4-cube.

---

• phase 3: 0000 envoie le message sur le lien 3 à 1000,
• phase 2: 0000 et 1000 envoient le message sur le lien 2, à 0100 et 1100 respectivement,
• ainsi de suite jusqu'à la phase 0.

Chapter 9  Remote Method Invocation

9.1  Architecture

private void writeObject(ObjectOutputStream aOutputStream) throws IOException;
private void readObject(ObjectInputStream aInputStream) 
             throws ClassNotFoundException, IOException;

9.2  Exemple: RMI simple

---

Figure 9.1: Les classes d'un ``Hello World'' distribué''

---

import java.rmi.*;

public interface HelloInterface extends Remote {
    public String say() throws RemoteException;
}

import java.rmi.*;
import java.rmi.server.*;

public class Hello extends UnicastRemoteObject 
  implements HelloInterface {
  private String message;
  
  public Hello(String msg) throws RemoteException {
    message = msg; }

  public String say() throws RemoteException {
    return message;
  }
}

javac HelloInterface.java
javac Hello.java

rmic Hello

  import java.rmi.*;
  public class HelloClient {
    public static void main(String[] argv) {
      try {
        HelloInterface hello = 
        (HelloInterface) Naming.lookup
                ("//cher.polytechnique.fr/Hello");
        System.out.println(hello.say());
      } catch(Exception e) {
          System.out.println("HelloClient exception: "+e);
      }
    }
  }

  import java.rmi.*;
  
  public class HelloServer {
    public static void main(String[] argv) {
      try {
        Naming.rebind("Hello",new Hello("Hello, world!"));
        System.out.println("Hello Server is ready.");
      } catch(Exception e) {
          System.out.println("Hello Server failed: "+e);
      }
    }
  }

javac HelloClient.java
javac HelloServer.java

rmiregistry &

[goubaul1@cher HelloNormal]$ java HelloServer
Hello Server is ready.

[goubaul1@loire HelloNormal]$ java HelloClient
Hello, world!

9.3  RMI avec Callback

---

Figure 9.2: Organisation des classes, pour un RMI avec callback

---

interface TemperatureListener extends java.rmi.Remote {
    public void temperatureChanged(double temperature)
         throws java.rmi.RemoteException;
}

interface TemperatureSensor extends java.rmi.Remote {
    public double getTemperature() throws
        java.rmi.RemoteException;
    public void addTemperatureListener
        (TemperatureListener listener)
        throws java.rmi.RemoteException;
    public void removeTemperatureListener
        (TemperatureListener listener)
        throws java.rmi.RemoteException; }

import java.util.*;
import java.rmi.*;
import java.rmi.server.*;

public class TemperatureSensorServer 
    extends UnicastRemoteObject
    implements TemperatureSensor, Runnable {
    private volatile double temp;
    private Vector list = new Vector();

    public TemperatureSensorServer() 
      throws java.rmi.RemoteException {
        temp = 98.0; }

    public double getTemperature() 
      throws java.rmi.RemoteException {
        return temp; }

public void addTemperatureListener
              (TemperatureListener listener)
  throws java.rmi.RemoteException {
  System.out.println("adding listener -"+listener);
  list.add(listener); }

public void removeTemperatureListener
              (TemperatureListener listener)
  throws java.rmi.RemoteException {
  System.out.println("removing listener -"+listener);
  list.remove(listener); }

public void run()
{ Random r = new Random();
  for (;;)
    { try {
        int duration = r.nextInt() % 10000 +2000;
        if (duration < 0) duration = duration*(-1);
        Thread.sleep(duration); }
      catch(InterruptedException ie) {}
      int num = r.nextInt();
      if (num < 0)
        temp += .5;
      else
        temp -= .5;
      notifyListeners(); } }

private void notifyListeners() {
  for (Enumeration e = list.elements(); e.hasMoreElements();) 
  { TemperatureListener listener = 
        (TemperatureListener) e.nextElement();
    try {
      listener.temperatureChanged(temp);
    } catch(RemoteException re) {
        System.out.println("removing listener -"+listener);
        list.remove(listener); } } }

public static void main(String args[]) {
  System.out.println("Loading temperature service");
  try {
    TemperatureSensorServer sensor = 
        new TemperatureSensorServer();
    String registry = "localhost";
    if (args.length >= 1)
      registry = args[0];
    String registration = "rmi://"+registry+
                          "/TemperatureSensor";
    Naming.rebind(registration,sensor);

    Thread thread = new Thread(sensor);
    thread.start(); }
  catch (RemoteException re) {
    System.err.println("Remote Error - "+re); }
  catch (Exception e) {
    System.err.println("Error - "+e); } } }

import java.rmi.*;
import java.rmi.server.*;

public class TemperatureMonitor extends UnicastRemoteObject
    implements TemperatureListener {
    public TemperatureMonitor() throws RemoteException {}

public static void main(String args[]) {
  System.out.println("Looking for temperature sensor");
  try {
    String registry = "localhost";
    if (args.length >= 1)
    registry = args[0];
    String registration = "rmi://"+registry+
                          "/TemperatureSensor";
    Remote remoteService = Naming.lookup(registration);
    TemperatureSensor sensor = (TemperatureSensor) 
                                 remoteService;

    double reading = sensor.getTemperature();
    System.out.println("Original temp : "+reading);
    TemperatureMonitor monitor = new TemperatureMonitor();
    sensor.addTemperatureListener(monitor);

  } catch(NotBoundException nbe) {
      System.out.println("No sensors available"); }
    catch (RemoteException re) {
      System.out.println("RMI Error - "+re); }
    catch (Exception e) {
      System.out.println("Error - "+e); } }

public void temperatureChanged(double temperature)
  throws java.rmi.RemoteException {
  System.out.println("Temperature change event : "
                    +temperature);
}

[goubaul1@cher Ex3]$ javac *.java
[goubaul1@cher Ex3]$ rmic TemperatureMonitor
[goubaul1@cher Ex3]$ rmic TemperatureSensorServer

[goubaul1@cher Ex3]$ rmiregistry &
[goubaul1@cher Ex3]$ java TemperatureSensorServer
Loading temperature service

[goubaul1@loire Ex3]$ rmiregistry &
[goubaul1@loire Ex3]$ java TemperatureMonitor cher
Looking for temperature sensor
Original temp : 100.0
Temperature change event : 99.5
Temperature change event : 100.0
Temperature change event : 100.5
Temperature change event : 100.0
Temperature change event : 100.5
Temperature change event : 101.0
Temperature change event : 100.5
Temperature change event : 100.0
Temperature change event : 100.5
Temperature change event : 101.0
Temperature change event : 101.5

adding listener -TemperatureMonitor_Stub[RemoteStub 
[ref: [endpoint:[129.104.254.64:3224](remote),
objID:[6e1408:f29e197d47:-8000, 0]]]]

[goubaul1@doubs Ex3]$ rmiregistry &
[goubaul1@doubs Ex3]$ java TemperatureMonitor cher
Looking for temperature sensor
Original temp : 101.5
Temperature change event : 102.0
Temperature change event : 102.5
Temperature change event : 103.0
Temperature change event : 102.5
Temperature change event : 103.0
Temperature change event : 103.5
Temperature change event : 102.5
Temperature change event : 102.0

adding listener -TemperatureMonitor_Stub[RemoteStub 
[ref: [endpoint:[129.104.254.57:3648](remote),
objID:[6e1408:f29de7882e:-8000, 0]]]]

Temperature change event : 102.0
Temperature change event : 102.5
Temperature change event : 103.0
Temperature change event : 102.5
Temperature change event : 103.0
Temperature change event : 103.5
^C
[goubaul1@loire Ex3]$ 

removing listener -TemperatureMonitor_Stub[RemoteStub 
[ref: [endpoint:[129.104.254.64:3224](remote),
objID:[6e1408:f29e197d47:-8000, 0]]]]

removing listener -TemperatureMonitor_Stub[RemoteStub 
[ref: [endpoint:[129.104.254.57:3648](remote),
objID:[6e1408:f29de7882e:-8000, 0]]]]

9.4  RMI avec réveil de serveur

• java.rmi définit l'interface RemoteInterface, et les exceptions,
• java.rmi.activation (depuis JAVA2): permet l'activation à distance des objets,
• java.rmi.dgc: s'occupe du ramassage de miettes dans un environnement distribué,
• java.rmi.registry fournit l'interface permettant de représenter un rmiregistry, d'en créer un, ou d'en trouver un,
• java.rmi.server fournit les classes et interfaces pour les serveurs RMI.

---

Figure 9.3: Les différentes classes et interfaces RMI

---

public interface InterfaceObjetActivable 
  extends java.rmi.Remote
{  public void MethodeA() throws java.rmi.RemoteException;
   public void MethodeB() throws java.rmi.RemoteException;
  ... }

public class ImplementationObjetActivable extends
             java.rmi.activation.Activatable
             implements InterfaceObjetActivable
{
  public ImplementationObjetActivable (
    java.rmi.activation.ActivationID activationID,
    java.rmi.MashalledObject data) throws
    java.rmi.RemoteException
    { super(activationID,0); }

  public void doSomething()
  {
    ...
  }
}

9.4.1  Exemple d'une ``lampe''

---

Figure 9.4: Classes pour la lampe activable à distance

---

package examples;
import java.rmi.*;

public interface RMILightBulb extends Remote {
    public void on() throws RemoteException;
    public void off() throws RemoteException;
    public boolean isOn() throws RemoteException;
}

package examples;
import java.rmi.*;

public class LightBulbClient {
    public static void main(String args[]) {
 System.out.println("Recherche d'une lampe...");

  /* voir Server */
System.setSecurityManager(new RMISecurityManager()); 
try {
  String registry = "localhost";
  if (args.length >= 1) 
    registry = args[0];
  String registration = "rmi://"+registry+
              "/ActivatableLightBulbServer";
  Remote remoteService = Naming.lookup(registration);
  RMILightBulb bulbService = (RMILightBulb) remoteService;

    System.out.println("Appel de bulbservice.on()");
    bulbService.on();
    System.out.println("Lampe : "+bulbService.isOn());

    System.out.println("Appel de bulbservice.off()");
    bulbService.off();
    System.out.println("Lampe : "+bulbService.isOn());

    } catch(NotBoundException nbe) {
      System.out.println("Pas de lampe dans le 
                        repertoire de services!");
   } catch(RemoteException re) {
   System.out.println("RMI Error - "+re);
  } catch(Exception e) {
  System.out.println("Error - "+e);
  }
 }
}

package examples;

import java.rmi.*;
import java.rmi.activation.*;

public class ActivatableLightBulbServer 
extends Activatable implements RMILightBulb {
    public ActivatableLightBulbServer
             (ActivationID activationID, 
              MarshalledObject data) 
                throws RemoteException {
        super(activationID,0);
        setBulb(false); }

public boolean isOn() throws RemoteException {
  return getBulb();
}

public void setBulb(boolean value) 
  throws RemoteException {
  lightOn = value; }

public boolean getBulb() throws RemoteException {
  return lightOn; } }

private boolean lightOn;

public void on() throws RemoteException {
  setBulb(true);
}

public void off() throws RemoteException {
  setBulb(false);
}

package examples;
import java.rmi.*;
import java.rmi.activation.*;
import java.util.Properties;
public class Setup {
  public static void main(String[] args) throws Exception {
    System.setSecurityManager(new RMISecurityManager());
    Properties props = new Properties();
    props.put("java.security.policy",
"/users/profs/info/goubaul1/Cours03/RMI/Ex2/activepolicy");

  ActivationGroupDesc.CommandEnvironment ace = null;
  ActivationGroupDesc exampleGroup = 
    new ActivationGroupDesc(props, ace);

ActivationGroupID agi =
  ActivationGroup.getSystem().registerGroup(exampleGroup);

  String location = 
"file:/users/profs/info/goubaul1/Cours03/RMI/Ex2/";
  MarshalledObject data = null;
  ActivationDesc desc = new ActivationDesc
    (agi, "examples.ActivatableLightBulbServer",
     location, data);

java.io.File location = new java.io.File(".");
String strLoc = "file://"
+URLEncoder.encode(location.getAbsolutePath(),"UTF-8");
System.out.println("Code \`a ex\'ecuter : "+strLoc);

java -Djava.rmi.server.codebase=http://hostname:port/path

RMILightBulb stub = (RMILightBulb)Activatable.register(desc);
System.out.println("Got stub for ActivatableLightBulbServer");

Naming.rebind("ActivatableLightBulbServer", mri);
System.out.println("Exported ActivatableLightBulbServer");
System.exit(0); } }

9.4.2  Complément: politiques de sécurité

java.security.AccessControlException: access denied
(java.net.SocketPermission 127.0.0.1:1099 connect,resolve)

System.setSecurityManager(new RMISecurityManager() {
  public void checkConnect(String host, int port) {}
  public void checkConnect(String host, int port, 
                           Object context) {}
});

grant codeBase "file:/home/goubault/-" {
  permission java.security.AllPermission;
};

grant codeBase "file:/home/goubault/-" {
  permission java.net.SocketPermission 
    "129.104.254.54:1024-", "connect, accept";
}

java -Djava.security.policy=FICHIER
     -D-Djava.rmi.server.codebase=file:/LOCATION
     MACLASSE

javac -d . RMILightBulb.java
javac -d . LightBulbClient.java
javac -d . Setup.java
javac -d . ActivatableLightBulbServer.java
rmic ActivatableLightBulbServer

grant {
  permission java.security.AllPermission;
};

[goubaul1@loire Ex2]$ java 
  -Djava.security.policy=activepolicy 
  -Djava.rmi.server.codebase=file:/. examples.Setup
Got the stub for the ActivatableLightBulbServer
Exported ActivatableLightBulbServer

[goubaul1@cher Ex2]$ java -Djava.security.policy=activepolicy 
examples.LightBulbClient loire
Looking for light bulb service
Invoking bulbservice.on()
Bulb state : true
Invoking bulbservice.off()
Bulb state : false

public class RMILightBulbImpl extends 
java.rmi.server.UnicastRemoteObject 
                implements RMILightBulb {
    public RMILightBulbImpl() 
    throws java.rmi.RemoteException {
      setBulb(false);
    }

    private boolean lightOn;

    public void on() 
      throws java.rmi.RemoteException {
        setBulb(true); }

    public void off() 
      throws java.rmi.RemoteException {
        setBulb(false); }

    public boolean isOn() 
      throws java.rmi.RemoteException {
        return getBulb(); }

    public void setBulb(boolean value) {
        lightOn = value; }
    public boolean getBulb() {
        return lightOn; } }

public interface RMILightBulb extends java.rmi.Remote {
    public void on() throws java.rmi.RemoteException;
    public void off() throws java.rmi.RemoteException;
    public boolean isOn() throws java.rmi.RemoteException;
}

[goubaul1@cher Ex1]$ java LightBulbServer
Loading RMI service
RemoteStub [ref: [endpoint:[129.104.254.54:1867](local),
            objID:[0]]]

[goubaul1@loire Ex1]$ java LightBulbClient cher
Looking for light bulb service
Invoking bulbservice.on()
Bulb state : true
Invoking bulbservice.off()
Bulb state : false

9.5  CORBA

---

Figure 9.5: Le dialogue CORBA

---

---

Figure 9.6: Le cycle de développement CORBA

---

interface Vecteur {
  typedef double vect[100]; // Definition du type vect 
  attribute long size;      // size est un attribut 
                            // de type long (entier)
  attribute vect T ;        // T est un attribut de 
                            // type vect
  double maxElement();      // maxElement est une 
                       // methode retournant un double
  void mult(in double a);   // mult est une methode 
                            // prenant pour parametre
                            // un double transmis 
};                        //par le client (mot cle in)

• VecteurOperations.java : définition de l'interface qui contient la signature des méthodes de l'objet Vecteur.
• Vecteur.java : définition de l'interface Vecteur qui hérite de VecteurOperations.
• VecteurHelper.java : regroupe des méthodes destinées à vous aider lors de l'utilisation des objets Vecteur.
• VecteurHolder.java : outils pour prendre en charge le passage de paramètres avec les méthodes de l'objet Vecteur.
• _VecteurStub.java : stub de l'objet Vecteur. Cette classe sera utilisée dans le code de notre client de façon implicite, elle représentera l'objet distant en mettant à notre disposition les méthodes qui s'y trouvent.
• _VecteurImplBase.java : squelette de l'objet Vecteur. C'est la classe de base de notre futur objet vecteur. On en dérivera une classe pour coder le fonctionnement réel de notre objet.

public class VecteurImplem extends _VecteurImplBase {
    private int size=100;
    private double T[];
    VecteurImplem(double[] Tab) {
        for(int i=0;i<size;i++) {
            T[i]=Tab[i]; } }

    VecteurImplem() {} ;

    public int size() {
        return size; }

    public void size(int newSize) {
        size = newSize; }

    public double[] T() {
        return T; }

    public void T(double[] newT) {
        for(int i=0;i<size;i++) {
            T[i]=newT[i]; } }

    public double maxElement () {
        double m = T[0];
        for (int i=1;i<size;i++) {
            if (T[i]>m) { m = T[i]; } };
        return m; }

    public void mult(double a) {
        for (int i=0;i<size;i++) {
            T[i]=T[i]*a; } } }

import org.omg.CosNaming.*;
import org.omg.CosNaming.NamingContextPackage.*;
import org.omg.CORBA.*;

public class VecteurServeur {
    public static void main(String args[]) {
        try{
  // Cree et initialise l'ORB
  ORB orb = ORB.init(args, null);
  // Cree le servant et l'enregistre sur l'ORB
  VecteurImplem vecteurRef = new VecteurImplem();
  orb.connect(vecteurRef);
  // Obtention de la reference du RootPOA
  org.omg.CORBA.Object objRef = 
  orb.resolve_initial_references("NameService");
  NamingContext ncRef = NamingContextHelper.narrow(objRef);
  // Enregistre la reference de l'objet
  NameComponent nc = new NameComponent("Vecteur", "");
  NameComponent path[] = {nc};
  ncRef.rebind(path, vecteurRef);
  // attend les invocations de clients
  java.lang.Object sync = new java.lang.Object();
  synchronized (sync) {
  sync.wait(); }
  } catch (Exception e) {
      System.err.println("ERROR: " + e);
      e.printStackTrace(System.out); } } }

import org.omg.CosNaming.*;
import org.omg.CORBA.*;

public class VecteurClient {
  public static void main(String args[]) {
    try{
      // Cree et initialise l'ORB.
      ORB orb = ORB.init(args, null);
      // Obtention de la reference du RootPOA
      org.omg.CORBA.Object objRef = 
        orb.resolve_initial_references("NameService");
      NamingContext ncRef = NamingContextHelper.narrow(objRef);
      // trouve la r\'ef\'erence \`a l'objet
      NameComponent nc = new NameComponent("Vecteur", "");
      NameComponent path[] = {nc};
      Vecteur vecteurRef = VecteurHelper.narrow
                             (ncRef.resolve(path));
      // Utilisation de l'objet
      ...
      } catch (Exception e) {
          System.out.println("ERROR : " + e) ;
          e.printStackTrace(System.out); } } }

javac *.java

Chapter 10  Algèbre linéaire

10.1  Produit matrice-vecteur sur anneau

for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
    y[i] = y[i]+a[i,j]*x[j];

float a[r][n];
float x[r],y[r];

matrice-vecteur(A,x,y) {
  q = my_num();
  p = tot_proc_num();
  for (step=0;step<p;step++) {
    send(x,r);
    for (i=0;i<r;i++) 
      for (j=0;j<r;j++)
        y[i] = y[i]+a[i,(q-step mod p)r+j]*x[j];
    receive(temp,r); 
    x = temp;
  }
}