Arithmétique redondante

Arithmétique redondante

Nous présentons ici l’arithmétique redondante et l’arithmétique mixte. Cette pré- sentation est brève, car ne faisant pas parti de cette thèse. Elle a pour but d’expliquer les principes fondamentaux de ces arithmétiques de manière à mieux comprendre l’in- térêt de leur utilisation. Le lecteur intéressé par plus de détails pourra se reporter à la thèse de Yannick Dumonteix [Dum01]. Nous montrons ensuite les performances des différents opérateurs arithmétiques, avant de nous intéresser à différentes architectures qui ont été mises en œuvre en utilisant l’arithmétique redondante.

La représentation Carry-Save

Un chemin de données arithmétiques ne se réduit pas à des opérateurs arith- métiques, il contient également des opérateurs non arithmétiques, comme les multi- plexeurs ou les opérateurs booléens par exemple. Ces opérateurs doivent conserver les signaux à leur interface en arithmétique classique, c’est pourquoi l’utilisation de l’arithmétique redondante seule dans un circuit s’avère illusoire. De plus l’interface du chemin de données ne doit pas non plus être modifiée.L’idée qui a été émise est donc d’utiliser conjointement l’arithmétique redondante et l’arithmétique classique. Ainsi, les opérateurs arithmétiques peuvent avoir des en- trées/sorties aussi bien en représentation redondante qu’en représentation classique. Cela permet de traiter les signaux pour lesquels la représentation classique est néces- saire.

d’avoir les convertisseurs nécessaires au passage d’une notation à une autre : en pratique, cela s’avère assez simple étant donné que passer de la notation Carry- Save à une notation classique se fait en additionnant les deux termes du nombre Carry-Save avec un additionneur classique, et passer d’une notation Borrow- Save à une notation classique se fait de même avec un opérateur de soustraction.Additionneur à propagation de retenue séquentielle L’algorithme employé est l’algorithme intuitif et purement séquentiel d’une addition à la main, comme montré dans la Figure 2.1. On parlera de Carry Ripple Adder. La complexité de la surface et du délai de cet additionneur sont en O(N ) (N étant la dynamique des nombres à addition- ner).

Additionneur de Sklansky Cet additionneur, aussi appelé CLA pour Carry Looka-head Adder, fait partie des additionneurs à retenue anticipée. Le principe est d’anticiper la propagation de la retenue de façon à s’affranchir de l’attente du calcul de l’addition du bit précédent. L’architecture correspondante est montrée dans la Figure 2.2. C’est une structure ayant une complexité de O(N log2(N )) en surface et O(log2(N )) en délai. La chaine critique a donc pu être améliorée par rapport au Ripple, mais au détrimentSoustraction Il n’y a pas d’architecture spécifique pour la soustraction en arith- métique classique. Effectuer une soustraction se fait en additionnant à un nombre le complément à deux du nombre à soustraire : A B = A + not(B) + 1. En pratique, un additionneur est utilisé, avec une série d’inverseurs pour obtenir le complément à un du nombre à soustraire et la retenue entrante de l’additionneur positionnée à 1.

Plus précisément, sa surface est de l’ordre de grandeur de deux fois celle du Ripple, l’additionneur « le plus petit » en arithmétique classique, et il est en temps constant, quelle que soit la dynamique de ses entrées (temps correspondant à la traversée de deux étages d’additionneurs complets  noté FA pour full-adder).Addition Borrow-Save L’utilisation de la notation Borrow-Save permet de réaliser les soustractions avec des architectures redondantes. Un addi- tionneur redondant effectue soit l’addition de deux nombres Borrow-Save : BS0 + BS1 = BS+ pour obtenir une sortie BorrowSave, l’architecture est une nouvelle fois iden- tique à celle pour le Carry-Save, à ceci près qu’il faut modifier la cellule de base qu’est le FA en une cellule dite plus-plus-minus (notée PPM, cf. Figure 2.5.b) [JDK91] (cf. exemple de l’addition de deux nombres Borrow-Save dans la Figure 2.5.a).

Multiplication

Les architectures d’additionneurs redondants et mixtes allient une petite taille (comparable à celle du plus petit additionneur classique) et un temps de propaga- tion constant. On en déduit l’atout majeur de l’arithmétique redondante : l’addition de deux nombres se fait en temps constant, quelle que soit la taille des opérandes à sommer. L’addition étant un opérateur fondamental, le gain potentiel est important.Dans ce qui suit, nous présentons les différentes étapes nécessaires pour effec- tuer une multiplication. Ces étapes nous servent à montrer l’impact de l’utilisation de l’arithmétique redondante sur la multiplication. Nous ne présentons pas en dé- tail l’architecture des différentes étapes, les lecteurs intéressés peuvent se référer à [DM00, Dum01, AFT02].