Brevet FR2692382A1 — publié le 19931217

i 2692382 La présente invention concerne un processeur parallèle pour le traitement rapide d'un nombre important de données selon un algorithme identique pour chacune des données Un tel processeur est en particulier destiné au traitement d'images, pixel par pixel, et temps réel. on connait dans l'état de la technique différents types de processeurs à architecture parallèle, en particulier des processeurs fonctionnant selon le mode "simple flot d'instruction, multiple flots de données" Pour les processeurs de l'état de la technique, une seule unité de contrôle gère le fonctionnement d'une pluralité d'unités de calculs, et plusieurs données sont traitées simultanément. L'association d'un nombre important d'unités de calcul interconnectées, intégrant chacune des mémoires vives pour le stockage des données et des informations relatives au traitement, ainsi que le résultat des traitements, forme un réseau matriciel. Le parallélisme de type "simple flot d'instruction, multiple flots de données" est en particulier adapté aux traitements de bas niveau, c'est-à-dire pour les opérations ponctuelles ou sur un voisinage indépendant de la position du pixel dans l'image. Le brevet américain US 4 144 566 décrit en particulier un processeur parallèle comportant un grand nombre de processeurs élémentaires raccordés en parallèle sur un bus d'adresse et un bus de commande, et comportant chacun une mémoire et des moyens de commande et de calcul pour opérer des calculs sur les bits adressés dans la mémoire et sur des bits provenant soit de la mémoire interne, soit d'organes périphériques extérieurs La mémoire de masse et lesdits moyens de commande et de calcul sont interconnectés à une mémoire rapide de faible capacité, les moyens de commande comportant une seule bascule de stockage permettant d'opérer en série des calculs sur 2 2692382 les bits extraits de la mémoire et/ou provenant dudit périphérique. Par "moyen de commande", on entend en particulier des structures permettant d'aiguiller l'information depuis une ou plusieurs sources vers une ou plusieurs destinations, et notamment des multiplexeurs. Afin d'améliorer la puissance et la vitesse de calcul, le brevet américain US 4 215 401 décrit un processeur parallèle massif comportant une pluralité d'unités de calcul élémentaires UCE, chacune des unités de calcul élémentaires étant reliée aux unités de calcul élémentaires voisines pour former une matrice d'unités de calcul élémentaires interconnectées de dimension N x M Les unités de calcul élémentaires sont en outre reliées à un contrôleur central. Chacune des unités de calcul élémentaires comprend une mémoire vive, un accumulateur à un bit d'entrée, un accumulateur à un bit de sortie et une porte NAND L'usage de portes NAND comme l'unité de traitement, et l'organisation des mémoires impliquent une relative complexité des séquences d'instruction et une limitation de la vitesse de traitement. Le brevet européen O 122 048 divulgue un Ordinateur de traitement en parallèle de données, comprenant une pluralité de cellules de traitement (P) et un dispositif de commande pour engendrer des signaux de commande en réponse à des instructions de programme, chaque cellule comprenant un élément de traitement arithmétique ayant trois bornes d'entrée (Dl, D 2,C) et une pluralité de bornes de sortie (PLUS, RETENUE; +, CY, BW) Chaque cellule comprend en outre une pluralité de mémoires pouvant être commandées pour fournir des signaux d'entrée de données aux bornes d'entrée de l'élément de traitement en réponse a des signaux de commande provenant du dispositif de commande Les mémoires sont connectées au dispositif de commande et a l'élément de traitement arithmétique 3 2692382 de telle sorte qu'à la fois des opérations arithmétiques et des opérations logiques, comprenant des opérations logiques mettant en jeu une pluralité de signaux d'entrée de données, puissent être exécutées par l'élément de traitement arithmétique en réponse à l'application sélective d'un niveau logique de UN binaire ou de ZERO binaire en provenance de l'une des mémoires à l'une des bornes d'entrée de l'élément de traitement. Le but de la présente invention est d'optimiser le processeur afin d'équilibrer les ressources consacrées à la gestion de la mise en forme des données et à l'alimentation des unités de calcul élémentaires en données d'une part, et les ressources consacrées à l'exécution des traitement logiques et/ou arithmétique d'autre part. A cet effet, l'invention concerne plus particulièrement un processeur parallèle constitué, outre une partie de contrôle générant l'ensemble des commandes nécessaire au fonctionnement de la partie affectée au calcul et à la gestion des données, par: un ensemble d'UCE de a séries de Kunités de calcul élémentaires UC Eij, i désignant un entier compris entre 1 et acet j désignant un entier compris entre 1 et K, ledit ensemble comportant L lignes d'entrée-sortie, chacune des unités de calcul élémentaires UC Ei,j disposant de M lignes Lce pour l'entrée de données et de N lignes Lcs pour la sortie de données, chacune de ces lignes Lce, Lcs étant connectée à l'une des lignes d'entrée-sortie Lces de l'ensemble; une mémoire de masse de grande capacité disposant de O lignes d'entrée-sortie Lmes pour l'écriture et la lecture de mots de O bits, l'ensemble échangeant des données avec ladite mémoire de masse; une structure de transposition effectuant la transformation dite "directe" d'un ensemble de Q données de P bits en un ensemble de P mots de Q bits, 4 2692382 un mot étant constitué par l'association des Q bits de poids équivalent des Q données, ladite structure de transposition assurant par ailleurs la transformation dite "réciproque" de P' mots de Q' bits en Q' données de P' bits Une telle structure communique avec les ports d'entrée- sortie grâce à l'entrée de "données" ayant respectivement P et P' bits, et avec la mémoire de masse par des "mots" ayant respectivement Q et Q' bits Les lignes permettant ces échanges peuvent être monodirectionnelles ou bidirectionnelles, et distinctes ou communes pour les transferts de "données" et de "mots"; un ensemble de ports permettant l'échange de données entre la structure de transposition ou la mémoire de masse d'une part et l'extérieur d'autre part Les différents ports ne comportent pas obligatoirement le même nombre de lignes, et peuvent être individuellement mono-directionnels ou bidirectionnels; l'ensemble d'UCE échangeant des données avec la mémoire, la mémoire échangeant des données avec la structure de transposition et avec l'ensemble de ports et la structure de transposition échangeant des données avec l'ensemble de ports. Dans la présente description, une "Donnée" regroupe l'ensemble des bits d'une même information. Un "Mot" regroupe l'ensemble des bits de même poids d'un ensemble de données. La transposition de donnée en mot est désignée par "transposition directe" alors que la transposition de "mots" en "données" est désignée par "transposition réciproque". Dans le processeur selon l'invention, chacune des unités de calcul élémentaire UC Ej,j effectue un traitement identique sur les données provenant de la mémoire de masse, selon des instructions fournies de façon identique par le contrôleur central à chaque unité de calcul élémentaire UC Ei,j Ce mode de 2692382 réalisation permet de limiter les flux de données et donc d'accélérer la vitesse de traitement d'un nombre important de données. Le nombre x K d'unités de calcul élémentaires est typiquement compris entre quelques dizaines et plusieurs milliers, et dépend essentiellement des progrès technologiques en matière d'intégration de circuits. Le nombre L de lignes d'entrée-sortie est égal au nombre d'unités de calcul, à un sous-multiple ou à un multiple de ce nombre. Le nombre M d'entrées de chacune des unités de calcul élémentaires est typiquement compris entre 1 et 32. Le nombre N de sorties de chacune des unités de calcul élémentaires est typiquement compris entre 1 et 32. la longueur O de lignes d'entrée-sortie Lmes de la mémoire de masse de grande capacité est égal à L ou à un sous-multiple de L. P et P' sont égaux au nombre de lignes des ports externes auxquels ils sont connectés Q et Q' sont égaux à la longueur O de lignes d'entrée-sortie Lmes de la mémoire de masse ou à des sous-multiple de 0. Les transferts entre l'ensemble d'unités de calcul élémentaires et la mémoire de grande capacité dépendent des valeurs de O et L: * si O = L, l'ensemble des informations présent en sortie d'une des éléments est transféré en un cycle à l'entrée de l'autre élément * si O 6 2692382 mémoire de grande capacité sont transmises en un cycle à O des L lignes de l'ensemble d'unités de calcul élémentaires les unités de calcul élémentaires non sollicitées sont bloquées en écriture. Les transferts entre la mémoire de grande capacité et la structure de transposition dépendent des valeurs de O, Q et Q' * si Q = O L'ensemble des informations présent en sortie de structure de transposition est transféré en un cycle à l'entré de la mémoire de grande capacité * Si Q non sollicitée est bloquée en écriture. * si Q' = L L'ensemble des informations présent en sortie de la mémoire de grande capacité est transféré en un cycle à l'entré de structure de transposition * si Q' de structure de transposition. Les transferts de la mémoire de grande capacité vers l'ensemble de ports ainsi que les transferts entre l'ensemble de ports et la mémoire de grande capacité dépendent des valeurs de R désignant le nombre de lignes du ports sollicité par le transfert qui est inférieur à O. Pour les transferts de la mémoire de grande capacité vers un port configuré en sortie, les informations présentes en sortie de la mémoire de grande capacité sont transmise intégralement ou partiellement en un ou plusieurs cycles, en connectant 7 2692382 R des O lignes de la mémoire de grande capacité aux R lignes du port sollicité en sortie, pour chaque cycle. Pour les transferts d'un port configuré en entrée vers la mémoire de grande capacité, les informations présentes sur le port configuré en entrée sont transmises en un cycle à R des O lignes de la mémoire de grande capacité La partie de la mémoire non sollicitée est bloqué en écriture. Les transferts entre un port et la structure de transposition dépendent des valeurs de P, P' et de R. Les informations présentes en sortie "données" de la structure de transposition sont transmises en un cycle au port configuré en sortie (R = P). Les information présentes sur un port configuré en entrée sont transmises en un cycle à l'entrée "données" de la structure de transposition (R = P). Selon un mode de réalisation simplifié, chacune des K unités de calcul élémentaires UC Ej d'une série i d'unités de calcul élémentaires UC Ei,j accède aux éléments de mémoire Mj-r à Mj+r et écrit dans les éléments de mémoire Mj-s à Mj+s sans échanger de données avec une unités de calcul élémentaires UC Ej T ou jÉj' Avantageusement, chacune des K unités de calcul élémentaires UC Ei,j accède aux éléments de mémoire Mi-t, j-r à Mi+t,j+r et écrit dans les éléments de mémoire Mi-u,j-s à Mi+uj+s sans échanger de données avec une unités de calcul élémentaires UC Eji,jr o iÉil et jÉj'. La présente invention sera mieux comprise à la lecture de la description qui suit, faisant référence aux dessins annexés o: la figure 1 représente schématiquement l'environnement d'un processeur selon l'invention; la figure 2 représente la structure générale du processeur selon l'invention; 8 2692382 la figure 3 représente de façon schématique l'architecture d'un élément de mémoire de la structure de transposition, selon un premier mode de réalisation; - la figure 4 représente le réseau de mémoires et les liaisons avec les différents BUS; la figure 5 représente le schéma de principe d'une cellule du réseau de mémoire; la figure 6 représente de façon schématique l'architecture d'un deuxième mode de réalisation d'un élément de mémoire de la structure de transposition; la figure 7 représente le réseau de mémoires et les liaisons avec les différents BUS; la figure 8 représente le schéma de principe d'une cellule du réseau de mémoire; la figure 9 représente de façon schématique l'architecture d'un troisième mode de réalisation d'un élément de mémoire de la structure de transposition; la figure 10 représente le réseau de mémoires et les liaisons avec les différents BUS; la figure 11 représente le schéma de principe d'une cellule du réseau de mémoire; la figure 12 représente l'architecture d'une Unité de Calcul élémentaire. La figure 1 représente l'architecture d'ensemble d'un exemple d'application d'un processeur selon l'invention La chaîne de traitement d'image comporte essentiellement trois modules ( 1 à 3). Le premier module est constitué par une station de travail en imagerie ( 1) capable d'acquérir et de restituer des images en temps réel, connecté à une caméra numérique ( 5) et à un moniteur ( 6). Cette station de travail est généralement équipée d'un processeur vidéo ( 7) dotée d'une mémoire de programme locale ( 8), d'une mémoire de données ( 9) permettant de mémoriser les informations provenant d'une caméra, ou destinées au transfert vers un moniteur, et de plusieurs opérateurs câblés pour réaliser des fonctions spécifiques. Le deuxième module ( 3) peut être composé d'un processeur unique ou d'un processeur de type Multiple instruction Multiple donnée, dont le processeur élémentaire peut être un processeur classique, un processeur vectoriel, un transputer. Ce deuxième module ( 3) assure les transformations moyen et haut niveau tel que le passage image à liste et le traitement de ces listes. Le troisième module ( 4) est constitué par un processeur selon l'invention, comportant une structure de calcul ( 101) destinée au traitement en temps réel vidéo sur la base d'algorithmes du bas niveau en traitement d'images (calculs sur voisinages). Cette structure de calcul ( 101) reçoit des commandes provenant d'un contrôleur central ( 102) générant les instructions nécessaires au fonctionnement de la structure de calcul ( 101). L'ensemble de l'architecture est connectée d'une part à un BUS industriel standard (référencé "Multibus" sur la figure 1) pour les commandes, et d'autre part sur un ensemble de BUS vidéo numérique (référencé "BUS images" sur la figure 1) pour les échanges de données qui permettent des échanges de type pipeline ou, par un système d'aiguillage, des communications plus complexes. La figure 2 représente la structure générale du processeur selon l'invention. Dans l'exemple décrit, le processeur comporte: un ensemble d'UCE ( 21) de 512 unités de calcul élémentaires identiques Cet ensemble forme un réseau uni-dimensionnel dans lequel chaque processeur élémentaire dispose d'une ligne de sortie et de 7 lignes d'entrée Chacune des lignes d'indice i parmi les L= 512 lignes d'entrée-sortie de l'ensemble d'UCE ( 21) est connecté à la sortie du processeur élémentaire d'indice i et à l'entrée des 7 processeurs élémentaires d'indice i-3 à i+ 3. une mémoire de masse ( 22) disposant de 512 lignes d'entrée-sortie de données et qui permet l'écriture de mots de 512 bits. une structure de transposition ( 23) composée de deux mémoires de transposition 32 * 512 identiques et indépendantes ayant chacune un adressage permettant la lecture ou l'écriture sous un format "donnée" ( 32 bits) et la lecture et l'écriture sous le format "mot"( 512 bits) Chacune des mémoires de transposition permet à tout moment d'effectuer soit une transposition données-mots, soit une transposition mots-données. un ensemble de ports ( 24) composé dans l'exemple décrit de deux ports bi-directionnels de 32 bits. Le processeur selon l'invention communique avec son environnement extérieur par des données de 32 bits ( Q = Q' = 32) Par contre, la communication entre l'ensemble d'unités de calcul ( 21) et la mémoire de masse ( 22) ainsi que la communication entre la mémoire de masse et la structure de transposition s'effectue avec des données de 512 bits (K=L=O=P=P'= 512). La description qui suit concerne plus particulièrement différentes formes de réalisation de la structure de transposition. La transposition de "mots" de 32 bits en "données" de 512 bits est assurée par une ou plusieurs mémoires dites de transposition ou "mémoires orthogonales" De tels éléments permettent d'effecteur soit les transformations directes (écriture de "données", lecture de "mots"), soit les transformations réciproques (écriture de "mots", lecture de "données"), soit les deux transformations. il 2692382 Les Ecritures ou Lectures d'informations dans un format peuvent se faire soit par décalage, soit par adressage On peut distinguer trois types d'éléments de transposition: un premier type à double décalage orthogonal o le décalage dans une direction correspond à l'accès sous un format alors que le décalage dans une direction orthogonale correspond à l'accès sous l'autre format; un deuxième type à double adressage croisé, un adressage correspondant à l'accès sous un format et l'autre adressage correspondant à l'adressage sous l'autre format; un troisième type hybride permettant l'accès à un format par décalage et l'accès à l'autre format par adressage. Les figures 3 à 11 représente des mémoires de transposition ayant des accès donnée et mot par adressage. Dans le cas o la structure de transposition ( 23) est composée d'une mémoire de transposition à lecture écriture "mots" et lecture écriture "données" une tel mémoire permet d'effectuer aussi bien les transformations directes que réciproques, comme illustrée par les figures 3 à 5. La figure 3 représente de façon schématique l'architecture de la structure de transposition, constituée par une mémoire à Lecture et à Ecriture "données"et à Lecture Ecriture "mots" La figure 4 représente le réseau de mémoires et les liaisons avec les différents BUS. Chaque cellule ( 28 à 31) dont la figure 5 représente le schéma de principe communique avec: des lignes de commande d'Ecriture "mots" ( 32), des lignes de commande de Lecture "mots" ( 33) des lignes de "données" en Ecriture ( 34) des lignes de "données" en Lecture ( 35) des lignes de "mots" en Ecriture ( 36) 12 2692382 des lignes de "mots" en Lecture ( 37) des lignes de commande d'Ecriture "données" ( 38) des lignes de commande de Lecture "données" ( 40). Chaque cellule élémentaire ( 28 à 31) comporte: une porte OR ( 41) dont les entrées reçoivent les signaux de commande d'Ecriture "données" et de commande d'Ecriture "mots" par les lignes ( 32) et ( 38), une porte OR dont les entrées sont reliées aux lignes de "mots" en écriture ( 36) et de "données" en Ecriture ( 34) une mémoire ( 45) une porte ( 43) commandée par le signal provenant des lignes de commande de Lecture "mots" ( 33) et dont la sortie est reliée aux lignes de "mots" en lecture ( 37) une porte ( 44) commandée par le signal provenant des lignes de commande de lecture "données" ( 40) et dont la sortie est reliée aux lignes de "données" en Lecture ( 35). Dans le cas o l'élément de mémoire de la structure de transposition ( 23) n'assure pas les deux transformations, on peut distinguer une première architecture de mémoire qui assure les transformations directe de données en mots (figures 6 à 8) et une seconde architecture de mémoire qui assure la transformation réciproque de mots en données (figure 9 à 11). La figure 6 représente l'architecture générale de la mémoire à Ecriture "données" et à Lecture "mots" La figure 7 représente le réseau de mémoires et les liaisons avec les différents BUS. Chaque cellule ( 50 à 53) dont la figure 8 représente le schéma de principe communique avec: 13 2692382 des lignes de commande de Lecture "mots" ( 57) des lignes de "données" en Ecriture ( 55) des lignes de "mots" en Lecture ( 56) des lignes de commande d'Ecriture "données" ( 54) Chaque cellule élémentaire ( 50 à 53) comporte: une mémoire ( 58) recevant les signaux les lignes de commande d'Ecriture "données" ( 54) et des lignes de "données" en Ecriture ( 55), une porte ( 59) commandée par le signal provenant des lignes de commande de Lecture ( 57) et dont la sortie est reliée aux lignes de "mots" en Lecture ( 56). La figure 9 représente l'architecture générale de la seconde mémoire, à Lecture "données" et à Ecriture "mots" La figure 10 représente le réseau de mémoires et les liaisons avec les différents BUS. Chaque cellule ( 60 à 63) dont la figure 11 représente le schéma de principe communique avec: des lignes de commande d'Ecriture "mots" ( 67), des lignes de "données" en Lecture ( 66) des lignes de "mots" en Ecriture ( 64) des lignes de commande de Lecture "données" ( 65) Chaque cellule élémentaire ( 60 à 63) comporte: une mémoire ( 68) recevant les signaux des lignes de commandes d'Ecriture ( 67) et des lignes de"mots" en Ecriture ( 64), une porte ( 69) commandée par le signal provenant des lignes de commande de Lecture ( 65) et dont la sortie est reliée aux lignes de données en Lecture ( 66). La figure 12 représente l'architecture d'une Unité de Calcul élémentaire Chaque Unité de Calcul élémentaire est constituée par deux mémoires vives RAM I ( 70) et RAM II ( 71), du type mémoire double accès pour permettre la lecture et l'écriture simultanée à des adresses différentes, composées chacune de r mots de un bit, et par deux structures de calcul, la première structure de calcul ( 72) étant une unité arithmétique et logique bit série et la seconde structure de calcul ( 73) étant une unité arithmétique mot parallèle. L'Unité de Calcul élémentaire comporte en outre un ensemble ( 74)de multiplexeurs et de registres reliant les sorties et les entrées des éléments. Dans l'exemple décrit, on dispose d'une ligne de sortie et de 7 lignes d'entrée de données. La présente invention est décrite dans ce qui précède en référence à un exemple de réalisation non limitatif. 2692382 R E V E N D I C A T I O N S 1 Processeur parallèle comportant une pluralité d'unités de calcul élémentaires identiques, des mémoires pour le stockage des données et au moins un contrôleur générant l'ensemble des commandes nécessaire au fonctionnement de la partie affectée au calcul et à la gestion des données, caractérisé en ce qu'il comporte: un ensemble de ( 21) de a séries de K unités de Calcul Elémentaires UC Ei, j, i désignant un entier compris entre 1 et a et j désignant un entier compris entre 1 et K, ledit ensemble comportant L lignes d'entrée-sortie, chacune des unités de calcul élémentaires UC Ei,j disposant de M lignes Lce pour l'entrée de données et de N lignes LCS pour la sortie de données, chacune de ces lignes Lce, Lcs étant connectée à l'une des lignes d'entrée-sortie Lces de l'ensemble ( 21); une mémoire de masse ( 22)de grande capacité disposant de O lignes d'entrée-sortie Lmes pour l'écriture et la lecture de mots de O bits, l'ensemble ( 21) échangeant des données avec ladite mémoire de masse ( 22); une structure de transposition effectuant la transformation dite "directe" d'un ensemble de Q données de P bits en un ensemble de P mots de Q bits, un mot étant constitué par l'association des Q bits de poids équivalent des Q données, ladite structure de transposition assurant par ailleurs la transformation dite "réciproque" de P' mots de Q' bits en Q' données de P' bits Une telle structure communique avec les ports d'entrée-sortie grâce à l'entrée de "données" ayant respectivement P et P' bits, et avec la mémoire de masse par des "mots" ayant respectivement Q et Q' bits Les lignes permettant ces échanges peuvent être monodirectionnelles ou bidirectionnelles, et distinctes 16 2692382 ou communes pour les transferts de "données" et de "mots"; un ensemble de ports ( 24) permettant l'échange de données entre l'ensemble ( 21), la mémoire ( 22) et la structure de transposition ( 23), l'ensemble ( 21) échangeant des données avec la mémoire ( 22), la mémoire ( 22) échangeant des données avec la structure de transposition ( 23) et avec l'ensemble de ports ( 24) et la structure de transposition ( 23) échangeant des données avec l'ensemble de ports ( 24). 2 Processeur parallèle selon la revendication 1 caractérisé en ce que chacune des K unités de calcul élémentaires UC Ej d'une série i d'unités de calcul élémentaires UC Ei,j accède aux éléments de mémoire Mj-r à Mj+r et écrit dans les éléments de mémoire Mj-s à Mj+s sans échanger de données avec une unité de calcul élémentaire UC Eji ou jÉj'. 3 Processeur parallèle selon la revendication 1 caractérisé en ce que chacune des K unités de calcul élémentaires UC Ei,j accède aux éléments de mémoire Mi-t, j-r à Mi+t,j+r et écrit dans les éléments de mémoire Mi-u,j-s à Mi+uj+s sans échanger de données avec une unités de calcul élémentaires UC Ejt,j I o iÉi' et jÉj'. 4 Processeur parallèle selon l'une quelconque des revendications précédentes caractérisé en ce que structure de transposition ( 23) est constituée par au moins une mémoire à Lecture et à Ecriture "données" et à Lecture Ecriture "mots". 5 Processeur parallèle selon l'une quelconque des revendications 1 à 3 caractérisé en ce que structure de transposition ( 23) est composée de deux types de mémoires, l'un des types correspondant à des mémoires en Ecriture "données" et Lecture "mots", l'autre correspondant à des mémoires en Ecriture "mots" et Lecture "données". 6 Processeur parallèle selon l'une quelconque des revendications précédentes caractérisé en ce que chaque Unité de Calcul élémentaire est constituée par deux mémoires vives ( 70, 71), du type mémoire double accès pour permettre la lecture et l'écriture simultanée à des adresses différentes, composées chacune de r mots de un bit, et par deux structures de calcul, la première structure de calcul ( 72) étant une unité arithmétique et logique bit série et la seconde structure de calcul ( 73) étant une unité arithmétique mot parallèle et en ce qu'elle comporte en outre un ensemble ( 74) de multiplexeurs et de registres reliant les sorties et les entrées des éléments.