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.