<Desc/Clms Page number 1>
BREVET D'INVENTION
INTERNATIONAL STANDARD ELECTRIC CORPORATION 320 Park Avenue NEW YORK 22, N. Y.
Etats-Unis d'Amérique CALCULATEUR ASSOCIATIF PERMETTANT UNE
MULTIPLICATION RAPIDE
La présente invention revendique la priorité d'une demande de brevet déposée aux Etats-Unis d'Amérique le 2 août 1982 au nom de John Michael COTTON sous le NO 104 242.
<Desc/Clms Page number 2>
La présente invention se rapporte en général au traitement associatif de données et plus spécifiquement à une structure de manipulation associative permettant une multiplication rapide de nombres de longueurs variables sous commande d'un masque. La structure de traitement associatif de la présente invention est particulièrement avantageuse lorsqu'elle est utilisée dans une configuration LSI (circuit intégré à grande échelle) ou VLSI (circuit intégré à très grande échelle) car un nombre réduit de circuits et de connexions de borne est obtenu par les nouveaux circuits proposés.
Des calculateurs associatifs ayant la possibilité ci-dessus mentionnée d'effectuer des multiplications rapides avec des nombres de longueurs variables sous commande d'un masque sont utiles non seulement dans des ordinateurs à manipulation associative, mais sont aussi généralement utiles dans des systèmes nécessitant une possibilité de calcul rapide.
De tels systèmes comprennent par exemple des postes de travail d'ingénieur, des systèmes de gestion de base de données, l'analyse topologique, la visualisation de graphiques, la reconnaissance de la parole, l'amélioration des images, les applications radar telles que less ànesdants-me àdé alage de phase, les ouvertures synthétiques, l'analyse et la poursuite des échos-et des ondes, les systèmes de traitement de textuelles télécommunications, y compris les applications de filtrage numérique.
<Desc/Clms Page number 3>
Les calculateurs associatifs peuvent être considérés comme des assemblages de calculateurs à chemin unique où chaque cellule séparée peut accéder seulement aux cellules voisines. On peut opérer les calculateurs associatifs par des séries de données en parallèle, leurs mémoires étant adressables par le contenu et la structure des données étant basée sur des étiquettes.
Tandis qu'un'calculateur conventionnel opère séquentiellement dans le temps sur un élément de données, un calculateur associatif opère simultanément sur de nombreuses données objets. Afin que ceci soit utile, les données objets doivent être du même type pour toute instruction individuelle de telle sorte que l'on applique la même série d'instructions séquentiëDes pour opérer simultanément sur ces données objets. Ce type de calculateur est connu sous le sigle SIMD (calculateurà instruction unique pour données multiples).
Le calculateur associatif peut être constitué par une
EMI3.1
matrice à élément binaire unique réalisés LSI, chacun capable par exemple d'avoir de 2K à 64 K éléments binaires de mémoire. Ces calculateurs cellulaires obéissent simultanément à la même instruction, chacun opérant sur ses propres données. Les cellules peuvent communiquer avec leurs voisines dans les quatre sens et aussi avec des registres extérieurs d'entrée et de sortie de données.
Les cellules dans une rangée de la matrice du calculateur associatif peuvent être configurées dynamiquement (d'une instruction à l'autre) en un nombre arbitraire de champs de longueurs prédéterminées arbitraires (dans les limites de la largeur de la matrice). Chaque champ, peut alors opérer indépendemment comme s'il appartenait à un ordinateur séparé ayant la longueur de mots donnée, capable d'accomplir des opération arithmétiques et logiques. Tous ces champs peuvent alors obéir simultanément
<Desc/Clms Page number 4>
- 4- à la même instruction, ou ils peuvent être sélectivement inhibés sous commande du programme.
L'effet net est celui d'un jeu d'ordinateurs ayant une longueur de mot définie arbitrairement qui, lorsqu'ils sont autorisés, obéissent à la même opération arithmétique ou logique appliquée simultanément des éléments de données différents. Cet ensemble d'ordinateurs peut résoudre des problèmes nécessitant des calculs matriciels, arithmétiques, algébriques, vectoriels, des traitements de l'image (pixel), des problèmes de recherche et de reconnaissance de forme et de parole. Ils peuvent effectuer des calculs arithmétiques avec toute la précision désirée tant avec une virgule fixe qu'avec une virgule flottante. Le débit de cet ensemble de calculateurs dépend de la taille de la matrice, de la longueur et du nombre des champs et de la proportion de la matrice qui est autorisée pour une opération particulière.
Par exemple, on peut estimer qu'une matrice de 128 x 128 cellules opérant simultanément sur 2048 nombres de 8 éléments binaires en utilisant une horloge de 10 MHz accomplira environ 4 milliardsd'additions ou d'opérations logiques par seconde et environ l milliard de multiplications par seconde.
Les mémoires associatives, parfois intitulées mémoires adressables par leur contenu, sont généralement bien connues et organisées pour fonctionner dans un calculateur associatif où des opérations arithmétiques peuvent être accomplies sur un ou plusieurs mots numériques simultanément emmagasinés dans la mémoire. De tels calculateurs associatifs sont décrits dans le brevet américain No 4 068 305. Comme illustré dans le brevet américain No 4 296 475, de telles mémoires adressables par le contenu sont organisées par mots et des efforts ont été entrepris pour réduire le nombre de bornes de connexion requises pour utiliser la mémoire.
Une association entre
<Desc/Clms Page number 5>
EMI5.1
- certains éléments binaires d'un mot d'instruction et des drapeaux précédemment attribués (par exemple à partir de bascules de statut) est connue et telle qu'un processeur de données exécute des instructions conditionnelles en fournissant des éléments binaires de masquage dans le mot d'instruction pour remplacer un ou plusieurs éléments binaires d'association. Ce qui précède est décrit dans le brevet américain No 4 010 452. Le brevet américain No 4 044 338 décrit une mémoire associative ayant des zones associables séparément. Un couplage sélectif d'éléments de circuit à un bus de données où chaque élément de circuit a une adresse associative est décrit dans le brevet américain No 4 188 670.
Le brevet américain No 4 159 538 est représentatif d'une mémoire associative LSI où le nombre des connexions extérieures est réduit en partageant certaines bornes de connexion entre les données d'entrée et de sortie et l'information de masquage.
Une mémoire associative à laquelle on peut accéder sériellement est décrite dans le brevet américain No 4 153 943.
L'invention décrit un processeur associatif dans lequel une matrice associative de cellules de traitement est configurée afin d'obtenir une multiplication rapide de nombres de longueurs variables, tels que des nombres binaires fi n par comp1émmt d9Jx) sous contrôle d'un masque. Une configuration convenant pour une multiplication avec signe est décrite où les séquences de manipulation dans toutes les cellules sont compatibles 1\J a\ rautre, que les cellules soient au bord ou au milieu d'une rangée de la matrice, et indépendemment des séquences de calculs qui doivent être réalisées.
Une structure de cellule associative est décrite, comprenant une unité de logique arithmétique améliorée ayant des chemins de retenue séparés pour les additions et les soustractions qui peuvat être autorisées et actives simultanément ou alternativement.
La Fig. 1 est un diagramme schématique d'uncalculateur
<Desc/Clms Page number 6>
associatif illustrant de façon générais les contrôles extérieurs.
La Fig. 2 est un dessin simplifié d'une matrice associative comprenant 20 cellules sur 4 avec masquage verti- cal et horizontal.
EMI6.1
La Fig. élémentaire. La Ë4estundiagtantte pLieu .
La Fig. 5 est une simplifiée d'une rangée de dix cellules de multiplication.
La Fig. 6 illustre l'écoulement des données pour une multiplication série-parallèle.
La Fig. 7 est un diagramme schématique d'une configuration de cellules associatives permettant une multiplication de longueur arbitraire.
La Fig. 8 est une variante du circuit de la Fig. 7 possédant des possibilités de calcul additionnelles.
La Fig. 9 est un diagramme schématique complétant l'illustration de l'opération d'une cellule associative.
La Fig. 10 illustre une rangée de cellules associatives accomplissant une multiplication suivant la présente invention.
La Fig. 11 est un diagramme schématique et logique de l'unité de logique arithmétique d'une cellule associative illustrative de l'opération de la présente invention.
En se référant à la Fig. 1 pour une réalisation préférée, un diagramme schématique simplifié est illustré représentant une matrice 100 ensemble avec ses registres de masquage 102 & 104 resp. parla direction horizontale et verticale.
Ces enregistreurs autorisent ou inhibent sélectivement des parties de la matrice 100, définissant effectivement de la sorte quelle partie de la matrice 100 va opérer pour une instruction particulière du contrôleur de matrice 106. Ce contrôleur peut être réalisé par tout contrôleur. microprogramme avec une
<Desc/Clms Page number 7>
mémoire programmée et/ou programmable pour emmagasiner des programmes d'application et les interpréter comme séquence d'opération de matrice qui sont couplés aux masques 102 et 104 par des lignes d'instruction de masquage 108 et à la matrice 100 par des lignes d'instruction de matrice 110. D'ordinaire, il peut y avoir 40 lignes 108 et 40 lignes 110 dans une matrice.
Les instructions sur les lignes 108 accomplissent une commande de microprogramme, pour les masques 102 et 104 et couplent des adresses de matrice au registre d'adresse 112. L'adresse est celle pour la mémoire fournie par cellule de la matrice qui est décrite plus loin en relation avec 212 à la Fig. 3. Les instructions sur la ligne 110 accomplissent une commande de microprogramme, pour la matrice 100. L'effet combiné des instructions sur les lignes 108 et 110 peut être utilisé pour que la matrice et ses masques effectuent une recherche d'un dossier pour das éléments ayant une caractéristique particulière et ensuite. multiplient une partie de ces enregistrements par un certain facteur.
Une matrice associative, qui peut être considérée comme un sous-ensemble d'uncatculateur associatif, est illustrée schématiquement à la Fig. 2. A titre d'exemple, la matrice 202 comprend 20 cellules sur 4, l'une d'elles étant désignée par 204. La matrice associative comporte un registre de masquage horizontal 206 de 4 éléments binaires, un registre de marquage vertical 208 de 20 éléments binaires et un registre vertical ENTREE/SORTIE 210 de 20 éléments binaires.
En se référant à la Fig. 3, une cellule associativeélé- moeke telle que 204 est représentée dans un arrangement suivant une caractéristique descalculateurs associatifs existants.
La cellule 204 qui est identique à toutes les autres dans la matrice 202, comporte une première bascule 210 et une sériede huit autres bascules représentée collectivement par 212, ensemble avec la logique de commande associée. Le groupe de huit, bascules
<Desc/Clms Page number 8>
représente une mémoire permettant un accès aléatoire et une bascule 212 agit comme enregistreur d'élément binaire de mémoire. Le nombre 8 est uniquement un exemple et pourrait être tout autre nombre tel que 8000 ou 64000. Une unité de logique arithmétique (ALU) 214 est utilisée comme il est bien connu afin d'accomplir des opérations arithmétiques et elle peut être d'un modèle connu. De même, comme il est bien connu pour le traitement de données, lorsque ALU 214 est utilisé comme additionneur, elle a une sortie somme sur la ligne 216 et une sortie retenue sur la ligne 218.
Lorsque ALU 214 accomplit une addition, le chiffre binaire de somme sur la ligne 216 est renvoyé à la bascule 210 pari'entrée de porte 220 du commutateur de sélection 222. lorsqu'on accomplit une addition, le chiffre binaire de retenue est couplé à la ligne de"sortie lente"224 par l'entrée de porte 226 du commutateur de sélection 228.
La ligne d'entrée rapide 230 est une connexion--------------- ----------vers la porte de sélection 232 pour autoriser l'envoi d'opérandes, par exemple à des fins de recherches,
EMI8.1
vers la partie ALU 214 de la cellule. La ligne est une connexion pour transmettre le résultat au registre I/O 210 de la Fig. 2. La ligne de sortiel chiffre binaire de retend ou de décalage vers la cellule suivante.
Des données d'une cellule voisine, soit une entrée de retenu ou une donnée qui est décalée, sont couplées à l'entrée par la ligne 234. Les registres de masquage vertical et horizontal 206 et 208 sont respectivement constitués par des cellules associatives similaires à la cellule 204 et sont reliés aux connexions 205 et 207 de la Fig. 3.
Les Figs. 4 à 6 illustrent l'opération d'un multiplieur série-parallèle qui consiste en un certain nombre d'unités identiques comme montré en guise d'exemple par 300,302 et 304 à la Fig. 4. Les bascules 306,308 et 310 emmagasinent le multiplicande. Le multiplicateur est envoyé, un chiffre binaire
<Desc/Clms Page number 9>
à la fois par la ligne d'entrée rapide 312. La Fig. 4 illustre une partie (3 unités) d'un multiplieur de cinq chiffres binaires par exemple qui nécessiteraient 10 unités comme montré à la Fig. 5.
L'opération de l'unité 302 du multiplieur se passe de la manière suivante : la valeur du multiplicateur est envoyée par la ligne d'entrée rapide 312 et combinée par la porte ET 314 aveclechiffre binaire résidant du multiplicande, le résultat étant utilisé comme une des entrées de l'additionneur 316. La seconde entrée de ce dernier, sur la ligne 318, provent de la sortie lente de l'unité précédente qui donne le résultat de la multiplication avec le chiffre binaire précécent lors de l'opération dans la cellule 300 utilisant le. multiplicateur sur la ligne 312. La troisième entrée de l'additionneur 316 est fournie par le chiffre binaire de retenue emmagasiné dans la bascule 320 et résultant de l'étape précédente de la multiplication.
Les résultats de somme et de retenue de l'addition obtenus par l'étape considérée de la multiplication sont emmagasinés respectivement dans les bascules 322 et 320. L'opération des cellules 300 et 304 est identique à celle de la cellule 302.
En se référant maintenant à la Fig. 5, l'opération de multiplication série-parallèle sera décrite pour un exemple de multiplication où un multiplicande de cinq chiffrrbinaires est multiplié par un multiplicateur de cinq cnifSes binaires.
Le produit sera de dixchiffres binaires. Dix unités de multiplication sont illustrées par la Fig. 5 et sont capables d'accomplir la multiplication définie.
Quoiqu'une rangée de dix unités de multiplication l à 10 est représentée, il faut noter que seulement cinq de ces unités sont nécessaires pour accomplir une multiplication de cinq sur cinq, telles que les unités l à 5 de la rangée d'unité de la Fig. 5. Les unités 6 à 10 pourraient alternative-
<Desc/Clms Page number 10>
être remplacées par un enregistreur à décalage. Dans des opérations arithmétiques sérielles, les chiffres binaires du produit pourraient être utilisés aussi rapidement qu'ils sont générés par l'unité 5.
Chacune des unités de la Fig. 5 est capable d'emmagasiner simultanément un chiffre binaire de somme S et un chiffre binaire de retenue C. En accomplissant chaque pas de la multiplication, chaque unité propage son chiffEe binaire de somme vers la droite. Dans chaque unité, le chiffre binaire de somme entrant est combiné avec le chiffrebinaire de retenue existant et avec le résultat de l'opération logique ET du chiffre binaire de multiplicande résidant et le chiffrebinaire du multiplicateur entrant pour dériver de nouveaux chiffres binaires de somme et de retenue comme décrit en se référant à la Fig. 4.
Un nombre binaire qui est le résultat d'une addition binaire peut être décrit comme consistant en deux rangées, une première contenant les chiffres binaires de somme et une seconde ceux des retenues. Des calculs peuvent être effectués sur de telles représentations de nombres binaires et l'absorption finale des retenues peut être retardée jusqu'au moment où il est nécessaire de produire le résultat sous la forme finale consistant en une seule rangée de chiffres binaires de somme. La présente technique de multiplication tire partie de la représentation à deux rangées------------ ------d'une addition binaire jusqu'à la fin de la multiplication lorsque toutes les retenues sont finalement absorbées.
L'exemple numérique suivant d'une multiplication de cinq sur cinq est décrit en se référant à la Fig. 6.
MC = 11011 MP = 01110 Le produit sera 0101111010.
A la Fig. 6, une rangée d'unité de multiplication est
<Desc/Clms Page number 11>
illustrée, les colonnes verticales représentant, dix unités de multiplication ou, alternativement, cinq (les unités l à 5) et cinq étages d'un enregistreur à décalage (les unités 6 à 10). La figure illustre comment une addition est accomplie par chaque unité ou étage ; cependant, on doit comprendre que. la propriété additive n'est pas requise dans les unités 6 à 10 pour une multiplication de cinq sur cinq.
Les chiffres. binaires du multiplicande sont conservés dans les bascules 350,352, 354,356 et 358 des unités l à 5. Ces chiffres, binaires sont l'objet d'une combinaison logique ET avec un chiffre binaire du multiplicateur à l'aide des portes ET dans chaque cellule et représentas par 360,362, 364,366 et 368. Ainsi, les chiffres binaires du multiplicateur fonctionnent en tant que masque pour ceux du multiplicande.
EMI11.1
La erg. sept rangées explicativespoucl'eepiepeédtB etcuÉladmmimesth=nplè & -puisque comme indiqué, elLeneccmpmad qu'une seule ligne où toutes les retenues (C) sont zéro tandis que les chiffres binaires de somme (S) forment comme on le voit le produit final déjà indiqué ci-dessus. La rangée supérieure par contre, c'est-à-dire la première, montre les conditions des dix unités avant que la multiplication ne débute.
Tant la ligne supérieure que la ligne inférieure indique uniquement des zéros, ceci correspondant à l'état de tous les chiffres binaires de somme et de retenue. La première opération montrée est d'ajouter le multiplicande (MC) à toutes les unités. Puisque le chiffrebinaire de poids le moins élevé du multiplicateur (MP) est zéro, l'effet dans la première rangée est d'ajouter toute une série de zéros aux unités initialement vides. Ce résultat apparaît à la ligne supérieurede Edeuxième rangée où l'on peut voir que tous les éléments binaires de retenue et de somme sont toujours zéro.
Pour cette seconde rangée, on veut à nouveau ajouter le multiplicande au contenu de chacune des unités et comme
<Desc/Clms Page number 12>
cette fois, le chiffrebinaire du multiplicateur, c'est-à-dire le chiffre binaire de poids 2 est un"un", la ligne inférieure de la seconde rangée indique maintenant les chiffres binaires du multiplicande, c'est-à-dire 11011 dans les colonnes 1 à 5.
A l'aide des flèches reliant les différents chiffres binaires entre les colonnes et rangées adjacentes et suite aux explications déjà données, notamment en relation avec les cellules montrées à la Fig. 4, on voit maintenant que pour la ligne supérieure de chaque rangée, le chiffre binaire de retenue (C) et celui de la somme (S) sont chaque fois définisen fonction de trois autres chiffres binaires qui leur sont directement ou indirectement associés par les flèches. Le premier apparaît à la ligne inférieure dans la rangée immédiatement supérieure et dans la même colonne. Il représente le chiffre du multiplicande. Le second est le chiffre binaire de gauche dans la ligne supérieure de cette case supérieure et constitue la retenue précédemment emmagasinée.
Le troisième finalement se trouve immédiatement à gauche du précédent et représente la somme de l'étage voisin. Par exemple, en considérant la ligne supérieure de la troisième rangée pour la deuxième colonne, la retenue est donc bien 0 la somme 1 puisque dans la seconde rangée, le chiffre du multiplicande est 1 à la seconde ligne dans la deuxième colonne tandis que la première ligne indique un 0 tant en ce qui concerne la retenue de la deuxième colonne que la somme de la première.
On peut ainsi suivre complètement le tableau de la Fig. 6 où les deuxièmes lignes des troisièmes et quatrièmes rangées représentent encore 11011 dans les colonnes 1 à 5, c'est-à-dire le multiplicande, puisque les chiffres de poids 4 et 8 du multiplicateur sont encore 1. Par contre, la deuxième ligne de la cinquième rangée correspond à celle de la prémisse, c'est-à-dire uniquement des zéros puisque c'est là la valeur du chiffre du multiplicateur ayant le poids le plus élevé (16).
<Desc/Clms Page number 13>
Le temps de traitement nécessité pour l'addition de tous les "zéros"de la cinquième rangée n'est pas perdu puisque cela sert à propager les chiffres binaires de retenue vers la droite, ceci étant évidemment nécessaire pour obtenir le produit final de la multiplication. Au cas où les chiffres binaires du produit sont utilisés aussi vite qu'ils sont générés par l'unité No 5, l'addition des"zéros"dans la cinquième rangée serait nécessaire puisque l'on ne connaîtrait pas la valeur du chiffre binaire du produit avant que l'addition des zéros ne soit accomplie.
La sixième rangée correspond à l'addition finale des chiffres binaires de retenue ce qui produit finalement la ligne unique de la septième rangée donnant le produit final 0101111010 de la multiplication du nombre binaire 11011 par allO, le chiffre de retenue dans les dix colonnes étant chaque fois O.
La multiplication série-parallèle décrite ci-dessus en se référant aux Figures 5 à 7 est la base du mécanisme de multiplication incorporé dans l'arrangement de cellules associatives pour le calculateur associatif de la présente invention. Dans un multiplieur série-parallèle n'effectuant que des multiplications, les configurations des interconnexions pour décaler la valeur du multiplicateur dans les circuits du multiplieur-et pour prendre le résultat et l'utiliser à un autre endroit sont prédéterminées pour des circuits multiplieurs d'une taille spécifiée.
Les caractéristiques nouvelles de l'invention concernent] a fourniture de chemins sélectionnables pour le multiplieur et les résultats d'une multiplication d'un opérand de longueur sélectionnable dont la position dans une rangée de cellules associatives est variable et peut être déterminée par un logiciel ou en accédant au contenu d'une mémoire.
En se référant maintenant à la Fig. 7, un diagramme
<Desc/Clms Page number 14>
schématique d'une multiplication de longueur arbitraire ou variable y est représenté. Une telle multiplication utilisant un arrangement de cellules associatives est particulièrement avantageuse pour des applications dans des circuits de lignes de télécommunication qui peuvent utiliser le calculateur associ- actif pour des filtres numériques récursifs dans l'égaliseur.
De même, le calculateur associatif peut être utilisé dans le filtre du convertisseur 2 fils/4 fils qui est un filtre numérique transversal.. Une multiplication de longueur variable utilisant uncalculateur associatif configuré comme une matrice expansible est aussi avantageux dans d'autres applications que la télécommunication et est généralement applicable au traitement des signaux et des bases de données.
Afin d'obtenir une matrice expansible, l'opération de multiplication doit avoir une longueur variable et être sous contrôle d'un masque. Ainsi, lorsqu'elle est autorisé pendant une opération de multiplication, chaque cellule associative doit accepter un chiffre. binaire du multiplicateur, un chiffre binaire du multiplicande et deux chiffres du résultat. Un chiffre du résultat peutremplacer celui dans--------- le multiplicande. lorsqu'elle est inhibée pendant une opération de multiplication, chaque cellule associative doit être connectée à ses voisines de telle sorte que si elle est à la limite d'une région active, elle fournira la connexion"bouclée en retour" nécessaire entre les entrées et les sorties des cellules actives pour permettre l'accomplissement d'une multiplication sérielle.
La Figure 7 illustre l'opération de multiplication de longueur arbitraire suivant la présents invention. Les flèches indiquent l'écoulement des données. La Figure 8 illustre les conditions initiales pour une opération de multiplication impliquant un multiplicateur A et un multiplicande B, ces deux
EMI14.1
nombres étant par exemple des nombres binaires positifs utilisant l'arithmétique'à complément de deux. Fig. 7 illustre aussi la
<Desc/Clms Page number 15>
multiplication pendant les premières n+l impulsions de décalage appliqués aux cellules. A la fin de cette période (de n+l impulsions de décalage où ce nombre représente celui deschiffres binaires dans A), le multiplicateur A aura été remplacé par les premiers n+lchiffres binaires (les moins significatifs) du résultat R.
Les n+l chiffres binaires les plus significatifs sont contenus dans les registres de délais binaires et dans les registres de retenues binaires des unitésarithmétiques.
On peut se référer à la Fig. 4 pour la configuration des registres et de l'unité ALU dans le cas où de simples bascules sont employées. Les chiffres binaires les plus significatifs seront à droite.
La configuration de la Fig. 7 qui montre une rangée de cellules associatives, chacune ayant une unité de logique arithmétique (ALU) 400,401.... 402, des registres pour contenir
EMI15.1
les chiffres du multiplicande en 403, o J-n 404 et 405 avec le registre 403 (LS) contenant le chiffre binaire le moins significatif,. registres 406,407 et 408 pour
EMI15.2
contenir les chiffres du multiplicateur s,-.,..., aaveclenegistre 406 (MS) contenant le chiffe binaire le plus significatif. Lorsque le masque est autorisé, l'opération de traitement se produit dans chaque cellule. Lorsqu'il est inhibé, à l'extrémité de droite de la section d'autorisation de masque, la sortie du registre 408 est couplée aux unités ALU 400, 401,... 402 et un chiffre binaire zéro est inséré sur la ligne 412 à partir de la cellule inhibée.
A l'autre extrémité de la section autorisée par masquage, la cellule d'inhibition de masquage connecte ALU 400 à la bascule 406 à travers la ligne 414.
La configuration de la Fig. 7 ne peut pas accomplir une multiplication signée. Cette dernière est celle où le chiffre binaire le plus significatif (MSB) représente son signe.
En effet, suivant une arithmétique à complément de deux, le
<Desc/Clms Page number 16>
négatif de tout nombre binaire est obtenu en changeant tous
EMI16.1
n ses chiffres binaires et en lui ajoutant n étant le nombre de chiffres binaires. Il en résulte que pour multiplier deux nombres binaires P et Q suivant cette notation et qui peuvent donc être soit positif soit négatif., on peut écrire PQ = (-a 2 + A) (-b 2 + B) = a b 2 - a B 2 - b A 2 + AB n n n n n n où A et B sont des nombres binaires positifs de n chiffres et où a et b, les chiffresles plus significatifs (MSB) de P # Q représentant n n le signe qui doit leur être affecté, sont soit 0 soit 1.
En se référant à nouveau à l'arrangement du multi- plieur de la Fig. 7, la signification binaire de Q réside dans la position tandis que celle de P est représentée par le moment où le coefficient est inséré de telle sorte que a. 2j est représenté par actif où T est la j ième impulsion de décalage insérant les données de la bascule 408 sur la ligne 410.
Ce qui suit est un exemple d'une représentation espace/temps d'une multiplication signée :
<Desc/Clms Page number 17>
EMI17.1
o -2 -b b 0 0 0 direction du décalage T n Tl 1 0, '+alb' supposant que 1 zéros sont 1 T'1 +ao (-bn). n 2 1 ; .
1 1 +a2b'n-2 1 T'1 n-l 1 +a ' +a ta Tn' n-2 t+a, 1 '+a. n- T 1 "n-1 ' ) l, l, l,
<Desc/Clms Page number 18>
De ce qui précède on peut déterminer que la même configuration de circuit que celle qui est applicable pour des nombres non signés est opérative pour des nombres signés à condition que l'unité de logique arithmétique pour le chiffre le plus significatif du nombre Q (qui est représenté par bn) est mise sur soustraction au lieu d'addition. Egalement, lorsque le chiffre le plus significatif de P (qui est représenté par an) est entrain d'être inséré, les unités arithmétiques qui étaient précédemment établies pour l'addition doivent l'être pour la soustraction et vice-versa pour l'unité précédemment établie pour la soustraction.
On aura pu aussi détermine que pour une opération convenable impliquant des nombres pourvus d'un signe, 2n impulsions de décalage doivent être appliquées avec des"zéros"insérés au lieu des coefficients de P. Les résultats doivent être décalés ou bien dans un second jeu de basculesbinaires (registre) ou les résultats LS (les moins significatifs) doivent être inscrits ailleurs, après Tn impulsions de décalage) avant que la moitié la plus significative du résultat soit insérée.
En se référant maintenant à la Fig. 8, une cellule associative modifiée par rapport à celle décrite en référence à la Fig. 7 est montrée qui permet d'obtenir les caractéristiques mentionnées ci-dessus. La structure de cellule est telle que les coefficients indiqués sur cette figure sont contenus dans les registres 450,452, 454 et 456, autant de cellules adjacentes que nécessaire étant utilisées pour contenir ce nombre. De même en ce qui concerne les registres 458,460, 462 et 464 dont chacun est respectivement couplé aux unités ALU 466,468, 470 et 472. On peut voir que certaines opérations numériques se produisent maintenant pendant que le masque est inhibé plutôt que pendant la période d'autorisation.
La signification en est que l'utilisation de la fonction d'inhibition de masquage indentifie la cellule qui accomplit non seulement la connexion
<Desc/Clms Page number 19>
entre la sortie de la bascule 456 vers la ligne de décalage 471 mais qui détermine aussi que l'unité ALU 472 accomplit une fonction de soustraction lorsque les unités ALU 466,468 et 472 autorisées par masquage accomplissent une addition (et inversément, l'unité ALU 472 accomplit une addition lorsque les autres unités ALU sont en train de soustraire).
Comme à la Fig. 7, la cellule de masquage inhibée à l'autre extrémité de la section autorisée accomplit la connexion de l'unité ALU 466 à la bascule 450 par la ligne 473.
Bien que le circuit de la Fig. 8 soit une amélioration par rapport à celui de la Fig. 7, on s'est aperçu qu'une modification supplémentaire est requise afin d'assurer (1) que les cellules du bord dans la zone d'inhibition de masquage sont compatibles et (2) que le chiffre de retenue d'une opération d'addition est compatible avec une opération de soustraction subséquente dans l'unité de logique arithmétique. Avant d'attaquer la solution de ces problèmes, il seront décrits en plus de détails.
La Fig. 9 illustre la nature du problème de la compatibilité des cellules de bord. Le problème n'est pas provoqué par la connexion effective de cellules au"bords"ou les cellules à masquageinhibasde chaque côté d'une section autorisée, mais plutôt par une cellule au milieu de la zone où le masquage est inhibé, illustié par la cellule D à la Fig. 9.
Cette cellule accomplit simultanément les opérations des cellules de bords inhibées par masquage décrites ci-dessus.
(les bascules 482 et 484 ccntisnnent les valeurs provenant des calculs précédents). La sortie de la bascule 482 est connectée à la ligne 483 de la même manière que la bascule 456 de la Fig. 8 est connectée à la ligne de décalage 471 de multiplicateur, et la sortie de retenue de l'unité ALU 480 est connectée à l'entrée de la bascule 484 par la cellule voisine E inhibée par masquage.
<Desc/Clms Page number 20>
En outre, l'unité ALU 480 va accomplir des additions ou des soustractions de manière analogue à celles de l'unité ALU 472 de la Fig. 8.
La conséquence de ce qui précède est que les valeurs dans les bascules 482 et 484 seront modifiées en fonction d'une séquence d'impulsions de décalage appliquée à toutes les cellules dans la rangée pendant les multiplications prenant place dans la zoneautorisée par masquage. Ceci n'est pas acceptable car les valeurs ne devraient pas être modifiées étant donné qu'elles seront nécessaires dans des opérations subséquentes.
La description détaillée de la façon dont ces chiffres seraient changés est donnée ci-dessous.
La table de vérité montrée ci-dessous illustre les états logiques pour la réalisation de la fonction de soustraction dans l'unité ALU 480 de la cellule D de la Fig. 9 où : A est un nombre contenu dans le registre 482 B est un nombre contenu dans le registre 484 quifonctionne comme multiplicande
EMI20.1
C. le chiffre entrant de retenue C,, le chiffre sortant de retenue R. le résultat entrant de l'étape précédente R le résultat sortant. o estL'Etat est celui de la cellule D en fonction des valeurs de A, B et C.
TABLE DE VERITE
EMI20.2
<tb>
<tb> Ri <SEP> A <SEP> B <SEP> Ci <SEP> Etat <SEP> RD <SEP> Co
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0
<tb> oooiiii
<tb> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 2 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 3 <SEP> 1 <SEP> 1
<tb> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 4 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 5 <SEP> 1 <SEP> 1
<tb> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 6 <SEP> 0 <SEP> 1
<tb> 0 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 7 <SEP> 1 <SEP> 1
<tb>
<Desc/Clms Page number 21>
Les états 0, 2,5 et 7 sont stables, mais l'état 6 va en 1 qui à son tour passe en 3 et ensuite en 7, tandis que l'état 4 va en O. De ce qui précède,
on constate que chaque cellule d'inhibition de masquage doit être inhibée exceptée pour la cellule C qui est à l'extrémité gauche de la zone d'inhibition masquage illustrée à la Figure 10. On notera que cette cellule contient le chiffre le plus significatif du multiplicande et on s'y référera en tant que telle dans le reste de la description et les revendications. La différence où la manière d'identifier la cellule, peut être accomplie en appliquant un élément binaire de données d'entrée à cette cellule particulière, ou en ayant un second élément binaire d'identification interne qui peut être établi par une instruction antérieure.
La Fig. 10 illustre une rangée de cellules associatives accomplissant une multiplication de trois chiffres binaires dans les cellules A, B et C. Chaque cellule est identique à celles décrite en se référant à la Fig. 9 et par conséquent on se référera à la Fig. 8 pour une description de l'opération. Les cellules D, E et F sont identiques à celles décrites en se référant à la Fig. 9, et chacune contient les bascules et les unités ALU décrites précédemment en relation avec cette dernière figure.
Le second problème mentionné ci-dessus, c'est-à-dire celui de la compatibilité de la retenue d'une opération d'addition avec une soustraction subséquente dans l'unité ALU sera maintenant considéré. Ce problème qui peut aussi être décrit comme le fait d'avoir une addition et une soustraction alternative dans ce qui est en fait un additionneur à "emmagasinage de retenue"peut être résolu par modification du circuit de l'unité ALU pour avoir des chemins d'emmagasinage de retenue séparés pour l'addition et la soustraction et qui peuvent être actifs soit simultanément soit alternativement.
<Desc/Clms Page number 22>
En se référant maintenant à la Fig. 11, un circuit ALU capable de résoudre les problèmes identifiés ci-dessus est illustré.
Un circuit additionneur/soustracteur 500 qui peut
EMI22.1
être constitué par des circuits de combinaisons connus et quint décritspar la table de vérité subséquente est alimenté par des nombres a et b qui peuvent être un multiplicateur et un multiplicande, ou toute autre opérande. Les nombres a et b sont couplés au circuit additionneur/soustracteur 500 par la porte 502 du type ET et l'entrée F. Le résultat R' de l'étage de cellule antérieur et du temps de décalage précédent est couplé par la ligne 504 à une bascule de retard 506 et delà vers le circuit additionneur/soustracteur 500 à l'entrée R'. La retenue C'du temps de décalage antérieur est obtenue de la bascule de retard 508 qui reçoit la retenue C de la sortie C du circuit 500, la retarde d'un temps de décalage, et l'applique à l'entrée C'du circuit 500.
De façon analogue, la sortie de retenue de soustraction B du circuit 500 est appliquée à la bascule de retard 510, retardée d'un temps de décalage, et appliquée à l'entrée B'du circuit 500 en tant que retenue du temps de décalage antérieur. Les données à entrée rapide de la porte 502 du type ET sont appliquées au circuit 500 par l'entrée F. Le résultat du calcul R est couplé de la sortie R du circuit 500 vers la cellule suivante et devient l'entrée R'pour cette cellule.
Les tables de vérité pour les fonctions d'addition et de soustraction de l'unité de logique arithmétique 500 de la Fig. 11 sont montrées ci-dessous, où : F est un nombre binaire entant R'est le résultat de l'étage antérieur et du temps de décalage précédent C'est la retenue d'addition du temps de décalage précédent B'est la retenue de soustraction du temps de décalage précédent
<Desc/Clms Page number 23>
R est le résultat du calcul C est la retenue d'addition courante B est la retenue de soustraction courante Pour la fonction d'addition R = F + R'+ C'-B', la table de vérité est :
EMI23.1
<tb>
<tb> F <SEP> R'C'B'R <SEP> C <SEP> B
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP>
<tb> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1
<tb> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0
<tb> 0 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0
<tb> 1 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP>
<tb> 1 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1 <SEP>
<tb> 1 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP>
<tb> 1 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0
<tb> 1 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP>
<tb> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1.
<SEP> 1 <SEP> 1 <SEP>
<tb> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0
<tb> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 0
<tb>
<Desc/Clms Page number 24>
Pour la fonction de soustraction R = F-R'+ C'-B', la table de vérité est :
EMI24.1
<tb>
<tb> F <SEP> R' <SEP> C' <SEP> B' <SEP> R <SEP> C <SEP> B
<tb> o <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP>
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP>
<tb> 0010 <SEP> 100 <SEP>
<tb> 0011 <SEP> 000 <SEP>
<tb> 0100 <SEP> 101 <SEP>
<tb> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 1
<tb> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0
<tb> 0 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1
<tb> 1 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP>
<tb> 1 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1 <SEP>
<tb> 1 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0
<tb> 1 <SEP> 0
<SEP> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0
<tb> 1 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP>
<tb> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP>
<tb> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> 0 <SEP>
<tb> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 0 <SEP> O' <SEP>
<tb>
Quoique les principes de l'invention aient été décrits ci-dessus en se référant à des exemples particuliers, il est bien entendu que cette description est faite seulement à titre d'exemple et ne constitue aucunement une limitation de la portée de l'invention.