<html><head><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>1. Introduction</title><link href="style.css" rel="stylesheet" type="text/css"><meta content="DocBook XSL Stylesheets V1.68.1" name="generator"><link rel="start" href="index.html" title="Le traitement en parallèle sous Linux"><link rel="up" href="index.html" title="Le traitement en parallèle sous Linux"><link rel="prev" href="index.html" title="Le traitement en parallèle sous Linux"><link rel="next" href="ar01s02.html" title="2. Linux sur SMP"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table summary="Navigation header" width="100%"><tr><th align="center" colspan="3">1. Introduction</th></tr><tr><td align="left" width="20%"><a accesskey="p" href="index.html">Précédent</a> </td><th align="center" width="60%"> </th><td align="right" width="20%"> <a accesskey="n" href="ar01s02.html">Suivant</a></td></tr></table><hr></div><div class="sect1" lang="fr"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="N10073"></a>1. Introduction</h2></div></div></div><p>
L'<span class="emphasis"><em>exécution en parallèle</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Parallel Processing</em></span></span> ») se
rapporte à l'idée d'accélérer l'exécution d'un programme en le divisant
en plusieurs fragments pouvant être exécutés simultanément, chacun sur
son propre processeur. Un programme exécuté sur <span class="emphasis"><em>N</em></span>
processeurs pourrait alors fonctionner <span class="emphasis"><em>N</em></span> fois plus
vite qu'il ne le ferait en utilisant un seul processeur.
</p><p>
Traditionnellement, les processeurs multiples sont fournis avec un
« <span class="quote">ordinateur en parallèle</span> » spécialement conçu. De ce fait,
Linux gère désormais les systèmes <span class="emphasis"><em>SMP</em></span> (souvent
vendus en tant que « <span class="quote">serveurs</span> ») dans lesquels plusieurs
processeurs partagent le même bus et la même mémoire au sein d'un même
ordinateur. Il est également possible à un groupe d'ordinateurs (par
exemple un groupe de PC fonctionnant chacun avec Linux) d'être
interconnectés par un réseau pour former un ensemble de traitement en
parallèle (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">cluster</em></span></span> »). La
troisième alternative pour l'exécution parallèle sous Linux est
l'utilisation du jeu d'instructions multimédias étendu (MultiMedia
Extend : MMX) pour agir en parallèle sur des vecteurs de données
entières. Il est enfin possible d'utiliser un système Linux comme
« <span class="quote">hôte</span> » hébergeant un moteur de calcul en parallèle
<span class="emphasis"><em>dédié</em></span>. Toutes ces approches sont traitées en détails
dans ce document.
</p><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1009A"></a>1.1. Le traitement en parallèle correspond-il à mes besoins ?</h3></div></div></div><p>
Bien que l'emploi de multiples processeurs puisse accélérer nombre
d'opérations, la plupart des applications ne peuvent encore tirer
profit du traitement en parallèle. A la base, le traitement en
parallèle est approprié si :
</p><p>
<div class="itemizedlist"><ul type="disc"><li><p>
Votre application est suffisamment parallélisée pour faire bon
usage de multiples processeurs. C'est, en partie, une question
d'identification des différentes portions du programme pouvant
être exécutées indépendamment et simultanément sur des processeurs
séparés, mais vous découvrirez aussi que certaines choses qui
<span class="emphasis"><em>peuvent</em></span> être exécutées en parallèle
ralentissent le traitement si elles sont exécutées en parallèle
sur un système particulier. Par exemple, un programme qui
s'exécute en quatre secondes sur une machine unique pourrait
être capable de n'occuper qu'une seconde du temps de chacune
de quatre machines, mais n'apportera pourtant aucun gain de
temps s'il faut trois secondes ou plus à ces machines pour
coordonner leurs actions.
</p></li><li><p>
Soit l'application qui vous intéresse en particulier a été
<span class="emphasis"><em>parallélisée</em></span>, c'est-à-dire réécrite
pour tirer profit du traitement en parallèle, soit vous comptez
produire au moins un peu de code original qui le fasse.
</p></li><li><p>
Vous êtes intéressé par la recherche de nouvelles solutions impliquant
un traitement en parallèle, ou au moins souhaitez vous familiariser
avec. Le traitement en parallèle sous Linux n'est pas forcément
difficile, mais ce n'est pas une notion familière à beaucoup
d'utilisateurs, et il n'existe pas de livre intitulé « <span class="quote">Le
<span class="foreignphrase"><em class="foreignphrase">Parallel Processing</em></span> pour les
nuls</span> », en tout cas pas encore. Ce guide est un bon point de
départ, mais il ne contient pas l'intégralité de ce que vous devez
connaître.
</p></li></ul></div>
</p><p>
La bonne nouvelle, c'est que si tout ce qui vient d'être dit est vrai,
vous découvrirez cependant que le traitement en parallèle sous Linux
peut apporter les performances d'un supercalculateur à des programmes
effectuant des opérations complexes ou travaillant sur de très grandes
quantités de données. Mais en plus, cela peut être fait en utilisant du
matériel peu onéreux et que vous possédez sûrement déjà. Avec çà, il
reste aisé d'utiliser un système de traitement en parallèle sous Linux à
d'autres choses lorsqu'il n'est pas en train d'accomplir un traitement
en parallèle.
</p><p>
Si le traitement en parallèle ne correspond <span class="emphasis"><em>pas</em></span> à
vos besoins, mais que vous souhaitez tout de même améliorer sensiblement
les performances de votre machine, il reste des choses que vous pouvez
faire. Par exemple, vous pouvez améliorer les performances d'un
programme séquentiel en remplaçant votre processeur par un plus rapide,
en ajoutant de la mémoire, en remplaçant un disque IDE par un
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">fast wide SCSI</em></span></span> », et cætera.
Si c'est ce qui vous intéresse, sautez directement à la section 6.2,
sinon poursuivez votre lecture.
</p></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N100C3"></a>1.2. Terminologie</h3></div></div></div><p>
Bien que le traitement en parallèle ait été utilisé pendant de
nombreuses années par de nombreux systèmes, il reste étranger à la
plupart des utilisateurs. Aussi, avant de traiter des différentes
alternatives, il est important de se familiariser avec une poignée de
termes usuels :
</p><div class="variablelist"><dl><dt><span class="term">SIMD :</span></dt><dd><p>
SIMD (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Single Instruction stream, Multiple Data stream</em></span></span> », ou
« <span class="quote">Un seul flot d'instruction, plusieurs flots de données</span> »),
fait référence à un modèle d'exécution en parallèle dans
lequel tous les processeurs traitent la même opération à
la fois, mais où chaque processeur est autorisé à agir sur
sa propre donnée. Ce modèle convient naturellement au concept
où l'on applique le même traitement sur chaque élément d'un
tableau, et est ainsi souvent associé à la manipulation de
vecteurs ou de tableaux. Toutes les opérations étant
implicitement synchronisées, les interactions entre processeurs
SIMD tendent à être facilement et efficacement mises en œuvre.
</p></dd><dt><span class="term">MIMD :</span></dt><dd><p>
MIMD (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Multiple Instruction stream, Multiple Data stream</em></span></span> »,
ou « <span class="quote">Plusieurs flots d'instructions, plusieurs flots de données</span> »),
se rapporte au modèle d'exécution en parallèle dans lequel chaque
processeur agit essentiellement seul. C'est le modèle qui convient
le mieux à la décomposition d'un programme pour une exécution en
parallèle sur une base fonctionnelle. Par exemple, une processeur
peut mettre à jour une base de données pendant qu'un autre produit
l'affichage graphique de la nouvelle entrée. C'est un modèle plus
flexible que l'exécution en SIMD, mais qui s'accomplit au risque
d'un cauchemar pour le débogueur, les « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">race conditions</em></span></span> »
ou « <span class="quote">accès concurrents</span> », dans lesquels un programme peut planter
de façon intermittente à cause des différences de minutage entre
les opérations des différents processeurs lorsque celles d'un de ces
processeurs sont réorganisées en fonction de celles d'un autre.
</p></dd><dt><span class="term">SPMD :</span></dt><dd><p>
SPMD (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Single Program, Multiple Data</em></span></span> »),
ou « <span class="quote">Un seul programme, plusieurs données</span> », est une version
restreinte du MIMD dans laquelle tous les processeurs
exécutent le même programme. Contrairement au SIMD, chaque
processeur peut suivre un chemin différent dans le programme.
</p></dd><dt><span class="term">Bande passante :</span></dt><dd><p>
La bande passante
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">bandwidth</em></span></span> ») d'un système
de communication correspond à la quantité maximum de données que l'on
peut transmettre en une unité de temps… une fois que la
transmission de données a commencé. La bande passante des connexions
série est souvent mesurée en <span class="emphasis"><em>bauds</em></span> ou en
<span class="emphasis"><em>bits par seconde (b/s)</em></span>, ce qui correspond en
général à huit fois ou dix fois le nombre d'<span class="emphasis"><em>octets par
secondes (O/s ou B/s</em></span>, B =
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Byte</em></span></span> » =
« <span class="quote">Octet</span> »). Par exemple, un modem à 1200 bauds (N.D.T. :
comme celui du Minitel) peut transférer environ 120 octets à la seconde
(B/s), tandis qu'une connexion réseau ATM à 155 Mb/s est environ
130 000 fois plus rapide, en transférant environ 17 Mo/s. Une bande
passante élevée permet un transfert efficace de larges blocs de données
entre processeurs.
</p></dd><dt><span class="term">Latence :</span></dt><dd><p>
La latence d'un système de communication représente le temps minimum
nécessaire pour la transmission d'un objet, en incluant toutes les
données « <span class="quote">forfaitaires</span> » logicielles pour l'émission et la
réception (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">overhead</em></span></span> »). Le
temps de latence est très important dans les traitements en parallèle
car il détermine la <span class="emphasis"><em>granularité</em></span>, la
durée minimum d'exécution d'un segment de code pour gagner en vitesse
d'exécution grâce au traitement en parallèle. Concrètement, si un
segment de code s'exécute en moins de temps qu'il n'en faut pour
transmettre son résultat (ce délai-ci formant la latence), exécuter ce
segment en série plutôt qu'en parallèle sera plus rapide puisqu'il n'y
aura pas de délai de transmission.
</p></dd><dt><span class="term">Envoi de messages (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Message passing</em></span></span> ») :</span></dt><dd><p>
Les envois de message sont un modèle d'interaction entre les différents
processeurs d'un système parallèle. En général, un message est construit
logiciellement sur un processeur et envoyé via une interconnexion réseau
à un autre processeur. Bien que le surcoût en temps
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">overhead</em></span></span> ») engendré par la
gestion de chaque message (ce délai formant la latence) soit élevé,
typiquement, il n'y a que peu de restrictions quant à la quantité
d'informations que ce message peut contenir. Ainsi, l'envoi de messages
peut assurer une bande passante élevée en apportant une méthode efficace
pour transmettre de grandes quantités d'informations d'un processeur à
un autre. En revanche, afin de réduire les besoins en coûteuses
opérations d'envoi de message, les structures de données à l'intérieur
d'un programme doivent être réparties à travers tous les processeurs de
façon à ce que la plupart des données référencées par chaque processeur
se trouve dans sa mémoire locale… Cette tâche porte le nom de
« <span class="quote">répartition des données</span> » (« <span class="quote"><span class="emphasis"><em>data
layout</em></span></span> »).
</p></dd><dt><span class="term">Mémoire partagée :</span></dt><dd><p>
La mémoire partagée est elle aussi un modèle d'interaction entre les
processeurs d'un système parallèle. Les systèmes comme les machines
biprocesseurs Pentium faisant fonctionner Linux partagent
<span class="emphasis"><em>physiquement</em></span> la même mémoire entre tous leurs
processeurs, si bien qu'une valeur écrite par un processeur est
directement accessible par un autre processeur. A l'inverse, la mémoire
partagée <span class="emphasis"><em>logiquement</em></span> peut être implémentée sur les
systèmes où chaque processeur dispose d'une mémoire qui lui est propre,
en convertissant chaque référence à une zone non locale de la mémoire en
une communication inter-processeur appropriée. Cette implémentation de
la mémoire partagée est généralement considérée comme étant plus facile
à utiliser que les files de messages. La mémoire partagée physiquement
peut présenter à la fois une bande passante élevée et des temps de
latence très bas, mais seulement lorsque les différents processeurs
n'essaient pas d'accéder au bus simultanément. Ainsi, le modèle de
répartition des données peut avoir une sérieuse influence sur les
performances, et les effets de cache et autres peuvent rendre très
difficile la détermination du meilleur modèle.
</p></dd><dt><span class="term">Fonctions d'agrégation (<span class="foreignphrase"><em class="foreignphrase">Aggregate Functions</em></span>) :</span></dt><dd><p>
Dans le modèle des files de messages comme dans celui de la mémoire
partagée, une communication est initiée par un processeur seul. Par
contraste, une fonction d'agrégation est un modèle implicitement
parallèle dans lequel tous les processeurs d'un groupe agissent
ensemble. Le cas le plus simple est celui des <span class="emphasis"><em>barrières de
synchronisation</em></span>, dans lequel chaque processeur se met en
attente jusqu'à ce que le groupe entier ait atteint la barrière. Si
chaque processeur émet une donnée en atteignant une barrière, il est
possible de demander à l'électronique responsable des communications
d'émettre en retour une valeur à chaque processeur, valeur qui pourrait
être fonction des données collectées sur tous les processeurs. Par
exemple, la valeur de retour pourrait être la réponse à la question
« <span class="quote">Est-ce qu'un processeur a trouvé la réponse ?</span> » ou
pourrait être la somme d'une valeur propre à chaque processeur. Les
temps de latence peuvent être bas, mais la bande passante a tendance à
être basse elle aussi. Traditionnellement, ce modèle est surtout utilisé
pour contrôler l'exécution en parallèle, plutôt que pour distribuer les
données.
</p></dd><dt><span class="term">Communication collective :</span></dt><dd><p>
C'est un autre nom pour les fonctions d'agrégation, utilisé le plus
souvent en référence à celles qui sont construites en utilisant de
multiples opérations d'envoi de message.
</p></dd><dt><span class="term">SMP :</span></dt><dd><p>
SMP (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Symmetric
Multi-Processor</em></span></span> ») se rapporte au concept d'un
groupe de processeurs travaillant ensemble en tant qu'homologues, si
bien que chaque partie d'un travail peut être effectuée de la même façon
par n'importe quel processeur de ce groupe. Typiquement, le SMP implique
la combinaison du MIMD et de la mémoire partagée. Dans l'univers IA32,
SMP signifie souvent « <span class="quote">compatible MPS</span> »
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Intel MultiProcessor
Specification</em></span></span> »). À l'avenir, cela pourrait
signifier
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Slot 2</em></span></span> »…
</p></dd><dt><span class="term">SWAR :</span></dt><dd><p>
SWAR (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">SIMD Within A
Register</em></span></span> », ou « <span class="quote">SIMD à l'intérieur d'un
registre</span> ») est un terme générique qui désigne le concept
consistant à partitionner un registre en plusieurs champs entiers et à
effectuer des opérations sur toute la largeur du registre pour faire du
calcul en parallèle SIMD sur tous les champs à la fois. En considérant
une machine avec des registres longs de <span class="emphasis"><em>k</em></span> bits (et
donc autant pour les chemins de données, et les unités des fonctions),
on sait depuis longtemps que les opérations sur les registres ordinaires
peuvent fonctionner comme des opérations parallèle SIMD sur
<span class="emphasis"><em>n</em></span> champs de <span class="emphasis"><em>k/n</em></span> bits. Bien que ce
type de parallélisme puisse être mis en œuvre en utilisant les
registres entiers et les instructions ordinaires, plusieurs modèles
récents de microprocesseurs intègrent des instructions spécialisées pour
améliorer les performances de cette technique pour des tâches orientées
multimédia. En plus du <span class="emphasis"><em>MMX</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">MultiMedia eXtension</em></span></span> »)
d'Intel/AMD/Cyrix, il existe : <span class="emphasis"><em>MAX</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">MultimediA eXtension</em></span></span> ») sur
l'Alpha de Digital, <span class="emphasis"><em>MAX</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Multimedia Acceleration
eXtension</em></span></span> ») sur le PA-RISC de Hewlett-Packard,
<span class="emphasis"><em>MDMX</em></span> (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Digital Media
eXtension</em></span></span> », prononcé « <span class="quote">Mad Max</span> »)
sur MIPS, et <span class="emphasis"><em>VIS</em></span> (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Visual
Instruction Set</em></span></span> ») sur le SPARC V9 de Sun. En
dehors des trois constructeurs qui ont adopté le MMX, tous ces jeux
d'instructions sont comparables, mais incompatibles entre eux.
</p></dd><dt><span class="term">Processeur auxiliaires, dédiés. (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Attached Processors</em></span></span> ») :</span></dt><dd><p>
Les processeurs auxiliaires sont essentiellement des calculateurs dédiés
à une tâche particulière, reliés à un système <span class="emphasis"><em>hôte</em></span>
et servant à accélérer certains types de calculs. Par exemple, de
nombreuses cartes vidéo et son pour PC embarquent des processeurs dédiés
conçus pour accélérer respectivement les opérations graphiques et le
<span class="emphasis"><em>DSP</em></span> audio (DSP : « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Digital
Signal Processing</em></span></span> », soit « <span class="quote">Traitement
Numérique du Signal</span> »). Il existe aussi une large variété de
<span class="emphasis"><em>processeurs de tableaux</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">array processors</em></span></span> »), nommés
ainsi car ils sont conçus pour accélérer les opérations arithmétiques
sur les tableaux. À dire vrai, un certain nombre de supercalculateurs
commerciaux sont en réalité formés de processeurs dédiés rattachés à des
stations de travail hôtes.
</p></dd><dt><span class="term">RAID :</span></dt><dd><p>
RAID (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Redundant Array of Inexpensive
Disks</em></span></span> », soit « <span class="quote">Batterie Redondante de
Disques Peu Coûteux</span> ») est une technologie simple servant à
améliorer tant la bande passante que la fiabilité des accès disque. Même
si le RAID se décline en plusieurs variantes, toutes ont en commun deux
concepts-clés : D'abord, chaque bloc de données est
<span class="emphasis"><em>découpé</em></span> en segments distribués à un groupe de
<span class="emphasis"><em>n+k</em></span> disques de façon à ce que chaque disque n'ait à
lire que <span class="emphasis"><em>1/n</em></span>ième de la donnée… offrant ainsi
<span class="emphasis"><em>n</em></span> fois la bande passante d'un seul disque. Ensuite,
des données redondantes sont écrites pour que les données puissent être
recouvrées si un des disques vient à défaillir. C'est important car
autrement, si l'un des <span class="emphasis"><em>n+k</em></span> disques tombait en
panne, le système de fichiers entier pourrait être perdu. Il existe une
bonne présentation du système RAID sur <a href="http://www.dpt.com/uraiddoc.html" target="_top">http://www.dpt.com/uraiddoc.html</a>, ainsi que des informations
concernant le RAID pour Linux sur <a href="http://linas.org/linux/raid.html" target="_top">http://linas.org/linux/raid.html</a>. Hormis la prise en charge du
matériel RAID spécialisé, Linux gère aussi le RAID logiciel 0, 1, 4 et 5
à travers plusieurs disques hébergés sur un système Linux unique.
Reportez-vous aux Software RAID mini-HOWTO et Multi-Disk System Tuning
mini-HOWTO pour plus de détails. Le RAID au travers de plusieurs disques
<span class="emphasis"><em>sur plusieurs machines en clusters</em></span> n'est pas
directement pris en charge.
</p></dd><dt><span class="term">IA32 :</span></dt><dd><p>
L'IA32 (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Intel
Architecture</em></span></span> », 32 bits) n'a rien à voir avec le
traitement en parallèle, mais se réfère à la classe de processeurs dont
les instructions sont compatibles avec celles de l'Intel 386.
Concrètement, tout processeur Intel x86 après le 286 est compatible avec
le modèle de mémoire « <span class="quote">à plat<sup>[<a href="#ftn.N101F7" name="N101F7">1</a>]</sup></span> » qui caractérise l'IA32. AMD et Cyrix font eux
aussi une multitude de processeurs compatibles IA32. Comme Linux a
évolué principalement sur des processeurs IA32 et que c'est là qu'est
centré le marché de la grande consommation, il est commode d'utiliser le
terme IA32 pour distinguer ce type de processeur des PowerPC, Alpha,
PA-RISC, MIPS, SPARC, et cætera. La future IA64 (64 bits avec EPIC,
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Explicitly Parallel Instruction
Computing</em></span></span> ») va certainement compliquer les
choses, mais la production de Merced, le premier processeur IA64, n'est
pas envisagée avant 1999.
</p></dd><dt><span class="term">Produits du commerce :</span></dt><dd><p>
Depuis la mort de plusieurs fabricants de supercalculateurs en parallèle,
les solutions commerciales toutes faites et prêtes à l'emploi (en
anglais « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Commercial Off-The-Shelf</em></span></span> »
ou <span class="foreignphrase"><em class="foreignphrase">COTS</em></span>, pour « <span class="quote">disponibles en
rayons</span> ») sont couramment considérées comme une nécessité dans le
monde des systèmes de calcul en parallèle. En étant totalement puriste, les
seuls moyens de traitement en parallèle disponibles sous forme de
produits du commerce utilisant des PC sont des choses comme les serveurs
Windows NT en SMP et les différentes applications Windows utilisant le
MMX. Être aussi puriste ne mène à rien. L'idée fondamentale de
l'utilisation de produits du commerce est de réduire les coûts et les
temps de développement. Ainsi, une manière plus complète et plus utile
de comprendre l'utilisation de ce type de produit serait de dire que
la plupart des sous-systèmes tirent profit du marché de masse mais que
d'autres technologies sont utilisées là où elles servent vraiment. Le
plus souvent, les produits du commerce pour le traitement en parallèle
sont utilisés au sein d'un groupe de machines
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">cluster</em></span></span> ») dans lequel les
postes sont des PC courants, mais dont l'interface réseau et les
logiciels ont été quelque peu <span class="emphasis"><em>personnalisés</em></span>…
classiquement, fonctionnant sous Linux avec des applications dont le
code source est libre et disponible (par exemple sous
<span class="foreignphrase"><em class="foreignphrase">copyleft</em></span> ou dans le domaine public), mais
pas littéralement des produits du commerce.
</p></dd></dl></div></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1021D"></a>1.3. Algorithme d'exemple</h3></div></div></div><p>
Afin de bien comprendre l'usage des différentes approches de
programmation en parallèle mises en évidence dans ce guide,
il est utile d'étudier cet exemple. Bien qu'un algorithme
simple de traitement en parallèle eût suffi, si l'on en choisit
un qui a déjà été utilisé pour faire la démonstration d'autres
systèmes de programmation parallèle, il devient un peu plus facile
de comparer et mettre en évidence les caractéristiques de ces différentes approches. le livre
de M. J. Quinn, <span class="foreignphrase"><em class="foreignphrase">Parallel Computing Theory And Practice</em></span>
(« <span class="quote">Théorie et Pratique du Calcul en Parallèle</span> »), seconde édition, édité
par McGraw Hill, New York en 1994, utilise un algorithme parallèle
qui calcule la valeur de Pi pour présenter différents environnements
de programmation sur supercalculateurs parallèles (par exemple, le
<span class="foreignphrase"><em class="foreignphrase">message passing</em></span> du nCube ou la mémoire partagée des Sequent). Dans ce
guide, nous utiliserons le même algorithme.
</p><p>
Cet algorithme calcule la valeur approchée de Pi en faisant la
somme de l'aire située sous <span class="emphasis"><em>x</em></span> au carré. En
tant que programme C purement séquentiel, l'algorithme ressemble à :
</p><p>
<pre class="programlisting">
#include <stdlib.h>
#include <stdio.h>
main(int argc, char **argv)
{
register double largeur, somme;
register int intervalles, i;
/* Lit le nombre d'intervalles désiré */
intervalles = atoi(argv[1]);
largeur = 1.0 / intervalles;
/* fait le calcul */
somme = 0;
for (i=0; i<intervalles; ++i) {
register double x = (i + 0.5) * largeur;
somme += 4.0 / (1.0 + x * x);
}
somme *= largeur;
printf("Estimation de la valeur de pi: %f\n", somme);
return(0);
}
</pre>
</p><p>
En revanche, cet algorithme séquentiel conduit facilement à une
implémentation « <span class="quote">parallèle et embarrassante</span> ». L'aire est
subdivisée en intervalles, et un nombre quelconque de processeurs peut
faire la somme de l'intervalle qui lui est assigné indépendamment des
autres, sans nécessité d'interaction entre les processeurs. Une fois que
les sommes locales ont toutes été calculées, elles sont additionnées
pour former la somme globale. Cette étape requiert un certain niveau de
coordination et de communication entre les différents processeurs.
Enfin, cette somme globale est renvoyée à l'écran par un seul
processeur, en tant que valeur approximative de Pi.
</p><p>
Dans ce guide, les différentes implémentations parallèles de cet algorithme
apparaissent là ou les différentes méthodes de programmation sont traitées.
</p></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1023D"></a>1.4. Structure du document</h3></div></div></div><p>
Le reste de ce document est divisé en cinq parties. Les sections
2, 3, 4 et 5 correspondent aux trois différents types de configuration
matérielle pouvant assumer le traitement en parallèle en utilisant
Linux.
</p><div class="itemizedlist"><ul type="disc"><li><p>
La section 2 traite des systèmes Linux sur SMP, lesquels prennent
directement en charge l'exécution MIMD en utilisant la mémoire
partagée, même si les files de messages sont facilement mises en
place, elles aussi. Bien que Linux sache gérer les configurations
SMP jusqu'à 16 processeurs, la plupart des ordinateurs SMP de type PC
sont dotés soit de deux, soit de quatre processeurs identiques.
</p></li><li><p>
La section 3 traite des batteries d'ordinateurs en réseau
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">clusters</em></span></span> »), chaque machine
fonctionnant sous Linux. Un <span class="foreignphrase"><em class="foreignphrase">cluster</em></span> peut
être utilisé comme un système de traitement en parallèle gérant
directement l'exécution en MIMD et l'échange de messages, et peut-être
même aussi la mémoire partagée logique. L'exécution SIMD simulée et la
communication des fonctions d'agrégation peuvent aussi être prises en
charge, selon le réseau exploité. Le nombre de processeurs compris dans
un <span class="foreignphrase"><em class="foreignphrase">cluster</em></span> peut s'étendre de deux à
plusieurs milliers, la principale limitation étant le câblage physique
du réseau. Dans certains cas, des machines de différents types peuvent
être mélangées au sein d'un <span class="foreignphrase"><em class="foreignphrase">cluster</em></span>. Par
exemple, un réseau qui combinerait des Alpha DEC et des Pentium sous
Linux serait appelé <span class="foreignphrase"><em class="foreignphrase">cluster</em></span>
<span class="emphasis"><em>hétérogène</em></span>.
</p></li><li><p>
La section 4 traite du SWAR, le « <span class="quote">SIMD dans un registre</span> ».
C'est une forme très restrictive d'exécution en parallèle, mais d'un
autre coté, c'est une possibilité intégrée aux processeurs ordinaires.
Ces derniers temps, les extensions MMX et autres des processeurs
modernes ont rendu cette approche encore plus efficace.
</p></li><li><p>
La section 5 traite de l'utilisation de PC sous Linux comme hôtes pour
des systèmes de calcul parallèle simples. Sous forme de carte
d'extension ou de boîtiers externes, les processeurs auxiliaires peuvent
apporter à des systèmes Linux une formidable puissance de traitement
pour des applications spécifiques. Par exemple, des cartes ISA
disponibles à peu de frais fournissent de multiples processeurs DSP,
offrant plusieurs centaines de MégaFLOP aux calculs de grande envergure.
En revanche, ces cartes ne sont <span class="emphasis"><em>que</em></span> des
processeurs. Elle n'embarquent généralement pas de système
d'exploitation, de disque dur, ou de connecteur pour terminal de
contrôle, et cætera. Pour rendre ces systèmes exploitables,
l'« <span class="quote">hôte</span> » Linux doit fournir ces facilités.
</p></li></ul></div><p>
La section finale de ce document couvre les aspects d'intérêt général
concernant le traitement en parallèle sous Linux, non spécifique à l'une
des approches listées ci-dessus.
</p><p>
En lisant ce document, gardez à l'esprit que nous n'avons pas tout
testé, et que beaucoup de choses rapportées dans ce document ont
toujours « <span class="quote">un caractère expérimental</span> » (une jolie manière de
dire que cela ne fonctionne pas tout à fait comme espéré ;-) ). Cela
dit, le traitement en parallèle sous Linux est désormais exploitable, et
un groupe incroyablement vaste de personnes travaille à le rendre encore
meilleur.
</p><p>
L'auteur de la version originale de ce guide est le Dr (Ph.D) Hank
Dietz, actuellement Professeur Associé de l'<span class="foreignphrase"><em class="foreignphrase">Electrical
and Computer Engineering</em></span> à l'université de Purdue, West
Lafayette, IN, 47907-1285. Dietz est propriétaire des droits sur ce
document, conformément aux règles du <span class="foreignphrase"><em class="foreignphrase">Linux Documentation
Project</em></span> (LDP). Bien qu'un effort ait été fait pour
assurer l'exactitude de cette présentation, ni Dietz ni l'Université de
Purdue ne peuvent être tenus responsables d'éventuels problèmes ou
erreurs, et l'Université de Purdue n'endosse la responsabilité d'aucun
produit ou travaux traités dans ce document.
</p></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1027A"></a>1.5. Note du traducteur</h3></div></div></div><p>
Chers lecteurs, avant de poursuivre la lecture de ce guide, il est
important de revenir, notament au vu de la date de publication de cette
version française, sur plusieurs points :
</p><div class="itemizedlist"><ul type="disc"><li><p>
Le Professeur Henry G. Dietz (dit « <span class="quote">Hank</span> »), après avoir
enseigné plusieurs années à l'Université de Purdue et y avoir développé
la plupart de ce qui forme ce document, <span class="emphasis"><em>mène aujourd'hui ses recherches à
l'Université du Kentucky</em></span>. Son site personnel se trouve
désormais ici: <a href="http://aggregate.org/hankd/" target="_top">http://aggregate.org/hankd/</a>. Cela signifie
également que la plupart des références à l'Université de Purdue sont
désormais caduques. Toutefois, un certain nombre de ces références ont
été conservées en l'état dans ce guide, ce lorsque le contenu référencé
était toujours disponible sur le site de l'Université sans avoir été
transféré vers le nouveau site. En tout état de cause, dirigez-vous en
priorité sur le site de l'Université du Kentucky pour tout contact ou
pour obtenir les informations les plus récentes.
</p></li><li><p>
La totalité des termes, notament techniques, employés dans ce documents
ont été traduits en français, à quelques exceptions près. C'est par
exemple le cas du mot
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">cluster</em></span></span> », qui désigne en
informatique la mise en parallèle de plusieurs machines individuelles et
coordonnées de manière à les faire agir comme un seul super-ordinateur.
Le terme français homologue est « <span class="quote">grappe</span> ». Toutefois, la
fréquence à laquelle ce mot est employé tant dans ce document (un
chapitre entier est consacré à ce sujet précis) que dans la communauté
du traitement en parallèle en général est telle que le terme original a
été conservé dans la présente version française. Dans le même esprit, la
notion de « <span class="quote">bande passante</span> » se retrouve très fréquement tout
au long de ce guide. C'est à la base un abus de langage, mais la
popularité de cette formule est également suffisament grande pour la
conserver en l'état.
</p></li><li><p>
La version originale de ce document a été écrite en 1998, la version
française est parue en 2004. Il va sans dire qu'au cours d'une aussi
longue période, le paysage informatique a beaucoup évolué, spécialement
en ce qui concerne le développement du noyau Linux. Certaines
technologies réseau (telles que ATM, FireWire, ou Fiber Channel) ou de
<span class="foreignphrase"><em class="foreignphrase">clustering</em></span> (comme MOSIX), recensées comme
indisponibles en 1998, ont depuis intégré le noyau, ou sont devenues
disponibles. En revanche, il est très peu probable qu'une technologie
connue pour fonctionner sous Linux lors de la rédaction de ce document
soit devenue inutilisable depuis.
</p></li><li><p>
Plus encore que celui de l'industrie informatique, le paysage du
<span class="foreignphrase"><em class="foreignphrase">World Wide Web</em></span> s'est transformé de façon
à rendre la plupart des liens proposés obsolètes. Un effort a été fait
pour assurer leur mise à jour ou leur remplacement, ainsi que la
pertinence de leur contenu. En dépit de cela, un certain nombre d'entre eux,
en particulier ceux dont les projets étaient hébergés sur les
pages personnelles d'étudiants de grandes écoles, n'ont pu être corrigés
et ont été retirés du document.
</p></li></ul></div><p>
Malgré toutes ces réserves, les techniques couvertes par ce document
sont suffisament générales pour rester valables au cours du temps et au
travers des différents modèles de machines, et son contenu présente
toujours un intérêt à la fois pédagogique et historique, qui restera encore
longtemps profitable au lecteur. Tout ceci justifie une publication même
tardive.
</p><p>
Enfin, le traducteur s'est efforcé de rendre le présent document aussi
correct et fidèle à son original que possible, mais n'est pas
infaillible. Tout signalement d'un contresens, d'une erreur technique,
ou tout autre défaut de traduction sera apprécié à sa juste valeur à
l'adresse suivante :
<code class="email"><<a href="mailto:dvandenbroeck CHEZ free POINT fr">dvandenbroeck CHEZ free POINT fr</a>></code>.
</p><p>
Bonne lecture !
</p></div><div class="footnotes"><br><hr align="left" width="100"><div class="footnote"><p><sup>[<a href="#N101F7" name="ftn.N101F7">1</a>] </sup>
N.D.T. : « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">flat memory
model</em></span></span> », dans lequel toute la mémoire se trouve
dans le même plan mémoire, par opposition aux segments, mémoire paginée,
et tout autre modèle composé.
</p></div></div></div><div class="navfooter"><hr><table summary="Navigation footer" width="100%"><tr><td align="left" width="40%"><a accesskey="p" href="index.html">Précédent</a> </td><td align="center" width="20%"> </td><td align="right" width="40%"> <a accesskey="n" href="ar01s02.html">Suivant</a></td></tr><tr><td valign="top" align="left" width="40%">Le traitement en parallèle sous Linux </td><td align="center" width="20%"><a accesskey="h" href="index.html">Sommaire</a></td><td valign="top" align="right" width="40%"> 2. Linux sur SMP</td></tr></table></div></body></html>
