Brevet FR2571163A1 — publié le 19860404

La présente invention concerne un système de traitement de données pour traitement de vecteurs, qui comporte un ensemble de commande d'invalidation d'antémémoire pour invalider une adresse enregistrée dans un répertoire d'antémémolre. Dans un ggstèmle informatique classique comportant une antémémoire de stockage direct, une condition préalable est que les données dans l'antémémoire et les données dans une mémoire principale soient identiques les unes aux autres. En particulier, pour la commande d'une antémémoire dans un système de multiprocesseurs où chaque processeur comporte une antémémoire et partage une mémoire principale unique avec les autres, on peut se reporter à l'article intitulé "Cache Memories" de ALAN JAY SMITH dans "Computing Surveys Vol. 14, n0 3", pages 473-530, numéro de septembre 1982.Dans le système de multiprocesseurs décrit, lorsqu'un certain processeur exécute un stockage dans la mémoire principale,une adresse de cette mémoire principale devant être utilisée pour l'opération de stockage est envoyée a tous les autres processeurs partageant la même mémoire principale du système. Alors, chaque processeur procède à une interrogation pour savoir si la donnée associée à l'adresse de stockage est présente dans son antémémoire. Si elle est présente, le processeur doit invalider cette donnée dans l'antémémoire comme cela est de pratique courante, ou la mettre à jour de manière à faire l'égalisation de la donnée avec celle de la mémoire principale.Une difficulté majeure pour la diffusion des adresses de stockage réside en ce que chaque antémémoire du système doit céder un cycle pour la consultation d'invalidation a tout processeur qui exécute une opération de stockage. Un système de commande d'invalidation d'antémémoire rapide et efficace est décrit dans le brevet des Etats-Unis d'Amérique n0 4 142 234, par exemple Selon le système. décrit, une mémoire de filtrage d'empilage d'adresses d'invalidation de tampon (EAIT) est associée à chaque antémémoire d'un système de multiprocesseurs. La mémoire de filtrage sert à filtrer des demandes répétées d'invalidation du même bloc dans une antémémoire, comme décrit en colonne 2 du brevet des Etats-Unis d'Amérique n0 4 142 234. Cela permet d'améliorer le rendement d'invalidation.Dans ce type de système de multiprocesseurs, dans le cas où un certain processeur exécute une instruction de déplacement de caractère pour stocker des données dans des adresses contiguës de la mémoire principale,les demandes d'invalidation associées aux adresses contiguës s'accumulent dans l'EAIT de sorte qu'on peut attendre un effet de filtrage se conformant à la longueur de bloc de l'antémémoire.Cependant, le problème avec un tel système est que, étant donné qu'une adresse de stockage est sortie de 1'EAIT en réponse à chaque stockage, on rencontre des difficultés pour déterminer ce que. doivent être le temps de maintien d'une adresse de stockage dans 1'EAIT et la longueur d'entrée de 1'EAIT. Un autre problème est que,dans le cas où une donnée constituée d'un certain nombre d'éléments doit être stockée dans les adresses de la mémoire principale à des distances égales par une seule instruction ou un stockage en parallèle doit être exécuté par augmentation du nombre des imbrications de la mémoire principale, il est nécessaire que le système décrit ci-dessus recueille des adresses d'invalidation en parallèle et cela ne peut être mis en oeuvre sans augmentation des éléments constituant le matériel. Par conséquent, un objet de la présente invention est un système informatique pour traitement de vecteurs qui permet de résoudre le problème exposé ci-dessus. Selon un aspect de la présente invention, on prévoit un système de traitement de données pour traitement de vecteurs qui comprend : une mémoire principale; un ensemble d'exploitation de vecteurs en parallèle comportant une pluralité d'interfaces avec la mémoire principale pour-l'accès d'une pluralité de données d'élément, un ensemble d'exploitation scalaire comprenant une antémémoire; et un ensemble de commande d'invalidation d'antémémoire pour exécuter une commande pour l'invalidation d'une adresse de l'antémémoire qui est stockée dans un répertoire d'antémémoire.L'ensemble de commande d'invalidation d'antémémoire comprend le répertoire d'antémémoire pour maintenir des données d'adresse de bloc associves aux données stockées dans l'antémémôire; un circuit de génération d'adresses pour générer des adresses d'interrogation d'invalidation d'antémémoire basées sur une adresse de départ d'une instruction de stockage de vecteur, une distance entre données d'élément, et un certain nombre d'éléments de stockage de vecteur; un circuit de détection pour contrler si une adresse de bloc appliquée a celui-ci a partir du circuit de génération d'adresses et comportant des adresses de stockage de vecteur est classée dans le répertoire d'antémémoire ou dans une copie du répertoire d'antémémoire et, dans ce cas, produire un signal de coincidence; un circuit d'invalidation pour invalider une adresse classée associée du répertoire d'antémémoire en réponse au signal de coincidence sorti par le circuit de détection, un circuit de contrôle de nombre d'éléments pour vérifier un certain nombre d'éléments de vecteur contenus dans une largeur de bloc de l'antêmémoire en termes de distance entre les éléments de stockage de vecteur et la longueur de bloc de l'antémémoire et ainsi, générer un signal associé au nombre d'éléments de vecteur, et un circuit d'instruction de filtrage d'adresses d'invalidation d'antémémoire pour délivrer une instruction au circuit de génération d'adresses afin de filtrer les adresses d'invalidation d'antémémoire dans le même bloc de l1an- témémoire, et mettre à jour en réponse à la sortie du circuit de contrôle de nombre d'éléments de façon qu'une adresse d'invalidation -d!ait-émémoire précédente puisse être laissée telle qu'elle ou qu'une adresse suivante d'antémémoire d'invalidation d'antémémoire puisse remplacer cette adresse d'invalidation d'antémémoire précédente lorsque l'adresse précédente d'invalidation d'antémémoire est identique å l'adresse suivante d'invalidation d'antémémoire. La présente invention sera hien comprise lors de la description suivante faite en liaison avec les dessins ci-joints dans lesquels La figure 1 représente un mode de réalisation de la présente invention; La figure 2 est un schéma d'une construction détaillée d'un circuit de génération d'adresses 5 représenté en figure 1; La figure 3 est un schéma d'une construction détaillée d'un circuit 7 d'instruction de filtrage d'adresses d'invalidation d'antémémoire représenté en figure 1; La figure 4 est un schéma détaillé d'un circuit 7 de contrôle de numéro d'éléments représenté en figure 1; et La figure 5 est un schéma d'une construction détaillée d'un circuit de commande d'invalidation représenté en figure 1. Dans toutes les figures, les mêmes numéros de référence représentent les mêmes éléments de structure. En liaison avec la figure 1, un système de traitement de données pour traitement vectoriel selon la présente invention comprend un registre 1 de base, un registre 2 de distance,un registre 3 de nombre d'éléments, un registre 4 de longueur de bloc, un circuit 5 de génération d'adresse, un circuit 6 de contrôle de nombre d'éléments, un circuit 7 d'instruction de filtrage d'adresse d'invalidation d'antémémoire, un répertoire 100 d'antémémoire, un circuit 150 d'invalidation et des trajets de transfert 201 à 207. Le répertoire 100 d'antémémoire comprend un registre 101 d'adresse instaurée, un registre 102 d'adresse de bloc, des mémoires 110 et 111, des circuits de comparaison 121 et 122, des portes 131 à 133, et des registres 140 143. Le circuit d'invalidation 150 comprend un registre 151 d'adresse de lecture 5 bits, des mémoires 5 bits 153 et 154, un registre 5 bits 155 d'adresse d'écriture d'invalidation, et un circuit 156 de commande d'invalidation. En liaison avec la figure 2, le circuit 5 de génération d'adresse comprend des circuits de commutation 51 et 52 à deux entrées, un additionneur 54, et un registre 55 d'adresse de stockage. En liaison avec la figure 3, le circuit 7 d'instruction de filtrage d'adresse d'invalidation d'antémémoire comprend un circuit 71 de commutation à six entrées, un circuit 73 détecteur d'élément zéro, un circuit 74 de détection de filtrage, et un circuit 72 de soustraction du nombre d'éléments restants qui comporte un registre 75 de nombre d'éléments restants, un circuit 76 de commutation a deux entrées, et un soustracteur 77. En liaison avec la figure 5, le circuit de commande d'invalidation 156 de la figure 1 comprend un registre de rythme d'écriture 157, un registre 158 de spécification de niveau d'écriture et des portes ET 159, 160 et 161. Le mode de réalisation cité ci-dessus fonctionne de la manière suivante. En liaison avec la figure 1, le registre de base 1 et le registre de distance 2 fournissent respectivement une adresse de départ (B) d'un stockage de vecteur et d'une distance inter-élément de stockage de vecteur (D) au circuit 5 via les trajets 201 et 202. En liaison avec la figure 2, le circuit 5 de génération d'adresse génère des adresses de vecteur B + D, B + 2D, B + 3D, ... B + (E - l)D. (E : nombre d'éléments indiqués par le registre 3 de nombre d'éléments); les résultats successifs étant chargés dans le registre 55 d'adresse de stockage sur la base d'un cycle de machine. Le circuit 51 de commutation à deux entrées est commandé par une ligne de commande 206 de manière à choisir le trajet 201 lorsque la génération d'adresses de stockage a commencé, puis un trajet de transfert 218. Le circuit 52 de commutation à deux entrées choisit continuellement le trajet 202 jusqu'à ce qu'une instruction soit appliquée via la ligne 206. La partie d'ordre élevé de l'adresse de stockage (donnée d'adresse de bloc d'antémémoire) et la partie d'ordre inférieur de l'adresse de stockage (adresse instaurée) sont appliquées via des trajets de transfert 207 et 208 aux registres 102 et 101, respectivement, dans le répertoire 100. De nouveau en liaison avec la figure 1, l'antémémoire selon ce mode de réalisation particulier comporte une construction a deux niveaux (ou deux compartiments), une antémémoire de niveau O et une antémémoire de niveau 1 (non représentée). Dans la mémoire 110 niveau O et la mémoire 111 niveau 1 sont respectivement classées les adresses de bloc correspondant à la donnée de la partie de la mémoire principale, qui sont stockées dans les antémémoires niveau O et niveau 1, sur la mémoire principale en relation appariée avec des adresses instaurées indiquées par le registre d'adresses instaurées. Dans le circuit d'invalidation 150,le contenu de la mémoire 153 5 bits niveau 0, et celui de la mémoire 154 5 bits niveau 1, montrent si oui ou non les contenus de leurs mémoires associées 110 et 111 sont valables. Dans ce mode de réalisation particulier,supposons que l'état valable de chacune des mémoires 153 et 154 soit représenté par V = 1, et l'état non valable par V = O. A partir du circuit 5 de génération d'adresses,l'adresse instaurée est appliquée au registre 151 d'adresses de lecture 5 bits simultanément à sa fourniture au registre 101 d'adresses instaurées. La donnée d'adresse de bloc classée dans le répertoire 100 d'antémémoire est sortie de la mémoire 110 niveau O et la mémoire 111 niveau 1 qui sont désignées par une sortie 210 du registre 101 d'adresses instaurées. Les circuits de comparaison 121 et 122 comparent respectivement les données d'adresse de bloc provenant des mémoires 110 et 111 avec le contenu du registre 102 d'adresses de bloc. Les portes ET/NON ET 131 et 132 fournissent respectivement des ET des sorties des circuits de comparaison 121 et 122 et des sorties 214 et 215 des mémoires 151 et 154, qui sont désignées et lues par une sortie 216 du registre 151. Leurs sorties de porte ET sont chargées respectivement dans le registre 141 de colncidence niveau O et le registre 143 de coincidence niveau 1, alors que leurs sorties porte NON ET sont appliquées à la porte NON ET 133. Le NON ET sorti par la porte 133 est chargé dans le registre 141 de confidence d'antémémoire.En réponse à un 1 du registre 141, la donnée d'adresse instaurée associée à la coincidence est fournie par le registre 140 d'adresse de coincidence au registre 155 d'adresses d'écriture d'invalidation 5 bits via le trajet 211. Alors, le circuit d'invalidation 150 reçoit à son circuit de commande d'invalidation 156 un signal de colncidence 212 sorti par le registre 141 et un signal de coincidence 213, niveau 0, provenant du regi#stre 142 (ou 143). Tout d'abord, le registre 157 de rythme d'écriture et le registre 158 de spécification de niveau d'écriture sont chargés.Les sorties des registres 157 et 158 sont appliquées a des portes ET et NON ET 159 à 161 qui à leur tour développent un signal 162 d'instruction d'écriture de niveau O ou un signal 163 d'instruction d'écriture de niveau 1. En réponse au signal d'instruction 163, la sortie O du registre 152 d'écriture d'invalidation de bit est écrite dans une position désignée par le registre 155 d'adresse d'écriture d'invalidation 5 bits,d'où il résulte l'invalidation du niveau O ou du niveau 1. Le traitement d'une invalidation d'antémémoire associée aux adresses de stockage de vecteur se comprendra à la lecture de la description faite jusqu'ici. On décrira ensuite en détail le circuit 6 de contrôle de nombre d'éléments et le circuit 7 d'instruction de filtrage d'adresse d'invalidation d'antémémoire qui sont les caractéristiques de la présente invention. Dans le mode de réalisation représenté en figures 1 , 3 et 4, on suppose que la longueur de bloc (BS) d'antémémoire est 128 multiplets, la donnée de stockage de vecteur a une largeur de 4 multiplets, et la distance minimum entre éléments est 4 multiplets. Le registre de base 1 et le registre de distance 2 ont chacun des données d'adresse 32 bits, alors que le registre 3 du nombre d'éléments est capable d'indiquer éléments avec 9 bits. Alors que le mode de réalisation donné à titre d'illustration a traité le registre de distance 2 en termes de valeurs positives, il peut naturellement ope- rer avec des mémoires où les distances sont négatives et la direction est opposée, bien que non décrit pour simplifier. En liaison avec la figure 4, un certain nombre de distances entre-éléments (Do 31) sont fournies par le registre de distances 1 au circuit 6 de contrôle de nombre d'éléments via le trajet 202.Le circuit 6 classe les distances entre-éléments en six sortes, c'est-à-dire {distance entre-éléments = (4 multiplets), (5 à 8 multiplets), (9 à 16 multiplets),(17 à 32 multiplets), (33 à 64 multiplets), (64 multiplets et plus}}. Plus spécifiquement, dans le cas où la distance entre-éléments est 4 multiplets, la longueur de blocs (BS) est 128 multiplets, et par conséquent 128/4 (32) éléments de vecteur peuvent être stockés dans le bloc d'antémémoire 1. En d'autres termes,l'invalidation d'un bloc est de fait équivalente à l'invalidation de 32 adresses successives d'antémémoire. Ainsi, le traitement d'une pluralité d'adresses de stockage de vecteur comme une seule adresse d'invalidation est appelée ici "traitement de filtrage d'adresse".De la meme manière les adresses d'invalidation peuvent être filtrées jusqu'à 128/8 (16) dans le cas des distances entre-éléments 5 à 8, 128/16 (8) dans le cas des distances entre#éléments 9 à 16, 128/32 (4) dans le cas des distances entre-éléments 17 à 32 multiplets, et 128/64 (2) dans le cas des distances entre-éléments 33 à 64. En liaison avec la figure 4, les portes ET 601 à 609, 613 et 618 à 621 et les portes NON ET 610 à 612 et 614 à 617 constituent une partie d'un circuit de porte pour classer les distances entre#éléments en six sortes. La description se poursuivra en supposant un circuit répondant au fait que la distance entre#élé- ments a une longueur de 4 multiplets. De façon que la distance entre#éléments soit de 4 multiplets, les contenus (Do 31) du registre l-de distance doivent être D29 =1, D0-28 =0, et D30,31 = 0.Les portes 601 à 606 détectent les contenus Do-28 = 0 et D30,31 = 0, alors que la porte 613 fournit une opération ET de ces contenus et de D29 pour développer ainsi un signal de détection S5 à 4 multiplets. Inutile de dire que toutes les sorties du registre 1 de distances appliquées aux portes 601 à 606 sont des sorties# complémentaires. De la même manière, un signal S4 apparaît comme signal de détection 5 à 8 multiplets, un signal S3 comme signal de détection 9 à 16 multiplets, un signal S2 comme un signal de detection 17 à 32 multiplets, et un signal S1 comme signal de détection 33 à 64 multiplets. Le signal S1 à S5 est appliqué au circuit 7 d'instruction de filtrage d'adresse d'invalidation d'antémémoire. En parallèle, avec le signal S1 à S5, un certain nombre d'éléments (E) sont fournis par le registre 3 de nombre d'éléments au circuit 7. Le circuit de commutation 71 à six entrées sert de circuit de décalage associé à (E/l), (E/2), (E/4), (E/8), (E/16) et (E/32). Parmi eux, un circuit associé avec le signal S à S5 est choisi de manière à réduire le nombre dtinva- lidations d'antémémoire. En liaison avec la figure 3, le circuit 72 de soustraction du nombre d'éléments restants est séquen- tiellement décrémenté de 1 à la fois jusqu'à ce que le nombre filtré d'éléments devienne zéro. Le résultat des soustractions successives est chargé dans le registre 75 du nombre d'éléments restants et chaque sortie de ce dernier est contrôlé par le détecteur 73 d'élé- ment zéro. Lors de la détection du zéro, un signal 218 de fin de traitement d'invalidation est appliqué au circuit 5 de génération d'adresses (figure 1) de manière à terminer l'opération de préparation d'adresse de stockage de vecteur.Jusqu'à l'apparition du signal 218,le détecteur de filtrage 74 vérifie continuellement Si l'un quelconque des signaux S1 à S5 apparait et, si tel est le cas, produit un signal de commutation 206. Comme représenté en figure 2, la sortie du registre 4 est sélec tionnée en réponse à une entrée de l'additionneur 54 de sorte que des adresses de stockage B + BS, B + 2-BS, B + 3.BS, ..., B + {E/ (2 ) + 1).BS sont produites, où 2x ~ (BS/D) Comme décrit ci-dessus, la construction selon la présente invention permet d'améliorer l'efficacité de traitement d'un système dans lequel, en réponse à un stockage de vecteur, on contrôle si un bloc associé à une adresse de stockage de vecteur a été classée dans une antémémoire scalaire et, dans ce cas, le fichier associé est invalidé. On notera qu'une pluralité de jeux de répertoire res d'antémémoire 100, de circuits 5 de génération d'adresses et de circuits d'invalidation 150 peuvent être employés de manière à améliorer encore l'efficacité de traitement, au lieu d'un seul jeu représenté et décrit. Dans le mode de réalisation illustré, on a considéré seulement les éléments de stockage de vecteur nombre contenus dans un seul bloc et non l'adresse de départ (B) d'un stockage de vecteur et, au lieu de cela, le bloc suivant est de plus invalidé. Cependant, un système qui tient compte de l'adresse de départ rentre également dans le cadre de la présente invention. Pour résumer, on verra que la présente invention permet l'exécution d'un traitement d'invalidation d'antémémoire non sur la base d'une adresse de stockage de vecteur mais sur celle d'une adresse de bloc par contrôle d'un certain nombre d'éléments de stockage de vecteurs contenus dans une seule longueur de bloc d'une antémémoire, La présente invention n'est pas limitée aux exemples de réalisation qui viennent d'être décrits, elle est au contraire susceptible de modifications et de variantes qui apparaitront à l'homme de l'art. REVENDICATIONS 1 - Système de traitement de données pour traitement de vecteurs, caractérisé en ce qu'il comprend - une memoire principale; - un moyen d'opération par vecteurs en parallèle ayant une pluralité d'interfaces avec la mémoire principale pour accéder à une pluralité de données d'élément; - un moyen d'opération scalaire ayant une antémémoire; - un moyen de répertoire (100) d'antémémoire pour maintenir des données d'adresse de bloc associées aux données stockées dans l'antémémoire; et - un moyen de commande d'invalidation d'antémémoire pour exécuter une commande afin d'invalider une adresse du répertoire d'antémémoire;; - le moyen de commande d'invalidation d'antémémoire comprenant - un moyen de génération d'adresses (5) pour produire des adresses d'invalidation d'antémémoire sur la base d'une adresse de départ d'une instruction de stockage de vecteur, une distance entre données d'élément, et un certain nombre d'éléments de stockage de vecteurs; - un moyen de détection (73, 74) pour contrôler si une adresse de bloc comprenant des adresses d'invalidation d'antémémoire appliquées au moyen de détection à partir du moyen de génération d'adresse est classée dans le répertoire d'antémémoire ou une copie du répertoire d'antémémoire et, si tel est le cas,pour générer un signal de coincidence; ; - un moyen d'invalidation (150) pour invalider une adresse classée associée du répertoire d'antémémoire en réponse au signal de coincidence sortant du moyen de détection; - un moyen (6) de contrôle de nombre d'éléments pour contrôler un certain nombre d'éléments de vecteur contenus dans une longueur de bloc stockée dans le repertoire d'antémémoire par contrôle d'une distance entre les éléments de stockage de vecteur et la longueur de bloc et, ainsi, générer un signal correspondant au nombre d'éléments de vecteur dans la longueur de bloc; et - un moyen (7) d'instruction de filtrage d'adresse d'invalidation d'antémémoire pour délivrer une instruction au moyen de génération d'adresse et filtrer l'adresse d'invalidation d'antémémoire en réponse à la sortie du moyen de contrôle du nombre d'éléments.