Brevet FR2570851A1 — publié le 19860328

UNITE ARITHMETIQUE ET LOGIQUE A PROPAGATION DE RETENUE ACCELEREE La présente invention concerne une unité arithmétique et logique telle que celles que l'on utilise dans les microprocesseurs ou d'autres circuits de traitement de signaux binaires. Une unité arithmétique et logique est destinée à recevoir deux nombres binaires à plusieurs chiffres et à effectuer sur ces nombres des opérations simples de type arithmétique (addition des deux nombres, soustraction) ou logique (complémentation, fonction OU, etc...). Elle est constituée par une succession de cellules de traitement correspondant chacune à un rang binaire déterminé: une cellule de rang i reçoit d'une part les bits de rang i des signaux à traiter, d'autre part une retenue de la cellule de rang précédent, et enfin des signaux de commande communs à toutes les cellules, ces signaux de commande déterminant la fonction arithmétique ou logique à réaliser; la cellule de traitement de rang i fournit une retenue pour la -cellule de rang suivant et un signal de sortie correspondant au chiffre de rang i du résultat du traitement arithmétique ou logique. Plus précisément, mais sans rentrer dans tous les détails, l'organisation d'une unité arithmétique et logique peut comprendre, à chaque étage correspondant à un rang binaire donne' i, d'une part au moins une cellule d'aiguillage recevant les bits de rang i des signaux à traiter et les signaux de commande, et une cellule de calcul de résultat et de retenue recevant la ou les sorties de cette cellule d'aiguillage ainsi que la retenue issue de la cellule de rang précédent, et fournissant d'une part le signal de résultat (bit de rang i du résultat) et d'autre part une retenue pour l'étage suivant. L'unité arithmétique et logique représentée à la figure I correspond à ce type d'organisation classique. Elle comprend par exemple 8 étages, pour traiter des nombres de 8 bits. Les signaux de commande sont au nombre de huit et sont amenés par un bus globalement désigné par la référence cd. Ils sont communs à toutes les cellules de traitement. Chaque étage comprend ici deux cellules d'aiguillage désignées respectivement par la lettre P et la lettre K, affectees d'un chiffre correspondant au rang binaire de l'étage considéré : PO et KO pour le rang 0, PI et K I pour le rang I etc... Chaque étage comprend aussi une cellule de calcul de résultat et de retenue désignée par les lettres CR affectées d'un chiffre correspondant au rang de l'étage considéré: CR0 à CR7. Ces cellules de calcul de résultat et de retenue sont représentées globalement chacune dans un cadre tireté respectif. Une cellule d'aiguillage Pi de rang i reçoit comme signaux de commande d'aiguillage tout ou partie des signaux de commande du bus cd; elle reçoit comme signaux d'entrée à aiguiller un bit a. d'un premier nombre binaire A et un bit b. de même rang i d'un second nombre binaire B; elle peut recevoir aussi comme signaux d'entrée à aiguiller un bit I et un bit 0. A sa sortie cette cellule fournit soit ai, soit son complément, soit bi, soit son complément, soit I indépen damment de ai et bi, soit 0 indépendamment de ai et bi. I I i La cellule d'aiguillage Ki reçoit les mêmes signaux d'entrée à aiguiller: ai, bi, 1, 0, mais des signaux de commande qui peuvent être différents et qui sont pris également parmi les signaux du bus cd. Les sorties des cellules Pi et Ki sont appliquées comme signaux d'entrée à la cellule de calcul de résultat et de retenue CRi du même étage. Cette cellule reçoit également comme troisième signal d'entrée une retenue c. qui est issue de la cellule de calcul de résultat et de retenue de étage de rang précédent i-l. La cellule CRi fournit d'une part un signal de retenue c1+1 pour étage suivant, d'autre part un signal de sortie Si (S0 à S7) qui constitue le bit de rang i d'un nombre S constituant le résultat du traitement logique ou arithmétique effectué sur les nombres A et B. Ici, les cellules de calcul de résultat et de retenue ont été représentées sous forme de deux éléments : un élément de propagation de retenue proprement dit (CPO à CP7) qui reçoit une retenue de l'étage précédent et fournit une retenue pour l'étage suivant, et une porte OU exclusif (EXO à EX7) qui établit le signal Si de résultat du traitement arithmétique ou logique ; en pratique cette porte OU-Exclusif peut recevoir simplement la sortie de la cellule d'aiguillage Pi et la retenue de étage précédent. Cependant, la constitution interne de la cellule de calcul de résultat et de retenue peut être différente et elle n'est donnée ici qu'à titre d'exemple. Pour terminer la description de la figure 1, on peut mentionner qu'une retenue d'entrée c, est appliquée à l'étage de rang 0, cette retenue étant issue soit d'un registre extérieur non représenté, soit encore d'un circuit d'aiguillage non représenté et commandé par les signaux du bus de commande cd ou par d'autres signaux de commande. De même, l'étage de rang le plus élevé fournit une retenue de sortie pour l'ensemble (c8 sur la figure 1). La présente invention propose d'essayer d'améliorer la rapidité de fonctionnement d'une telle unité arithmétique et logique, c'est-àdire de réduire l'intervalle de temps entre le moment où les signaux A et B et la retenue d'entrée cO sont tous présents à l'entrée de l'unité et le moment où le résultat du calcul est obtenu c'est-à-dire le moment où les bits 50 à S7 et c8 sont présents sur les sorties respectives de résultat et de retenue de l'unité. Or cet intervalle de temps c#umule trois durées qui sont - le temps d'établissement des aiguillages à partir des signaux de commande sur le bus cd ; ce temps peut être de 5 nanosecondes par exemple. - le temps de propagation de la retenue entre le premier et le dernier étage à travers les éléments de propagation de retenue de chacun des étages; en effet, l'obtention d'un résultat à la sortie d'un étage dépend de la retenue reçue par cet étage, retenue qui elle même dépend de la retenue reçue par l'étage précédent; ce temps peut être de 2 nanosecondes par étage. - et le temps de calcul proprement dit à travers un étage: c'est le temps nécessaire, lorsque tous les signaux d'entrée, de retenue et de commande sont présents aux entrées d'un étage, pour qu'un résultat apparaisse à la sortie de cet étage; ce temps peut être de l'ordre de 5 nanosecondes. Dans ce cumul de temps, la présente invention s'intéresse au temps de propagation de la retenue. En effet, ce temps est proportionnel au nombre d'étages donc au nombre de bits traités: pour 8 bits, le temps est égal à 8 fois le temps élémentaire de propagation à travers un étage. Mais pour 16 bits il est de seize fois ce temps. Or on tend de plus en plus à faire des unités arithmétiques et logiques plus puissantes, pouvant traiter 16 ou 32 bits, ce qui peut ralentir beaucoup la vitesse d'obtention des résultats donc la vitesse globale de fonctionnement du processeur incorporant cette unité. Par exemple, si le temps de propagation élémentaire par étage est de 2 nanosecondes, on aboutit à un temps global de fonctionnement de 42 nanosecondes (16 bits) ou 74 nanosecondes (32 bits). La méthode habituellement utilisée pour essayer de réduire ce temps de propagation est d'éviter cette propagation en effectuant un calcul de retenue au lieu d'une propagation de retenue (procédés par anticipation de retenue). Mais ce calcul est complexe et on s'aperçoit que la durée de calcul est quand même de plusieurs dizaines de nanosecondes: des procédés à anticipation de retenue présentent un intérêt lorsque la technologie est telle que le temps de propagation élémentaire serait relativement long (5 nanosecondes par exemple) mais pas lorsqu'il est minimisé (2 nanosecondes pour des technologies MOS avec canal court). La présente invention propose une astuce d'organisation pour réduire le temps de traitement global d'une unité arithmétique et logique. Cette invention s'applique à une unité de traitement arithmétique et lo#gique du type décrit ci-dessus c'est-à-dire une unité de traitement comportant une succession de cellules de traitement correspondant chacune à un ran#g binaire déterminé, chaque cellule de traitement comprenant d'une part au moins une cellule d'aiguillage recevant comme signaux d'entrée à aiguiller un bit d'un premier signal A et un bit de rang correspondant d'un second signal B, et recevant des signaux de commande d'aiguillage communs à toutes les cellules de traitement, et d'autre part une cellule de calcul de résultat et de retenue recevant les signaux de sortie de la cellule d'aiguillage de même rang, et recevant sur une entrée de retenue un signal de retenue issu de la cellule de calcul de résultat et de retenue de rang immédiatement précédent, la cellule de calcul de résultat et de retenue comportant encore une sortie de résultat et une sortie de retenue. Selon l'invention, l'unité de traitement est divisée en deux groupes de cellules de traitement; le premier groupe comprend les cellules correspondant aux rangs binaires les moins élevés et le second groupe les cellules correspondant aux rangs binaires les plus élevés; l'unité comprend un multiplexeur ayant une entrée de commande de sélection reliée à la sortie de retenue de la cellule de rang le plus élevé du premier groupe, cette sortie n'étant pas reliée par ailleurs à une entrée de retenue d'une autre cellule; le deuxième groupe de cellules de traitement comprend deux ensembles semblables de cellules de calcul de résultat et de retenue, fonctionnant en parallèle, l'entrée de retenue d'une cellule de calcul de résultat et de retenue étant reliée à la sortie de retenue de la cellule de calcul de résultat et de retenue de rang immédiatement inférieur du même ensemble, sauf en ce qui concerne l'entrée de retenue de la cellule de rang le plus faible de chaque ensemble, qui reçoit systématiquement un bit I pour le premier ensemble et un bit 0 pour le second ensemble; les sorties de résultat des- cellules de calcul des deux ensembles du deuxième groupe sont reliées à des entrées respectives du multiplexeur, celui-ci étant agencé pour transmettre soit toutes les sorties de résultat du premier ensemble soit toutes les sorties de résultat du second ensemble selon l'état du signal reçu sur son entrée de commande de sélection. En d'autres mots, on divise l'unité en deux groupes ; le premier groupe (de rang moins élevé) fonctionne normalement; le deuxième groupe (de rang plus élevé) fonctionne avec deux chaines de propagation de retenue travaillant en parallèle, l'une recevant une retenue initiale d'entrée égale à O et l'autre une retenue initiale d'entrée égale à I; des résultats sont obtenus simultanément par ces deux chaînes et on sélectionne en sortie un seul des résultats en fonction de la retenue véritable Q ou 1 qui devrait être appliquée au deuxième groupe, c'est-à-dire en fonction de la retenue qui apparaît en sortie du premier groupe. Avec cette organisation, on divise par deux le temps de propagation dans la chaîne de propagation de retenue; par exemple on passe de 16x2 nanosecondes à 8x2 nanosecondes; le multiplexeur ne rajoute que quelques nanosecondes au temps d'obtention du résultat définitif, de sorte qu'on gagne sur le temps de fonctionnement global de l'unité arithmétique et logique. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description détaillée qui suit et qui est faite en référence aux dessins annexés dans lesquels: - la figure 1 déjà décrite représente une organisation classique d'unité arithmétique et logique, - la figure 2 représente une unité arithmétique et logique selon l'invention, - la figure 3 représente un exemple de cellule de calcul de résultat et de retenue. Par souci de clarté des figures, on a représenté l'unité arithmétique et logique avec seulement huit étages, mais on aura compris d'après ce qui précède que l'invention est d'autant plus intéressante à appliquer que le nombre de bits de signaux à traiter donc le nombre d'étages est plus élevé. Sur la figure 2, les éléments correspondants aux éléments de la figure J portent les mêmes références. Ces éléments communs sont les suivants: les cellules d'aiguillage KO à K7 et PO à P7 sont inchangées et reçoivent les mêmes signaux d'entrée qui sont les bits respectifs de rang 0 à 7 des nombres A et B à traiter, ainsi que des bits 0 et I ; ces cellules reçoivent aussi les signaux de commande du bus cd. Toutes les cellules KO à K7 sont commandées simultanément par certains signaux du bus cd et toutes les cellules PO à P7 sont commandées par d'autres signaux ou les mêmes du bus cd. Les cellules de calcul de résultat et de retenue sont identiques à celles de la figure I c'est-à-dire qu'elles ont chacune deux entrées de commande, une entrée de retenue, une sortie de retenue, et une sortie de résultat. Mais leurs connexions mutuelles sont différentes. De plus, pour une unité à n étages (ici n=8) pour traiter des nombres de n bits, il y a maintenant plus de n cellules de propagation de retenue. Il y en a de préférence n+n/2. Les étages de l'unité sont divisés en deux groupes qui comprennent de préférence n/2 étages chacun. Le premier groupe comprend les étages de rang le plus faible, traitant les bits de rang le plus faible, ici aO à a3 et b à b3. Le deuxième groupe comprend les étages de rang le plus élevé, traitant les bits de rang le plus fort, ici a4 à a7 et b4 à b7. Le premier groupe est constitué exactement comme à la figure 1: chaque cellule de calcul de résultat et de retenue CR0 à CR3 reçoit les sorties des cellules d'aiguillage de l'étage de même rang (KO à K3 et PO à P3), et possède une entrée retenue cO à C3 qui reçoit la sortie de retenue de la cellule de calcul de résultat et de retenue de rang précédent, sauf pour la première cellule qui reçoit une retenue d'entrée c, issue d'un organe extérieur, registre ou circuit d'aiguillage ou autre. Chaque cellule CR0 à CR3 possèdé par ailleurs une sortie de résultat S0 à S3 et une sortie de retenue reliée à l'entrée de retenue de la cellule de calcul de résultat et retenue de rang immédiatement supérieur, sauf la cellule de rang le plus élevé du premier groupe (CR3) qui fournit un signal de retenue CS qui n'est pas transmis à une cellule de calcul de rang supérieur. Le deuxième groupe d'étages est constitué avec deux ensembles de cellules de calcul de résultat et de retenue formant deux chaînes de propagation séparées travaillant en parallèle. Le premier ensemble comprend des cellules de calcul de résultat et de retenue CR'4 à CR'7 connectées de manière analoguqe aux cellules CR4 à CR7 de la figure 1: chaque cellule de calcul CR'4 à CR'7 correspondant aux rangs respectifs 4 à 7 possède deux entrées de commande reliées aux sorties des cellules d'aiguillage de même rang P4 à P7 et K4 à K7;; elle possède aussi une entrée de retenue C'4 à c'7 qui reçoit la sortie de retenue de la cellule de calcul de rang immédiatement inférieur du même premier ensemble, sauf en ce qui concerne la cellule de rang le plus bas du premier ensemble (du deuxième groupe d'étages), à savoir la cellule CR'4 qui reçoit sur sont entrée de retenue un bit invariable c'4=l indépendamment de l'état des sorties de retenue des autres étages (interruption de la chaîne de propagation de retenue à ce niveau).Chaque cellule de calcul du premier ensmble du deuxième groupe possède enfin une sortie de résultat S'4 à S'7 respectivement et une sortie de retenue reliée à l'entrée de la cellule de propagation de rang immédiatement supérieur, sauf en ce qui concerne la sortie de retenue de la cellule de rang la plus élevé (CR'7) qu fournit une sortie de retenue finale c'8 non reliée à un autre étage. Le deuxième ensemble de cellules de calcul de résultat et de retenue comprend des cellules CR"4 à CR"7 montées exactement comme les cellules CR'4 à CR'7 du premier ensemble: chaque cellule Cl1'4 à CR"-7 correspondant aux rangs respectifs 4 à 7 possède deux entrées de commande reliées aux sorties des cellules d'aiguillage de même rang P4 à P7 et K4 à K7; elle possède aussi une entrée de retenue c"4 à c"7 qui reçoit la sortie de retenue de la cellule de calcul de rang immédiatement inférieur du deuxième ensemble, sauf en ce qui concerne la cellule de rang le plus bas du deuxième ensemble (du deuxième groupe d'étages toujours), à savoir la cellule CR"4 qui reçoit sur son entrée de retenue un bit invariable c"4=0 (donc un bit complémentaire de celui qui est reçu par la cellule correspondante CR'4 du premier ensemble), indépen damment de l'état des sorties de retenue des autres étages (interruption de la chaîne de propagation de retenue).Chaque cellule de calcul du deuxième ensemble du deuxième groupe possède enfin une sortie de résultat S"4 à 5"7 respectivement et une sortie de retenue reliée à l'entrée de la cellule de calcul de rang immédiatement supérieur, sauf en ce qui concerne la sortie de retenue de la cellule de rang le plus élevé (CR"7) qui fournit une sortie de retenue finale c"8 non reliée à un autre étage. Enfin, l'unité arithmétique et logique représentée à la figure 2 comprend un multiplexeur MUX ayant des entrées reliées aux sorties de résultat S'4 à S'7 et S"4 à S"7 et de préférence aussi des entrées reliées aux sorties de retenue finales c'8 et c"g. Ce multiplexeur a des sorties S4 à S7 et une sortie cg, et il possède une entrée de commande de sélection recevant la sortie de retenue CS de la cellule de propagation de rang le plus élevé (CR3) du premier groupe d'étages de l'unité. Le multiplexeur est agencé pour que si le signal C5 est au niveau logique I les sorties S4 et S7 et cg fournissent les niveaux logiques présents sur les sorties S'4 à S'7 et c'g du premier ensemble de cellules de calcul ; et si le signal CS est au niveau logique 0, les sorties S4 à S7 et cg fournissent les niveaux logiques présents sur les sorties S"4 à S"7 et c"g. Par conséquent, avec cette organisation, on fait simulta nsment deux hypothèses sur la valeur de la retenue qui devrait être propagée par la sortie de la cellule CR3: l'hypothèse que cette retenue est égale à I est faite par la chaîne CR'4 à CR'7 du premier ensemble et donne lieu à des résultats S'4 à S'7 et c'8; l'hypothèse contraire est faite simultanément par la chaîne CR"4 à CR"7 du deuxième ensemble et donne lieu à des résultats s"4 à S"7 et c"g. A là fin de la propagation de la retenue dans le premier groupe d'étages (CR0 à CR3 > on sait quelle est la véritable retenue en sortie de la cellule CR3 et il ne reste plus qu'à choisir par le multiplexeur des résultats correspondant à la bonne hypothèse. L'intérêt de cette disposition est que lorsqu'on connait la véritable retenue sur la sortie CS, les résultats 5'4 à S'7 et S"4 et S"7 sont déjà connus (ou presque) et on n'a donc plus qu'à prévoir le temps de fonctionnement du multiplexeur et non un temps de propagation supplémentaire dans les étages de rang le plus élevé. On peut envisager que dans certains cas il soit plus intéressant, au point de vue du gain de temps obtenu avec cette structure, que l'unité soit partagée en deux groupes inégaux de cellules de traitement, par exemple 7 cellules pour le premier groupe et 9 cellules pour le second pour un ensemble de 16 cellules. A titre d'exemple seulement on a représenté à la figure 3 une structure possible de cellule de calcul de résultat et de retenue de rang i. Dans cet exemple, la cellule comprend un premier transistor T I servant à la propagation de la retenue: ce transistor relie l'entrée de retenue ci à la sortie de retenue ci+l ; ce transistor est commandé par la sortie de l'aiguillage Pi; un deuxième transistor T2, commandé par la sortie de l'aiguillage Ki, permet de relier la sortie de retenue ci ] à la masse; une porte OU-Exclusif EXi correspondant à celle qui est représentée aux figures I et 2 a une entrée connectée à l'entrée de retenue ci et une autre entrée connectée à la sortie de l'aiguillage Pi; enfin, un troisième transistor T3, recevant sur sa grille de commande des impulsions de mise en conduction temporaire, permet d'appliquer sur la sortie de retenue ci+ I une tension de précharge Vp pendant une phase de précharge de l'unité de traitement. REVENDICATION Unité arithmétique etlou logique comportant une succession de cellules de traitement correspondant chacune à un rang binaire déterminé, chaque cellule de traitement comprenant d'une part au moins une cellule d'aiguillage (KO à K7, PO à P7) recevant comme signaux d'entrée à aiguiller un bit d'un premier signal A et un bit de rang correspondant d'un second signal B, et recevant des signaux de commande d'aiguillage (cd) communs à toutes les cellules de traitement, et d'autre part une cellule de calcul de-résultat et de retenue (CR0 à CR7) recevant les signaux de sortie de la cellule d'aiguillage de même rang et recevant sur une entrée de retenue (c0 à C7) un signal de retenue issu de la cellule de calcul de résultat et de retenue de rang immédiatement inférieur, la cellule de calcul de résultat et de retenue comportant encore une sortie de résultat et une sortie de retenue, caractérisé en ce que: - l'unité est divisée en un premier groupe de cellules de traitement (CR0 à CR3) correspondant aux rangs binaires les moins élevés et un deuxième groupe (CR4 à CR7) correspondant aux rangs les plus élevés;; - l'unité comprend un multiplexeur (MUX) ayant une entrée de commande de sélection (ces) reliée à la sortie de retenue de la cellule de rang le plus élevé (CR3) du premier groupe, cette sortie de retenue n'étant pas reliée par ailleurs à une entrée de retenue d'une autre cellule, - le deuxième groupe comporte deux ensembles semblables de cellules de calcul de résultat et de retenue (CR'4 à CRI7 et CR"4 à CR"7) fonctionnant en parallèle, l'entrée de retenue (c'4 à c'7 et C114 à c"7) d'une cellule de calcul de résultat et de retenue étant reliée à la sortie de retenue de la cellule de calcul de résultat et de retenue de rang immédiatement inférieur du même ensemble, sauf en ce qui concerne l'entrée de retenue de la cellule de rang le plus faible de chaque ensemble (CR'4, CR"4) qui reçoit systématiquement un bit 1 pour le premier ensemble et un bit 0 pour le second ensemble, - les sorties de résultat (S'4 à S'7 et 5"4 à S"7) des cellules de calcul de résultat et de retenue des deux ensembles du deuxième groupe sont reliées à des entrées respectives du multiplexeur (MUX), celui-ci étant agencé pour transmettre soit toutes les sorties de résultat du premier ensemble (S'4 à S'7) soit toutes les sorties de résultat du second ensemble (S"4 à S"7) selon l'état du signal reçu sur son entrée de commande de sélection (CS).