Beowulf HOWTO
Jacek Radajewski and Douglas Eadline (traduction : Emmanuel
PIERRE,
[email protected] )
v1.1.1, 22 Novembre 1998
Ce document est une introduction � l'architecture Beowulf Supercompu�
teur. Il fournit les informations de base sur la programmation par�
all�le, et inclut des liens vers des documents plus sp�cifiques et des
pages web.
______________________________________________________________________
Table des mati�res
1. Pr�ambule
1.1 Mise en garde
1.2 Copyright
1.3 Au sujet de ce HOWTO
1.4 Au sujet des auteurs
1.5 Remerciements
2. Introduction
2.1 A qui s'adresse ce HOWTO ?
2.2 Qu'est-ce que Beowulf ?
2.3 Classification
3. Aper�u de l'Architecture
3.1 A quoi cela ressemble-t-il ?
3.2 Comment utiliser les autres noeuds ?
3.3 En quoi un Beowulf diff�re-t-il d'un COW ?
4. Conception du Syst�me
4.1 Brefs rappels sur la programmation parall�le
4.2 Les m�thodes de programmation parall�le
4.2.1 Pourquoi plus d'un CPU ?
4.2.2 La "caisse" en programmation parall�le
4.2.2.1 Syst�mes d'exploitation Mono-T�che:
4.2.2.2 Syst�mes d'exploitation Multi-T�ches:
4.2.2.3 Syst�mes d'exploitation Multi-T�ches avec plusieurs CPU:
4.2.2.4 Sous-t�ches (Threads) sur les autres CPU d'un Syst�me d'exploitation Multi-T�ches:
4.2.2.5 Envoyer des messages sur des Syst�mes d'exploitation Multi-T�ches avec plusieurs CPU:
4.3 Architectures pour le calcul parall�le
4.3.1 Architectures Mat�rielles
4.3.2 Architectures Logicielles et API
4.3.2.1 Messages
4.3.2.2 Threads
4.3.3 Architecture des Applications
4.4 Convenance
4.5 Ecrire et porter des logiciels parall�les
4.5.1 D�terminer les parties concurrentes de votre programme
4.5.2 Estimer le parall�lisme efficacement
4.5.3 D�crire les parties concurrentes de votre programme
4.5.3.1 Les m�thodes explicites
4.5.3.2 M�thodes Implicites
5. Ressources Beowulf
5.1 Points de d�part
5.2 Documentation
5.3 Publications
5.4 Logiciels
5.5 Machines Beowulf
5.6 D'autres Sites Int�ressants
5.7 Histoire
6. Code Source
6.1 sum.c
6.2 sigmasqrt.c
6.3 prun.sh
______________________________________________________________________
11.. PPrr��aammbbuullee
11..11.. MMiissee eenn ggaarrddee
Nous n'accepterons aucune responsabilit� pour toute information
incorrecte pr�sente dans ce document, ni pour aucun des dommages qui
pourraient en r�sulter.
11..22.. CCooppyyrriigghhtt
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.
11..33.. AAuu ssuujjeett ddee ccee HHOOWWTTOO
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).
11..44.. AAuu ssuujjeett ddeess aauutteeuurrss
� Jacek Radajewski est Administrateur R�seau, et pr�pare un degr�
honorifique en Informatique � l'Universit� du Southern Queensland,
Australie. Le premier contact de Jacek avec Linux eut lieu en 1995
et il en tomba amoureux du premier coup. Jacek construisit son
premier cluster Beowulf en Mai 1997 et a jou� avec cette
technologie depuis, toujours � la recherche de la meilleure mani�re
de tout organiser. Vous pouvez joindre Jacek par courriel �
[email protected]
� Douglas Eadline, Ph.D. est le President et le Principal
Scientifique (Principal Scientist) � Paralogic, Inc., Bethlehem,
PA, USA. Form� en tant que Chimiste Physique/Analytique, il s'est
investi dans les ordinateurs depuis 1978, ann�e o� il a construit
sa premi�re machine pour l'utiliser avec l'instrumentation
chimique. A ujourd'hui, le Dr. Eadline s'int�resse � Linux, aux
clusters Beowulf, et aux algorithmes parall�les. Le Dr. Eadline
peut �tre joint par courriel �
[email protected]
11..55.. RReemmeerrcciieemmeennttss
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:
� Becky pour son amour, son soutien, et sa compr�hension.
� Tom Sterling, Don Becker, et les autres personnes de la NASA qui
furent � l'origine du projet Beowulf.
� Thanh Tran-Cong et la Faculty of Engineering and Surveying pour
avoir donn� la machine Beowulf _t_o_p_c_a_t pour les tests de Beowulf.
� Mon sup�rieur Christopher Vance pour de nombreuses bonnes id�es.
� Mon ami Russell Waldron pour de grandes id�es de programmation, son
int�r�t g�n�ral pour le projet, et son soutien.
� Mon ami David Smith pour la relecture de ce document.
� Et de nombreuses autres personnes sur la liste de diffusion Beowulf
qui nous ont fournis beaucoup de retour et d'id�es.
� Toutes les personnes qui sont responsables du syst�me
d'exploitation Linux et de tous les autres outils gratuits utilis�s
sur _t_o_p_c_a_t et les diverses machines Beowulf.
22.. IInnttrroodduuccttiioonn
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.
22..11.. AA qquuii ss''aaddrreessssee ccee HHOOWWTTOO ??
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.
22..22.. QQuu''eesstt--ccee qquuee BBeeoowwuullff ??
_F_a_m_e_d _w_a_s _t_h_i_s _B_e_o_w_u_l_f_: _f_a_r _f_l_e_w _t_h_e _b_o_a_s_t _o_f _h_i_m_, _s_o_n _o_f _S_c_y_l_d_, _i_n
_t_h_e _S_c_a_n_d_i_a_n _l_a_n_d_s_. _S_o _b_e_c_o_m_e_s _i_t _a _y_o_u_t_h _t_o _q_u_i_t _h_i_m _w_e_l_l _w_i_t_h _h_i_s
_f_a_t_h_e_r_'_s _f_r_i_e_n_d_s_, _b_y _f_e_e _a_n_d _g_i_f_t_, _t_h_a_t _t_o _a_i_d _h_i_m_, _a_g_e_d_, _i_n _a_f_t_e_r
_d_a_y_s_, _c_o_m_e _w_a_r_r_i_o_r_s _w_i_l_l_i_n_g_, _s_h_o_u_l_d _w_a_r _d_r_a_w _n_i_g_h_, _l_i_e_g_e_m_e_n _l_o_y_a_l_: _b_y
_l_a_u_d_e_d _d_e_e_d_s _s_h_a_l_l _a_n _e_a_r_l _h_a_v_e _h_o_n_o_r _i_n _e_v_e_r_y _c_l_a_n_. 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.
22..33.. CCllaassssiiffiiccaattiioonn
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:
� le mat�riel est disponible de noubreuses sources (faible co�t,
maintenance facile)
� ne d�pendant pas d'un seul vendeur de mat�riel
� support des drivers par les commodit�s Linux
� bas� habituellement sur des standards (SCSI, Ethernet, etc.)
Les d�savantages d'un syst�me de CLASSE I sont:
� de meilleures performances peuvent n�cessiter du mat�riel de CLASSE
II
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 performances peuvent �tre assez bonnes !
Les d�savantages des syst�mes de CLASSE II sont:
� le support des drivers peut varier
� reposent sur un seul vendeur de mat�riel
� peuvent �tre plus chers que les syst�mes de CLASSE I.
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.
33.. AAppeerr��uu ddee ll''AArrcchhiitteeccttuurree
33..11.. AA qquuooii cceellaa rreesssseemmbbllee--tt--iill ??
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� _b_e_l_d_i_n et les machines clientes sont _s_c_i_l_a_b_0_1,
_s_c_i_l_a_b_0_2, _s_c_i_l_a_b_0_3, jusqu'� _s_c_i_l_a_b_2_0. 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 _s_c_i_l_a_b_0_2, se
logue, et a le m�me environnement que s'il �tait logu� sur le serveur,
ou _s_c_i_l_a_b_1_5. 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.
33..22.. CCoommmmeenntt uuttiilliisseerr lleess aauuttrreess nnooeeuuddss ??
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.024s
La 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.
33..33.. EEnn qquuooii uunn BBeeoowwuullff ddiiffff��rree--tt--iill dd''uunn CCOOWW ??
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.
44.. CCoonncceeppttiioonn dduu SSyysstt��mmee
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.
44..11.. BBrreeffss rraappppeellss ssuurr llaa pprrooggrraammmmaattiioonn ppaarraallll��llee
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.
44..22.. LLeess mm��tthhooddeess ddee pprrooggrraammmmaattiioonn ppaarraallll��llee
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.
44..22..11.. PPoouurrqquuooii pplluuss dd''uunn CCPPUU ??
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:
1. Avec l'utilisation de syst�mes d'exploitations multi-t�ches, il est
possible de faire plusieurs choses en m�me temps. Cela est un
"parall�lisme" naturel qui est exploit� par plus d'un CPU de bas
prix.
2. La vitesse des processeurs double tous les 18 mois mais qu'en est-
il de la vitesse de la m�moire ? Malheureusement, celle-ci
n'augmente pas aussi vite que celle des processeurs. Gardez �
l'esprit que beaucoup d'applications ont besoin de m�moire autre
que celle du cache processeur et de l'acc�s disque. Faire les
choses en parall�le est une fa�on de contourner ces limitations.
3. Les pr�dictions indiquent que la vitesse des processeurs ne
continuera pas � doubler tous les 18 mois apr�s l'an 2005. Il y a
divers obstacles � surmonter pour maintenir ce rythme.
4. Suivant l'application, la programmation parall�le peut acc�l�rer
les choses de 2 � 500 fois (et m�me plus dans certains cas). De
telles performances ne sont pas disponibles sur un seul processeur.
M�me les Superordinateurs qui utilisaient � un moment un seul
processeur sp�cialis� tr�s rapide sont maintenant constitu�s de
nombreux CPU plus banals.
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.
44..22..22.. LLaa ""ccaaiissssee"" eenn pprrooggrraammmmaattiioonn ppaarraallll��llee
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:
44..22..22..11.. SSyysstt��mmeess dd''eexxppllooiittaattiioonn MMoonnoo--TT��cchhee::
Une caisse ouverte (et en service) qui ne peut traiter qu'un client �
la fois.
Exemple en Informatique : MS DOS
44..22..22..22.. SSyysstt��mmeess dd''eexxppllooiittaattiioonn MMuullttii--TT��cchheess::
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
44..22..22..33.. SSyysstt��mmeess dd''eexxppllooiittaattiioonn MMuullttii--TT��cchheess aavveecc pplluussiieeuurrss CCPPUU::
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
44..22..22..44.. SSoouuss--tt��cchheess ((TThhrreeaaddss)) ssuurr lleess aauuttrreess CCPPUU dd''uunn SSyysstt��mmee
dd''eexxppllooiittaattiioonn MMuullttii--TT��cchheess::
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.
44..22..22..55.. pplluussiieeuurrss CCPPUU:: EEnnvvooyyeerr ddeess mmeessssaaggeess ssuurr ddeess SSyysstt��mmeess
dd''eexxppllooiittaattiioonn MMuullttii--TT��cchheess aavveecc
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.
44..33.. AArrcchhiitteeccttuurreess ppoouurr llee ccaallccuull ppaarraallll��llee
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.
44..33..11.. AArrcchhiitteeccttuurreess MMaatt��rriieelllleess
Il y a typiquement deux fa�ons d'assembler un ordinateur parall�le:
1. La m�moire locale des machines qui communiquent par messages
(Clusters Beowulf)
2. Les machines � m�moire partag�e qui communiquent � travers la
m�moire (machines SMP)
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.
44..33..22.. AArrcchhiitteeccttuurreess LLooggiicciieelllleess eett AAPPII
Il y a basiquement deux fa�ons d'"exprimer" la concurrence dans un
programme:
1. En envoyant des Messages entre les processeurs
2. En utilisant les threads du syst�me d'exploitation (natives)
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.
44..33..22..11.. MMeessssaaggeess
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.
44..33..22..22.. TThhrreeaaddss
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.
44..33..33.. AArrcchhiitteeccttuurree ddeess AApppplliiccaattiioonnss
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).
44..44.. CCoonnvveennaannccee
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.
44..55.. EEccrriirree eett ppoorrtteerr ddeess llooggiicciieellss ppaarraallll��lleess
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:
1. Y aller et construire un Beowulf CLASSE I et apr�s y ajuster votre
application. Ou ex�cuter des applications parall�les que vous savez
fonctionner sur votre Beowulf (mais attention � la portabilit� et �
l'efficacit� en accord avec les informations cit�es ci-dessus).
2. Examiner les applications dont vous avez besoin sur votre Beowulf,
et faire une estimation quant au type de mat�riel et de logiciels
qu'il vous faut.
Dans chaque cas, vous devrez consid�rer les besoins en efficacit�. En
g�n�ral, il y a trois choses � faire:
1. D�terminer les parties concurrentes de votre programme
2. Estimer le parall�lisme efficacement
3. D�crire les parties concurrentes de votre programme
Examinons-les successivement:
44..55..11.. DD��tteerrmmiinneerr lleess ppaarrttiieess ccoonnccuurrrreenntteess ddee vvoottrree pprrooggrraammmmee
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.
44..55..22.. EEssttiimmeerr llee ppaarraallll��lliissmmee eeffffiiccaacceemmeenntt
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 _P_e_r_f_o_r_m_a_n_c_e
_C_o_n_s_i_d_e_r_a_t_i_o_n_s _f_o_r _I_/_O_-_D_o_m_i_n_a_n_t _A_p_p_l_i_c_a_t_i_o_n_s _o_n _P_a_r_a_l_l_e_l _C_o_m_p_u_t_e_r_s
(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.
44..55..33.. DD��ccrriirree lleess ppaarrttiieess ccoonnccuurrrreenntteess ddee vvoottrree pprrooggrraammmmee
Il y a plusieurs fa�ons de d�crire les parties concurrentes de votre
programme:
1. L'ex�cution parall�le explicite
2. L'ex�cution parall�le implicite
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.
44..55..33..11.. LLeess mm��tthhooddeess eexxpplliicciitteess
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 !
44..55..33..22.. MM��tthhooddeess IImmpplliicciitteess
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.
55.. RReessssoouurrcceess BBeeoowwuullff
55..11.. PPooiinnttss ddee dd��ppaarrtt
� Liste de diffusion US Beowulf. Pour s'inscrire, envoyer un courriel
�
[email protected] avec le mot _s_u_b_s_c_r_i_b_e dans
le corps du message.
� Homepage Beowulf
http://www.beowulf.org
� Extreme Linux
http://www.extremelinux.org
� Extreme Linux Software pour Red Hat
http://www.redhat.com/extreme
55..22.. DDooccuummeennttaattiioonn
� La derni�re version du Beowulf HOWTO en
Anglais
http://www.sci.usq.edu.au/staff/jacek/beowulf.
� La derni�re version du Beowulf HOWTO en Fran�ais
http://www.e-
nef.com/linux/beowulf.
� Construire un syst�me Beowulf
http://www.cacr.caltech.edu/beowulf/tutorial/building.html
� Les liens de Jacek sur Beowulf
http://www.sci.usq.edu.au/staff/jacek/beowulf.
� Beowulf Installation and Administration HOWTO (DRAFT)
http://www.sci.usq.edu.au/staff/jacek/beowulf.
� Linux Parallel Processing HOWTO
http://yara.ecn.purdue.edu/~pplinux/PPHOWTO/pphowto.html
55..33.. PPuubblliiccaattiioonnss
� Chance Reschke, Thomas Sterling, Daniel Ridge, Daniel Savarese,
Donald Becker, and Phillip Merkey _A _D_e_s_i_g_n _S_t_u_d_y _o_f _A_l_t_e_r_n_a_t_i_v_e
_N_e_t_w_o_r_k _T_o_p_o_l_o_g_i_e_s _f_o_r _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n.
Proceedings Fifth IEEE International Symposium on High Performance
Distributed Computing, 1996.
http://www.beowulf.org/papers/HPDC96/hpdc96.html
� Daniel Ridge, Donald Becker, Phillip Merkey, Thomas Sterling
Becker, and Phillip Merkey. _H_a_r_n_e_s_s_i_n_g _t_h_e _P_o_w_e_r _o_f _P_a_r_a_l_l_e_l_i_s_m _i_n
_a _P_i_l_e_-_o_f_-_P_C_s. Proceedings, IEEE Aerospace, 1997.
http://www.beowulf.org/papers/AA97/aa97.ps
� Thomas Sterling, Donald J. Becker, Daniel Savarese, Michael R.
Berry, and Chance Res. _A_c_h_i_e_v_i_n_g _a _B_a_l_a_n_c_e_d _L_o_w_-_C_o_s_t _A_r_c_h_i_t_e_c_t_u_r_e
_f_o_r _M_a_s_s _S_t_o_r_a_g_e _M_a_n_a_g_e_m_e_n_t _t_h_r_o_u_g_h _M_u_l_t_i_p_l_e _F_a_s_t _E_t_h_e_r_n_e_t _C_h_a_n_n_e_l_s
_o_n _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n. Proceedings, International
Parallel Processing Symposium, 1996.
http://www.beowulf.org/papers/IPPS96/ipps96.html
� Donald J. Becker, Thomas Sterling, Daniel Savarese, Bruce Fryxell,
Kevin Olson. _C_o_m_m_u_n_i_c_a_t_i_o_n _O_v_e_r_h_e_a_d _f_o_r _S_p_a_c_e _S_c_i_e_n_c_e _A_p_p_l_i_c_a_t_i_o_n_s
_o_n _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n. Proceedings,High Performance
and Distributed Computing, 1995.
http://www.beowulf.org/papers/HPDC95/hpdc95.html
� Donald J. Becker, Thomas Sterling, Daniel Savarese, John E.
Dorband, Udaya A. Ranawak, Charles V. Packer. _B_E_O_W_U_L_F_: _A _P_A_R_A_L_L_E_L
_W_O_R_K_S_T_A_T_I_O_N _F_O_R _S_C_I_E_N_T_I_F_I_C _C_O_M_P_U_T_A_T_I_O_N. Proceedings, International
Conference on Parallel Processing, 95.
http://www.beowulf.org/papers/ICPP95/icpp95.html
� Publications sur le site de Beowulf
http://www.beowulf.org/papers/papers.html
55..44.. LLooggiicciieellss
� PVM - Parallel Virtual Machine/Machine Parall�le Virtuelle
http://www.epm.ornl.gov/pvm/pvm_home.html
� LAM/MPI - Local Area Multicomputer / Message Passing Interface
Multi-Ordinateurs locaux / Interface de Transmission de Messages
http://www.mpi.nd.edu/lam
� BERT77 - outil de conversion FORTRAN
http://www.plogic.com/bert.html
� logiciels Beowulf de la page du Projet Beowulf
http://beowulf.gsfc.nasa.gov/software/software.html
� Jacek's Beowulf-outils
ftp://ftp.sci.usq.edu.au/pub/jacek/beowulf-
utils
� bWatch - logiciel de surveillance de
cluster
http://www.sci.usq.edu.au/staff/jacek/bWatch
55..55.. MMaacchhiinneess BBeeoowwuullff
� Avalon consiste en 140 processeurs Alpha, 36 Go de RAM, et est
probablement la machine Beowulf la plus rapide, allant � 47.7
Gflops et class�e 114�me sur la liste du Top 500.
http://swift.lanl.gov/avalon/
� Megalon-A Massively PArallel CompuTer Resource (MPACTR) consiste en
14 quadri CPU Pentium Pro 200 noeuds, et 14 Go de RAM.
http://megalon.ca.sandia.gov/description.html
� theHIVE - Highly-parallel Integrated Virtual Environment est un
autre Superordinateur Beowulf rapide. theHIVE est de 64 noeuds, une
machine de 128 CPU avec un total de 4 Go de RAM.
http://newton.gsfc.nasa.gov/thehive/
� Topcat est une machine beaucoup plus petite, constitu�e de 16 CPU
et 1.2 Go de RAM.
http://www.sci.usq.edu.au/staff/jacek/topcat
� MAGI cluster -- c'est un tr�s bon site avec de nombreux liens de
qualit�.
http://noel.feld.cvut.cz/magi/
55..66.. DD''aauuttrreess SSiitteess IInntt��rreessssaannttss
� Linux SMP
http://www.linux.org.uk/SMP/title.html
� Paralogic - Achetez un Beowulf
http://www.plogic.com
55..77.. HHiissttooiirree
� L�gendes - Beowulf
http://legends.dm.net/beowulf/index.html
� Les Aventures de Beowulf
http://www.lnstar.com/literature/beowulf/beowulf.html
66.. CCooddee SSoouurrccee
66..11.. ssuumm..cc
/* Jacek Radajewski
[email protected] */
/* 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;
}
66..22.. ssiiggmmaassqqrrtt..cc
/* Jacek Radajewski
[email protected] */
/* 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;
}
66..33.. pprruunn..sshh
#!/bin/bash
# Jacek Radajewski
[email protected]
# 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&
