TPs de STR

Le but de cette série de 4/5 TPs est de vous faire programmer une version distribuée de la méthode de la puissance (un algorithme qui sert à calculer des vecteurs propres) via une librairie MPI. Vous allez devoir programmer (au moins) deux manières de faire et les comparer.

Charles Bouillaguet

TP #1 : prise en main de MPI

TP #2 : méthode de la puissance

Description du problème

Vous pouvez télécharger ci-dessous le code source (en C) d'une implémentation séquentielle de la méthode de la puissance. Ce code est commenté et ne devrait pas vous poser de gros problèmes. Vous pouvez le compiler et l'éxecuter, il va fabriquer une matrice à peu près aléatoire de la taille que vous voulez, puis va en calculer un vecteur propre, et enfin sauvegarder ce vecteur dans un fichier.

Le problème est que pour des grosses matrices (disons 200'000 x 200'000), d'une part ça prend du temps (le code séquentiel s'exécute en 13 heures et 40 minutes environ), et d'autre part la matrice occupe beaucoup d'espace (298Go en l'occurence), ce qui empêche de réaliser le calcul en pratique sur la plupart des machines.

Mais en distribuant le calcul, on peut espérer:
  1. Que ça aille plus vite avec P machines qu'avec une seule.
  2. Que même si aucune des P machines n'a assez de RAM pour stocker toute la matrice, elles peuvent la stocker ensemble de manière répartie.

Ressources

Travail à faire

Vous devez écrire (au moins) deux versions parallèles, en utilisant une bibliothèque MPI, et comparer leurs efficacités respectives. Les versions à programmer sont :

RAPPEL : ces trois techniques sont décrites dans la documentation qu'on a écrite pour vous. Les deux premières méthodes sont les plus faciles. En principe, c'est le troisième qui doit donner les meilleurs résultats, mais sa réalisation est sérieusement plus difficile.

Pour vous faire envie, voici le résultat de l'exécution de la décomposition par bloc sur 16 machines. On voit clairement apparaître les itérations (calculs en vert, communications en rouge). Là on peut voir un un zoom sur les communications d'une seule itération.

Dans tous les cas, on peut faire certaines hypothèses pour se simplifier la vie, par exemple supposer que la taille de la matrice est un multiple de P.

Pour chacune de ces implémentations, vous devrez mesurer le temps d'exécution pour différentes tailles de la matrice, et essayer d'expliquer les différences.

Soyez joueur : essayer de "faire passer" le plus gros calcul possible (c'est-à-dire pour la plus grande taille possible de la matrice). Identifiez les facteurs limitants. Ne le faites pas tous en même temps, sinon bonjour les dégats.

Les modifications à apporter au code séquentiel ne sont pas énormes : pour faire la version "par lignes", il suffit de modifier 7 lignes de code et d'en ajouter 19. Pour la version "par colonnes", il faut modifier 13 lignes et en ajouter 20.

À rendre

Vous devrez nous remettre, avant le 20 décembre, une archive contenant :

Conseils

Ne paniquez pas.

Vous avez intérêt à y aller progressivement, et à vérifier et tester chaque étape avant de passer à la suivante. Commencez par distribuer la génération de la matrice (facile). Puis, passez au produit matrice-vecteur (plus dur). Enfin, faites le bloc [produit matrice-vecteur]+[calcul de la norme du résultat], qui pose des problèmes supplémentaires. Et ainsi de suite.

C'est un peu plus facile de traiter le cas où la matrice est découpée en blocs de ligne, plutôt qu'en blocs de colonnes (à notre avis en tout cas).

Ressources sur MPI

Contact

Contacter Charles Bouillaguet pour des questions, bugs, problèmes, crises d'angoisses, etc.

Valid XHTML 1.1