Nous n'accepterons aucune responsabilit� pour toute information incorrecte pr�sente dans ce document, ni pour aucun des dommages qui pourraient en r�sulter.
Copyright © 1997 - 1998 Jacek Radajewski et Douglas Eadline. Le droit de distribuer et de modifier ce document est autoris� sous la licence GNU General Public License.
Jacek Radajewski a commenc� � travailler sur ce document en novembre 1997 et a �t� ensuite rejoint par Douglas Eadline. En quelques mois, le HOWTO Beowulf est devenu un document consistant, et en ao�t 1998, il a �t� d�coup� en trois: Beowulf HOWTO, Beowulf Architecture Design HOWTO, the Beowulf Installation and Administration HOWTO. La Version 1.0.0 de ce document a �t� soumise au Linux Documentation Project le 11 novembre 1998. Nous esp�rons que ce ne soit que le d�but de ce qui deviendra une documentation compl�te du Projet de Documentation Beowulf (Beowulf Documentation Project).
L'�criture du HOWTO Beowulf a �t� longue, et il est finalement complet gr�ce � de nombreuses personnes. Nous voudrions remercier celles qui suivent pour leur aide et leurs contributions � ce HOWTO:
Au fur et � mesure que les niveaux de performance et de commodit� des ordinateurs et des r�seaux augmentent, il devient de plus en plus facile de construire des syst�mes informatiques parall�les � partir de composants facilement disponibles, plut�t que de construire des processeurs sur de tr�s co�teux Superordinateurs. En fait, le rapport prix/performances d'une machine de type Beowulf est de trois � dix fois meilleur que celui des superordinateurs traditionnels. L'architecture Beowulf s'�chelonne bien, elle est facile � construire et vous ne payez que pour le mat�riel, puisque la pluspart des logiciels sont gratuits.
Ce HOWTO s'adresse aux personnes qui ont d�j� eu au moins des contacts avec le syst�me d'exploitation Linux. La connaissance de la technologie Beowulf ou d'un syst�me d'exploitation plus complexe et de concepts r�seaux n'est pas essentielle, mais des aper�us de la programmation parall�le sont bienvenus (apr�s tout, vous devez avoir de bonnes raisons de lire ce document). Ce HOWTO ne r�pondra pas � toutes les questions que vous pourriez vous poser au sujet de Beowulf, mais, esp�rons-le, vous donnera des id�es et vous guidera dans la bonne direction. Le but de ce HOWTO est de fournir des informations de base, des liens et des r�f�rences vers des documents plus approfondis.
Famed was this Beowulf: far flew the boast of him, son of Scyld, in the Scandian lands. So becomes it a youth to quit him well with his father's friends, by fee and gift, that to aid him, aged, in after days, come warriors willing, should war draw nigh, liegemen loyal: by lauded deeds shall an earl have honor in every clan. Beowulf est le po�me �pique le plus ancien en Anglais qui ait �t� conserv�. C'est l'histoire d'un h�ros d'une grande force et d'un grand courage qui a d�fait un monstre appel� Grendel. Voir l' Historique pour en savoir plus sur le h�ros Beowulf.
Il y a peut-�tre de nombreuses d�finitions de Beowulf, autant que de personnes qui construisent ou utilisent des Superordinateurs Beowulf. Certains disent qu'ils peuvent appeler leur syst�me Beowulf seulement s'il est construit de la m�me fa�on que la machine d'origine de la NASA. D'autres vont � l'extr�me inverse et appellent ainsi n'importe quel syst�me de stations qui ex�cutent du code parall�le. Ma d�finition d'un Beowulf se situe entre ces deux avis, et est fond�e sur de nombreuses contributions dans la liste de diffusion Beowulf.
Beowulf est une architecture multi-ordinateurs qui peut �tre utilis�e pour la programmation parall�le. Ce syst�me comporte habituellement un noeud serveur, et un ou plusieurs noeuds clients connect�s entre eux � travers Ethernet ou tout autre r�seau. C'est un syst�me construit en utilisant des composants mat�riels existants, comme tout PC capable de faire tourner Linux, des adaptateurs Ethernet standards, et des switches. Il ne contient aucun composant mat�riel propre et est ais�ment reproductible. Beowulf utilise aussi des �l�ments comme le syst�me d'exploitation Linux, Parallel VirtualMachine (PVM) et Message Passing Interface (MPI). Le noeud serveur contr�le l'ensemble du cluster et sert de serveur de fichiers pour les noeuds clients. Il est aussi la console du cluster et la passerelle (gateway) vers le monde ext�rieur. De grandes machines Beowulf peuvent avoir plus d'un noeud serveur, et �ventuellement aussi d'autres noeuds d�di�s � des t�ches particuli�res, par exemple comme consoles ou stations de surveillance. Dans de nombreux cas, les noeuds clients d'un syst�me Beowulf sont idiots (dumb): plus ils sont idiots, mieux ils sont. Les noeuds sont configur�s et contr�l�s par le noeud serveur, et ne font que ce qu'on leur demande de faire. Dans une configuration client sans disque (diskless), les noeuds clients ne connaissent m�me pas leur adresse IP ou leur nom jusqu'� ce que le serveur leur dise qui ils sont. Une des principales diff�rences entre Beowulf et un Cluster de Stations de travail (COW) est le fait que Beowulf se comporte plus comme une simple machine plut�t que comme plusieurs stations de travail. Dans de nombreux cas, les noeuds clients n'ont pas de claviers ni de moniteurs, et on n'y acc�de que par une connection distante ou par un terminal s�rie. Les noeux Beowulf peuvent �tre envisag�s comme un CPU + des ensembles de m�moires qui peuvent �tre branch�s dans le cluster, exactement comme un CPU ou un module m�moire peut �tre branch� dans une carte m�re.
Beowulf n'est pas un ensemble de mat�riels sp�cialis�s, une nouvelle
topologie r�seau ou le dernier hack du kernel. Beowulf est une technologie de
clustering d'ordinateurs Linux pour former un superordinateur parall�le,
virtuel. M�me s'il y a de nombreux paquetages comme des patches du noyau, PVM,
les librairies MPI, et des outils de configuration qui rendent l'architecture
Beowulf plus rapide, plus facile � configurer, et plus facilement utilisable, on
peut construire une machine de classe Beowulf en utilisant une distribution
Standard de Linux sans ajouter d'autres logiciels. Si vous avez deux Linux en
r�seau qui partagent au moins le m�me syst�me de fichier racine via
NFS, et qui se font confiance pour ex�cuter des sessions distantes (rsh), alors
on peut dire que vous avez un simple Beowulf de deux noeuds.
Les syst�mes Beowulf ont �t� construits � partir de nombreux constituants. Pour des consid�rations de performances, des composants moins communs (i.e. produits par un seul fabricant) ont �t� utilis�s. Afin de recenser les diff�rents types de syst�mes et de rendre les discussions au sujet des machines un peu plus faciles, nous proposons la m�thode simple de classification suivante:
CLASSE I BEOWULF:
Cette classe concerne des machines faites d'�l�ments globalement disponibles. Nous devrons utiliser les tests de certification "Computer Shopper" pour d�finir les composants d'assemblage. ("Computer Shopper" est un mensuel sur les PC et leurs composants.) [NdT: US seulement ; pour un �quivalent, on peut �voquer par exemple "PC Direct".] Le test est le suivant:
Un Beowulf CLASSE I est une machine qui peut �tre assembl�e � partir de pi�ces trouv�es dans au moins quatre journaux de publicit� de grande diffusion.
Les avantages des syst�mes de CLASS I sont:
Les d�savantages d'un syst�me de CLASSE I sont:
CLASSE II BEOWULF
Un Beowulf CLASSE II Beowulf est simplement une machine qui ne passe pas le test de certification "Computer Shopper". Ce n'est pas une mauvaise chose. D'autre part, il s'agit plut�t d'une classification de la machine.
Les avantages d'un syst�me de CLASSE II sont:
Les d�savantages des syst�mes de CLASSE II sont:
Une CLASSE n'est pas n�cessairement meilleure qu'une autre. Cela d�pend surtout de vos besoins et de votre budget. Cette classification des syst�mes sert seulement � rendre les discussions sur les syst�mes Beowulf un peu plus succintes. La "Conception du Syst�me" peut aider � d�terminer quelle sorte de syst�me est le plus appropri� � vos besoins.
Je pense que la meilleure fa�on de d�crire l'architecture d'un superordinateur
Beowulf est d'utiliser un exemple qui est tr�s proche du vrai Beowulf, mais
aussi familier � beaucoup d'administrateurs syst�mes. L'exemple le plus proche
d'une machine Beowulf est un Unix de laboratoire avec un serveur et un certain
nombre de clients. Pour �tre plus sp�cifique, j'utiliserai le DEC Alpha au
laboratoire d'informatique de la Facult� des Sciences de l'USQ comme exemple. Le
serveur est appel� beldin et les machines clientes sont
scilab01, scilab02, scilab03, jusqu'�
scilab20. Tous les clients ont une copie locale du syst�me
d'exploitation Digital Unix 4.0 install�, mais ont l'espace disque utilisateur
(/home) et /usr/local du serveur via NFS (Network File
System). Chaque client a une entr�e pour le serveur et tous les autres clients
dans son fichier /etc/hosts.equiv: ainsi tous les clients peuvent
ex�cuter une cession distante (rsh) vers tout autre. La machine serveur est un
serveur NIS pour tout le laboratoire, ainsi les informations des comptes sont
les m�mes sur toutes les machines. Une personne peut s'asseoir � la console de
scilab02, se logue, et a le m�me environnement que s'il �tait logu� sur
le serveur, ou scilab15. La raison pour laquelle les clients ont la
m�me pr�sentation est que le syst�me d'exploitation est install� et configur� de
la m�me fa�on sur toutes les machines, les espaces /home et
/usr/local sont physiquement sur le m�me serveur et les clients y
acc�dent via NFS. Pour plus d'informations sur NIS et NFS, reportez-vous �
NIS et
NFS.
Maintenant que nous avons une vision correcte de l'architecture du syst�me,
regardons comment nous pouvons utiliser les cycles CPU des machines
dans le laboratoire. Toute personne peut se loguer sur n'importe
laquelle des machines, et lancer un programme dans son r�pertoire
de base, mais peut aussi �clater la m�me t�che sur diff�rentes
machines simplement en ex�cutant un shell distant. Par exemple, si
nous voulons calculer la somme des racines carr�es de tous les entiers
inclus strictement entre 1 et 10, nous �crivons un simple programme appel�
sigmasqrt (voir
code source) qui fait cela exactement. Pour
calculer la somme des racines carr�es des nombres de 1 � 10, nous
ex�cutons :
[jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 10 22.468278 real 0m0.029s user 0m0.001s sys 0m0.024sLa commande
time nous permet de v�rifier le temps mis
en ex�cutant cette t�che. Comme nous pouvons le voir, cet exemple
a pris seulement une petite fraction de seconde (0.029 sec) pour s'ex�cuter,
mais que se passe-t-il si je veux ajouter la racine carr�e des entiers de 1
� 1 000 000 000 ?
Essayons ceci, et calculons le temps �coul�:
[jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 1000000000 21081851083600.559000 real 16m45.937s user 16m43.527s sys 0m0.108s
Cette fois, le temps d'ex�cution de ce programme est consid�rablement sup�rieur. La question �vidente qui se pose est: est-il possible de diminuer le temps d'ex�cution de cette t�che et comment ? La r�ponse �vidente est de d�couper la t�che en un ensemble de sous-t�ches et d'ex�cuter ces sous-t�ches en parall�le sur tous les ordinateurs. Nous pouvons s�parer la grande t�che d'addition en 20 parties en calculant un intervalle de racines carr�es et en les additionnant sur un seul noeud. Quand tous les noeuds ont fini les calculs et retournent leurs r�sultats, les 20 nombres peuvent �tre additionn�s ensemble et fournir la solution finale. Avant de lancer ce processus, nous allons cr�er un "named pipe" qui sera utilis� par tous les processus pour �crire leurs r�sultats:
[jacek@beldin sigmasqrt]$ mkfifo output [jacek@beldin sigmasqrt]$ ./prun.sh & time cat output | ./sum [1] 5085 21081851083600.941000 [1]+ Done ./prun.sh real 0m58.539s user 0m0.061s sys 0m0.206s
Cette fois, cela prend 58.5 secondes. C'est le temps qui a �t� n�cessaire entre le d�marrage du processus et le moment o� les noeuds ont fini leurs calculs et �crit leurs r�sultats dans la pipe. Ce temps n'inclut pas l'addition finale des 20 nombres, mais il repr�sente une petite fraction de seconde et peut �tre ignor�. Nous pouvons voir qu'il y a un avantage significatif � ex�cuter une t�che en parall�le. En fait la t�che en parall�le s'est ex�cut�e 17 fois plus vite, ce qui est tr�s raisonnable pour un facteur 20 d'augmentation du nombre de CPU. Le but de l'exemple pr�c�dent est d'illustrer la m�thode la plus simple de parall�liser du code concurrent. En pratique, des exemples aussi simples sont rares et diff�rentes techniques (les API de PVM et PMI) sont utilis�es pour obtenir le parall�lisme.
Le laboraroire d'informatique d�crit plus haut est un exemple parfait d'un cluster de stations (COW). Qu'est-ce qui rend donc Beowulf si sp�cial et en quoi diff�re-t-il d'un COW ? En r�alit� il n'y a pas beaucoup de diff�rence, mais un Beowulf a quelques caract�ristiques uniques. La premi�re est que dans la plupart des cas, les noeuds clients dans un cluster Beowulf n'ont pas de clavier, de souris, de carte graphique ni de moniteur. Tous les acc�s aux noeuds clients sont faits par une connection distante du noeud serveur, un noeud d�di� � une console, ou une console s�rie. Cela parce qu'il n'y a aucun besoin pour un noeud client d'acc�der � des machines en dehors du cluster, ni pour des machines en dehors du cluster d'acc�der � des noeuds clients directement; c'est une pratique habituelle que les noeuds clients utilisent des adresses IP priv�es comme les plages d'adresses 10.0.0.0/8 ou 192.168.0.0/16 (RFC 1918 http://www.alternic.net/rfcs/1900/rfc1918.txt.html). D'habitude la seule machine qui est aussi connect�e au monde externe en utilisant une seconde carte r�seau est le noeud serveur. La fa�on la plus habituelle d'acc�der au syst�me est soit d'utiliser la console du serveur directement, soit de faire un telnet ou un login distant (rlogin) sur le noeud serveur d'une station personnelle. Une fois sur celui-ci, les utilisateurs peuvent �diter et compiler leur code, et aussi distribuer les t�ches sur tous les noeuds du cluster. Dans la plupart des cas, les COW sont utilis�es pour des calculs parall�les la nuit et les week-ends, quand les stations ne sont pas utilis�es pendant les journ�es de travail, utilisant ainsi les p�riodes de cycles libres des CPU. D'autre part, le Beowulf est une machine d�di�e au calcul parall�le, et optimis�e pour cette t�che. Il donne aussi un meilleur rapport prix/performance puisqu'il est constitu� de composants grand public et qu'il tourne principalement � partir de logiciels libres. Beowulf donne aussi davantage l'image d'une seule machine, ce qui permet aux utilisateurs de voir le cluster Beowulf comme une seule station de calcul.
Avant d'acheter du mat�riel, il serait de bon aloi de consid�rer le design de votre syst�me. Il y a deux approches mat�rielles qui sont impliqu�es dans le design d'un syst�me Beowulf: le type de noeuds ou d'ordinateurs que vous allez utiliser, et la m�thode que vous allez utiliser pour vous connecter aux noeuds d'ordinateurs. Il n'y a qu'une seule approche logicielle qui puisse affecter votre choix mat�riel: la librairie de communication ou API. Une discussion plus d�taill�e sur le mat�riel et les logiciels de communication est fournie plus loin dans ce document.
Alors que le nombre de choix n'est pas grand, il y a des consid�rations de conception qui doivent �tre prises pour la construction d'un cluster Beowulf. La science (ou art) de la "programmation parall�le" �tant l'objet de nombreuses interpr�tations, une introduction est fournie plus bas. Si vous ne voulez pas lire les connaissances de base, vous pouvez survoler cette section, mais nous vous conseillons de lire la section Convenance avant tout choix d�fninitif de mat�riel.
Cette section fournit des informations g�n�rales sur les concepts de la programmation parall�le. Ceci n'est PAS exhaustif, ce n'est pas une description compl�te de la programmation parall�le ou de sa technologie. C'est une br�ve description des enjeux qui peuvent influer fortement sur le concepteur d'un Beowulf, ou sur son utilisateur.
Lorsque vous d�ciderez de construire votre Beowulf, de nombreux points d�crits plus bas deviendront importants dans votre processus de choix. A cause de la nature de ses "composants", un Superordinateur Beowulf n�cessite de prendre de nombreux facteurs en compte, car maintenant ils d�pendent de nous. En g�n�ral, il n'est pas du tout difficile de comprendre les objectifs impliqu�s dans la programmation parall�le. D'ailleurs, une fois que ces objectifs sont compris, vos attentes seront plus r�alistes, et le succ�s plus probable. Contrairement au "monde s�quentiel", o� la vitesse du processeur est consid�r�e comme le seul facteur important, la vitesse des processeurs dans le "monde parall�le" n'est que l'un des param�tres qui d�termineront les performances et l'efficacit� du syst�me dans son ensemble.
La programmation parall�le peut prendre plusieurs formes. Du point de vue de l'utilisateur, il est important de tenir compte des avantages et inconv�nients de chaque m�thodologie. La section suivante tente de fournir quelques aper�us sur les m�thodes de programmation parall�le et indique o� la machine Beowulf fait d�faut dans ce continuum.
R�pondre � cette question est important. Utiliser 8 CPU pour lancer un traitement de texte sonne comme "trop inutile" -- et ce l'est. Et qu'en est-il pour un serveur web, une base de donn�es, un programme de ray-tracing, ou un planificateur de projets ? Peut-�tre plus de CPU peuvent-ils am�liorer les performances. Mais qu'en est-il de simulations plus complexes, de la dynamique des fluides, ou d'une application de Fouille de Donn�es (Data Mining) ? Des CPU suppl�mentaires sont absolument n�cessaires dans ces situations. D'ailleurs, de multiples CPU sont utilis�s pour r�soudre de plus en plus de probl�mes.
La question suivante est habituellement: "Pourquoi ai-je besoin de deux ou quatre CPU ? Je n'ai qu'� attendre le m�ga super rapide processeur 986." Il y a de nombreuses raisons:
Si vous avez besoin de vitesse -- � cause d'un probl�me li� au calcul et/ou aux entr�es/sorties --, il vaut la peine de consid�rer l'approche parall�le. Comme le calcul parall�le est impl�ment� selon de nombreuses voies, r�soudre votre probl�me en parall�le n�cessitera de prendre quelques d�cisions importantes. Ces d�cisions peuvent affecter dramatiquement la protabilit�, la performance, et le co�t de votre application.
Avant d'�tre par trop technique, regardons un vrai "probl�me de calcul parall�le" en utilisant un exemple qui nous est familier: faire la queue � une caisse.
Consid�rons un grand magasin avec 8 caisses regroup�es devant le magasin. Imaginons que chaque caisse est un CPU et chaque client un programme informatique. La taille du programme (quantit� de calcul) est la taille de la commande de chaque client. Les analogies suivantes peuvent �tre utilis�es pour illustrer les concepts de la programmation parall�le:
Une caisse ouverte (et en service) qui ne peut traiter qu'un client � la fois.
Exemple en Informatique : MS DOS
Une caisse ouverte, mais maintenant nous pouvons traiter une partie de chaque commande � un instant donn�, aller � la personne suivante et traiter une partie de sa commande. Tout le monde "semble" avancer dans la queue en m�me temps, mais s'il n'y a personne dans la queue, vous serez servi plus vite.
Exemple en Informatique : UNIX, NT avec un seul CPU
Maintenant on ouvre plusieurs caisses dans le magasin. Chaque commande peut �tre trait�e par une caisse diff�rente et la queue peut avancer plus vite. Ceci est appel� SMP - Gestion Multiple Sym�trique (Symmetric Multi-processing). M�me s'il y a plus de caisses ouvertes, vous n'avancerez pas plus vite dans la queue que s'il n'y avait qu'une seule caisse.
Exemple en Informatique : UNIX, NT avec plusieurs CPU
Si vous "s�parez" les objets de votre commande, vous pouvez �tre capable d'avancer plus vite en utilisant plusieurs caisses en m�me temps. D'abord, nous postulons que vous achetez une grande quantit� d'objets, parce que le temps que vous investirez pour "s�parer" votre commande doit �tre regagn� en utilisant plusieurs caisses. En th�orie, vous devriez �tre capables de vous d�placer dans la queue "n" fois plus vite qu'avant, o� "n" est le nombre de caisses. Quand les caissiers ont besoin de faire des sous-totaux, ils peuvent �changer rapidement les informations visuellement et en discutant avec toutes les autres caisses "locales". Ils peuvent aussi aller chercher directement dans les registres des autres caisses pour trouver les informations dont ils ont besoin pour travailler plus vite. La limite �tant le nombre de caisses qu'un magasin peut effectivement installer.
La loi de Amdals montre que l'acc�l�ration de l'application est li�e � la portion s�quentielle la plus lente ex�cut�e par le programme (NdT: i.e. major�e par la t�che la plus lente).
Exemple en Informatique : UNIX ou NT avec plusieurs CPU sur la m�me carte-m�re avec des programmes multi-threads.
De fa�on � am�liorer la performance, la Direction ajoute 8 caisses � l'arri�re du magasin. Puisque les nouvelles caisses sont loin du devant du magasin, les caissiers doivent t�l�phoner pour envoyer leurs sous-totaux vers celui-ci. La distance ajoute un d�lai suppl�mentaire (en temps) dans la communication entre caissiers, mais si la communication est minimis�e, cela ne pose pas de probl�me. Si vous avez vraiment une grosse commande, une qui n�cessite toutes les caisses, alors comme avant votre vitesse peut �tre am�lior�e en utilisant toutes les caisses en m�me temps, le temps soppl�mentaire devant �tre pris en compte. Dans certains cas, le magasin peut n'avoir que des caisses (ou des �lots de caisses) localis�s dans tout le magasin : chaque caisse (ou �lot) doit communiquer par t�l�phone. Puisque tous les caissiers peuvent discutter par t�l�phone, leur emplacement importe peu.
Exemple en Informatique : Une ou plusieurs copies d'UNIX ou NT avec plusieurs CPU sur la m�me, ou diff�rentes cartes-m�res communiquant par messages.
Les sc�narios pr�c�dents, m�me s'ils ne sont pas exacts, sont une bonne repr�sentation des contraintes qui agissent sur les syst�mes parall�les. Contrairement aux machines avec un seul CPU (ou caisse), la communication est importante.
Les m�thodes et architectures habituelles de la programmation parall�le sont repr�sent�es ci-dessous. M�me si cette description n'est en aucun cas exhaustive, elle est suffisante pour comprendre les imp�ratifs de base dans la conception d'un Beowulf.
Il y a typiquement deux fa�ons d'assembler un ordinateur parall�le:
Un Beowulf typique est une collection de machines mono-processeurs connect�es utilisant un r�seau Ethernet rapide, et qui est ainsi une machine � m�moire locale. Une machine � 4 voies SMP est une machine � m�moire partag�e et peut �tre utilis�e pour du calcul parall�le -- les applications parall�les communiquant via la m�moire partag�e. Comme pour l'analogie du grand magasin, les machines � m�moire locale (donc � caisse individuelle) peuvent �tre scalairis�es jusqu'� un grand nombre de CPU ; en revanche, le nombre de CPU que les machines � m�moire partag�e peuvent avoir (le nombre de caisses que vous pouvez placer en un seul endroit) peut se trouver limit� � cause de l'utilisation (et/ou de la vitesse) de la m�moire.
Il est toutefois possible de connecter des machines � m�moire partag�e pour cr�er une machine � m�moire partag�e "hybride". Ces machines hybrides "ressemblent" � une grosse machine SMP pour l'utilisateur et sont souvent appel�es des machines NUMA (acc�s m�moire non uniforme) parce que la m�moire globale vue par le programmeur et partag�e par tous les CPU peut avoir diff�rents temps d'acc�s. A un certain niveau d'ailleurs, une machine NUMA doit "passer des messages" entre les groupes de m�moires partag�es.
Il est aussi possible de connecter des machines SMP en tant que noeuds de m�moire locale. Typiquement, les cartes-m�res de CLASSE I ont soit 2 ou 4 CPU et sont souvent utilis�es comme moyens pour r�duire le co�t global du syst�me. L'arrangeur (scheduler) interne de Linux d�termine combien de ces CPU sont partag�s. L'utilisateur ne peut (� ce jour) affecter une t�che � un processeur SMP sp�cifique. Cet utilisateur peut quand m�me d�marrer deux processus ind�pendants ou un programme multi-threads et s'attendre � voir une am�lioration de performance par rapport � un syst�me � simple CPU.
Il y a basiquement deux fa�ons d'"exprimer" la concurrence dans un programme:
D'autres m�thodes existent, mais celles-l� sont le plus g�n�ralement employ�es. Il est important de se souvenir que l'expression de concurrence n'est pas n�cessairement contr�l�e par la couche mat�rielle. Les Messages et les Threads peuvent �tre impl�ment�s sur des SMPn NUMA-SMP, et clusters -- m�me si, comme expliqu� ci-dessous, l'efficacit� et la portabilit� sont des facteurs importants.
Historiquement, la technologie de passage de messages refl�tait les d�buts des ordinateurs parall�les � m�moire locale. Les messages n�cessitent la copie des donn�es tandis que les Threads utilisent des donn�es � la place. Le temps de latence et la vitesse � laquelle les messages peuvent �tre copi�s sont les facteurs limitants des mod�les de passage de messages. Un message est assez simple: des donn�es et un processeur de destination. Des API de passage de messages r�pandues sont entre autres PVM ou MPI. Le passage de Messages peut �tre impl�ment� avec efficacit� en utilisant ensemble des Threads et des Messages entre SMP et machines en cluster. L'avantage d'utiliser les messages sur une machine SMP, par rapport aux Threads, est que si vous d�cidez d'utiliser des clusters dans le futur, il est facile d'ajouter des machines ou de scalairiser vos applications.
Les Threads ont �t� d�velopp�s sur les syst�mes d'exploitation parce que la m�moire partag�e des SMP (moutiprocessorage symm�trique) permettait une communication tr�s rapide et une synchronisation de la m�moire partag�e entre les parties d'un programme. Les Threads marchent bien sur les syst�mes SMP parce que la communication a lieu � travers la m�moire partag�e. Pour cette raison, l'utilisateur doit isoler les donn�es locales des donn�es globales, sinon les programmes ne fonctionneront pas correctement. Cela est en contraste avec les messages: une grande quantit� de copie peut �tre �limin�e avec les threads car les donn�es sont partag�es entre les processus (threads). Linux impl�mente les Threads POSIX. Le probl�me avec les Threads vient du fait qu'il est difficile de les �tendre au-del� d'une machine SMP, et, comme les donn�es sont partag�es entre les CPU, la gestion de la coh�rence du cache peut contribuer � le charger. Etendre les Threads au-del� des limites des performances des SMP n�cessite la technologie NUMA qui est ch�re et n'est pas nativement support�e par Linux. Impl�menter des Threads par dessus les messages a �t� fait ( (http://syntron.com/ptools/ptools_pg.htm)), mais les Threads sont souvent inefficients une fois impl�ment�s en utilisant des messages.
On peut r�sumer ainsi les performances:
performance performance
machine SMP cluster de machines scalabilit�
----------- ------------------- -----------
messages bonne meilleure meilleure
threads meilleure mauvaise* mauvaise*
* n�cessite une technologie NUMA co�teuse.
Pour ex�cuter une application en parall�le sur des CPU multiples, celle-ci doit �tre explicitement d�coup�e en parties concurrentes. Une application standard mono-CPU ne s'ex�cutera pas plus rapidement m�me si elle est ex�cut�e sur une machine multi-processeurs. Certains outils et compilateurs peuvent d�couper les programmesn mais la parall�lisation n'est pas une op�ration "plug and play". Suivant l'application, la parall�lisation peut �tre facile, extr�mement difficile, voire impossible suivant les contraintes de l'algorithme.
Avant de parler des besoins applicatifs, il nous faut introduire le concept de Convenance (Suitability).
Beaucoup de questions au sujet du calcul parall�le ont la m�me r�ponse:
"Cela d�pend enti�rement de l'application."
Avant de passer directement aux opportunit�s, il y a une distinction tr�s importante qui doit �tre faite: la diff�rence entre CONCURRENT et PARALLELE. Pour clarifier cette discussion, nous allons d�finir ces deux termes ainsi:
les parties CONCURRENTES d'un programme sont celles qui peuvent �tre calcul�es ind�pendamment.
Les parties PARALLELES d'un programme sont celles qui sont ex�cut�es sur des �l�ments de calculs au m�me moment.
La distinction est tr�s importante, parce que la CONCURRENCE est une propri�t� d'un programme et l'efficacit� en PARALLELISME est une propri�t� de la machine. Id�alement, l'ex�cution en parall�le doit produire des performances plus grandes. Le facteur limitant les performances en parall�le est la vitesse de communication et le temps de latence entre les noeuds de calcul. (Le temps de latence existe aussi dans les applications TMP thread�es � cause de la coh�rence du cache). De nombreux tests de performances communs sont hautement parall�les, et ainsi la communication et le temps de latence ne sont pas les points importants. Ce type de probl�me peut �tre appel� "�videmment parall�le". D'autres applications ne sont pas si simples et ex�cuter des parties CONCURRENTES du programme en PARALLELE peut faire en sorte que le programme fonctionne plus lentement, et ainsi d�caler toute performance de gain dans d'autres parties CONCURRENTES du programme. En termes plus simples, le co�t en temps de communication doit en p�tir au profit de celui gagn� en temps de calcul, sinon l'ex�cution PARALLELE des parties CONCURRENTES est inefficace.
La t�che du programmeur est de d�terminer quelles parties CONCURRENTES le programmeur DOIT ex�cuter en PARALLELE et pour quelles parties il NE DOIT PAS le faire. Sa r�ponse d�terminera l'EFFICACITE de l'application. Le graphe suivant r�sume la situation pour le programmeur:
| *
| *
| *
% des | *
appli- | *
cations | *
| *
| *
| *
| *
| *
| ****
| ****
| ********************
+-----------------------------------
temps de communication/temps de calcul
Dans un ordinateur parall�le parfait, le rapport communication/calcul devrait �tre �gal et tout ce qui est CONCURRENT pourrait �tre impl�ment� en PARALLELE. Malheureusement, les vrais ordinateurs parall�les, incluant les machines � m�moire partag�e, sont sujets aux effets d�crits dans ce graphe. En concevant un Beowulf, l'utilisateur devrait garder celui-ci en t�te parce que la performance d�pend du rapport entre le temps de communication et le temps de calcul pour un ORDINATEUR PARALLELE SPECIFIQUE. Les applications peuvent �tre portables entre les ordinateurs parall�les, mais il n'y a aucune garantie qu'elles seront efficaces sur une plateforme diff�rente.
EN GENERAL, IL N'EXISTE PAS DE PROGRAMME PORTABLE EFFICACE EN PARALLELE
Il y a encore une autre cons�quence au graphe pr�c�dent. Puisque l'efficacit� d�pend du rapport communication/calcul, changer juste un composant du rapport ne signifie pas n�cessairement qu'une application s'ex�cutera plus rapidement. Un changement de vitesse processeur, en gardant la m�me vitesse de communication, peut avoir des effets inattendus sur votre programme. Par exemple, doubler ou tripler la vitesse du processeur, en gardant la m�me vitesse de communication, peut maintenant rendre des parties de votre programme qui sont efficaces en PARALLELE, plus efficaces si elles �taient ex�cut�es SEQUENTIELLEMENT. Cela dit, il se peut qu'il soit plus rapide maintenant d'ex�cuter les parties qui �taient avant PARALLELES en tant que SEQUENTIELLES. D'autant plus qu'ex�cuter des parties inefficaces en PARALLELE emp�chera votre application d'atteindre sa vitesse maximale. Ainsi, en ajoutant un processeur plus rapide, vous avez peut-�tre ralenti votre application (vous enp�chez votre nouveau CPU de fonctionner � sa vitesse maximale pour cette application).
UPGRADER VERS UN CPU PLUS RAPIDE PEUT REELLEMENT RALENTIR VOTRE APPLICATION
Donc, en conclusion, pour savoir si oui ou non vous pouvez utiliser un environnement mat�riel parall�le, vous devez avoir un bon aper�u des capacit�s d'une machine particuli�re pour votre application. Vous devez tenir compte de beaucoup de facteurs: vitesse de la CPU, compilateur, API de passage de messages, r�seau... Notez que se contenter d'optimiser une application ne donne pas toutes les informations. Vous pouvez isoler une lourde partie de calcul de votre programme, mais ne pas conna�tre son co�t au niveau de la communication. Il se peut que pour un certain syst�me, le co�t de communication ne rende pas efficace de parall�liser ce code.
Une note finale sur une erreur commune: on dit souvent qu'"un programme est PARALLELISE", mais en r�alit� seules les parties CONCURRENTES ont �t� identifi�es. Pour toutes les raisons pr�c�dentes, le programme n'est pas PARALLELISE. Une PARALLELISATION efficace est une propri�t� de la machine.
A partir du mmoment o� vous avez d�cid� de concevoir et de construire un Beowulf, consid�rer un instant votre application en accord avec les observations pr�c�dentes est une bonne id�e.
En g�n�ral, vous pouvez faire deux choses:
Dans chaque cas, vous devrez consid�rer les besoins en efficacit�. En g�n�ral, il y a trois choses � faire:
Examinons-les successivement:
Cette �tape est couvent consid�r�e comme "parall�liser votre programme". Les d�cisions de parall�lisation seront faites � l'�tape 2. Dans cette �tape, vous avez besoin de d�terminer les liens et les besoins dans les donn�es.
D'un point de vue pratique, les applications peuvent pr�senter deux types de concurrence: calcul (travaux num�riques) et E/S (Bases de Donn�es). M�me si dans de nombreux cas, la concurrence entre calculs et E/S est orthogonale, des applications ont besoin des deux. Des outils existants peuvent faire l'analyse de la concurrence sur des applications existantes. La plupart de ces outils sont con�us pour le FORTRAN. Il y a deux raisons pour lesquelles le FORTRAN est utilis�: historiquement, la majorit� des applications gourmandes en calculs num�riques �taient �crites en FORTRAN et c'�tait donc plus facile � analyser. Si aucun de ces outils n'est disponible, alors cette �tape peut �tre quelque peu difficile pour des applications existantes.
Sans l'aide d'outils, cette �tape peut n�cessiter un cycle de tests et erreurs, ou seulement de bons vieux r�flexes bien �duqu�s. Si vous avez une application sp�cifique en t�te, essayez de d�terminer la limite du CPU (li�e au calcul) ou les limites des disques (li�es aux E/S). Les sp�cifit�s de votre Beowulf peuvent beaucoup d�pendre de vos besoins. Par exemple, un probl�me li� au calcul peut ne n�cessiter qu'un petit nombre de CPU tr�s rapides et un r�seau tr�s rapide � faible temps de latence, tandis qu'un probl�me li� aux E/S peut mieux travailler avec des CPU plus lents et un Ethernet rapide.
Cette recommandation arrive souvent comme une surprise pour beaucoup, la croyance habituelle �tant que plus le processeur est rapide, mieux c'est. Mais cela n'est vrai que si vous avez un budget illimit�: les vrais syst�mes peuvent avoir des contraintes de co�ts qui doivent �tre optimis�es. Pour les probl�mes li�s aux E/S, il existe une loi peu connue (appel�e la loi de Eadline-Dedkov) qui est assez utile:
Soient deux machines parall�les avec le m�me index de performance CPU cumul�e, celle qui a les processeurs les plus lents (et probablement un r�seau de communication interprocesseur plus lent) aura les meilleures performances pour des applications domin�es par les E/S.
M�me si les preuves de cette r�gle vont au-del� de ce document, vous pouvez trouver int�ressant de lire l'article Performance Considerations for I/O-Dominant Applications on Parallel Computers (format Postscript 109K) (ftp://www.plogic.com/pub/papers/exs-pap6.ps)
Une fois que vous aurez d�termin� quel type de concurrence vous avez dans votre application, vous devrez estimer � quel point elle sera efficace en parall�le. Voir la Section Logiciels pour une description des outils Logiciels.
En l'absence d'outils, il vous faudra peut-�tre improviser votre chemin lors de cette �tape. Si une boucle li�e aux calculs est mesur�e en minutes et que les donn�es peuvent �tre transf�r�es en secondes, alors c'est un bon candidat pour la parall�lisation. Mais souvenez-vous que si vous prenez une boucle de 16 minutes et la coupez en 32 morceaux, et que vos transferts de donn�es ont besoin de quelques secondes par partie, alors cela devient plus r�duit en termes de performances. Vous atteindrez un point de retours en diminution.
Il y a plusieurs fa�ons de d�crire les parties concurrentes de votre programme:
La diff�rence principale entre les deux est que le parall�lisme explicite est d�termin� parl'utilisateur, alors que le parall�lisme implicite est d�termin� par le compilateur.
Il y a principalement des m�thodes o� l'utilisateur peut modifier le code source sp�cifique pour une machine parall�le. L'utilisateur doit soit ajouter des messages en utilisant PVM ou MPI, soit ajouter des threads POSIX. (Souvenez vous que les threads ne peuvent se d�placer entre les cartes-m�res SMP).
Les m�thodes explicites tendent � �tre les plus difficiles � impl�menter et � d�boguer. Les utilisateurs ajoutent typiquement des appels de fonctions dans le code source FORTRAN 77 standard ou C/C++. La librairie MPI a ajout� des fonctions pour rendre certaines m�thodes parall�les plus faciles � impl�menter (i.e. les fonctions scatter/gather). De plus, il est aussi possible d'ajouter des librairies standard qui ont �t� �crites pour des ordinateurs parall�les. Souvenez-vous quand m�me du compromis efficacit�/portabilit�.
Pour des raisons historiques, beaucoup d'applications gourmandes en calculs sont �crites en FORTRAN. Pour cette raison, FORTRAN dispose du plus grand nombres de supports pour le calcul parall�le (outils, librairies ...). De nombreux programmeurs utilisent maintenant C ou r��crivent leurs applications FORTRAN existantes en C, avec l'id�e que C permettra une ex�cution plus rapide. M�me si cela est vrai puisque C est la chose la plus proche du code machine universel, il a quelques inconv�nients majeurs. L'utilisation de pointeurs en C rend la d�termination des d�pendances entre donn�es et l'analyse automatique des pointeurs extr�mement difficiles. Si vous avez des applications existantes en FORTRAN et que vous voudrez les parall�liser dans le futur - NE LES CONVERTISSEZ PAS EN C !
Les m�thodes implicites sont celles dans lesquelles l'utilisateur abandonne quelques d�cisions de parall�lisation (ou toutes) au compilateur. Par exemple le FORTRAN 90, High Performance FORTRAN (HPF), Bulk Synchronous Parallel (BSP), et toute une s�rie de m�thodes qui sont en cours de d�veloppement.
Les m�thodes implicites n�cessitent de la part de l'utilisateur des informations concernant la nature concurrente de leur application, mais le compilateur prendra quand m�me beaucoup de d�cicions sur la mani�re d'ex�cuter cette concurrence en parall�le. Ces m�thodes procurent un niveau de portabilit� et d'efficacit�, mais il n'y a pas de "meilleure fa�on" de d�crire un probl�me concurrent pour un ordinateur parall�le.
/* Jacek Radajewski jacek@usq.edu.au */
/* 21/08/1998 */
#include <stdio.h>
#include <math.h>
int main (void) {
double result = 0.0;
double number = 0.0;
char string[80];
while (scanf("%s", string) != EOF) {
number = atof(string);
result = result + number;
}
printf("%lf\n", result);
return 0;
}
/* Jacek Radajewski jacek@usq.edu.au */
/* 21/08/1998 */
#include <stdio.h>
#include <math.h>
int main (int argc, char** argv) {
long number1, number2, counter;
double result;
if (argc < 3) {
printf ("usage : %s number1 number2\n",argv[0]);
exit(1);
} else {
number1 = atol (argv[1]);
number2 = atol (argv[2]);
result = 0.0;
}
for (counter = number1; counter <= number2; counter++) {
result = result + sqrt((double)counter);
}
printf("%lf\n", result);
return 0;
}
#!/bin/bash # Jacek Radajewski jacek@usq.edu.au # 21/08/1998 export SIGMASQRT=/home/staff/jacek/beowulf/HOWTO/example1/sigmasqrt # $OUTPUT doit �tre un canal nomm� (named pipe) # mkfifo output export OUTPUT=/home/staff/jacek/beowulf/HOWTO/example1/output rsh scilab01 $SIGMASQRT 1 50000000 > $OUTPUT < /dev/null& rsh scilab02 $SIGMASQRT 50000001 100000000 > $OUTPUT < /dev/null& rsh scilab03 $SIGMASQRT 100000001 150000000 > $OUTPUT < /dev/null& rsh scilab04 $SIGMASQRT 150000001 200000000 > $OUTPUT < /dev/null& rsh scilab05 $SIGMASQRT 200000001 250000000 > $OUTPUT < /dev/null& rsh scilab06 $SIGMASQRT 250000001 300000000 > $OUTPUT < /dev/null& rsh scilab07 $SIGMASQRT 300000001 350000000 > $OUTPUT < /dev/null& rsh scilab08 $SIGMASQRT 350000001 400000000 > $OUTPUT < /dev/null& rsh scilab09 $SIGMASQRT 400000001 450000000 > $OUTPUT < /dev/null& rsh scilab10 $SIGMASQRT 450000001 500000000 > $OUTPUT < /dev/null& rsh scilab11 $SIGMASQRT 500000001 550000000 > $OUTPUT < /dev/null& rsh scilab12 $SIGMASQRT 550000001 600000000 > $OUTPUT < /dev/null& rsh scilab13 $SIGMASQRT 600000001 650000000 > $OUTPUT < /dev/null& rsh scilab14 $SIGMASQRT 650000001 700000000 > $OUTPUT < /dev/null& rsh scilab15 $SIGMASQRT 700000001 750000000 > $OUTPUT < /dev/null& rsh scilab16 $SIGMASQRT 750000001 800000000 > $OUTPUT < /dev/null& rsh scilab17 $SIGMASQRT 800000001 850000000 > $OUTPUT < /dev/null& rsh scilab18 $SIGMASQRT 850000001 900000000 > $OUTPUT < /dev/null& rsh scilab19 $SIGMASQRT 900000001 950000000 > $OUTPUT < /dev/null& rsh scilab20 $SIGMASQRT 950000001 1000000000 > $OUTPUT < /dev/null&