Brevet FR2918190A1 — publié le 20090102

DISPOSITIF D'ADRESSAGE POUR PROCESSEUR PARALLELE La présente invention concerne un dispositif d'adressage pour processeur parallèle, applicable en particulier à des calculateurs parallèles de type SIMD. Le terme SIMD se réfère à la classification des calculateurs parallèles introduite par Flynn. Il désigne un calculateur parallèle de type Single Instruction Multiple Data Stream (SIMD). ~o Dans le passé, une ou plusieurs cartes électroniques étaient nécessaires pour implémenter un SIMD. Aujourd'hui, un SIMD peut être implanté sur un circuit intégré unique, par exemple un FPGA ou un ASIC. Un SIMD décrit en relation avec la figure 1, comporte un seul séquenceur 1, 15 une seule mémoire d'instructions 2, un grand nombre de processeurs élémentaires 3 ou Processing Elements (PEs). Chaque PE 3 comporte une Unité Arithmétique et Logique (ALU) 31, 20 un ensemble de mémoires et/ou de registres de données 32. A chaque cycle, le séquenceur détermine l'instruction suivante et la lit dans la mémoire d'instructions, transmet cette instruction à tous les PEs. 25 La plupart des instructions définissent : une opération à exécuter l'adresse Ad où aller chercher chaque opérande de l'opération la ou les adresses Ad où stocker le résultat. L'opération à exécuter comprend un ou plusieurs opérandes. Elle 30 peut se limiter à une opération élémentaire (exemple une inversion de signe ou une addition ou un if ou un calcul de maximum) comprenant un ou plusieurs opérandes ou être la combinaison de plusieurs opérations élémentaires comprenant chacune un ou plusieurs opérandes (exemple : une multiplication suivie d'une addition). De même, le résultat peut être 35 stocké à une ou plusieurs adresses. Chaque PE exécute cette même instruction en même temps mais sur des données différentes, en l'occurrence sur l'ensemble de mémoires et/ou de registres qui lui appartient. Bien entendu, lorsque nous disons à chaque cycle, nous parlons d'un cycle logique dont l'exécution peut s'étendre sur plusieurs cycles physiques selon la technique classique du pipeline. L'important est qu'une nouvelle instruction soit démarrée à chaque cycle et qu'une nouvelle instruction soit achevée à chaque cycle. Peut importe si l'exécution de l'instruction s'étend sur plusieurs cycles. Considérons par exemple l'instruction R(23) = R(8) + R(3) * R(19). Elle signifie lire le contenu du registre 3, le multiplier par le contenu du registre 19, ajouter le résultat de cette multiplication au contenu du registre 8 et écrire le résultat de cette addition dans le registre 23. Cette même instruction va être exécutée en parallèle par tous les PEs. Mais chacun l'exécutera sur l'ensemble de registres qui lui appartient. Au total, s'il y a 128 PEs, l'exécution de l'instruction aura pour conséquence que 128 registres 3 seront lus, 128 registres 19 seront lus, 128 registres 8 seront lus, 128 multiplications seront réalisées sur 2 fois 128 valeurs différentes, 128 additions seront réalisées sur 2 fois 128 valeurs différentes et 128 résultats différents seront écrits dans 128 registres 23. L'efficacité d'un SIMD vient de ce haut niveau de parallélisme. En général, sur un SIMD, chaque PE a la possibilité de lire, c'est-à-dire d'aller chercher les opérandes d'une instruction, non seulement dans l'ensemble des mémoires et/ou registres qui lui appartiennent mais également dans tout ou partie de l'ensemble des mémoires et/ou registres qui appartiennent à l'un de ses voisins. Une variante qui peut être un complément ou une alternative est que chaque PE ait la possibilité d'écrire le résultat d'une instruction, non seulement dans des mémoires et/ou registres qui lui appartiennent mais également dans des mémoires et/ou registres qui appartiennent à l'un de ses voisins. La notion de voisinage entre PEs est définie par l'architecture du SIMD et plus précisément par la topologie d'interconnexion entre PEs. Plusieurs topologies d'interconnexion entre PEs ont été proposées. Les plus complexes sont de véritables réseaux d'interconnexion entre PEs. La plus simple est une colonne verticale de PEs. Une autre topologie simple est une grille bidimensionnelle de PEs. On peut aussi imaginer des grilles multidimensionnelles de PEs. En général, dans ces 3 derniers cas, les extrémités sont recollées . Ainsi, dans la topologie mono dimensionnelle, la colonne verticale de PEs devient un cercle de PEs (on dit souvent un anneau de PEs). Grâce à ce recollage, le voisin Sud du PE le plus au Sud est le PE le plus au Nord et le voisin Nord du PE le plus au Nord est le PE le plus au Sud. De même, dans la topologie bidimensionnelle, la grille de PEs devient un tore. Enfin, dans la topologie multidimensionnelle, la grille multidimensionnelle devient un tore multidimensionnel. Dans le cas d'une topologie, mono dimensionnelle (colonne verticale ou anneau de PEs), chaque PE dispose de 2 voisins que nous appellerons N et S (pour Nord et Sud). Dans le cas d'une topologie bidimensionnelle (grille bidimensionnelle ou tore de PEs), chaque PE dispose de 4 voisins que nous appellerons N, S, E, W (pour Nord, Sud, Est, Ouest). Dans le cas d'une topologie multidimensionnelle (grille multidimensionnelle ou tore multidimensionnel de PEs), chaque PE dispose de 2" voisins, si n est la dimension de l'espace. Dans la suite de ce document, nous considérerons d'abord le cas des topologies mono dimensionnelles, puis le cas des topologies 20 bidimensionnelles, puis le cas des topologies multidimensionnelles. Une instruction typique sur un SIMD moderne demande à tous les PEs (ou à certains d'entre eux) d'effectuer une opération la même pour tous, portant sur plusieurs opérandes et de stocker le résultat en un ou plusieurs 25 emplacements. Pour reprendre l'exemple précédent, l'instruction R(23) = R(8) + R(3) * R(19) demande à tous les PEs d'effectuer une opération portant sur 3 opérandes et de stocker le résultat en un emplacement. Dans la plupart des SIMD, l'instruction définit pour chaque opérande et pour chaque résultat, l'adresse où les différents PEs vont lire 30 l'opérande (ou stocker le résultat). En conséquence, pour un opérande donné, comme pour un emplacement de résultat donné, l'adresse est nécessairement la même pour tous les PEs. Une telle approche pose problème, notamment sur des applications typiques des SIMD comme le traitement d'images, la 35 compression d'images, la génération synthétique d'images, le traitement du signal ou certaines techniques de résolution d'équations aux dérivées partielles. Par exemple, lorsque ces applications utilisent des algorithmes dans lesquels un pixel est calculé à partir de ses voisins, et cela que la topologie des PEs soit mono, bi, tri ou multidimensionnelle. Pour illustrer cette difficulté, prenons un exemple mettant en oeuvre du traitement d'images et analysons-le en considérant un SIMD de 16 PEs organisé en anneau. Dans toute la suite de ce document et afin de simplifier les formules mathématiques les processeurs sont numérotés à partir de 0 ; de même pour les lignes et les colonnes d'une structure de données (signal, image ou volume). Une manière classique de ranger les pixels de l'image dans les mémoires des différents PEs est d'utiliser le PEO (PE n 0) pour stocker et traiter la ligne 0 de l'image, le PE1 (PE n 1) pour stocker et traiter la ligne 1 et ainsi de suite jusqu'au PE15 (PE n 15) pour stocker et traiter la ligne 15. Comme une image comporte en général plus de 16 lignes, l'utilisateur utilisera le PEO pour stocker et traiter les lignes 0, 16, 32, 48, 64, 80, ... de l'image, le PEI pour stocker et traiter les lignes 1, 17, 33, 49, 65, 81, ...de l'image et ainsi de suite jusqu'au PE15 pour stocker et traiter les lignes 15, 20 31, 47, 63, 79, 95, ...de l'image. Dans ce rangement, si Np désigne le nombre de PEs et si Lx désigne la largeur de l'image à traiter, un pixel de coordonnées (x, y) est rangé dans le processeur p à l'adresse Ad selon les formules suivantes : p=yMod Np 25 Ad = x + Lx * Int(y / Np), (Int(z) désignant la partie entière de z). Ce rangement est représenté figure 2. Cette figure considère le cas d'une image de largeur 64 pixels et montre une manière usuelle de la ranger sur un SIMD de 16 PEs organisé en topologie anneau. Dans cette figure, les colonnes représentent les colonnes de l'image, les lignes 30 représentent les lignes de l'image, le numéro du PE est indiqué à l'extrême gauche de chaque ligne et l'adresse où est rangé chaque pixel est indiquée à l'intérieur de chaque case. Dans cette figure, comme dans les 2 suivantes, les frontières entre zones d'adresses homogènes (zone ayant la même adresse sur tous les PEs) sont matérialisées par des traits noirs. Par convention, on a choisi une représentation visuelle dans laquelle la gauche d'une image est constituée des pixels d'abscisse faible tandis que le haut d'une image est constitué des pixels d'ordonnée faible. Ainsi, le coin supérieur gauche d'un carré dont les bords sont parallèles aux axes de coordonnées est le point d'abscisse la plus faible et d'ordonnée la plus faible tandis le coin inférieur droit est le point d'abscisse la plus forte et d'ordonnée la plus forte. Cette convention est conservée dans la suite. Ce rangement revient à considérer le SIMD comme un anneau vertical de PEs. On pourrait évidemment faire le choix inverse consistant à considérer le SIMD non pas comme un anneau vertical de PEs mais comme un anneau horizontal et utiliser les PEs pour stocker non plus les lignes mais les colonnes de l'image. La figure 3 illustre ce rangement. En réalité, il ne s'agit que d'un choix de représentation visuelle pour le programmeur qui ne change quasiment rien au niveau de la machine. Ce qui est exposé ci-après concernant une représentation en lignes se généralise bien évidemment à une représentation en colonnes. Le type d'allocation des lignes de l'image aux PEs décrit ci-dessus ne pose aucun problème lorsqu'il s'agit d'opérations simples telles que l'addition de 2 images, la multiplication de 2 images, la multiplication d'une image par une constante, la convolution d'une image par un masque ligne, . En fait, lorsqu'il s'agit d'opérations dans lesquelles les pixels servant d'opérandes et le pixel résultat sont stockés par le même PE. Les choses deviennent plus compliquées lorsqu'il s'agit d'opérations dans lesquelles les pixels servant d'opérandes et le pixel résultat sont stockés par des PEs différents. Par exemple, dans le cas de la convolution d'une image par un masque à 2 dimensions, le PE qui est en charge de stocker le pixel résultat doit aller chercher les opérandes dont il a besoin pour effectuer ses calculs non seulement dans des mémoires et/ou registres qui lui appartiennent mais aussi dans des mémoires et/ou registres qui appartiennent aux PEs voisins, voire aux voisins des voisins, voire encore plus loin. Supposons que l'on veuille effectuer une convolution 3x3 sur un carré 32x32 dont le coin supérieur gauche a pour coordonnées x=8, y=4 et dont le coin inférieur droit a pour coordonnées x=39, y=35 et stocker le résultat sur un carré 32x32 dont le coin supérieur gauche a pour coordonnées x=8, y=68 et dont le coin inférieur droit a pour coordonnées x=39, y=99. On rappelle comme indiqué plus haut que dans le repère xy considéré, l'axe des x est croissant de gauche à droite, l'axe des y de haut en bas. Soient a(-1, -1), a(0, -1), a(1, -1), a(-1, 0), a(0, 0), a(1, 0), a(-1, 1), a(0, 1), a(1, 1), les 9 coefficients du filtre de convolution. Soient I(x,y) les pixels de l'image d'origine. Soient R(x,y+64) les pixels de l'image résultat. Le calcul à effectuer, pour chaque valeur de x comprise entre 8 et 10 39 et pour chaque valeur de y comprise entre 4 et 35 est le suivant : R(x,y+64) = a(-1, -1) * I(x-1, y-1) + a(0, -1) * I(x, y-1) + a(1, -1) * I(x+1, y-1) + a(-1, 0) * I(x-1, y) + a(0, 0) * I(x, y) + a(1, 0) * I(x+1, y) + a(-1, 1) * y+1) + a(0, 1) * I(x, y+1) + a(1, 1)) * I(x+l, y+1). La lère opération est d'effectuer cette convolution sur un 15 segment vertical 16x1 dont l'extrémité supérieure a pour coordonnées x=8, y=4 et dont l'extrémité inférieure a pour coordonnées x=8, y=19. Ce segment apparaît en gris foncé sur la figure 2. La lère étape de cette lère opération est de lire un segment vertical 16x1 dont l'extrémité supérieure a pour coordonnées x=7, y=3 et dont l'extrémité inférieure a pour coordonnées x=7, 20 y=18. Ce segment apparaît en gris clair sur la figure 2. Chacun des 16 pixels lus est multiplié par le 1 er coefficient du masque de convolution. L'étape suivante est de lire un segment vertical 16x1 dont l'extrémité supérieure a pour coordonnées x=8, y=3 et dont l'extrémité inférieure a pour coordonnées x=8, y=18. Chacun des 16 pixels lus est multiplié par le 2ème coefficient du 25 masque de convolution et le résultat de cette 2ème multiplication est ajouté au résultat de la lère multiplication. Et ainsi de suite pour les 9 coefficients du masque de convolution. (9 coefficients car nous avons pris l'exemple d'une convolution 3x3). Le résultat est alors stocké sur un segment vertical 16x1 dont l'extrémité supérieure a pour coordonnées x=8, y=68 et dont 30 l'extrémité inférieure a pour coordonnées x=8, y=83. La lère opération est alors achevée. Il y a ensuite 31 opérations similaires pour traiter les 31 colonnes restantes de la moitié supérieure du carré à traiter puis 32 opérations similaires pour traiter les 32 colonnes de la moitié inférieure de ce carré. La difficulté apparaît dès la 1ère étape de la 1ère opération. Elle est ensuite la même pour toutes les étapes de toutes les opérations. Pour cette 1ère étape, il faut lire un segment vertical 16x1 dont l'extrémité supérieure a pour coordonnées x=7, y=3 et dont l'extrémité inférieure a pour coordonnées x=7, y=18. Comme le montre la figure, les pixels à lire pour les PEs 3 à 15 sont rangés à l'adresse 7 tandis que les pixels à lire pour les PEs 0 à 2 sont rangés à l'adresse 71. Or, sur un SIMD conventionnel le séquenceur envoie la même adresse à tous les PEs. On peut objecter que l'exemple choisi concerne un rectangle dont les bords ne sont pas alignés sur les frontières entre zones d'adresses homogènes, c'est-à-dire un rectangle dont le bord supérieur a une ordonnée qui n'est pas un multiple du nombre de PEs. Cette objection ne résiste pas à l'analyse. D'une part, le cas de devoir traiter de tels rectangles est un cas fréquent en traitement d'images. D'autre part, même si le rectangle contenant l'image résultat avait des bords alignés sur les frontières entre zones d'adresses homogènes, il faudrait néanmoins, pour traiter les différentes étapes d'une convolution 3x3 aller chercher comme opérandes des segments verticaux 16x1 dont les extrémités ne seraient pas toutes alignées sur les frontières entre zones d'adresses homogènes. Plusieurs techniques ont été proposées pour contourner cette difficulté. Une lère technique est un chargement en 2 temps avec une activation conditionnelle des PEs. Dans un 1er temps, seuls les PEs devant lire à l'adresse 7 réalisent effectivement l'opération de lecture. Dans un 2ème temps, seuls les PEs devant lire à l'adresse 71 réalisent effectivement l'opération de lecture. C'est donc le programmeur de l'application qui doit gérer le fait que, pour réaliser cette lère étape, certains PEs doivent charger comme opérande un pixel qu'ils ont rangé à l'adresse 7 tandis que d'autres PEs doivent charger comme opérande un pixel qu'ils ont rangé à l'adresse 71. D'où une difficulté importante pour programmer ce type de machine. Mais aussi une moindre efficacité d'exécution due au surplus d'instructions à exécuter. Une 2ème technique est la mise en place d'un registre 35 d'indirection au sein de chaque PE. Un régistre d'indirection est un registre qui permet d'accéder à un mot dont l'adresse est contenue dans ce registre. Grâce à ce registre d'indirection, chaque PE peut calculer une adresse qui lui est propre, la charger dans le registre d'indirection et s'en servir pour accéder à sa propre mémoire. Mais, comme pour la 1 ère technique, on retrouve d'une part une difficulté supplémentaire de programmation puisque c'est le programmeur d'application qui doit gérer la difficulté et d'autre part une moindre efficacité d'exécution due au surplus d'instructions à exécuter. D'autres techniques ont été imaginées. Toutes ont en commun le fait qu'elles conduisent d'une part à une difficulté supplémentaire de programmation et d'autre part à une moindre efficacité d'exécution due au surplus d'instructions à exécuter. La difficulté est encore plus grande si l'on utilise un SIMD organisé selon une topologie bidimensionnelle. Les figures 4 reprennent le même exemple d'une image de largeur 64 pixels mais utilise un SIMD de 16 PEs organisé en topologie tore 4x4. Pour la 1 ère étape de la 1 ère opération, il faut lire un carré 4x4 dont le coin supérieur gauche a pour coordonnées x=7, y=3 et dont le coin inférieur droit a pour coordonnées x=10, y=6. Ce carré apparaît en gris clair sur la figure 4a. Comme le montre la figure 4b, les pixels à lire sont rangés non plus à 2 adresses différentes comme précédemment mais à 4 adresses différentes : adresse 1 pour le PE15, adresse 2 pour les PE 12, 13, 14, adresse 17 pour les PE 3, 7, 11, adresse 18 pour les autres PEs. La difficulté croît encore si l'on utilise un SIMD organisé selon une topologie multidimensionnelle. Par exempte, les pixels à lire sont rangés à 8 adresses différentes en topologie tridimensionnelle et à 16 adresses différentes en topologie quadri dimensionnelle. Sauf cas particuliers (position particulière de la zone à lire ou écrire) où le nombre d'adresses différentes est inférieur. Le but de l'invention est de pallier ces inconvénients. L'invention est basée sur la notion de champ d'action d'un opérande ou d'un résultat ; plus précisément, sur le fait que ce champ d'action est défini non pas par référence à des adresses de rangement dans les mémoires des PEs, mais par référence à la position du champ d'action dans la structure de données que l'on traite (signal ou image ou volume ou ...), soit à un niveau d'abstraction supplémentaire. Une instruction typique sur un SIMD moderne demande à tous les PEs ou à certains d'entre eux d'effectuer une opération la même pour tous, portant sur plusieurs opérandes et de stocker le résultat en un ou plusieurs emplacements. Par champ d'action d'un opérande, on entend l'ensemble des éléments d'une structure de donnée lus par les PEs pour acquérir cet opérande. De même, par champ d'action d'un résultat on entend l'ensemble des éléments d'une structure de donnée écrits par les PEs pour stocker le résultat. En reprenant l'exemple de la figure 2, la lève étape de la lève opération nécessite de lire un segment vertical 16x1 dont l'extrémité supérieure a pour coordonnées x = 7, y = 3 et dont l'extrémité inférieure a pour coordonnées x = 7, y = 18. Le champ d'action de l'opérande I(x-1, y-1) est composé des pixels de coordonnées (x = 7, y = 3), (x = 7, y = 4), (x = 7, y = 5), ..., (x = 7, y = 18) ; comme le montre la figure, les pixels à lire pour les PEs 3 à 15 sont rangés à l'adresse 7 tandis que les pixels à lire pour les PEs 0 à 2 sont rangés à l'adresse 71. Or, dans un calculateur SIMD conventionnel, l'instruction définit pour chaque opérande et pour chaque résultat, l'adresse où les différents PEs vont lire l'opérande ou stocker le résultat. En conséquence, un SIMD conventionnel ne sait prendre en compte que des champs d'action correspondant à des zones d'adressage homogène. Par exemple, dans un SIMD conventionnel, il est possible de prendre en compte un champ d'action dont l'extrémité supérieure a pour coordonnées x = 7, y = 0 et dont l'extrémité inférieure a pour coordonnées x = 7, y = 15, car tous ces pixels sont rangés à l'adresse 7, ou un champ d'action dont l'extrémité supérieure a pour coordonnées x = 7, y = 16 et dont l'extrémité inférieure a pour coordonnées x = 7, y = 31 car tous ces pixels sont rangés à l'adresse 71, mais pas un champ d'action dont l'extrémité supérieure a pour coordonnées x = 7, y = 3 et dont l'extrémité inférieure a pour coordonnées x = 7, y = 18 car certains pixels sont rangés à l'adresse 7 et d'autres à l'adresse 71. Dit autrement dans un SIMD conventionnel il n'est pas possible de prendre en compte un champ d'action lorsque celui-ci chevauche des zones d'adresses inhomogènes. Un processeur parallèle conçu selon l'invention permet aux différents opérandes ou résultats d'une instruction de prendre en compte des champs d'action qui ne correspondent pas nécessairement à des zones d'adresses homogènes. Plus précisément l'invention a pour objet un processeur parallèle qui comprend des processeurs élémentaires (PE) disposés selon une topologie, avec une position déterminée au sein de cette topologie et aptes à exécuter simultanément une même instruction sur des données différentes appartenant à une structure de données, l'instruction portant sur au moins un opérande et/ou fournissant au moins un résultat. Il est principalement caractérisé en ce que l'instruction comprend pour chaque opérande et/ou chaque résultat, des informations relatives à la position d'un champ d'action au sein de la structure de données, un champ d'action d'un opérande étant l'ensemble des éléments d'une structure de données lus par les PEs pour acquérir cet opérande, un champ d'action d'un résultat étant l'ensemble des éléments d'une structure de données écrits par les PEs pour stocker ce résultat, et en ce que le processeur parallèle comprend des moyens de calcul de l'adresse de chaque opérande et/ou de chaque résultat au sein de chaque processeur élémentaire, en fonction de la position du champ d'action et de la position du processeur élémentaire au sein de cette topologie. Le processeur parallèle proposé met en oeuvre le principe suivant : pour chaque opérande et pour chaque élément de la structure de données où stocker le résultat, l'instruction définit non pas l'adresse à laquelle le PE doit lire l'opérande ou écrire le résultat, mais des informations permettant de définir la position du champ d'action de l'opérande ou du résultat au sein de la structure de données. Grâce à ces informations et à une valeur liée à la position de chaque PE, des moyens de calcul permettent à chaque PE de connaître l'adresse à laquelle il doit lire l'opérande ou écrire le résultat. La forme de ces champs d'action (segment horizontal ou vertical, carré, rectangle ou parallélépipède) reste la même que sur un SIMD conventionnel car calquée sur la topologie des PEs. En revanche, la position du champ d'action est définie de manière 35 beaucoup plus flexible que sur un SIMD conventionnel. En particulier, un tel processeur parallèle permet de prendre en compte des champs d'action tels que ceux évoqués dans l'exemple du traitement d'image et illustré par les figures 2, 3 et 4 ; et cela bien que les cellules qui composent ces champs d'action se situent à des adresses différentes selon les PEs. Mais son intérêt va bien au-delà. A titre d'exemple, toutes les applications qui utilisent des algorithmes dans lesquels un pixel est calculé à partir de ses voisins peuvent en bénéficier. Cela englobe le traitement du signal, le traitement d'images, la compression d'images, la génération synthétique d'images et même certaines techniques de résolution d'équations aux dérivées partielles. Un exemple typique est la résolution d'équations aux dérivées partielles dans un espace à 3 dimensions par la méthode des différences finies. Pour ces applications, le bénéfice est double : la programmation d'un algorithme est simplifiée car le 15 programmeur n'a plus à se préoccuper de la notion de frontières entre zones d'adresses homogènes, - l'exécution est accélérée car il y a moins d'instructions à exécuter. Selon une caractéristique de l'invention, le processeur parallèle 20 comprend des moyens de calcul de la position du champ d'action en fonction desdites informations, reliés aux moyens de calcul de l'adresse. Les moyens de calcul de l'adresse au sein de chaque processeur élémentaire en fonction de la position du champ d'action peuvent être soit entièrement localisés au niveau de chaque processeur 25 élémentaire, soit partiellement localisés au niveau de chaque processeur élémentaire et partiellement regroupés entre plusieurs processeurs élémentaires. Le processeur parallèle selon l'invention comprend 30 éventuellement des moyens de calcul de la position du champ d'action en fonction desdites informations. Ces moyens de calcul de la position du champ d'action peuvent être soit entièrement regroupés entre tous les PE, soit entièrement localisés au niveau de chaque processeur 35 élémentaire, soit partiellement regroupés entre plusieurs PE et partiellement localisés au niveau d'autres processeurs élémentaires. De manière générale, les processeurs élémentaires sont disposés selon une topologie à P dimensions, P étant un entier supérieur ou égal à 1 et/ou les données à traiter appartiennent à une structure dans un espace à N dimensions, N étant un entier supérieur ou égal à 1. Selon une caractéristique de l'invention, pour chaque dimension le calcul de l'adresse de l'élément de la structure de données qui concerne un processeur élémentaire d'abscisse p selon ladite dimension, est obtenu par combinaison d'une valeur liée à la position du champ et d'une valeur liée à la position du processeur élémentaire. Selon un mode de réalisation de l'invention, le champ d'action présentant des extrémités définies par ses coordonnées, la position du champ d'action est par exemple définie par la position de l'extrémité dont les coordonnées sont minimales. Selon une caractéristique de l'invention, pour chaque dimension les moyens de calcul de l'adresse de l'élément de la structure de données qui concerne un processeur élémentaire d'abscisse p selon ladite dimension en fonction de la position du champ d'action comprennent des moyens de calcul de : Ad = Int((Wmin + Np ù 1 ù p) / Np), Np étant le nombre de processeurs élémentaires considéré sur ladite dimension, Wmin étant défini sur ladite dimension en fonction des 25 coordonnées de ladite position. Le processeur parallèle est par exemple de type SIMD. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description détaillée qui suit, faite à titre d'exemple non 30 limitatif et en référence aux dessins annexés dans lesquels : la figure 1 déjà décrite représente schématiquement un exemple de calculateur SIMD selon l'état de la technique, la figure 2 déjà décrite illustre, un rangement des 64 x 64 pixels d'une image dans un calculateur SIMD de 16 PEs organisé en anneau, la figure 3 déjà décrite illustre un autre rangement des 64 x 64 pixels d'une image dans un calculateur SIMD de 16 PEs organisé en anneau, les figures 4 déjà décrites illustrent un rangement des 64 x 64 5 pixels d'une image dans un calculateur SIMD de 16 PEs organisé en tore 4 x 4, la figure 4a représentant les PEs concernés, la figure 4b, les adresses à l'intérieur des PEs, la figure 5 représente schématiquement un exemple de processeur parallèle selon l'invention, 10 les figures 6 représentent schématiquement des exemples de réalisation hardware des moyens de calcul d'adresse selon l'invention dans les cas suivants : processeur parallèle mono dimensionnel et structure de données mono dimensionnelle (figure 6a), processeur parallèle mono dimensionnel et structure de données bidimensionnelle (figure 6b), processeur parallèle mono dimensionnel et structure de données multidimensionnelle (figure 6c), - processeur parallèle bidimensionnel et structure de donnéesbidimensionnelle (figure 6d et 6e). D'une figure à l'autre, les mêmes éléments sont repérés par les mêmes références. Selon l'invention, l'instruction définit non pas l'adresse à laquelle 25 chaque PE doit lire un opérande ou écrire, un résultat mais des informations sur la position du champ d'action au sein de la structure de données traitée. Cette position peut être définie soit en valeur absolue, soit en valeur relative par rapport à une position précédente. Un certain nombre d'étapes de calculs sont donc nécessaires pour en déduire une adresse propre à chaque PE. 30 Une l ère étape consiste à calculer la position du champ d'action à partir de l'instruction en cours d'exécution si celle-ci n'est pas définie en valeur absolue par l'instruction. A l'issue de cette 1 ère étape, le résultat est indépendant du PE. Une 2ème étape consiste à calculer l'adresse à laquelle chaque 35 PE doit lire un opérande ou écrire un résultat à partir de la position du champ 15 20 d'action. Comme on le verra dans les exemples plus loin, l'adresse est obtenue par addition ou soustraction d'une valeur liée à la position du champ et d'une valeur liée à la position du PE. A l'issue de cette 2ème étape, le résultat dépend du PE. Selon ce que l'on cherche à optimiser (par exemple : plutôt le nombre de fils ou plutôt le nombre de portes), ces calculs peuvent être soit réalisés au maximum en central donc une fois pour toutes et partagés entre plusieurs PEs, soit au contraire réalisés au maximum en local au niveau de chaque PE ou toute solution intermédiaire de regroupement de certains calculs communs. Les variantes étant très nombreuses, il n'est pas possible de les décrire toutes et on se limitera à quelques exemples. Ainsi, une implémentation illustrée figure 5 peut consister à calculer la position du champ d'action en central par les moyens de calcul 50 tandis que chaque PE utilise cette information pour en déduire une adresse Ad dans son ensemble de mémoires et/ou de registres ; cette adresse est obtenue par les moyens de calcul d'adresse 41, 42, 43 de chaque PE. L'avantage de ce principe est de minimiser le volume de calculs à réaliser dans chaque PE et donc le volume de hardware. Si l'on pousse la délocalisation à l'extrême, une autre implémentation peut consister à tout calculer au niveau de chaque PE: la position du champ d'action et l'adresse correspondante. L'inconvénient de cette variante est d'augmenter le volume de calculs à réaliser dans chaque PE et donc le volume de hardware. Toutefois, elle peut permettre de réduire le volume d'informations à transmettre à tous les PEs et donc le nombre de fils sur le circuit, ce qui peut être intéressant dans certains cas. A l'opposé, on peut souhaiter réduire au minimum le volume de calculs à réaliser dans chaque PE et donc le volume de hardware. Une autre implémentation peut alors consister à mutualiser certains calculs communs à plusieurs PEs au niveau d'un groupe de PEs, voire en central. Nous en verrons un exemple dans le 4ème exemple de réalisation. La réalisation des moyens de calcul d'adresse 41, 42, 43 de chaque PE peut être faite au moyen d'un.hardware câblé ou d'un hardware plus flexible, par exemple un processeur programmable. Les calculs peuvent être également réalisés en pur logiciel par les ALU des PEs, donc sans ajout de hardware supplémentaire, pourvu que chaque PE dispose d'un registre d'indirection. Une telle mise en oeuvre, encore plus économique en hardware, peut donc être intéressante dans certaines applications. Différents choix sont possibles quant aux informations définissant la position du champ d'action. Par exemple le centre du champ ou une extrémité dans une direction définie à l'avance. Comme tous ces choix sont équivalents à une translation près et que le passage de l'un à l'autre est trivial, nous ne nous étendrons donc pas plus sur ce point. On a choisi pour décrire les exemples de réalisation le cas où l'information choisie pour définir la position d'un champ d'action est le point du champ dont toutes les coordonnées sont minimales. Autrement dit, l'extrémité du champ dans la direction du point à l'infini valant -co sur chaque coordonnée. Soit, sur les figures 2, 3 et 4, le point de coordonnées (7, 3) pour la 1ère étape de la 1ère opération. L'invention peut être appliquée à des processeurs parallèles organisés en topologies mono, bi, tri ou multidimensionnelles et, dans chacune de ces topologies, sur des structures de données mono dimensionnelles (ex : signal), bidimensionnelles (ex : image), tridimensionnelles (ex : volume 3D pour la résolution d'équations aux dérivées partielles) ou multidimensionnelles, mais aussi pour différents modes de rangement de chaque structure de données sur chaque type de processeur parallèle. L'invention peut aussi être appliquée à des architectures de traitement faisant intervenir un grand nombre de processeurs élémentaires exécutant le même traitement sur des données différentes, y compris si cette architecture n'entre pas dans la catégorie des SIMD. Par exemple, si la structure de contrôle n'est pas un séquenceur ou n'est pas programmable ou si la programmation se fait à un niveau plus élevé qu'une instruction. On va à présent détailler quelques exemples de réalisation. Le 1 er exemple de réalisation concerne le cas d'un processeur parallèle mono dimensionnel par exemplé un anneau et d'une structure de données mono dimensionnelle par exemple un signal. On considère le cas où l'utilisateur a rangé ses données sur les processeurs parallèles de la manière suivante : l'élément x du signal est rangé dans le PE n p à l'adresse Ad avec : p = x Mod Np Ad = Int(x / Np) Np étant le nombre de PEs. Dans ce cas, l'ensemble des PEs est vu comme un segment de largeur Np et le champ d'action est un segment de largeur Np : il contient Np éléments. On considère le cas où l'information utilisée pour définir la position du champ est l'abscisse de l'extrémité gauche du champ, celle dont l'abscisse est minimum. Soit Xmin cette abscisse ; le champ d'action s'étend donc de Xmin à Xmin+Np-1. Chaque PE est concerné par un et un seul de ces éléments. L'équation permettant de calculer l'adresse de l'élément qui concerne le PE n p au sein du champ est la suivante : Ad = Int((Xmin + Np ù 1 ù p) / Np) Cette équation peut donner lieu à de nombreuses mises en oeuvre, allant du pur hardware au pur logiciel. Mentionnons toutefois une mise en oeuvre hardware particulièrement simple dans le cas où Np est une puissance de 2. Dans ce cas en effet, si LNp désigne le logarithme à base 2 de Np, le mode de calcul de Ad à partir de Xmin est le suivant : Additionner Xmin et (Np-1-p). On remarque d'ailleurs que, pour chaque PE, (Np-1-p) est une constante égale au complément à 2 de p (que l'on obtient en inversant tous les bits de p) et que cette constante peut être conservée en mémoire dans le PE n p. Supprimer les LNp derniers bits du résultat. Au total, il y a une seule addition par PE. Cette mise en oeuvre est illustrée figure 6a pour Np=16, LNp=4 et Xmin est sur 12 bits. Elle se caractérise par le fait que l'adresse à laquelle un PE doit lire un opérande ou écrire un résultat est obtenue par addition (ou soustraction) d'une valeur liée à la position du champ et d'une valeur liée à la position du PE. Ce type de mise en oeuvre particulièrement simple peut être transposé sur tous les exemples de réalisation qui vont être décrits. Plus généralement, il peut être transposé sur tout type de processeur parallèle organisé en topologies mono, bi, tri ou multidimensionnelles et, dans chacune de ces topologies, sur des structures de données mono (ex : signal), bi (ex : image), tri (ex : volume 3D) ou multidimensionnelles. Il suffit en fait de reprendre le calcul en fonction du type de processeur parallèle, de la structure de données et du rangement choisi puis d'adapter la mise en oeuvre en conséquence. ~o Le 2ème exemple de réalisation concerne le cas d'un processeur parallèle mono dimensionnel par exemple un anneau et d'une structure de données bidimensionnelle, par exemple une image. On peut reprendre le calcul fait pour une structure de données mono dimensionnelle en le transposant sur une structure de données 15 bidimensionnelle, en déduire des équations et adapter la mise en oeuvre en conséquence. On peut aussi utiliser un procédé qui permet de traiter une structure de données bidimensionnelle en se ramenant au cas que nous venons d'analyser pour une structure de données mono dimensionnelle. 20 Soit Np le nombre de PEs, Lx la largeur de l'image à traiter, c'est à dire le nombre de pixels sur chaque ligne et Ly sa hauteur c'est à dire le nombre de pixels sur chaque colonne. Il s'agit plus exactement des bornes supérieures pour les nombres de PEs, de pixels sur chaque ligne et chaque colonne. En effet, dans la plupart des cas et à des fins de simplification du 25 hardware, on préfère plonger l'image à traiter dans une image plus grande et donc choisir des valeurs Lx et Ly supérieures aux dimensions de l'image à traiter. D'une part, si l'on doit traiter plusieurs images de tailles différentes, on peut préférer faire un choix unique permettant de traiter la plus large d'entre elles. D'autre part, pour simplifier la mise en oeuvre lorsque celle-ci est en 30 hardware, on choisit souvent une puissance de 2. Une manière de revenir à une structure de données mono dimensionnelle (en d'autres termes, une manière de ranger les pixels sur les PEs) est d'écrire, pour chaque pixel (x, y) : w=x+Lx*y Ce type de rangement utilisé figure 3, revient à considérer l'ensemble des PEs comme un bloc horizontal de PEs, chaque PE étant responsable d'une colonne ou de plusieurs colonnes. Il diffère de celui analysé précédemment et représenté par la figure 2 qui revient à considérer l'ensemble des PEs comme un bloc vertical de PEs, chaque PE étant responsable d'une ligne ou de plusieurs lignes. Dans ce cas, il faut écrire, pour chaque pixel (x, y) : w=y+Ly*x En comparant ces 2 formules, on comprend aisément comment passer d'un rangement à l'autre. On indiquera d'ailleurs ultérieurement une manière générale pour passer d'un rangement à un autre. On se limitera donc pour le moment au 1 er rangement, utilisé figure 3 et caractérisé par la transformation : w=x+Lx*y Grâce à cette transformation, on peut ranger les pixels sur le processeur parallèle comme on l'a fait pour la 1ère réalisation : l'élément w du signal est rangé dans le PE n p à l'adresse Ad avec : p=wModNp Ad = Int(w / Np) Dans ce cas, le champ d'action est un segment horizontal de largeur Np. On considère, à titre d'exemple, le cas où l'information utilisée pour définir la position du champ est la position de l'extrémité du champ dont les coordonnées sont minimales. Soit Xmin, Ymin les coordonnées de ce point. Posons : Wmin = Xmin + Lx * Ymin L'équation permettant au PE n p de calculer l'adresse du pixel qui le concerne au sein du champ est la suivante : Ad = Int((Wmin + Np ù 1 ù p) / Np) C'est la même équation que dans la l ère réalisation. Simplement, Wmin remplace Xmin. On a ainsi un moyen simple de transposer, à une structure de données bidimensionnelle, toute mise en oeuvre utilisable pour une structure de données mono dimensionnelle et notamment celle que nous avons détaillée. Si Np et Lx sont des puissances de 2, il n'y a qu'une seule addition par PE. Désignons par LNp et LLx leurs logarithmes respectifs. Pour simplifier encore la réalisation, plutôt que d'effectuer cette addition sur Wmin, on remarque qu'elle ne porte en réalité que sur Xmin soit sur Lx bits seulement. Les autres opérations sont des concaténations de bits, beaucoup plus simples que des additions. Ainsi simplifié, le mode de calcul de Ad à partir de Xmin, Ymin est le suivant : Additionner Xmin et (Np-1-p). Supprimer les LNp derniers bits du résultat. Concaténer en poids faibles la quantité précédente représentée 10 sur LLx - LNp bits et en poids forts Ymin. Cette mise en œuvre est illustrée par la figure 6b pour Np=16, LNp=4, Xmin et Ymin sur 6 bits. Le 3ème exemple de réalisation est le cas d'un processeur 15 parallèle mono dimensionnel (par exemple un anneau) et d'une structure de données de dimension supérieure à 2. On considère tout d'abord le cas d'une structure de données tridimensionnelle (par exemple un volume 3D). Soit Lx la largeur du volume à traiter et Ly sa profondeur et Lz sa 20 hauteur, ou plus exactement, pour les raisons que nous avons vues précédemment, des bornes supérieures de ces 3 quantités. Une manière de revenir à une structure de données mono dimensionnelle (en d'autres termes, une manière de ranger les pixels sur les PEs) est d'écrire, pour chaque pixel (x, y, z) : 25 w=x+Lx*(y+Ly*z) On considère pour la suite le rangement w = x + Lx * (y + Ly * z). On peut aisément transposer le raisonnement à d'autres rangements tels que : w = x + Lx * (z + Lz * y)) 30 w=y+Ly*(x+Lx*z)) w = y + Ly * (z + Lz * x)) w=z+Lz*(x+Lx*y)) w = z + Lz * (y + Ly * x)) Grâce à cette transformation, on peut ranger les pixels sur le processeur parallèle comme on l'a fait pour la l ère réalisation: l'élément w du signal est rangé dans le PE n p à l'adresse Ad avec : p = w Mod Np Ad = lnt(w / Np) Dans ce cas, l'ensemble des PEs est vu comme un segment horizontal de largeur Np et le champ d'action est un segment horizontal de largeur Np. On considère à titre d'exemple, le cas où l'information utilisée pour ~o définir la position du champ est la position de l'extrémité du champ dont les coordonnées sont minimales. Soit Xmin, Ymin, Zmin les coordonnées de ce point. Posons : Wmin = Xmin + Lx * (Ymin + Ly * Zmin)) L'équation permettant au PE n p de calculer l'adresse du pixel qui 15 le concerne au sein du champ est la suivante : Ad = Int((Wmin + Np û 1 û p) / Np) C'est la même équation que dans la 1ère réalisation. Simplement, Wmin remplace Xmin. On a ainsi un moyen simple de transposer, à une structure de données tridimensionnelle, toute mise en oeuvre utilisable pour 20 une structure de données mono dimensionnelle et notamment celle que nous avons détaillée. Si Np, Lx et Ly sont des puissances de 2, il n'y a qu'une seule addition par PE. On désigne par LNp, LLx et LLy leurs logarithmes respectifs. Pour simplifier encore la réalisation, plutôt que d'effectuer cette addition sur Wmin, on remarque qu'elle ne porte en réalité que sur Xmin soit 25 sur Lx bits seulement. Les autres opérations sont des concaténations de bits, beaucoup plus simples que des additions, Ainsi simplifié, le mode de calcul de Ad à partir de Xmin, Ymin, Zmin est le suivant : Additionner Xmin et (Np-1-p). Supprimer les LNp derniers bits du résultat. 30 Concaténer en poids faibles la quantité précédente représentée sur Lx - LNp bits, en poids moyens Ymin représenté sur Ly bits et en poids forts Zmin représenté sur Lz bits. Le même principe peut être appliqué à des structures de données de dimension quelconque. Ainsi, en dimension 4, il suffit : 35 d'écrire pour chaque pixel (x, y, z, t) : w=x+Lx*(y+Ly*(z+Lz*t)), de définir la position du champ d'action grâce à Xmin, Ymin, Zmin, Tmin, de poser : Wmin = Xmin + Lx * (Ymin + Ly * (Zmin + Lz * Tmin)), 5 et enfin de calculer pour chaque PE : Ad = Int((Wmin + Np ù 1 ù p) / Np. Le 4ème exemple de réalisation est le cas d'un processeur parallèle bidimensionnel par exemple un tore et d'une structure de données 10 bidimensionnelle par exemple une image. Soit Nx le nombre de PEs sur l'axe des x, Ny le nombre de PEs sur l'axe des y et donc Nx*Ny le nombre total de PEs. Soit Lx la largeur de l'image à traiter et Ly sa hauteur, ou comme nous l'avons vu précédemment, des bornes supérieures de ces 2 quantités. De préférence, on choisit Lx et 15 Ly respectivement parmi les multiples de Nx et de Ny. On désigne par (px, py) le PE de coordonnées (px, py) sur le tore des PEs. On considère à titre d'exemple, le cas où l'utilisateur a rangé ses données sur le processeur parallèle de la manière suivante : le pixel (x, y) de l'image est rangé dans le PE (px, py) à l'adresse Ad avec : 20 px = x Mod Nx py=yMod Ny Adx = Int(x / Nx) Ady = Int(y / Ny) Ad = Adx + (Lx / Nx) * Ady 25 Dans ce cas de rangement utilisé figures 4, l'ensemble des PEs est vu comme un rectangle de largeur Nx et de hauteur Ny et le champ d'action est un rectangle de largeur Nx et de hauteur Ny. On remarque que ce rangement est calqué sur le rangement utilisé pour une structure de données mono dimensionnelle. En fait, il 30 reproduit ce rangement dans chacune des 2 directions de l'espace. Le dispositif de traitement sera donc exactement le même, mais devra être appliqué dans chacune des 2 directions de l'espace. On considère toujours à titre d'exemple, le cas où l'information utilisée pour définir la position du champ est le coin du champ dont les 35 coordonnées sont les plus faibles, c'est-à-dire l'extrémité du champ selon la direction du point à l'infini valant -0o sur chaque coordonnée. Soit Xmin, Ymin les coordonnées de ce point. Les équations permettant au PE (px, py) de calculer l'adresse de l'élément qui le concerne au sein du champ sont les suivantes : Adx = Int((Xmin + Nx ù 1 ù px) / Nx) Ady = Int((Ymin + Ny ù 1 ù py) / Ny) Ad=Adx+(Lx/Nx)*Ady On retrouve donc 2 fois, une fois sur l'axe des x, une fois sur l'axe des y, l'équation trouvée sur la lère réalisation et caractéristique du dispositif 1 o proposé. Comme nous l'avons dit, celle-ci peut donner lieu à de nombreuses mises en oeuvre, allant du pur hardware au pur logiciel. Mentionnons toutefois, comme nous l'avons fait pour les réalisations précédentes une mise en oeuvre hardware particulièrement simple dans le cas où Nx, Ny, Lx et Ly sont des puissances de 2. Si LNx 15 désigne le logarithme à base 2 de Nx, LNy le logarithme à base 2 de Ny, LLx le logarithme à base 2 de Lx, LLy le logarithme à base 2 de Ly, le mode de calcul de Ad à partir de Xmin, Ymin est le suivant Additionner Xmin et (Nx-1-px). On remarque que Xmin, Nx et px sont des valeurs communes à une colonne de PEs. Ce calcul n'est donc à 20 faire qu'une seule fois par colonne de PEs. En outre, la quantité (Nx-l-px) est une constante pour une colonne de PEs. Elle peut être conservée dans une mémoire unique pour une colonne de PEs. Supprimer les LNx derniers bits du résultat 4 Adx sur LLx-LNx bits. 25 Additionner Ymin et (Ny-1-py).On remarque que Ymin, Ny et py sont des valeurs communes à une ligne de PEs. Ce calcul n'est donc à faire qu'une seule fois par ligne de PEs. En outre, la quantité (Ny-1-py) est une constante pour une ligne de PEs. Elle peut être conservée dans une mémoire unique pour une ligne de PEs. 30 Supprimer les LNy derniers bits du résultat 4 Ady sur LLy-LNy bits. Ad = Adx + (Lx / Nx) * Ady, ce qui revient à concaténer en poids faible Adx représenté sur LLx-LNx bits et en poids fort Ady représenté sur LLy-LNy bits. On vérifie bien que le type de mise en oeuvre précédent a pu être transposé. Il y a désormais une seule addition par ligne de PEs et une seule addition par colonne de PEs. En outre, ces additions portent sur très peu de bits. D'où une mise en oeuvre encore bien plus économique que celle nécessaire aux réalisations précédentes. Cette mise en oeuvre est illustrée figure 6c pour Nx=4, Ny=4, LNx=2, LNy=2, Xmin et Ymin sur 6 bits. On a analysé successivement 4 réalisations choisies à titre d'exemples : ~o - processeur parallèle mono dimensionnel et structure de données mono dimensionnelle - processeur parallèle mono dimensionnel et structure de données bidimensionnelle - processeur parallèle mono dimensionnel et structure de données 15 multidimensionnelle - processeur parallèle bidimensionnel et structure de données bidimensionnelle. Toutefois, le principe proposé peut être appliqué à des processeurs parallèles organisés en topologies mono, bi, tri ou 20 multidimensionnelles et, dans chacune de ces topologies, sur des structures de données mono, bi, tri ou multidimensionnelles. On peut généraliser de la manière suivante. Soit n la dimension de la structure de données et p la dimension de la topologie du processeur parallèle. 25 Si n=p, on applique le principe dans chacune des p directions, exactement comme nous l'avons vu pour n=2 (4ème réalisation). Si n>p, comme nous l'avons vu dans le cas de la 2ème et de la 3ème réalisation, on réduit la dimension de la structure, en choisissant 2 axes, (puis 2 autres, puis 2 autres, ..., jusqu'à obtenir une structure de 30 dimension p) et à réduire ces 2 axes à un seul en appliquant une formule du type : w = x + Lx * y. Si n On a analysé jusqu'à présent des réalisations mettant en oeuvre un mode de rangement dans lequel 2 éléments successifs sur un axe (l'axe des x par exemple) sont conservés et traités par 2 PEs différents. Typiquement, dans le cas mono dimensionnel (1 ère réalisation), on a ~o considéré, à titre d'exemple, le cas où l'utilisateur a rangé l'élément x du signal dans le PE n p à l'adresse Ad avec : p = x Mod Np Ad = Int(x / Np). De même, dans le cas bidimensionnel (2ème réalisation), nous 15 avons pris pour exemple, le cas où l'utilisateur a rangé le pixel (x, y) dans le PE n p à l'adresse Ad avec : w = x + Lx * y p = w Mod Np Ad = Int(w / Np). 20 Il ne s'agit que d'exemples. Le procédé peut être appliqué à bien d'autres modes de rangement. Ainsi, pour rester dans le cas mono dimensionnel, l'utilisateur peut souhaiter définir une taille Lx et ranger l'élément x du signal dans le PE n p à l'adresse Ad avec : 25 xl =xMod Lx x2 = I nt(x / Lx) p=x2ModNp Ad = xl + Lx * lnt(x2 / Np). II s'agit d'un mode de rangement dans lequel un segment de Lx 30 éléments successifs sur l'axe des x est conservé et traité par le même PE, tandis que le PE suivant conserve et traite le segment suivant. L'équation permettant au PE n p de calculer à partir de Xmin, l'adresse de l'élément qui le concerne au sein du champ est la suivante : Xminl = Xmin Mod Lx 35 Xmin2 = Int(Xmin / Lx) Ad = Xminl + Lx * Int((Xmin2 + Np ù 1 ù p) / Np). Comme on le voit, cela revient à appliquer le procédé sur Xmin2 et à ne pas toucher à Xminl. On considère le cas où Lx et Np sont des puissances de 2 pour lequel une mise en oeuvre hardware particulièrement simple est possible. On désigne par LNp et LLx leurs logarithmes respectifs. Les équations ci-dessus peuvent s'interpréter ainsi : Découper Xmin en 2 parties, les poids faibles sur LLx bits constituant Xminl, les poids forts constituant Xmin2. Appliquer à Xmin2 le dispositif proposé dans la 1ère réalisation. Le résultat est : Int((Xmin2 + Np ù 1 ù p) / Np). Concaténer en poids faibles Xminl représenté sur Lx bits et en poids forts le résultat du dispositif. En d'autres termes, dans le cas où Lx et Np sont des puissances 15 de 2, il faut mettre à part les LLx bits de poids faible de Xmin, appliquer le dispositif aux autres bits de Xmin, concaténer en poids faible les LLx bits mis à part avec le résultat du dispositif. 20 Cette extension est totalement indépendante de l'extension mentionnée au paragraphe précédent ; elle peut lui être couplée. Elle s'applique donc au cas multidimensionnel, tant pour la topologie du processeur parallèle que pour la structure de données. Il suffit de l'appliquer dans chacune des dimensions. En conséquence, le procédé s'applique à tout 25 mode de rangement dans lequel un parallélépipède de taille Lx sur l'axe des x, Ly sur l'axe des y, ... est conservé et traité par le même PE, tandis que les PEs voisins (pour la topologie du processeur parallèle) conservent et traitent les parallélépipèdes voisins (pour la topologie de la structure de données). 30 On peut généraliser à d'autres rangements. Nous allons le montrer dans le cas multidimensionnel en nous plaçant dans le cas où les tailles de la structure de données (Lx, Ly, Lz, ...) ainsi que le nombre de processeurs (Nx, Ny, Nz, ...) dans chaque direction sont des puissances de 2. Le fait de choisir des puissances de 2 permet d'expliquer les opérations à 35 réaliser sur les représentations binaires, ce qui est plus simple, mais on peut généraliser à des valeurs quelconques de Lx, Ly, Lz, ., Nx, Ny, Nz, ... en remplaçant les opérations décrites sur les représentations binaires par des formules mathématiques utilisant des multiplications, des divisions, des modulo et des parties entières comme indiqué dans les exemples précédents. Pour ranger la structure de données sur le processeur parallèle puis appliquer le procédé à ce rangement, on peut procéder ainsi : Concaténer sur un mot unique de LLx + LLy + LLz +.. DTD: . bits les différentes coordonnées du point utilisé pour définir la position du champ ; cela revient à former ce que nous appelions précédemment w...DTD: Permuter l'ordre des bits de w (Il y a autant de rangements possibles que de permutations possibles) soit w' le mot ainsi obtenu. Découper w' en mots de taille LLx, LLy, LLz, ... bits ; soient wx', wy', wz', ... les mots ainsi obtenus. Appliquer le procédé dans chacune des dimensions du processeur parallèle, c'est-à-dire : - ajouter (Nx ù 1 ù px) à wx', -supprimer les LNx derniers bits du résultat ;on obtient Adx', - ajouter (Ny ù 1 ù py) à wy', supprimer les LNy derniers bits du résultat ; on obtient Ady', et ainsi de suite dans chaque direction du processeur parallèle. Permuter à nouveau l'ordre des bits de Adx', Ady', Adz', ... selon une permutation qui n'est pas nécessairement en rapport avec la précédente permutation. On obtient alors les adresses de rangement Adx, Ady, Adz dans chacune des directions du processeur parallèle. Concaténer ces adresses sur un mot unique Ad qui représente l'adresse concernée par le champ au sein de chaque PE. Pour illustrer ceci, on revient sur l'exemple illustré par la figure 2. On rappelle que cet exemple concerne un processeur parallèle mono dimensionnel de 16 PEs organisés en anneau, que la structure de données est une image de taille Lx = 64 et Ly = 64 et que les pixels de l'image sont rangés en ligne. On a donc Np= 164LNp=4 Lx = 64 4 LLx = 6 Ly = 64 4 LLy = 6 L'opération pour passer de Xmin, Ymin à Ad est la suivante : Concaténer Xmin, Ymin sur un mot unique de 6 + 6 = 12 bits. Soit w le mot ainsi obtenu. Permuter les 6 bits de poids faible et les 6 bits de poids fort de w. Soit w' le mot ainsi obtenu. Appliquer le procédé dans le cas d'un processeur parallèle mono dimensionnel, c'est-à-dire : - Ajouter (16 ù 1 ù p) à w', - Supprimer les 4 derniers bits du résultat. On obtient Ad'. Permuter les 2 bits de poids faible et les 6 bits de poids fort de 10 Ad'. Le mot ainsi obtenu est l'adresse Ad. Cela rentre donc bien dans le cadre de la généralisation que nous voulions illustrer. Cette mise en oeuvre est illustrée figure 6d avec Nx=4, Ny=4, LNx=2, LNy=2, Xmin et Ymin sur 6 bits : c'est une variante de la réalisation de la figure 6b avec une modification du mode de rangement. 15 Remarquons que l'on peut rendre la figure 6d plus facile à lire en décroisant les fils sans moindrement modifier le dispositif. On obtient alors la figure 6e. Bien d'autres modes de rangement sont possibles. Les variantes les plus simples consistent par exemple à changer les signes dans les 20 formules ou changer l'ordre des PEs. Il est impossible de les mentionner toutes. REVENDICATIONS 1 Processeur parallèle qui comprend des processeurs élémentaires (3) disposés selon une topologie, avec une position déterminée au sein de cette topologie et aptes à exécuter simultanément une même instruction sur des données différentes appartenant à une structure de données, l'instruction portant sur au moins un opérande et/ou fournissant au moins un résultat, caractérisé en ce que l'instruction comprend pour chaque opérande et/ou chaque résultat, des informations relatives à la position d'un champ d'action au sein de la structure de données, un champ d'action d'un opérande étant l'ensemble des éléments de la structure de données lus par les processeurs élémentaires pour acquérir cet opérande, un champ d'action d'un résultat étant l'ensemble des éléments de la structure de données écrits par les processeurs élémentaires pour stocker ce résultat, et en ce que le processeur parallèle comprend des moyens de calcul de l'adresse de chaque opérande et/ou chaque résultat au sein de chaque processeur élémentaire, en fonction de la position du champ d'action et de la position du processeur élémentaire au sein de la topologie. 2. Processeur parallèle selon la revendication précédente, caractérisé en ce qu'elle comprend des moyens (50) de calcul de la position du champ d'action en fonction desdites informations, reliés aux moyens de calcul de l'adresse. 3. Processeur parallèle selon l'une des revendications précédentes, caractérisé en ce que les moyens (41, 42, 43) de calcul de l'adresse au sein de chaque processeur élémentaire sont localisés au niveau de chaque processeur élémentaire. 4. Processeur parallèle selon l'une des revendications 1 à 2, caractérisé 35 en ce que les moyens de calcul de l'adresse au sein de chaque processeur élémentaire sont partiellement localisés au niveau dechaque processeur élémentaire et partiellement regroupés entre plusieurs processeurs élémentaires. 5. Processeur parallèle selon l'une des revendications précédentes prise 5 en combinaison avec la revendication 2, caractérisé en ce que les moyens de calcul de la position du champ d'action sont : - communs à tous les processeurs élémentaires ou -localisés en totalité ou en partie au niveau des moyens de calcul de l'adresse des données. 10 6. Processeur parallèle selon l'une des revendications précédentes, caractérisé en ce que les processeurs élémentaires sont disposés selon une topologie à P dimensions, P étant un entier supérieur ou égal à 1. 7. Processeur parallèle selon l'une des revendications précédentes, caractérisé en ce que les données à traiter présentent une structure à N dimensions, N étant un entier supérieur ou égal à 1. 20 8. Processeur parallèle selon l'une des revendications précédentes, caractérisé en ce que les processeurs élémentaires étant disposés selon une topologie à au moins une dimension, pour chaque dimension les moyens de calcul de l'adresse de l'élément de la structure de données qui concerne un processeur élémentaire 25 d'abscisse p selon ladite dimension est obtenue par combinaison d'une valeur liée à la position du champ et d'une valeur liée à la position du processeur élémentaire. 9. Processeur parallèle selon l'une des revendications précédentes, 30 caractérisé en ce que le champ d'action présentant des extrémités définies par ses coordonnées, la position du champ d'action est définie par la position de l'extrémité dont les coordonnées sont minimales. 1510. Processeur parallèle selon la revendication précédente, caractérisé en ce que les processeurs étant disposés selon une topologie à au moins une dimension, pour chaque dimension les moyens de calcul de l'adresse de l'élément de la structure de données qui concerne un PE d'abscisse p selon ladite dimension comprennent des moyens de calcul de : Ad = Int((Wmin + Np ù 1 ù p) / Np), Np étant le nombre de processeurs élémentaires considéré sur ladite dimension, Wmin étant défini sur ladite dimension en fonction des 10 coordonnées de ladite position. 11. Processeur parallèle selon la revendication précédente, caractérisé en ce que les processeurs sont disposés selon une topologie à une dimension et la structure de données est monodimensionnelle et en 15 ce que la position du champ d'action est définie par Xmin et Wmin =Xmin. 12. Processeur parallèle selon la revendication précédente, caractérisé en ce que Np étant une puissance de 2, les moyens de calcul de Ad 20 comportent des moyens pour : Additionner Xmin et (Np-1-p), Supprimer les LNp derniers bits du résultat, LNp étant le logarithme à base 2 de Np. 25 13. Processeur parallèle selon la revendication 10, caractérisé en ce que les processeurs sont disposés selon une topologie à une dimension, et la structure de données est bidimensionnelle, définie en fonction de X et Y, la dimension de la structure selon X étant inférieure à une valeur prédéterminée Lx et en ce que la position du champ d'action 30 est définie par Xmin, Ymin et Wmin =Xmin + Lx * Ymin. 14. Processeur parallèle selon la revendication précédente, caractérisé en ce que Np et Lx étant des puissances de 2, les moyens de calcul de Ad comportent des moyens pour : 35 Additionner Xmin et (Np-1-p),- Supprimer les LNp derniers bits du résultat, LNp étant le logarithme à base 2 de Np, - Concaténer en poids faible la quantité précédente représentée sur LLx-LNp bits et en poids fort Ymin, LLx 5 étant le logarithme à base 2 de Lx. 15. Processeur parallèle selon la revendication 10, caractérisé en ce que les processeurs sont disposés selon une topologie à une dimension, et la structure de données est tridimensionnelle, définie en fonction de ~o X, Y et Z, les dimensions de la structure selon X et Y étant respectivement inférieures à des valeurs prédéterminées Lx et Ly et en ce que la position du champ d'action est définie par Xmin, Ymin, Zmin et Wmin = Xmin + Lx * (Ymin+ Ly * Zmin). 15 16. Processeur parallèle selon la revendication précédente, caractérisé en ce que Np, Lx et Ly étant des puissances de 2, les moyens de calcul de Ad comportent des moyens pour : Additionner Xmin et (Np-1-p), Supprimer les LNp derniers bits du résultat, LNp étant le 20 logarithme à base 2 de Np, Concaténer en poids faible la quantité précédente représentée sur LLx-LNp bits, en poids moyen Ymin représenté sur Ly bits et en poids fort Zmin représenté sur Lz bits, LLx étant le logarithme à base 2 de Lx. 25 17. Processeur parallèle selon la revendication 10, caractérisé en ce que les processeurs sont disposés selon une topologie à une dimension, et la structure de données est à 4 dimensions, définie en fonction de X, Y, Z et T, les dimensions de la structure selon X, Y et Z étant 30 respectivement inférieures à des valeurs prédéterminées Lx, Ly et Lz et en ce que la position du champ d'action est définie par Xmin, Ymin, Zmin, Tmin et Wmin = Xmin + Lx * (Ymin+ Ly * (Zmin + Lz * Tmin)). 18. Processeur parallèle selon la revendication 10, caractérisé en ce que 35 les processeurs sont disposés selon une topologie à deux dimensions,et comprend respectivement Nx et Ny processeurs selon l'une et l'autre dimension, la structure de données est bidimensionnelle, définie en fonction de X et Y, la dimension de la structure selon X étant inférieure à une valeur prédéterminée Lx et en ce que la position du champ d'action est définie par Xmin, Ymin, et -l'adresse Adx de l'élément qui concerne le PE n px considéré selon X au sein du champ est obtenue par la formule Adx = Int((Xmin + Nx û 1 û px) / Nx), - et l'adresse Ady de l'élément qui concerne le PE n py considéré 10 selon Y au sein du champ est obtenue par la formule Ady = Int((Ymin + Ny û 1 û py) / Ny). 19. Processeur parallèle selon la revendication précédente, caractérisé en ce que Nx, Ny, Lx et Ly étant des puissances de 2, LLx et LLy étant 15 respectivement le logarithme à base 2 de Lx et Ly, les moyens de calcul de Ad comportent des moyens pour : Additionner Xmin et (Nx-1-px), Supprimer les LNx derniers bits du résultat, LNx étant le logarithme à base 2 de Nx, on obtient Adx sur LLx-LNx 20 bits, -Additionner Ymin et (Ny-1-py), Supprimer les LNy derniers bits du résultat, LNy étant le logarithme à base 2 de Ny, on obtient Ady sur LLy-LNy bits, 25 - Concaténer en poids faible Adx représentée sur LLx-LNx bits, et en poids fort Ady représenté LLy-LNy bits. 20. Processeur parallèle selon la revendication 10, caractérisé en ce que les processeurs sont disposés selon une topologie à au moins trois 30 dimensions, et comprend respectivement Nx, Ny, Nz, ... processeurs selon chaque dimension, la structure de données est définie sur au moins trois dimensions en fonction de X, Y, Z, ..., la dimension de la structure selon chacune des dimensions étant inférieure à une valeur prédéterminée Lx, Ly, Lz, ... , et Nx, Ny, Nz,..., Lx, Ly, Lz, ... étant 35 des puissances de 2, LLx, LLy, LLz, ... étant les logarithmes à base 2de Lx, Ly, Lz, ..., les moyens de calcul de Ad comportent des moyens pour: Concaténer sur un mot unique de LLx + LLy + LLz + ... bits les différentes coordonnées du point utilisé pour 5 définir la position du champ ; on obtient w, permuter l'ordre des bits de w ; soit w' le mot obtenu découper w' en mots de taille LLx, LLy, LLz, ... bits ; soient wx', wy', wz', ... les mots obtenus, Appliquer dans chacune des dimensions 10 i. ajouter (Nx ù 1 ù px) à wx', supprimer les LNx derniers bits du résultat ;on obtient Adx', iii. ajouter (Ny ù 1 ù py) à wy', iv. supprimer les LNy derniers bits du résultat ; on obtient 15 Ady', v. et ainsi de suite dans chaque direction, Permuter à nouveau l'ordre des bits de Adx', Ady', Adz', ; on obtient alors les adresses de rangement Adx, Ady, Adz dans chacune des directions, 20 - Concaténer ces adresses sur un mot unique Ad qui représente l'adresse concernée par le champ au sein de chaque PE. 21. Processeur parallèle selon l'une des revendications précédentes, 25 caractérisé en ce que le processeur parallèle est un calculateur de type SIMD.