<html><head><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>4. SIMD Within A Register : SWAR (Ex : utilisation de MMX)</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="ar01s03.html" title="3. Clusters de systèmes Linux"><link rel="next" href="ar01s05.html" title="5. Processeurs auxiliaires des machines Linux"></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">4. SIMD <span class="foreignphrase"><em class="foreignphrase">Within A Register</em></span> : SWAR (Ex : utilisation de MMX)</th></tr><tr><td align="left" width="20%"><a accesskey="p" href="ar01s03.html">Précédent</a> </td><th align="center" width="60%"> </th><td align="right" width="20%"> <a accesskey="n" href="ar01s05.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="N1119A"></a>4. SIMD <span class="foreignphrase"><em class="foreignphrase">Within A Register</em></span> : SWAR (Ex : utilisation de MMX)</h2></div></div></div><p>
Le 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 flux d'instruction,
plusieurs flux de données</span> ») à l'Intérieur d'Un Registre (ou
« <span class="quote">SIMD <span class="foreignphrase"><em class="foreignphrase">Within A
Register</em></span></span> » : SWAR) n'est pas un concept
récent. En considérant une machine dotée de registres, bus de données et
unités de fonctions de <span class="emphasis"><em>k</em></span> bits, il est connu depuis
longtemps que les opérations sur les registres ordinaires peuvent se
comporter comme des opérations parallèles SIMD sur
<span class="emphasis"><em>n</em></span> champs de
<span class="emphasis"><em>k</em></span>/<span class="emphasis"><em>n</em></span> bits chacun. Ce n'est en
revanche qu'avec les efforts récents en matière de multimédia que
l'accélération d'un facteur deux à huit apportée par les techniques SWAR
a commencé à concerner l'informatique générale. Les versions de 1997 de
la plupart des microprocesseurs incorporent une prise en charge
matérielle du SWAR<sup>[<a href="#ftn.N111BA" name="N111BA">23</a>]</sup> :
</p><p>
<div class="itemizedlist"><ul type="disc"><li><p>
<a href="http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/20726.pdf" target="_top">AMD K6 MMX (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">MultiMedia eXtensions</em></span></span> »)</a>
</p></li><li><p>
<a href="http://www.sun.com/sparc/vis/index.html" target="_top">Sun SPARC V9 VIS (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Visual Instruction Set</em></span></span> »)</a>
</p></li></ul></div>
</p><p>
Il existe quelques lacunes dans la prise en charge matérielle
apportée par les nouveaux microprocesseurs, des caprices comme
par exemple la prise en charge d'un nombre limité d'instructions
pour certaines tailles de champ. Il est toutefois important de
garder à l'esprit que bon nombre d'opérations SWAR peuvent se
passer d'accélération matérielle. Par exemple, les opérations
au niveau du bit sont insensibles au partitionnement logique d'un
registre.
</p><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N111DA"></a>4.1. Quels usages pour le SWAR ?</h3></div></div></div><p>
Bien que <span class="emphasis"><em>tout</em></span> processeur moderne soit capable
d'exécuter un programme en effectuant un minimum de parallélisme
SWAR, il est de fait que même le plus optimisé des jeux d'instructions
SWAR ne peut gérer un parallélisme d'intérêt vraiment général. A dire
vrai, de nombreuses personnes ont remarqué que les différences de
performance entre un Pentium ordinaire et un Pentium « <span class="quote">avec technologie MMX</span> »
étaient surtout dûes à certains détails, comme le fait que l'augmentation
de la taille du cache L1 coïncide avec l'apparition du MMX. Alors,
concrètement, à quoi le SWAR (ou le MMX) est-il utile ?
</p><div class="itemizedlist"><ul type="disc"><li><p>
Dans le traitement des entiers, les plus courts étant les meilleurs.
Deux valeurs 32 bits tiennent dans un registre MMX 64 bits, mais forment
aussi une chaîne de huit caractères, ou encore permettent de représenter un
échiquier complet, à raison d'un bit par case. Note : il
<span class="emphasis"><em>existera une version « <span class="quote">virgule flottante</span> » du
MMX</em></span>, bien que très peu de choses aient été dites à ce sujet.
Cyrix a déposé une présentation, <a href="ftp://ftp.cyrix.com/developr/mpf97rm.pdf" target="_top">ftp://ftp.cyrix.com/developr/mpf97rm.pdf</a>, qui contient quelques
commentaires concernant <span class="emphasis"><em>MMFP</em></span>. Apparemment, MMFP
pourra prendre en charge le chargement de nombres 32 bits en virgule
flottante dans des registres MMX 64 bits. Ceci combiné à deux pipelines
MMFP fournirait quatre FLOP <sup>[<a href="#ftn.N111F5" name="N111F5">24</a>]</sup> en simple précision par cycle d'horloge.
</p></li><li><p>
Pour le SIMD, ou parallélisme vectorisé. La même opération s'applique à
tous les champs, simultanément. Il existe des moyens d'annihiler ses
effets sur des champs sélectionnés (l'équivalent du
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">SIMD enable masking</em></span></span> », ou
« <span class="quote">activation du masquage</span> »), mais ils sont compliqués à
mettre en œuvre et grèvent les performances.
</p></li><li><p>
Pour les cas où la référence à la mémoire se fait de manière localisée
et régulière (et de préférence regroupée). Le SWAR en général, et le MMX
en particulier se révèlent désastreux sur les accès aléatoires.
Rassembler le contenu d'un vecteur <code class="literal">x[y]</code> (où
<code class="literal">y</code> est l'index d'un tableau) est extrêmement coûteux.
</p></li></ul></div><p>
Il existe donc d'importantes limitations, mais ce type de parallélisme
intervient dans un certain nombre d'algorithmes, et pas seulement dans les
applications multimédia. Lorsque l'algorithme est adapté, le SWAR est plus
efficace que le SMP ou le parallélisme en <span class="foreignphrase"><em class="foreignphrase">clusters</em></span>… et son utilisation
ne coûte rien !
</p></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1121A"></a>4.2. Introduction à la programmation SWAR</h3></div></div></div><p>
Le concept de base du 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> ») réside dans le fait que l'on peut utiliser des opérations sur
des registres de la taille d'un mot pour accélérer les calculs en effectuant des
opérations parallèles SIMD sur <span class="emphasis"><em>n</em></span> champs
de <span class="emphasis"><em>k</em></span>/<span class="emphasis"><em>n</em></span> bits. En revanche,
employer les techniques du SWAR peut parfois s'avérer maladroit, et certaines de leurs
opérations peuvent au final être plus coûteuses que leurs homologues en série
car elles nécessitent des instructions supplémentaires pour forcer le partitionnement
des champs.
</p><p>
Pour illustrer ce point, prenons l'exemple d'un mécanisme SWAR
grandement simplifié gérant quatre champs de 8 bits dans chaque
registre de 32 bits. Les valeurs de ces deux registres pourraient
être représentées comme suit :
</p><p>
<pre class="programlisting">
PE3 PE2 PE1 PE0
+-------+-------+-------+-------+
Reg0 | D 7:0 | C 7:0 | B 7:0 | A 7:0 |
+-------+-------+-------+-------+
Reg1 | H 7:0 | G 7:0 | F 7:0 | E 7:0 |
+-------+-------+-------+-------+
</pre>
</p><p>
Ceci indique simplement que chaque registre est vu essentiellement comme
un vecteur de quatre valeurs entières 8 bits indépendantes.
Alternativement, les valeurs <code class="literal">A</code> et
<code class="literal">E</code> peuvent être vues comme les valeurs, dans Reg0 et
Reg1, de l'élément de traitement 0 (ou « <span class="quote">PE0</span> » pour
« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">Processing Element 0</em></span></span> »),
<code class="literal">B</code> et <code class="literal">F</code> comme celles de l'élément
1, et ainsi de suite.
</p><p>
Le reste de ce document passe rapidement en revue les classes de
base des opérations parallèles SIMD sur ces vecteurs d'entiers et
la façon dont ces fonctions peuvent être implémentées.
</p><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N11252"></a>4.2.1. Opérations polymorphiques</h4></div></div></div><p>
Certaines opérations SWAR peuvent être effectuées de façon triviale
en utilisant des opérations ordinaires sur des entiers 32 bits, sans
avoir à se demander si l'opération est réellement faite pour agir en
parallèle et indépendemment sur ces champs de 8 bits. On qualifie ce
genre d'opération SWAR de <span class="emphasis"><em>polymorphique</em></span>, parce que
la fonction est insensible aux types des champs (et à leur taille).
</p><p>
Tester si un champ quelconque est non-nul est une opération polymorphique,
tout comme les opérations logiques au niveau du bit. Par exemple, un « <span class="quote">ET</span> »
logique bit-à-bit ordinaire (l'opérateur « <span class="quote"><code class="literal">&</code></span> »
du registre C) effectue son calcul bit-à-bit, quelque soit la taille des champs.
Un « <span class="quote">ET</span> » logique simple des registres ci-dessus donnerait :
</p><p>
<pre class="programlisting">
PE3 PE2 PE1 PE0
+---------+---------+---------+---------+
Reg2 | D&H 7:0 | C&G 7:0 | B&F 7:0 | A&E 7:0 |
+---------+---------+---------+---------+
</pre>
</p><p>
Puisque le bit de résultat <span class="emphasis"><em>k</em></span> de l'opération « <span class="quote">ET</span> » logique
n'est affecté que par les valeurs des bits d'opérande <span class="emphasis"><em>k</em></span>,
toutes les tailles de champs peuvent être prises en charge par une même instruction.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N11278"></a>4.2.2. Opérations partitionnées</h4></div></div></div><p>
Malheureusement, de nombreuses et importantes opérations SWAR ne sont
pas polymorphiques. Les opérations arithmétiques comme l'addition, la
soustraction, la multiplication et la division sont sujettes aux
interactions de la « <span class="quote">retenue</span> » entre les champs. Ces opérations sont
dites <span class="emphasis"><em>partitionnées</em></span> car chacune d'elles doit
cloisonner effectivement les opérandes et le résultat pour éviter les
interactions entre champs. Il existe toutefois trois méthodes différentes
pouvant être employées pour parvenir à ces fins :
</p><div class="sect4" lang="fr"><div class="titlepage"><div><div><h5 class="title"><a name="N11283"></a>4.2.2.1. Instructions partitionnées</h5></div></div></div><p>
L'approche la plus évidente pour implémenter les opérations partitionnées
consiste peut-être à proposer une prise en charge matérielle des
« <span class="quote">instructions parallèles partitionnées</span> » coupant le système de retenue
entre les champs. Cette approche peut offrir les performances les plus
élevées, mais elle nécessite la modification du jeu d'instruction du
processeur et implique en général des limitations sur la taille des
champs (Ex : ces instructions pourraient prendre en charge des champs larges
de 8 bits, mais pas de 12).
</p><p>
Le MMX des processeurs AMD, Cyrix et Intel, Le MAX de Digital, celui d'HP,
et le VIS de Sun implémentent tous des versions restreintes des instructions
partitionnées. Malheureusement, ces différents jeux d'instructions posent
des restrictions assez différentes entre elles, ce qui rend les algorithmes
difficilement portables. Étudions à titre d'exemple l'échantillon d'opérations
partitionnées suivant :
</p><p>
<pre class="programlisting">
Instruction AMD/Cyrix/Intel MMX DEC MAX HP MAX Sun VIS
+---------------------+---------------------+---------+--------+---------+
| Différence Absolue | | 8 | | 8 |
+---------------------+---------------------+---------+--------+---------+
| Maximum | | 8, 16 | | |
+---------------------+---------------------+---------+--------+---------+
| Comparaison | 8, 16, 32 | | | 16, 32 |
+---------------------+---------------------+---------+--------+---------+
| Multiplication | 16 | | | 8x16 |
+---------------------+---------------------+---------+--------+---------+
| Addition | 8, 16, 32 | | 16 | 16, 32 |
+---------------------+---------------------+---------+--------+---------+
</pre>
</p><p>
Dans cette table, les chiffres indiquent les tailles de champ reconnues
par chaque opération. Même si la table exclut un certain nombre d'instructions
dont les plus exotiques, il est clair qu'il y a des différences. Cela a pour effet
direct de rendre inefficaces les modèles de programmation en langages de haut niveau,
et de sévèrement restreindre la portabilité.
</p></div><div class="sect4" lang="fr"><div class="titlepage"><div><div><h5 class="title"><a name="N11295"></a>4.2.2.2. Opérations non partitionnées avec code de correction</h5></div></div></div><p>
Implémenter des opérations partitionnées en utilisant des instructions
partitionnées est certainement très efficace, mais comment faire lorsque
l'opération dont vous avez besoin n'est pas prise en charge par le matériel ?
Réponse : utiliser une série d'instructions ordinaires pour effectuer l'opération
malgré les effets de la retenue entre les champs, puis effectuer la correction
de ces effets indésirés.
</p><p>
C'est une approche purement logicielle, et les corrections apportent
bien entendu un surcoût en temps, mais elle fonctionne pleinement avec
le partitionnement en général. Cette approche est également « <span class="quote">générale</span> »
dans le sens où elle peut être utilisée soit pour combler les lacunes du
matériel dans le domaine des instructions partitionnées, soit pour apporter
un soutien logiciel complet aux machines qui ne sont pas du tout dotées
d'une prise en charge matérielle. À dire vrai, en exprimant ces séquences
de code dans un langage comme le C, on permet au SWAR d'être totalement
portable.
</p><p>
Ceci soulève immédiatement une question : quelle est précisément l'inefficacité
des opérations SWAR partitionnées simulées à l'aide d'opérations non partitionnées ?
Eh bien c'est très certainement la question à 65536 dollars, mais certaines opérations
ne sont pas aussi difficiles à mettre en œuvre que l'on pourrait le croire.
</p><p>
Prenons en exemple le cas de l'implémentation de l'addition d'un vecteur de quatre
éléments 8 bits contenant des valeurs entières, soit <code class="literal">x</code>+<code class="literal">y</code>,
en utilisant des opérations 32 bits ordinaires.
</p><p>
Une addition 32 bits ordinaire pourrait en fait rendre un résultat correct,
mais pas si la retenue d'un champ de 8 bits se reporte sur le champ suivant.
Aussi, notre but consiste simplement à faire en sorte qu'un tel report ne se produise
pas. Comme l'on est sûr qu'additionner deux champs de <span class="emphasis"><em>k</em></span> bits
ne peut générer qu'un résultat large d'au plus <span class="emphasis"><em>k</em></span>+1 bits,
on peut garantir qu'aucun report ne va se produire en « <span class="quote">masquant</span> » simplement le
bit de poids fort de chaque champs. On fait cela en appliquant un « <span class="quote">ET</span> » logique
à chaque opérande avec la valeur <code class="literal">0x7f7f7f7f</code>, puis
en effectuant un addition 32 bits habituelle.
</p><p>
<pre class="programlisting">
t = ((x & 0x7f7f7f7f) + (y & 0x7f7f7f7f));
</pre>
</p><p>
Ce résultat est correct… sauf pour le bit de poids fort de chacun
des champs. Il n'est question, pour calculer la valeur correcte, que
d'effectuer deux additions 1-bit partitionnées, depuis <code class="literal">x</code>
et <code class="literal">y</code> vers le résultat à 7 bits calculé
pour <code class="literal">t</code>. Heureusement, une addition
partitionnée sur 1 bit peut être implémentée à l'aide d'une
opération « <span class="quote">OU Exclusif</span> » logique ordinaire. Ainsi, le résultat est
tout simplement :
</p><p>
<pre class="programlisting">
(t ^ ((x ^ y) & 0x80808080))
</pre>
</p><p>
D'accord. Peut-être n'est-ce pas si simple, en fin de compte. Après tout, cela fait six
opérations pour seulement quatre additions. En revanche, on remarquera
que ce nombre d'opérations n'est pas fonction du nombre de champs. Donc,
avec plus de champs, on gagne en rapidité. À dire vrai, il se peut que
l'on gagne quand même en vitesse simplement parce que les champs sont
chargés et redéposés en une seule opération (vectorisée sur des entiers),
que la disponibilité des registres est optimisée, et parce qu'il y a
moins de code dynamique engendrant des dépendances (parce que l'on évite
les références à des mots incomplets).
</p></div><div class="sect4" lang="fr"><div class="titlepage"><div><div><h5 class="title"><a name="N112DC"></a>4.2.2.3. Contrôler les valeurs des champs</h5></div></div></div><p>
Alors que les deux autres approches de l'implémentation des opérations
partitionnées se centrent sur l'exploitation du maximum d'espace possible
dans les registres, il peut être, au niveau du calcul, plus efficace de
contrôler les valeurs des champs de façon à ce que l'interaction
de la retenue entre ceux-ci ne se produise jamais. Par exemple, si l'on sait que
toutes les valeurs de champs additionnées sont telles qu'aucun dépassement
ne peut avoir lieu, une addition partitionnée peut être implémentée à
l'aide d'une instruction ordinaire. Cette contrainte posée, une addition
ordinaire pourrait en fin de compte apparaître polymorphique,
et être utilisable avec n'importe quelle taille de champ sans programme de
correction. Ce qui nous amène ainsi à la question suivante : Comment s'assurer
que les valeurs des champs ne vont pas provoquer d'événements dus à la
retenue ?
</p><p>
Une manière de faire cela consiste à implémenter des instructions partitionnées
capables de restreindre la portée des valeurs des champs. Les instructions
vectorisées de maximum et de minimum du MAX de Digital peuvent être
assimilées à une prise en charge matérielle de l'écrêtage des valeurs des
champs pour éviter les interactions de la retenue entre les champs.
</p><p>
En revanche, si l'on ne dispose pas d'instructions partitionnées à même
de restreindre efficacement la portée des valeurs des champs, existe-t-il
une condition qui puisse être imposée à un coût raisonnable et qui soit
suffisante pour garantir le fait que les effets de la retenue n'iront pas
perturber les champs adjacents ? La réponse se trouve dans l'analyse des
propriétés arithmétiques. Additionner deux nombres de <span class="emphasis"><em>k</em></span>
bits renvoie un résultat large d'au plus <span class="emphasis"><em>k</em></span>+1 bits.
Ainsi, un champ de <span class="emphasis"><em>k</em></span>+1 bits peut recevoir en toute
sécurité le résultat d'une telle opération, même s'il est produit par
une instruction ordinaire.
</p><p>
Supposons donc que les champs de 8 bits de nos précédents exemples
soient désormais des champs de 7 bits avec « <span class="quote">espaces de séparation
pour retenue</span> » d'un bit chacun :
</p><p>
<pre class="programlisting">
PE3 PE2 PE1 PE0
+----+-------+----+-------+----+-------+----+-------+
Reg0 | D' | D 6:0 | C' | C 6:0 | B' | B 6:0 | A' | A 6:0 |
+----+-------+----+-------+----+-------+----+-------+
</pre>
</p><p>
Mettre en place un vecteur d'additions 7 bits se fait de la manière
suivante : On part du principe qu'avant l'exécution de toute instruction
partitionnée, les bits des séparateurs de retenue
(<code class="literal">A'</code>, <code class="literal">B'</code>,
<code class="literal">C'</code>, et <code class="literal">D'</code>)
sont nuls. En effectuant simplement une addition ordinaire, tous les
champs reçoivent une valeur correcte sur 7 bits. En revanche, certains
bits de séparation peuvent passer à 1. On peut remédier à cela en
appliquant une seule opération supplémentaire conventionnelle et masquant
les bits de séparation. Notre vecteur d'additions entières sur 7 bits,
<code class="literal">x</code>+<code class="literal">y</code>, devient
ainsi :
</p><p>
<pre class="programlisting">
((x + y) & 0x7f7f7f7f)
</pre>
</p><p>
Ceci nécessite seulement deux opérations pour effectuer quatre additions.
Le gain en vitesse est évident.
</p><p>
Les lecteurs avertis auront remarqué que forcer les bits de séparation
à zéro ne convient pas pour les soustractions. La solution est toutefois
remarquablement simple : Pour calculer <code class="literal">x</code>-<code class="literal">y</code>,
on garantira simplement la condition initiale, qui veut que tous les bits
de séparation de <code class="literal">x</code> valent 1 et que tous ceux
de <code class="literal">y</code> soient nuls. Dans le pire des cas, nous
obtiendrons :
</p><p>
<pre class="programlisting">
(((x | 0x80808080) - y) & 0x7f7f7f7f)
</pre>
</p><p>
On peut toutefois souvent se passer du « <span class="quote">OU</span> » logique en s'assurant
que l'opération qui génère la valeur de <code class="literal">x</code>
utilise <code class="literal">| 0x80808080</code> plutôt que
<code class="literal">& 0x7f7f7f7f</code> en dernière étape.
</p><p>
Laquelle de ces méthodes doit-on appliquer aux opérations partitionnées du
SWAR ? La réponse est simple : « <span class="quote">celle qui offre le gain en rapidité le
plus important</span> ». Ce qui est intéressant, c'est que la méthode idéale peut
être différente selon chaque taille de champ, et ce à l'intérieur d'un
même programme, s'exécutant sur une même machine.
</p></div></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N11349"></a>4.2.3. Opérations de communication et de conversion de type</h4></div></div></div><p>
Bien que certains calculs en parallèle, incluant les opérations sur les
pixels d'une image, ont pour propriété le fait que la <span class="emphasis"><em>n</em></span>ième
valeur d'un vecteur soit une fonction des valeurs se trouvant à la <span class="emphasis"><em>n</em></span>ième
position des vecteurs des opérandes, ce n'est généralement pas le cas. Par exemple,
même les opérations sur les pixels telles que l'adoucissement ou le flou réclament
en opérande les valeurs des pixels adjacents, et les transformations comme la transformée
de Fourrier (FFT) nécessitent des schémas de communications plus complexes (et moins
localisés).
</p><p>
Il est relativement facile de mettre efficacement en place un système de communication
à une dimension entre les valeurs du voisinage immédiat pour effectuer du SWAR, en utilisant
des opérations de décalage non partitionnées. Par exemple, pour déplacer une valeur depuis
<code class="literal">PE</code> vers <code class="literal">PE</code>(<span class="emphasis"><em>n</em></span>+1),
un simple décalage logique suffit. Si les champs sont larges de 8 bits, on utilisera :
</p><p>
<pre class="programlisting">
(x << 8)
</pre>
</p><p>
Pourtant, ce n'est pas toujours aussi simple. Par exemple, pour déplacer une valeur
depuis <code class="literal">PE</code><span class="emphasis"><em>n</em></span> vers
<code class="literal">PE</code>(<span class="emphasis"><em>n</em></span>-1), un simple décalage vers la
droite devrait suffire… mais le langage C ne précise pas si le décalage vers la
droite conserve le bit de signe, et certaines machines ne proposent, vers la droite,
qu'un décalage signé. Aussi, d'une manière générale, devons-nous mettre explicitement à
zéro les bits de signe pouvant être répliqués.
</p><p>
<pre class="programlisting">
((x >> 8) & 0x00ffffff)
</pre>
</p><p>
L'ajout de connexions « <span class="quote">à enroulement</span> »
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">wrap-around</em></span></span> ») à l'aide de
décalages non partitionnés <sup>[<a href="#ftn.N11385" name="N11385">25</a>]</sup> est aussi raisonnablement efficace. Par exemple, pour
déplacer une valeur depuis <code class="literal">PE</code><span class="emphasis"><em>i</em></span>
vers <code class="literal">PE</code>(<span class="emphasis"><em>i</em></span>+1) avec
enroulement :
</p><pre class="programlisting">
((x << 8) | ((x >> 24) & 0x000000ff))
</pre><p>
Les problèmes sérieux apparaissent lorsque des schémas de communications
plus généraux doivent être mis en œuvre. Seul le jeu
d'instructions du MAX de HP permet le réarrangement arbitraire des
champs en une seule instruction, nommée <code class="literal">Permute</code>.
Cette instruction <code class="literal">Permute</code> porte vraiment mal son
nom : Non seulement elle effectue une permutation arbitraire des
champs, mais elle autorise également les répétitions. En bref, elle met
en place une opération arbitraire de <code class="literal">x[y]</code>.
</p><p>
Il reste malheureusement très difficile d'implémenter
<code class="literal">x[y]</code> sans le concours d'une telle instruction. La
séquence de code est généralement à la fois longue et inefficace, parce
qu'en fait, il s'agit d'un programme séquentiel. Ceci est très décevant.
La vitesse relativement élevée des opérations de type
<code class="literal">x[y]</code> sur les les supercalculateurs SIMD MasPar
MP1/MP2 et Thinking Machines CM1/CM2/CM200 était une des clés majeures
de leur succès. Toutefois, un <code class="literal">x[y]</code> reste plus lent
qu'une communication de proximité, même sur ces supercalculateurs.
Beaucoup d'algorithmes ont donc été conçus pour réduire ces besoins en
opérations de type <code class="literal">x[y]</code>. Pour simplifier, disons que
sans soutien matériel, le meilleur est encore très certainement de
développer des algorithmes SWAR en considérant <code class="literal">x[y]</code>
comme étant interdit, ou au moins très coûteux.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N113BD"></a>4.2.4. Opérations récurrentes (réductions, balayages, et cætera)</h4></div></div></div><p>
Une récurrence est un calcul dans lequel il existe une relation
séquentielle apparente entre les valeurs à traiter. Si toutefois des
opérations associatives sont impliquées dans ces récurrences, il peut
être possible de recoder ces calculs en utilisant un algorithme
parallèle à structure organisée en arbre.
</p><p>
Le type de récurrence parallélisable le plus courant est probablement
la classe connue sous le nom de réduction associative. Par exemple,
pour calculer la somme des valeurs d'un vecteur, on écrit du code C
purement séquentiel, comme :
</p><p>
<pre class="programlisting">
t = 0;
for (i=0; i<MAX; ++i) t += x[i];
</pre>
</p><p>
Cependant, l'ordre des additions est rarement important. Les opérations
en virgule flottante et les saturations peuvent rendre différents résultats
si l'ordre des additions est modifié, mais les additions ordinaires sur les
entiers (et qui reviennent au début après avoir atteint la valeur maximum)
renverront exactement les mêmes résultats, indépendemment de l'ordre dans
lequel elles sont effectuées. Nous pouvons ainsi réécrire cette séquence
sous la forme d'une somme parallèle structurée en arbre, dans laquelle nous
additionnons d'abord des paires de valeurs, puis des paires de ces sous-totaux,
et ainsi de suite jusqu'à l'unique somme finale. Pour un vecteur de quatre
valeurs 8 bits, seulement deux additions sont nécessaires. La première effectue
deux additions de 8 bits et retourne en résultat deux champs de 16 bits,
contenant chacun un résultat sur 9 bits :
</p><p>
<pre class="programlisting">
t = ((x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff));
</pre>
</p><p>
La deuxième fait la somme de ces deux valeurs de 9 bits dans
un champs de 16 bits, et renvoie un résultat sur 10 bits :
</p><p>
<pre class="programlisting">
((t + (t >> 16)) & 0x000003ff)
</pre>
</p><p>
En réalité, la seconde opération effectue l'addition de deux champs de
16 bits… mais les 16 bits de poids fort n'ont pas de
signification. C'est pourquoi le résultat est masqué en une valeur de 10
bits.
</p><p>
Les balayages (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">scans</em></span></span> »),
aussi connus sous le nom d'opérations « <span class="quote">à préfixe parallèle</span> »
sont un peu plus difficile à mettre en œuvre efficacement. Ceci
est dû au fait que contrairement aux réductions, les balayages peuvent
produire des résultats partitionnées.
</p></div></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N113E5"></a>4.3. SWAR MMX sous Linux</h3></div></div></div><p>
Pour Linux, nous nous soucierons principalement des processeurs IA32. La
bonne nouvelle, c'est qu'AMD, Cyrix et Intel implémentent tous le même
jeu d'instructions MMX. En revanche, les performances de ces différents
MMX sont variables. Le K6, par exemple, n'est doté que d'un seul
<span class="foreignphrase"><em class="foreignphrase">pipeline</em></span> là où le Pentium MMX en a deux.
La seule nouvelle vraiment mauvaise, c'est qu'Intel diffuse toujours ces
stupides films publicitaires sur le MMX… ;-)
</p><p>
Il existe trois approches sérieuses du SWAR par le MMX :
</p><div class="orderedlist"><ol type="1"><li><p>
L'utilisation des fonctions d'une bibliothèque dédiée au MMX. Intel, en
particulier, a développé plusieurs « <span class="quote">bibliothèques de
performances</span> », offrant toute une gamme de fonctions optimisées à
la main et destinées aux tâches multimédia courantes. Avec un petit
effort, bon nombre d'algorithmes non-multimédia peuvent être
retravaillés pour permettre à quelques unes des zones de calcul intensif
de s'appuyer sur une ou plusieurs de ces bibliothèques. Ces
bibliothèques ne sont pas disponibles sous Linux, mais pourraient être
adaptées pour le devenir.
</p></li><li><p>
L'utilisation directe des instructions MMX. C'est assez compliqué, pour
deux raisons : D'abord, le MMX peut ne pas être disponible sur le processeur
concerné, ce qui oblige à fournir une alternative. Ensuite, l'assembleur IA32
utilisé en général sous Linux ne reconnaît actuellement pas les instructions
MMX.
</p></li><li><p>
L'utilisation d'un langage de haut niveau ou d'un module du
compilateur qui puisse directement générer des instructions MMX
appropriées. Quelques outils de ce type sont actuellement en cours de
développement, mais aucun n'est encore pleinement fonctionnel sous
Linux. Par exemple, à l'Université de Purdue (<a href="http://dynamo.ecn.purdue.edu/~hankd/SWAR/" target="_top">http://dynamo.ecn.purdue.edu/~hankd/SWAR/</a>), nous développons
actuellement un compilateur qui admettra des fonctions écrites dans un
« <span class="quote">dialecte</span> » explicite parallèle au langage C et qui générera
des modules SWAR accessibles comme des fonctions C ordinaires, et qui
feront usage de tous les supports SWAR disponibles, y compris le MMX.
Les premiers prototypes de compilateurs à modules ont été générés à
Fall, en 1996. Amener cette technologie vers un état réellement
utilisable prend cependant beaucoup plus de temps que prévu
initialement.
</p></li></ol></div><p>
En résumé, le SWAR par MMX est toujours d'un usage malaisé. Toutefois, avec
quelques efforts supplémentaires, la seconde approche décrite ci-dessus peut
être utilisée dès à présent. En voici les bases :
</p><p>
<div class="orderedlist"><ol type="1"><li><p>
Vous ne pourrez pas utiliser le MMX si votre processeur ne le prend pas
en charge. Le code GCC suivant vous permettra de savoir si votre processeur
est équipé de l'extension MMX. Si c'est le cas, la valeur renvoyée sera
différente de zéro, sinon nulle.
<pre class="programlisting">
inline extern
int mmx_init(void)
{
int mmx_disponible;
__asm__ __volatile__ (
/* Récupère la version du CPU */
"movl $1, %%eax\n\t"
"cpuid\n\t"
"andl $0x800000, %%edx\n\t"
"movl %%edx, %0"
: "=q" (mmx_disponible)
: /* pas d'entrée */
);
return mmx_disponible;
}
</pre>
</p></li><li><p>
Un registre MMX contient essentiellement ce que GCC appellerait un
<code class="literal">unsigned long long</code>. Ainsi, ce sont des variables
de ce type et résidant en mémoire qui vont former le mécanisme de communication
entre les modules MMX et le programme C qui les appelle. Vous pouvez aussi déclarer
vos données MMX comme étant des structures de données alignées sur des adresses
multiples de 64 bits (il convient de garantir l'alignement sur 64 bits en déclarant
votre type de données comme étant membre d'une <code class="literal">union</code>
comportant un champ <code class="literal">unsigned long long</code>).
</p></li><li><p>
Si le MMX est disponible, vous pouvez écrire votre code MMX en utilisant
la directive assemble <code class="literal">.byte</code> pour coder chaque
instruction. C'est un travail pénible s'il est abattu à la main, mais pour un
compilateur, les générer n'est pas très difficile. Par exemple, l'instruction MMX
<code class="literal">PADDB MM0,MM1</code> pourrait être encodée par la ligne
d'assembleur in-line GCC suivante :
<pre class="programlisting">
__asm__ __volatile__ (".byte 0x0f, 0xfc, 0xc1\n\t");
</pre>
Souvenez-vous que le MMX utilise une partie du matériel destiné aux opérations
en virgule flottante, et donc que le code ordinaire mélangé au MMX ne doit pas
invoquer ces dernières. La pile en virgule flottante doit également être vide
avant l'exécution de tout code MMX. Cette pile est normalement vide à l'entrée
d'une fonction C ne faisant pas usage de la virgule flottante.
</p></li><li><p>
Clôturez votre code MMX par l'exécution de l'instruction <code class="literal">EMMS</code>,
qui peut être encodée par :
<pre class="programlisting">
__asm__ __volatile__ (".byte 0x0f, 0x77\n\t");
</pre>
</p></li></ol></div>
</p><p>
Tout ce qui précède paraît rébarbatif, et l'est. Ceci dit, le MMX
est encore assez jeune… de futures versions de ce document proposeront
de meilleures techniques pour programmer le SWAR MMX.
</p></div><div class="footnotes"><br><hr align="left" width="100"><div class="footnote"><p><sup>[<a href="#N111BA" name="ftn.N111BA">23</a>] </sup>
N.D.T. : initialement, huit liens étaient proposés à cet endroit,
devenus pour la plupart obsolètes.
</p></div><div class="footnote"><p><sup>[<a href="#N111F5" name="ftn.N111F5">24</a>] </sup>
N.D.T. : FLOP = « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">FLoating point
OPeration</em></span></span> », ou « <span class="quote">OPération en Virgule
Flottante</span> ».
</p></div><div class="footnote"><p><sup>[<a href="#N11385" name="ftn.N11385">25</a>] </sup>
N.D.T. : il s'agit en fait de simuler la ré-entrée par le coté
opposé des données éjectées par le décalage. L'exemple qui suit permet
d'implémenter ce cas en langage C, mais la plupart des microprocesseurs
sont équipés d'instructions de rotation effectuant cela en une seule
opération.
</p></div></div></div><div class="navfooter"><hr><table summary="Navigation footer" width="100%"><tr><td align="left" width="40%"><a accesskey="p" href="ar01s03.html">Précédent</a> </td><td align="center" width="20%"> </td><td align="right" width="40%"> <a accesskey="n" href="ar01s05.html">Suivant</a></td></tr><tr><td valign="top" align="left" width="40%">3. <span class="foreignphrase"><em class="foreignphrase">Clusters</em></span> de systèmes Linux </td><td align="center" width="20%"><a accesskey="h" href="index.html">Sommaire</a></td><td valign="top" align="right" width="40%"> 5. Processeurs auxiliaires des machines Linux</td></tr></table></div></body></html>
