Ecole Polytechnique






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

TD 6

4 mars 2003

On commencera par finir l'exercice sur les rotations de Givens.

1  Objets activables à distance et RMI

On souhaite améliorer la façon dont pi est calculé par la méthode vue au TD 6, en faisant en sorte que les serveurs de calcul soient activables à distance. Modifier le programme de calcul de pi du TD 5 (ou du TD 6) comme indiqué précédemment.

2  Prise en main de JAVAPARTY

3  Enveloppe convexe parallèle

On souhaite calculer l'enveloppe convexe d'un ensemble de points sur n machines en parallèle, à l'aide de JavaParty. Il est rappelé que l'algorithme séquentiel fonctionne suivant le principe du ``diviser pour régner'' : Nous allons développer la classe ConvexHullHP suivante :

remote class ConvexHullJP {
    int[] x,y; /* coordonnees des points */
    int[] ch;  /* tableau contenant, les indices des points appartenant a l'enveloppe */
    int nMax;  /* nombre de points = taille de x et y */
    int nCh;   /* nombre de points de l'enveloppe = taille de ch <= nMax */

    ConvexHullJP(int[] tx,int[] ty);
    void merge(ConvexHullJP uh1,ConvexHullJP uh2);
    void compute();
    void printGraph();

    public static void main(String[] args) {
        int[] tx = { 8,15,19,22,33,41,47,50 };
        int[] ty = { 15,11,25,31,27,32,21,9 };
        ...
    }    
}
La méthode merge permet de réaliser la fusion (voir page web). La méthode printGraph permet d'obtenir une représentation graphique du résultat par la commande java ConvexHullJP | ch (son code est aussi donné sur la page web).

  1. Réfléchir à l'organisation des classes (remote ou pas)
  2. Ecrire le reste de la classe de façon à ce que les appels récursifs soient effectués sur des machines différentes par JavaParty.
  3. Afin de limiter le nombre de tâches, modifier le programme précédent pour que seuls les p premiers niveaux d'appels soient distribués, les suivant étant exécutés en séquentiel sur le noeud courant (en pratique on pourra poser p=2 pour utiliser 4 machines).
  4. Modifier le programme afin d'être sûr que chaque calcul s'effectuera sur une machine différente.
On suppose maintenant que les points donnés en entrée ne sont pas triées. Implémenter, en JavaParty, un algorithme de tri vu en cours (par exemple le tri pair-impair sur réseau lináire).


This document was translated from LATEX by HEVEA.