Parallélisme et MPI

[fafaro]

Salut,

Tout d'abord, si un sujet similaire existe, désolé...

Je voulais simplement savoir si quelques personnes parmi vous sont intéressés par un sujet sur la programmation distribuée par échange de message. J'ai mis MPI en titre, parce que c'est ce que j'utilise tous les jours, mais on peut compléter avec PVM ou tout ce que vous voulez.

Je commence donc par deux liens vers deux distributions MPI gratuites, LAM et MPICH, et un lien vers la page du forum MPI.

Ah, dernière chose : si le sujet vous intrigue, mais que vous ne savez pas de quoi il s'agit, n'hésitez pas à demander. J'essaierai de vous éclairer.

Sommaire des différents posts :

principes : ici et là.

compilation et exécution : ici.

communications point à point bloquantes et non bloquantes : ici.

communications collectives : ici.

[fafaro]

Ok, rapide présentation alors !

Petite précision : tout ce que je vais écrire sera orienté calcul scientifique (c'est ce que je connais le mieux...).

Commençons par le calcul parallèle. Lorsqu'un problème est trop gros pour être résolu en un temps raisonnable par une machine monoprocesseur (même très puissante), il est logique d'essayer de résoudre ce même problème en utilisant plusieurs processeurs.

Si le problème est bien posé (ce qui n'est pas toujours possible), on peut le découper en sous problèmes qui peuvent être résolus séparément et simultanément sur plusieurs processeurs. Les solutions des sous problèmes sont ensuite assemblées pour reconstituer la solution du gros problème. Comme on résout les petits problèmes plus rapidement que le gros, et qu'ils sont résolus en même temps, le temps de calcul baisse.

Voilà pour le principe.

Ce que j'appelle calcul distribué est le calcul parallèle sur une machine à mémoire distribuée : plusieurs processeurs, ayant chacun leur mémoire vive, reliés entre eux par un réseau quelconque (ethernet, myrinet ou autre).

Pour que ces processeurs puissent coopérer, il est nécessaire qu'ils échangent des informations. Et c'est là que l'échange de message intervient. Les informations échangées par les processeurs sont contenues dans des messages transitant sur le réseau d'interconnexion.

Il y a ici une grosse différence avec un pc bi-processeur, dans lequel les deux processeurs se partagent la même mémoir physique, et qui peuvent donc chacun avoir accès aux mêmes infos.

Est-ce que ça va jusque là ?

[fafaro]

Je continue.

On a donc deux choses à faire : découper notre gros problèmes en petits problèmes et faire en sorte que les processeurs communiquent entre eux pour résoudre tout ça comme il faut. Je crois que c'est le moment de sortir un exemple de mon chapeau

Prenons un algorithme de recherche du maximum dans une liste d'entiers. Si notre liste d'entiers n'est pas triée et qu'elle est composée de N nombres, il nous faut un nombre d'opérations proportionnel à N pour trouver le max. Si maintenant nous divisons la liste en P parts égales, il faut P fois moins d'opérations pour trouver le max de chaque sous-liste, puis il suffit de comparer les P max des sous-listes pour avoir le max global.

Bon, admettons que la liste complète soit sur la mémoire d'un proc que j'appelle 0. Il partage la liste en P et envoie un Pième à (P-1) autres procs grâce à des messages. Chaque proc cherche son max puis envoie le résultat à 0 dans un message. Le proc 0 reçoit chaque message et compare leur contenu avec son propre max local. Il dispose à la fin du max global. Si l'envoi des messages ne demandait aucun temps, on aurait divisé le temps de calcul total par presque P.

Comment fait-on ça en pratique ?

Je garde le même exemple du max. Voici un petit algo simple du code qui sera exécuté sur chaque processeur :

- quel processeur suis-je ?

- si je suis le proc 0 alors je partage la liste, je garde un bout pour moi et j'en envoie un morceau à chaque autre proc par des messages

- si je ne suis pas le proc 0, je reçois un message de 0 contenant une sous-liste

- je trie ma sous-liste

- si je ne suis pas 0, j'envoie mon max local à 0

- si je suis 0, je reçois les messages contenant les max locaux, je les compare au mien et j'obtiens le max global.

La difficultée dans ce qui précède réside dans la première étape (qui suis-je ?) et dans les envois de messages. MPI permet de résoudre ces problèmes, puisque MPI propose des fonctions (Fortran, C ou C++) réalisant ces opérations.

Je m'arrête de nouveau au cas où il y aurait des questions. Je ne reviendrai que demain pour la suite, si jamais des gens sont intéressés parmi vous.

[Atlantis]

je m'y interesse aussi. à noter que pour la comprehension (premiere approche) il y a l'article chez onversity. et il y a pas mal de doc en ligne avec les mots distributed ou MPI.

bon là j'en suis qu'aux bases car je mene ce projet de formation en // avec bcp d'autres ...

[fafaro]

Edit : J'ai supprimé le lien vers ma thèse qui pointait vers mon ancien labo. Si jamais vous voulez a partie consacrée à une introduction au calcul parallèle, vous pouvez me la demander par MP.

Merci

Je continuerai ce soir puisqu'il semble y avoir 1 ou 2 personnes que le sujet intéresse.

[jromang]

C'est un sujet qui m'intéresse de près ! Je n'ai encore jamais vraiment utilisé MPI, mais j'ai l'intention de m'y mettre dans les mois qui viennent (parallélisation de mon programme d'echecs). La question que je me pose est matérielle ; bien que MPI soit prévu pour la prgrammation en mémoire distribuée, d'après ce que j'ai lu sur MPICH on peut sans problème faire un MPI sur une machine bi-proc en mémoire partagée. Pour l'instant je n'ai qu'un PC mono-proc, alors je me pose la question suivante : qu'est ce qui serait le mieux pour faire de la programmation parrallèle MPI ?

- Achat d'un PC bi proc ?

- Achat d'un 2eme PC identique au mien ?

- Achat de 4 PC nano ITX basés sur des proc VIA pour pas cher ?

Et au niveau reseau il faut des cartes gigabit pour faire communiquer les machines ou le ethernet 100 est suffisant ?

[fafaro]

Salut,

Si tu veux faire du calcul parallèle sur une machine bi-processeur avec MPI, ça fonctionne. Mais il est plus efficace, à mon avis (mais je n'ai jamais vraiment testé), d'utiliser des instruction Open-MP par exemple, qui permettent d'utiliser tes deux procs à mémoire partagée très simplement.

Pour ce qui est de la carte réseau, ça dépend un peu de tes ambitions et de tes moyens. Tu peux très bien faire fonctionner le tout avec des cartes ethernet 100. Les cartes gigabit te donnent un plus sur la bande passante, mais ce n'est pas forcément un élément déterminant - si tu as besoin d'échanger beaucoup de petits messages, la bande passante n'a pas d'importance, alors que pour quelques échanges de gros messages, ça peut faire une différence de performances... Et il y a des réseaux plus performants et plus coûteux, mais je crois qu'il n'est pas util d'en parler, ça coûte vraiment trop cher . Pour info, le cluster de pcs de mon labo a fonctionné avec de l'ethernet 100 pendant 3 ans je crois, avant qu'on le bascule en gigabit.

Et pour ton conseil d'achat, je ne sais pas très bien quoi te répondre. Pour t'amuser et faire un peu de MPI tu n'as à priori besoin que d'un processeur. Il me semble en effet que MPI accepte de lancer plusieurs processus sur le même processeur. Ca te permet de faire quelques essais, d'apprendre à paralléliser un code, à utiliser MPI. Mais tu ne gagnes rien en matière de performance. Pour faire du vrai parallélisme, il faut plusieurs processeurs. Lesquels ? En bipro ou en monopro ? Ca dépend un peu de toi, je pense. Je dirais que pour minimiser l'investissement, racheter un pc monopro me paraît être une bonne option.

[lorinc]

encore que les carte VIA sont vraiment moins chere.

si tu veux absolument tester tout ça, et que le prix de 4 micro ITX reviennent à peu près à un gros PIV (ben oui, puisque tu va le charger comme s'il était plusieurs - donc il faut qu'il tienne), alors mieux vaut prendre la solution de clustering dès le dépard

enfin, pour ce que j'en dis

[jromang]

Merci pour vos conseils ! Mon objectif etant de gagner des performances ma machine mono proc ne suffira pas. Une autre question encore : si j'arrive a faire un programme MPI avec un bon gain de performances sur 2 cpu, est ce que je serai assuré d'avoir un bon gain avec 4 CPU ou plus ? Ou bien faut il un parc avec beaucoup de CPU dès le depart pour verifier le gain tout au long du développement ?

Sinon coté logiciel le cluster de ton labo fonctionnait avec quel OS ? Dans le cas d'un cluster de machines, on peut imaginer des noeuds sans disque dur (booter par le lan?) ? C'est pénible a mettre en place ?

[fafaro]

On a un disque sur chaque machine. On a installé Linux Mandrake sur chacun, une installation aussi réduite que possible. Puis on a ajouté MPI (chez nous, c'est MPI Lam), le compilateur Intel (avec lequel on a recompilé MPI Lam). Et si je ne me trompe pas, c'est tout ce qu'il y a de spécial. La solution sans disque ne me paraît pas optimale mais je me trompe peut-être.

Pour les performance, c'est un peu compliqué de répondre avec certitude. Il y a une loi théorique, qui s'appelle loi d'Amdahl, qui donne une limite à l'accélération que tu peux attendre. L'accélération, c'est le temps de calcul en utilisant 1 proc divisé par le temps de calcul en utilisant p procs.

En gros, ça dit que si ton code contient une fraction f (0<f<1) d'instructions qui ne peuvent être exécutées que séquentiellement (sur un seul proc), alors tu ne peux pas espérer diviser ton temps de calcul de plus de 1/(f+(1-f)/p), où p est le nombre de proc que tu utilises. Donc si l'algo que tu parallélises à un f grand, l'accélération max est faible, et il ne sert à rien d'avoir beaucoup de procs. Si f est petit, tu peux diviser le temps de calcul par presque 2 en multipliant le nombre de proc par 2, mais tu arriveras toujours à une valeur limite de l'accélération.

Exemple : tu as une fraction non parallélisable de 1/3. Ton accélération max pour 2 procs est égale à 1.5. C'est pas mal. Si tu passes à 4 procs, l'accélération max est égale à 2. Est-ce que ça vaut le coup de passer à 4 procs ?

Bon, d'après l'expérience que j'ai (j'en ai une petite qui peut servir parfois ), si tu as une accélération proche de 2 en passant de 1 à 2 procs, ça vaut le coup de passer à 4. Ca se gate quand tu te rapproches de 10/20 procs.

Attention : ce qui précède concernant la loi d'Amdahl est théorique. Ca ne se vérifie pas toujours, mais ça donne une idée en général pas trop mauvaise de ce qui nous attend.

[lorinc]

ça me rappelle des choses es histoire d'accélération... faudra que je ré-épluche mes vieux cours pour voir

en tout cas le sujet est et si tu pouvais un peu aérer tes premiers posts et mettre un chouillat de couler, ce serait vraiment

[fafaro]

C'est cool que le sujet vous plaise.

J'édite mes premiers posts quand j'ai un moment pour les rendre un peu plus agréables à lire.

[Atlantis]

Voilà, c'est ici.

[jromang]

Ok Je vais donc partir pour une solution 2 proc, et essayer d'obtenir la meilleure accélération la dessus ! Merci pour ces conseils J'espère que j'arriverai a faire progresser mon programme, en attendant si vous voulez vous chauffer un peu les neurones aux echecs vous pouvez le telecharger ici !

[fafaro]

Salut,

Je vais continuer un peu mes histoires de parallélisme. Un peu de MPI pour aujourd'hui. (plus précisément, MPI Lam, c'est la distribution que j'utilise).

Compilation : MPI Lam propose des commande mpicc et mpif77 pour compiler les codes incluant des appels MPI. Il me semble que MPICH propose des commandes équivalentes, pour les autres distributions, je ne sais pas (mais je suppose que oui).

Exécution : toujours avec Lam, on construit un fichier texte contenant les noms des machines que l'on veut utiliser. Appelons le noeud. On lance le démon lamd (qui est l'ami des messages) sur ces machines avec la commande lamboot -v noeud. Les machines sont numérotées par Lam de n0 à n(p-1), où p est le nombre de machines dans le fichier noeud.

Puis on écrit un fichier texte, mettons application, dans lequel on écrit la liste des application MPI que l'on veut exécuter simultanément, sous la forme

n0 -s h executable1

n1 -s h executable2

...

Les exécutables peuvent être identiques ou différents. L'important est que leurs appels MPI soient compatibles : si l'exécutables qui tourne sur n0 envoie un message à n1, il faut que l'exécutable qui tourne sur n1 s'attende à recevoir un message provenant de n0.

Enfin, on lance l'exécution avec la commande mpirun -O application.

Et c'est parti !

Jetons mainteant un oeil sur le code. Je n'écrirai les arguments des fonctions que pour leur version C (juste parce qu'il y en a parfois un de moins qu'en Fortran ).

Commençons par la base (je parle Fortran et C, mais pas C++, désolé ) : il faut inclure mpi.h en C et mpif.h en Fortran dans toute procédure ou fonction utilisant un appel MPI.

Une fois ceci fait, il faut penser à la chose suivante : la première fonction MPI appelée doit être MPI_Init(&argc,&argv) et la dernière MPI_Finalize().

Bon, c'est fini pour aujourd'hui. J'ai encore un peu de boulot et je ne veux pas partir trop tard pour me remettre à GTA Vice City .

[Atlantis]

t'inquiete pas si on participe pas plus, perso je lis attentivement tes textes mais comme je m'y connais à peine (on va dire mm pas dutout çá simpliera ) participer au topic pour l'instant n'est pas vraiment d'actualité en ce qui me concerne

[fafaro]

t'inquiete pas si on participe pas plus, perso je lis attentivement tes textes mais comme je m'y connais à peine (on va dire mm pas dutout çá simpliera :8 ) participer au topic pour l'instant n'est pas vraiment d'actualité en ce qui me concerne

Ok, je continuerai bientôt alors. Si j'ai au moins un lecteur, ça vaut le coup.

[lorinc]

je lis aussi

même si je me fais discret, et que je comrends sans doute moins qu'Atlantis...

[Mars105]

hello,

je m'incruste un peut dans la discution...

tout d'abord merci fafaro, continue ça m'interesse ^^

et je commance par une question ou deux:

premièrement, je disposte de plusieurs machine relativement differentes et mon but est de faire un cluster (vous l'aurez deviné...) seulement j'ai un problème qui me tracace:

si j'utilise 5 machine, et quand dans ces 5 machine une est nétement moin puissante que les autre, par example 4 2ghz et un 100mhz, bon c'est exagéré mais admeton...

les 3 "gros" doivent attendre que le "petit" aye terminé sa tache avant de commancer les suivantes?

si c'est le cas ça imposerait des machines relativement équivalantes pour éviter les pertes de performances, si non ça peut être très interessent. par example deux troi grosse machines et 4-5 500mhz dans le tas ferait une belle differance pour un petit cluster.

deuxièment, je connait rien au fortan mais je code en C/C++ principalement, le partage des taches se fait "manuelement" ou c'est le serveur qui le fait tout seul, j'entend par là qu'on doit dans le programme dire quel operations seront traitée par d'autre cpus? a la façon d'un thread en quelque sorte.

merci encors

[fafaro]

Salut !

Bon, c'est une très bonne question, cette histoire d'hétérogénéité du cluster. Je reprends donc ton exemple de 4 pc 2GHz et 1 à 100MHz, et celui de la recherche du maximum en parallèle. Si tu ne fais pas gaffe, tu partages la liste de nombres en 5 parties de même taille. Et là, c'est le drame Le 100MHz se traîne, les 2GHz trouvent leur max, mais ils doivent absolument attendre que le 100MHz ait fini. C'est donc le 100MHz qui fixe la vitesse de calcul

Mais si on est un peu plus malin, on ne partage pas de façon équitable, et on donne beaucoup plus de boulot aux machines puissantes. Si tu donnes une liste de nombres 10 fois plus petite au 100MHz et qu'il recherche le max 10 fois plus lentement que les 2GHZ, tout le monde finit en même temps.

En résumé, il vaut mieux des machines à peu près équivalentes. Mais si ce n'est pas le cas, on peut s'en sortir en étant un peu rusé (mais ça demande plus de boulot).

Pour ta deuxième questions, la parallélisation se fait toujours à la main. C'est toi qui décide, par exemple, qu'une boucle du genre for(i=0;i<N;i++) g(i) = 0., doit être découpée. Tu utilises par exemple alors une fonction MPI, MPI_Comm_rank(communicateur, 〉),qui permet à chaque processus de connaître son numéro. Un communicateur est un ensemble de processus. Il en existe un par défaut, MPI_COMM_WORLD, qui contient tous les processus lancés dans l'application parallèle. Par exemple, si mon fichier d'application est le suivant

n0 -s h toto

n1 -s h toto1

n2 -s h toto2

n3 -s h toto2

(je lance l'exécutable toto sur un proc, toto1 sur un proc, et toto2 sur 2 procs différents), toto est le processus 0, toto1 le numero 1, toto2-n2 le numéro2 et toto2-n3 le numéro 3. Le communicateur MPI_COMM_WORLD est constitué de ces 4 processus. Si toto contient la ligne MPI_Comm_rank(MPI_COMM_WORLD, 〉), la variable rang va prendre la valeur 0 à l'exécution de la fonction. Si cette fonction est exécutée dans le processus toto1, rang sera égal à 1 (et ainsi de suite).

D'autre part, MPI_Comm_size(communicateur, &taille) te donne le nombre de processus dans un communicateurs.

Donc, je reprends. Tu utilises ces fonctions. Tu connais le numéro du processus et le nombre de processus. Et tu peux partager ta boucle de la façon suivante :

N_local = N/taille

for(i=rang*N_local;i<(rang+1)*N_local;i++) g(i) = 0.

Et le tour est joué. Le premier processus fait la première partie, le 2ème fait la suite, etc...

Donc les instructions de parallélisation s'écrivent explicitement dans le code. Ce n'est pas le compilateur qui fait le boulot pour vous.

Et c'est la même chose en Fortran, en C et en C++.

[Mars105]

donc il faut garder des cpu le plus semblable possible, a moin de bien partager.

le partage se fait a la main.

ce qui amène une autre question, il existe un moyen de connaitre le nombre de cpu dispo a un moment T?

ex: j'ai 10 CPU dans mon cluster, 1 CPU tombe en panne ou n'est simplement pas dispo pur une raison X, je lance mon prog et la suite je pense que tu a compris

mon but final est de travailer sur un cluster hétérogène, seulement si un CPU est un 64bit je n'aurait pas moyen d'utiliser les ext. 64 a moin de compiler mon prog en 64, mais là il ne marche plus sur les 32...

quéstion liée: a la compilation on a un executable par cpu?

[fafaro]

Salut,

Désolé de ne pas poursuivre régulièrement cette introduction à MPI. Je suis tout à fait débordé en ce moment, entre mon boulot et World of Warcraft, j'ai plus une minute de libre

Réponse à tes questions :

- Effectivement, des machines semblables, c'est préférable, et on fait le partage soit même (ça peut être automatisé, mais de toute façon c'est toi qui code le mécanisme de répartition)

- Lorsque tu lances le code, tu le lances sur un nombre défini de machines, donc tu sais sur combien de machine tu le lances. Et ton code le sait aussi, via la fonction MPI_Comm_size. Par contre, le MPI que j'utilise ne sait pas gérer les pannes, ce qui signifie que si une machine plante pendant l'exécution, tout est foutu. Ca m'est arrivé plusieurs fois, pour des calculs d'une semaine, et c'était pas la joie

- Comme je l'ai dit plus haut, tu peux lancer des exécutables différents sur des machines différentes. Si tu compiles toto.c avec des options différentes et que tu obtiens les exécutables toto1 et toto2, tu peux lancer toto1 sur une machine et toto2 sur l'autre machine a priori. Cependant, je n'ai pas fait le test avec des machines 32bits et 64bits, et ca rique de poser des problèmes au niveau des formats de données dans les messages (si tu envoies un entier 32 bits à un code 64bits, il faut faire attention à ce qu'il va recevoir).

Voilà, j'essaie de revenir bientôt !

[fcouturier44]

Salut

Comme je suis nouveau sur ce forum, je me présente.

François, 25 ans thésard en planétologie à Nantes.

Je suis tombé sur cette page car je faisais des rechreches sur MPI, et je dois avouer que j'ai eu quelques réponses aussi bien ce forum que dans la these de Fabrice.

Merci à tous

Fabrice, toi qui t'y connais, y a t-il d'autres sites à visiter pour appronfondir mes connaissances en MPI (j'ai vu le CINES, entre autre, c'est bien mais y a t-il autre chose ?)

Merci d'avance

François

[fafaro]

Salut,

Tout d'abord, je m'excuse de mon inactivité forcée sur le topic, je suis assez occupé en ce moment entre la préparation d'un séminaire, un voyage professionnel à Madrid la semaine prochaine et la rédaction de mon dossier de candidature aux postes de maîtres de conférences... À ce sujet, si je suis recruté à Nantes, je me ferai un plaisir de répondre de mon mieux à toutes tes questions

Tu peux aller jeter un oeil sur le site de l'IDRIS, dans la partie Cours de l'IDRIS / Supports de cours, il y a des choses très bien. Tu peux aussi jeter un oeil sur les liens de ma page, c'est ici !

Si tu as des questions plus précises, n'hésites pas. De mon côté, je vous parle de communications bloquantes et non bloquantes dès que j'en ai le temps.

Ciao

PS : Tu travailles dans le labo de Christophe Sotin ? Je me souviens de ses cours d'astro, c'était vraiment pas mal

[fcouturier44]

oui exact, et Xtof, c'est mon directeur de thèse

Je vois que toi aussi tu es passé à Nantes

On a surement du se croiser (toi étant en physique et moi en sciences de la Terre)

F.