Brevet FR2438296A1 — publié le 19800430

La présente invention concerne un réseau d'alignement avec accès parallèle pour le traitement des données et en particulier pour classer un vecteur d'ordre d, dont les éléments sont enregistrés à une distance d l'un de l'autre, dans des modules de mémoire, parallèles d'un processeur de données parallèles. Selon l'art antérieur, on connaît un réseau de type cross-bar pour transférer et aligner des données entre un ensemble de modules de mémoire, parallèles et un ensemble de processeurs parallèles. Le réseau cross-bar connu se programme et se commande relativement facilement, toutefois, il est également relativement coûteux, car il faut N2 composants élémentaires pour transmettre les données, N étant le nombre de modules de mémoire parallèles enregistrant les données et qu'il faut aligner. On connaît également des réseaux nécessitant un nombre moins élevé de composants, mais qui posent des problèmes difficiles de commande. De façon caractéristique, un réseau d'alignement de ce type est le réseau Benes qui ne nécessite que 2Nlog2N éléments (voir Benes V.E. "Optimal Rearrangeable Multi-stage Connecting Networks, Part 2" BSTJ Vol. 43, 1964 p.1641. On connaît également des réseaux d'alignement qui nécessitent un nombre plus réduit de composants que le réseau cross-bar et qui ne sont pas trop difficiles à commander ou à programmer, mais nécessitent que les transitions des données multiples traversent, de façon cyclique, une seule couche d'alignement, ce qui augmente le temps nécessaire aux données à traverser le réseau (voir Roger C. Swanson, "Interconnecting for Parallel Memories to Unscramble p-Ordered Vectors", IEEE Trans. Computers, Nov. 1974. Swanson's "p-Ordered Vector" ; la terminologie utilisée dans la présente description concernant les vecteurs d'ordre d est celle de ces documents. La présente invention a pour but de créer un réseau d'alignement pour des vecteurs d, demandant un nombre plus réduit de composants qu'un réseau cross-bar et qui soient néanmoins faciles à commander, et qui ne nécéssitent qu'un seul passage à travers les éléments utilisés pour l'alignement. A cet effet, l'invention concerne un réseau d'alignement applicable à un système de données parallèles avec N modules parallèles, le réseau d'alignement ayant log2N (arrondis au nombre entier le plus proche) de niveau, chaque niveau ayant N éléments de sélection pour fournir un passage direct des données et assurer le décalage par incrément ou la transposition du passage des données. Le degré de décalage pour une transposition dans chaque niveau est égal à k2 (L-l) modulo N, k étant un nombre entier par rapport à N et est la racine primitive de N, L étant le nombre ou l'ordre du niveau. Un signal de commande fourni à chaque niveau détermine si les données traversent directement ou sont transposées. La présente invention sera décrite, plus en détail à l'aide des dessins annexés, dans lesquels - la figure 1 est un schéma-bloc d'un environnement de travail caractéristique d'un réseau d'alignement selon l'invention, - la figure 2 est un schéma-bloc d'un arrangement du réseau d'alignement, selon l'invention, applicable à l'environnement de la figure 1, - la figure 3 est un schéma logique de la porte de sélection à deux entrées du réseau d'alignement de la figure 2, - la figure 4 est un réseau d'alignement de retour, comme complément du réseau d'alignement de la figure 2, - la figure 5 est une illustration d'une mémoire morte (ROM) programmée pour fournir un mot de commande pour les réseaux d'alignement des figures 2 et 4, - la figure 6 comprenant les figures 6A, B et C est un tableau pour la création des mots de commande d'un réseau d'alignement coopérant avec 521 modules de mémoire, parallèles. DESCRIPTION DETAILLEE D'UN MODE DE REALISATION PREFERENTIEL DE L'INVENTION Selon la figure 1, le réseau d'alignement de l'invention assure l'interface entre un ensemble de modules de mémoire MO-M6 et un ensemble d'éléments de traitement PO-P6. On accède aux données enregistrées dans des modules de mémoire MO-M6, en parallèle, par les entrées de mémoire MP-MP1 alignées dans le réseau d'alignement 11 suivant le mot de commande m et qui sont appliquées par les entrées de traitement PPO-PP6 pour le traitement en parallèle par les éléments de traitement PO-P6. La figure 1 représente sept modules de mémoire MO-M6 et sept éléments de traitement PO-P6. En variante, d'autres répartitions peuvent être prévues avec un nombre différent de modules de mémoire et d'éléments de traitement. A titre d'exemple, on a représenté une matrice bi-dimensionnelle 5 x 5 formée d'éléments de données a11... a55 chargée dans les modules de mémoire MO-M6. Pour traiter en parallèle les éléments de données a111 a121 a13, a141 a15, il faut que le réseau d'alignement forme un chemin de passage direct des données entre les entrées de mémoire MPO,MPî, MP2, MP3, MP4 et les entrées de traitement PPO, PP1, PP2, PP3, PP4. Toutefois, pour traiter en parallèle les éléments de données a111 a21, a31, a41 et a511 il faut que le réseau d'alignement joue en principe un rle de décalage pour appliquer tous les éléments de données a11, a211 a311 a4l, a51 aux processeurs PO, P1, P2, P3, P4. Comme on le voit chaque élément de données de l'ensemble a111 a21 a31 a41, a51 est décalé dans 5 modules de mémoire (modulo 7) par rapport à l'élément de donnée précédent. Le décalage se fait suivant la formule modulo 7 puisqu'il y a 7 modules de mémoire MO-M6. De façon générale, le décalage nécessaire se fait selon modulo N, N étant égal au nombre de modules de mémoire A titre d'illustration, on examinera ci-après un exemple caractéristique du fonctionnement du réseau d'alignement 11, selon l'invention, en procédant par un examen général des applications les plus diverses de la présente invention. Selon la figure 2, le réseau d'alignement 11 à 7 entrées de mémoire MPO- MP6 et 7 entrées de traitement PPO-PP6 est divisée en un premier niveau 13, un second niveau 15 et un troisième niveau 17. Chacun des niveaux 13, 15, 17 se compose de 7 portes de sélection 19 à deux entrées, c'est-à-dire une première entrée 21, une seconde entrée 23 et une sortie 25 ainsi que deux entrées de commande de sélection EO, ES. Les entrées de commande des portes de sélection 19 du premier niveau 13 portent les références EO et ES et les entrées de commande des portes de sélection 19 du second niveau i5 portent les références EO', et ES' Lorsqu'un état logique 1 ou niveau vrai est appliqué à l'entrée de commande EO iou EO', EO") on a un chemin de communication de données entre la première entrée 21 et la sortie 25. Lorsqu'un état logique 1 ou niveau vrai est appliqué à l'entrée de commande ES (ou ES', ES") on a un chemin de communication de données entre la seconde entrée 23 et la sortie 25.Toutes les entrées de commande EO ES permettent de recevoir des niveaux binaires complémentaires si bien qu'un état logique ou vrai sur EO implique un niveau logique O ou faux sur ES et inversement. Le mode de réalisation préférentiel d'une porte de sélection 19, simple à deux entrées sera décrit ci-après. Toutes les portes de sélection 19 d'un certain niveau 13, 15, 17 peuvent avoir des entrées de commande EO, ES branchées en parallèle. Ainsi, trois bits d'un mot de commande m déterminent le cheminement de données ou le décalage entre les entrées de mémoire MPO ou MP6 et les entrées de traitement PPO-PP6. Le bit le plus significatif de m commande le niveau 17, le seond bit significatif commande le niveau 15 et le dernier bit significatif commande le niveau 13. En principe, le mot de commande m assure la commande de l'entrée ES des portes de sélection 19 et le complément binaire de m est appliqué à l'entrée EO des portes 19. Selon la figure 2, un mot de commande m est égal 000 ne produit aucun décalage, si bien que l'on a un passage direct de données entre les entrées de mémoire MPO-MP6 et les entrées de traitement PPO-PP6. Pour un mot de commande m égal à 100, on a un décalage de 4 (modulo 7) dans le niveau 17 et aucun décalage dans les niveaux 13 et 15, De la même manière, un mot de commande m égal à 010 introduit un décalage de 2 (modulo 7) dans le niveau 15 et un mot de commande m égal à 001 introduit un décalage de 3 (modulo 7) dans le niveau 13. Il est également possible d'assurer un décalage dans plus d'un niveau à la fois. Par exemple, un mot de commande m égal à 111, entraîne un décalage dans les trois niveaux 13, 15, 17. Toutefois, en pratique pour le réseau d'alignement 11 de la figure 2, il n'est pas nécessaire d'avoir des mots de commande égaux à 110 et à 111, puisqu'on arrive au même décalage, en utilisant respectivement les mots de commande 000 et 001. La porte de sélection 19 se réalise, comme indiqué à la figure 3, à l'aide d'une première porte ET 27, d'une seconde porte ET 29 et d'une porte OU 31. La porte ET 27 est reliée à EO et comporte une entrée directe 21 La porte ET 29 est reliée à ES et comporte une entrée de décalage 23. La porte OU 29 est reliée aux sorties des deux portes ET 27, 29 et présente une sortie 25. Dans certaines familles logiques la porte OU 29 peut être une porte OU réalisée par câblage au lieu d'une porte, en tant que telle. La réalisation de la porte de sélection 19, comme décrit ci-dessus est unidirectionnelle, car elle assure seulement le passage des données des entrées de mémoire MPO-MP6 vers les entrées de traitement PPO-PP6. C'est pourquoi, il faut prévoir un chemin inverse pour permettre aux données de passer des entrées de traitement PPO-PP6 vers les entrées de mémoire. Un tel passage inverse se réalise facilement, comme indiqué à la figure 4, à l'aide d'un premier niveau 13', d'un second niveau 15' et d'un troisième niveau 17'. Chaque niveau 13', 15', 17' comporte 7 portes de sélection 19 à deux entrées ; chaque porte transfère les données en retour vers les entrées de mémoire MPO-MP6 de la même manière que les données sont transférées aux entrées de traitement PPO-PP6 (figure 2). Par comparaison, les figures 2 et 4, on voit que le seul mot de commande m permet d'extraire des données des entrées de mémoire MPO-MP6 de les envoyer aux entrées de traitement choisies PPO-PP6 et de les retourner aux entrées de mémoireMPO-MP6, d'ou elles sont venues.Chaque niveau 13', 15' et 17' correspond respectivement à ceux de la figure 2, car le passage inverse des données se fait vers les entrées de mémoireMPO-MP6 de la même manière que le passage vers les entrées de traitement PPO-PP6 Le réseau d'alignement 11 décrit ci-dessus, dans le cas d'un système ayant 7 entrées de mémoire peut s'étendre au cas général d'un nombre N d'entrées de mémoire. Dans ca cas général, le réseau d'alignement 11 comporte plusieurs niveaux, chaque niveau ayant N portes de sélection 19 à deux entrées. Le nombre de niveaux est égal à log2(N) arrondi au nombre entier, le plus proche. Dans l'exemple ci-dessus, N est égal à 7 et log2(N) arrondi au nombre entier le plus proche est égal à 3.Le nombre total de portes 19 nécessaire dans le cas général est alors N x log2N arrondi au nombre entier le plus proche Chaque niveau du réseau d'alignement 11 permet soit un passage des données directement à travers ce réseau ou un décalage des données suivant le mot de commande m et en particulier pour des niveaux de tension appliqués aux bornes ES et EO de chaque porte de sélection 19. Le degré de décalage dans chaque niveau est égal à k2(L-l) modulo N, relation dans laquelle k est un nombre premier relatif N et correspond à la racine primitive de N, N étant le nombre de modules de mémoire et L le rang du niveau dans le réseau d'alignement 11. Par exemple, selon la figure 2, k = 3 et le décalage qui se fait dans le premier niveau 13 est égal à 32(1 1) = 3. Dans le second niveau 15, le décalage est égal à 32(2-1) modulo 7 = 2. Dans le troisième niveau 17, le décalage est égal 32(3#1) à 32(3 1) modulo 7 = 4. En fonctionnement, la distance d (qui est la distance entre deux éléments auxquels on veut accéder) est connue et il faut créer la valeur m e Par exemple, à la figure 1, pour accéder aux éléments a111 al2, a13, a141 a15, la distance d est égale à l'unité et aucun décalage n'est nécessaire dans le réseau d'alignement. Dans ce cas, m est égal à zéro. Toutefois, pour accéder aux éléments de données all, a21 a311 a41, a511 la distance d est égale à 5 et il faut calculer le mot de commande m pour créer le décalage adéquat par le réseau d'alignement 11. Le calcul de m est dérivé de la relation d = km modulo N (voir figure 5) qui illustre la création de m pour le système de la figure 2. Dans le mode de réalisation préférentiel, la valeur d est utilisée pour adresser m une mémoire ROM programmée, suivant l'équation d = km modulo N pour donner- la valeur m à l'adresse d. La figure 5 montre la création de m pour les valeurs de d dans le système avec k = 3 et N = 7. En variante m pourrait également être créé par un programme, en donnant les valeurs d, k et N Toutefois, il est préférable de former m à l'aide d'un circuit puisque dans les processeurs parallèles, la vitesse est pratiquement toujours la même. Le réseau d'alignement 11 de la figure 2 a été développé dans le cas d'un système à 7 modules de mémoire et avec k = 3. D'autres montages peuvent être envisagés. Par exemple dans un système à 17 modules de mémoire on peut utiliser k = à 3,5, 6, 7, 10, 11, 12, 14. La figure 6 donne sous la forme d'un tableau la création de m pour un système avec k = 3 et un nombre N de modules de mémoire égal à 521. On peut envisager d'autres réalisations de la présente invention. A titre d'exemple, selon la figure 2, on peut combiner les niveaux en parallèle plutôt qu'en série. Lorsque deux niveaux sont combinés, par exemple le niveau 13 et le niveau 15, il faut que chaque porte de section 19 présente quatre entrées et non pas deux pour assurer le décalage nécessaire dans le niveau 13, le déclage du niveau 15, le décalage combiné des niveaux 13 et 15 et le passage direct des données, La réalisation est ainsi plus complexe pour les portes 19 lorsque le nombre de portes 19 et le nombre de niveaux augmente. On peut faire un parallèle en combinant tous les niveaux 13, 15, 17 et en utilisant huit portes de délection d'entrées 19. En outre, dans certaines applications il peut être intéressant d'introduire un moyen d'enregistrement des données de décalage et de traitement entre le réseau d'alignement selon l'invention et les modules de mémoire en parallèle enregistrant les données à aligner. Par exemple, un tel dispositif peut être le commutateur électronique Barrel pour le décalage des données comme décrit dans le brevet U.S 3 610 903. Le commutateur décrit à ce brevet se compose d'une matrice rectangulaire de portes assurant le décalage suivant une seule cadence avec une entrée en parallèle à bits multiples, et un nombre pré-sélectionné d'emplacements vers la gauche ou la droite avec extrémité bloquée ou extrémité circulante. Le commutateur ci-dessus permet de stocker des vecteurs d'ordre d dans une mémoire en divers points de base ou de départ pour les décaler vers la position de démarrage la plus à gauche de la mémoire et de traiter ces vecteurs par le réseau d'alignement. D'autres variantes sont possibles. Par exemple, selon les figures 2 et 4, la porte de sélection 19 la plus à gauche dans tous les niveaux 13, 15, 17 assure seulement un passage direct des données quel que soit le mot de commande m. Ainsi, dans beaucoup d'applications on peut supprimer la porte de sélection 19 la plus à gauche. REVENDICATIONS 10) Réseau d'alignement avec accès parallèle à ces données pour aligner des données entre N entrées et N sorties, carac tarisécomposé d'un nombre log2N (arrondi au nombre entier le plus voisin) de niveaux ordonnés branchés en série entre les N entrées et les N sorties, chaque niveau ordonné se composant d'un ensemble N de caneaux d'entrée recevant des données en parallèle du niveau ordonné,précédent, dans un ensemble de niveaux ordonnés, un ensemble de N caneaux de sortie pour émettre les données en prallèle vers le niveau suivant de cet ensemble de niveaux ordonnés, un moyen pour assurer le passage direct des données entre un canal d'entrée et entre un canal d'entrée parmi les N caneaux d'entrée et un canal de sortie parmi N caneaux de sortie, ainsi qu'un moyen pour assurer le passage sélectif direct des données et le passage transposé des données entre tous les caneaux dans les N caneaux d'entrée et N caneaux de sortie, la transposition étant égale en nombre à k élevé à la puissance 2 lui-même élevé à la puissance(L - 1) k étant un nombre premier relatif pour N et la racine primitive de N, L étant l'ordre du niveau dans l'ensemble des niveaux ordonnés. 20) Réseau selon la revendication 1, caractérisé en ce que le moyen assurant le passage direct sélectif des données et le passage transposé des données se compose d'un ensemble de N-1 portes de sélection à deux entrées, chaque porte de délection étant reliée séparément par sa sortie à un canalde sortie distinct de l'ensemble des N caneaux de sortie. 30) Réseau selon la revendication 2, caractérisé en ce que chaque porte de sélection de l'ensemble se compose d'un moyen mis en oeuvre par des signeaux de commande binaires pour commander le chemin de passage des données entre l'une des deux entrées et la sortie.