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.
Hosting by: Hurra Communications GmbH
Generated: 2007-01-26 18:01:39