Brevet FR2479508A1 — publié le 19811002

La présente invention concerne les dispositifs de trai- tement de données du type comprenant plusieurs éléments de traitement logiquement disposés en rangées et colonnes de manière que chaque élé- ment ait quatre plus proches voisins. Un tel dispositif est décrit par exemple dans les brevets britanniques no 1 445 714, 1 536 933, 2 020 457, 2 019 620 et 2 037 042. Dans un tel dispositif, on veut ordinairement permettre que chaque élément envoie des informations à l'un quelconque de ses quatre plus proches voisins et en reçoive. Dans les brevets cités ci-dessus, on obtient ce résultat en connectant chaque élément à ses quatre plus proches voisins via une ligne de connexion distincte. Un but de l'invention est de réduire le nombre des lignes de connexion nécessaires pour assurer le transfert d'informations entre éléments voisins. Selon l'invention, il est proposé un dispositif de traitement de données comprenant plusieurs éléments de traitement logiquement disposés en rangées et colonnes, le dispositif se dis- tinguant en ce que chaque colonne se divise en plusieurs groupes d'éléments, les éléments de chaque groupe étant connectés ensemble de manière à permettre un transfert d'informations vers le nord et vers le sud entre éléments adjacents à l'intérieur d'un même groupe, et le dispositif se distinguant en ce qu'il comporte plusieurs cir- cuits de commutation ayant chacun deux états, o (a) dans le premier état, les circuits de commutation connectent l'élément situé le plus au nord dans chaque groupe à l'élément situé le plus au sud dans le groupe adjacent dans la direction nord, de manière à permettre le transfert d'informations vers le nord et vers le sud entre groupes adjacents de la même colonne, et (b) dans le deuxième état, les éléments de commutation connectent l'élément le plus au nord dans chaque groupe à l'élément le plus au sud dans le groupe adjacent dans la direction ouest, de manière à permettre le transfert d'informations vers l'est et vers l'ouest entre groupes adjacents de colonnes différentes. On voit donc que l'invention remplace plusieurs con- nexions est-ouest entre éléments d'un couple adjacent de groupes par une seule connexion "diagonale" entre l'élément le plus au nord d'un groupe et l'élément le plus au sud du groupe se trouvant à l'ouest de celui-ci. On produit le déplacement d'informations vers l'est ou vers l'ouest en plaçant les circuits de commutation dans leur deuxième état, puis en réalisant une série dedéplacements vers le nord ou vers le sud sAivant les connexions diagonales. On voit que l'invention réduit notablement le nombre des lignes de connexion. Dans un mode particulier de l'invention décrit ci-après, le dispositif comprend plusieurs éléments de traitement de données et plusieurs éléments de traitement de codes de contrôle, chaque élément de traitement de codes de contrôle maintenant un code de contrôle (par exemple des bits de parité) relativement à une pluralité déter- minée d'éléments de traitement de données. Dans le mode de réalisation décrit, l'invention est utilisée pour réduire le nombre des connexions entre les éléments de traitement de codes de contrôle. Toutefois, les éléments de traitement de données sont connectés de la manière clas- sique, c'est-à-dire que chaque élément possède une ligne de connexion distincte avec chacun de ses quatre voisins. On notera que l'expression "logiquement disposé" vise à indiquer que la disposition des éléments en rangées et colonnes ne constitue pas nécessairement une disposition matérielle réelle. En pratique, les éléments peuvent être montés sur des plaquettes de circuit imprimé suivant n'importe quelle configuration matérielle commode, des connexions électrique appropriées formant la disposition logique voulue. De même, on notera que les expressions "nord", "est", "sud" et "ouest" servent dans cette description à simplement décrire la relation logique existant entre les éléments et ne doivent pas être pris comme impliquant une disposition matérielle particulière quelconque. La description suivante, conçue à titre d'illustration de l'invention, vise à donner une meilleure compréhension de ses caractéristiques et avantages; elle s'appuie sur les dessins annexés, parmi lesquels la figure 1 est un schéma de principe global du dispo- sitif; la figure 2 montre les connexions existant entre les éléments de traitement de données, les éléments de traitement de parité et les circuits de contrôle de parité; la figure 3 montre les connexions existant entre les éléments de traitement de données; la figure 4 montre le circuit de l'un des éléments de traitement de données qui permet de sélectionner des entrées de don- nées en provenance d'éléments voisins la figure 5 montre les connexions existant entre les éléments de traitement de parité; les figures 6 et 7 montrent deux états possibles d'un circuit de commutation; la figure 8 montre le circuit de l'un des éléments de traitement de parité qui permet de sélectionner des entrées de bit de parité en provenance d'éléments voisins; et les figures 9 et 10 illustrent deux manières possibles de connecter des éléments de traitement de parité constitués de pla- quettes de circuit intégré à grande échelle. La figure 1 montre un dispositif de traitement de données comprenant 4 096 éléments de traitement de données identiques D disposés suivant 64 rangées et 64 colonnes. Chaque élément peut présenter la forme indiquée dans les brevets cités ci-dessus et en sera donc pas décrit en détail. Toutefois, en résumé, chaque élémentD contient une mémoire de données comportant un nombre important d'em- placements de bits adressables un à un, divers registres internes à un seul bit, un additionneur binaire à un seul bit, et diverses portes permettant de commander le déplacement d'une donnée entre la mémoire, le registre et l'additionneur. Les éléments D sont commandés par des signaux qui sont diffusés en parallèle à tous les éléments, de sorte que tous les éléments effectuent les mêmes opérations fondamentale- ment, mais sur des données différentes. On voit que l'ensemble d'éléments D se subdivise en soixante-quatre sousensembles carrés 10, qui contiennent chacun - 8 x 8 éléments. Chaque sousensemble est associé à un groupe 12 de huit éléments de traitement de parité P, à raison d'un par rangée. Comme cela est décrit dans le brevet cité n' 2 037 042, les éléments P de traitement de parité sont sensiblement identiques aux éléments D de traitement de données, et sont commandés par les mêmes signaux de commande, si bien que chaque élément de traitement de parité effectue fondamentalement sur les bits de parité les mêmes manipulations que les éléments de traitement de données effectuent sur les données. Par exemple, si un bit de donnée est transféré de la mémoire de chaque élément de traitement de données à l'un de ses registres internes, le bit de parité correspondant est transféré de la mémoire de chaque élément de traitement de parité au registre interne corres- pondant de cet élément. La figure 2 montre l'une des rangées d'éléments de traitement de données d'un sous-ensemble, et l'élément de traitement de parité correspondant. Des bits de donnée de sortie venant des huit éléments de traitement de données sont délivrés à un circuit 14 de contrôle de parité, o ils sont contrôlés relativement au bit de parité correspondant venant de l'élément de traitement de parité. S'il existe une erreur, le circuit de contrôle 14 produit un signal d'erreur. Le contrôle de parité est bien connu, de sorte qu'il n'est pas nécessaire de décrire en détail le circuit 14. La figure 3 montre la manière dont les éléments de traitement de données sont connectés ensemble de façon à permettre des transferts de données entre eux. Chaque élément D est connecté à ses quatre plus proches voisins au nord, à l'est, au sud et à l'ouest. On trouve une exception à cette disposition sur les fron- tières de l'ensemble, o, naturellement, les éléments ont moins que quatre voisins. Toutefois, les éléments situés sur le bord nord de l'ensemble peuvent être connectés à ceux se trouvant sur le bord sud, de sorte que chaque colonne consiste effectivement en une boucle d'éléments. De même, les rangées peuvent être connectées en boucles. La direction du transfert d'une donnée entre les élé- ments est commandée par un code d'acheminement qui est diffusé à tous les éléments en parallèle. Le code d'acheminement est-constitué de deux bits, dont la signification est la suivante Code d'acheminement Direction 00 nord 01 est sud il ouest Comme cela est indiqué sur la figure 4, chaque élément de traitement de données contient un multiplexeur 16 possédant quatre entrées 0, 1, 2 et 3 qui sont connectées de façon à recevoir des données en provenance des quatre éléments voisins respectivement au sud, à l'ouest, au nord et à l'est. Le multiplexeur 16 est commandé par le code d'acheminement, de sorte qu'il choisit l'une des quatre entrées en fonction de la valeur binaire de ce code. Par exemple, si le code d'acheminement est 00, c'est l'entrée 0 qui est sélectionnée, si bien que chaque élément accepte une donnée en provenance de son voisin sud. Il s'ensuit que la donnée circule en direction du nord. La figure 5 montre la manière dont les éléments de traitement de parité P sont interconnectés. A l'intérieur de chaque groupe 12, ils sont interconnectés par des connexions nord-sud 18. Toutefois, il n'existe pas de connexions est-ouest. De ce fait, le transfert de bits de parité entre groupes adjacents d'éléments de traitement de parité suivant la direction est-ouest est obtenu par des lignes diagonales 20 qui connectent l'élément le plus au nord dans chaque groupe avec l'élément le plus au sud dans le groupe adja- cent situé à l'ouest. Des éléments de commutations 22 sont prévus pour déterminer si les bits de parité doivent être déplacés entre groupes adjacents dans la direction nord-sud ou suivant les lignes diagonales 20. Chaque élément de commutation 22 possède'deux états et est commandé par le deuxième bit du code d'acheminement. Lorsque le code d'acheminement désigne le nord ou le sud (c'est-à-dire lorsque le deuxième bit est égal à 0), le circuit de commutation établit la connexion indiquée sur la figure 6, c'est-à-dire qu'il connecte l'élé- ment situé le plus au nord dans chaque groupe à l'élément situé le plus au sud dans le groupe adjacent situé au nord. Lorsque le code d'acheminement désigne l'est ou l'ouest (c'est-à-dire lorsque le deuxième bit est égal à 1), le circuit de commutation établit la connexion présentée sur la figure 7, c'est-a-dire qu'il connecte l'élément le plus au nord et l'élément le plus au sud aux lignes diagonales 20 respectives. Alors que les éléments de commutation 22 sont symbo- liquement représentés sur les dessins annexés sous forme de commu- tateurs mécaniques, ils sont en pratique des commutateurs électro- niques construits de manière classique A partir de composants logiques connus. Comme cela est montré sur la figure 8, chaque élément de traitement de parité P contient un multiplexeur 40 possédant quatre entrées 0, 1, 2 et 3 et est commandé par le code d'acheminement de la même manière que le multiplexeur 16 de la figure 4. Toutefois, dans ce cas, il n'existe pas de connexion avec les voisins est et ouest. En fait, l'entrée venant du voisin sud est connectée aux entrées O et 3, et l'entrée venant du voisin nord est connectée aux entrées 1 et 2. Ainsi, lorsque le code d'acheminement désigne l'ouest (11), les bits de parité se déplacent vers le nord à l'intérieur des groupes d'éléments et se déplacent suivant les lignes diagonales 20 (en raison des connexions de circuits de commutation présentées sur la figure 7) entre les groupes. On peut voir que, après que huit de ces déplacements ont été effectués, le contenu de chaque groupe d'élé- ments de traitement de parité s'est déplacé vers l'ouest jusque dans le groupe adjacent d'éléments de traitement de parité, ceci corres- pondant au déplacement vers l'ouest d'une donnée del'un des sous- ensemble 10 (figure 1) dans le sous-ensemble adjacent. De la même manière, lorsque le code d'acheminement désigne l'est (01), les bits de parité se déplacent vers le sud à l'intérieur des groupes et suivant les lignes diagonales 20 reliant les groupes, si bien que, après huit de ces déplacements, le contenu de chaque groupe d'élémentsde traitement de parité s'est déplacé vers l'est dans le groupe adjacent d'éléments de traitement de parité. En résumé, on peut voir que, à chaque fois qu'une donnée se déplace d'un multiple de huit pas entre les éléments de traitement de données D, les bits de parité correspondants se dépla- cent entre les éléments de traitement de parité de manière à les. maintenir dans la relation correcte vis-à-vis de la donnée. Les éléments de traitement de données et les éléments de traitement de parité sont de préférence conçus sous forme de plaquettes de circuit intégré à grande échelle. Commodément, quatre éléments de traitement peuvent être incorporés dans chaque plaquette de circuit intégré à grande échelle, de manière à constituer une partie 2 x 2 de l'ensemble. Toutefois, on peut voir sur la figure 5 que les éléments de traitement de parité doivent être connectés de manière linéaire, et non pas sous forme d'ensemble bidimensionnel. La résolution de ce problème est illustrée sur la figure 9. Celle-ci montre deux plaquettes de circuit intégré à grande échelle 40 et 42, contenant chacune une configuration 2 x 2 d'éléments de traitement de parité. L'élément sud-ouest de chaque plaquette pos- sède une connexion sud 44 qui est raccordée à la connexion nord 46 de l'élément nord-est de la même plaquette. De plus, la connexion sud 48 de l'élément sud-est de la plaquette supérieure 40 est raccor- dée à la connexion nord 50 de l'élément nord-ouest de la plaquette inférieure 42. Ceci a pour effet de réunir en série les huit élé- ments, par l'intermédiaire de leurs connexions nord-sudi pour ainsi former l'un des groupes 12 d'éléments de traitement de parité que représente la figure 5. Dans le brevet nO 2 020 457 cité ci-dessus, il est décrit une manière de réduire le nombre de bornes sur une plaquette de circuit intégré à grande échelle, qui consiste à combiner des couples adjacents de bornes. Le dispositif de l'invention pourrait également être mis en oeuvre au moyen de plaquettes ayant la forme décrite dans ce brevet. La figure 10 montre la manière dont deux de ces plaquettes, 52 et 54, pourraient être connectées pour produire le même effet que celui illustré sur la figure 9. Dans la configuration décrite ci-dessus, il existe différentes connexions de données aux multiplexeurs d'acheminement des éléments de traitement de données et des éléments de traitement de parité, ainsi que cela est montré sur les figures 4 et 8. Toutefois, en cas de mise en oeuvre par circuits intégrés à grande échelle, il serait probablement plus commode de rendre ces connexions identiques c'est-à-dire de les faire toutes de la manière présentée sur la figure 4) et, alors, de faire varier les adresses d'entrée délivrées aux multiplexeurs d'acheminement de manière que les éléments de trai- tement de parité ne reçoivent que les codes d'acheminement "nord" et "sud". Selon une autre variante du dispositif décrit ci-dessus, l'ensemble pourrait être divisé en sous-ensembles rectangulaires, et non pas carrés. Avec une telle configuration, il est clair que le nombre de pas nécessaires pour déplacer les bits de parité dans la direction est-ouest entre groupes adjacents, via les lignes diago- nales, serait différent du nombre de pas nécessaires pour déplacer les bits de donnée entre sousensembles adjacents. Il serait donc nécessaire d'introduire des circuits de commande supplémentaires afin d'invalider certaines des impulsions d'horloge (ou bien de créer des impulsions d'horloge supplémentaires) à destination des éléments de traitement de parité pendant les déplacements est-ouest, et, ainsi, assurer que les bits de parité> sont maintenus dans la relation correcte vis-A-vis des données. Bien entendu, l'homme de l'art sera en mesure d'ima- giner, à partir des dispositifs dont la description vient d'être donnée à titre simplement-illustratif et nullement limitatif, diverses autres variantes et modifications ne sortant pas du cadre de l'invention. 9 2479508 R E V EN D I C A T I 0 N S 1. Dispositif de traitement de données comprenant plusieurs éléments de traitement logiquement disposés en rangées et colonnes, caractérisé en ce que chaque colonne se divise en plusieurs groupes (12) d'éléments, les éléments (P) se trouvant à l'intérieur de chaque groupe (12) étant connectés ensemble de manière à permettre que l'in- formation soit transférée vers le nord et vers le sud entre éléments adjacents du même groupe, et en ce qu'il comprend plusieurs circuits de commutation (22) possé- dant chacun deux états, o (a) dans le premier état, les circuits de commutation (22) con- nectent l'élément (P) le plus au nord dans chaque groupe (12) à l'élé- ment le plus au sud dans le groupe adjacent situé dans la direction nord, de manière à permettre que l'information soit transférée vers le nord et vers le sud entre groupes adjacents de la même colonne, et (b) dans le deuxième état, les circuits de commutation (22) con- nectent l'élément (P) le plus au nord dans chaque groupe (12) à l'élé- ment le plus au sud du groupe adjacent situé dans la direction ouest, de manière à permettre que l'information soit transférée vers l'est et vers l'ouest entre groupes adjacents de colonnes différentes. 2. Dispositif selon la revendication 1, caractérisé en ce qu'un code d'acheminement possédant quatre valeurs qui représentent respectivement le nord, le sud, l'est et l'ouest est diffusé à tous les éléments de traitement (P) en parallèle. 3. Dispositif selon la revendication 2, caractérisé en ce que chaque élément de traitement (P) comporte un circuit de sélection (40) commandé par le code d'acheminement afin de sélectionner l'infor- mation venant de son voisin nord si le code d'acheminement représente le sud ou l'est, et l'information venant de son voisin sud si le code d'acheminement représente le nord ou l'ouest. 4. Dispositif selon la revendication 2 ou 3, caractérisé en ce que les circuits de commutation (22) sont commandés par le code d'acheminement de façon qu'ils se trouvent dans le premier état lors- que le code d'acheminement représente le nord ou le sud, et dans le deuxième état lorsque le code d'acheminement représente l'est ou l'ouest.