Algorithmes de multiplication pour circuitsasynchrones

Nicolas VEYRAT CHARVILLONfevrier-juillet 2004

Resume

L’utilisation de circuits asynchrones permet la realisation d’operateurs adelais variables. Contrairement aux circuits synchrones ou le delai d’unoperateur est constant et egal au delai du chemin critique plus une margede securite, la synchronisation locale bas niveau des circuits asynchronespermet a un operateur de fournir un resultat a la vitesse maximale permisepar la materiel pour le jeu de donnees fourni en entree. Ces circuits peuventdonc dans certains cas etre plus performants en termes de vitesse que lescircuits synchrones. Ils possedent de plus plusieurs proprietes interessantesque nous detaillerons plus loin. Au cours de ce stage j’ai etudie les algo-rithmes de multiplication entiere pour les circuits asynchrones dans le butd’en maximiser les performances en termes de vitesse/surface.

Remerciements

Je remercie tout d’abord Arnaud qui a dirige mon stage de DEA et a eula patience de supporter toutes mes questions.

D’autre part je voudrais remercier toute l’equipe du LIP et d’Arenairepour leur accueil chaleureux, leurs conseils et leurs discussions au coin cafe.

Table des matieres

Introduction 4

1 Circuits Asynchrones 61.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Classification des circuits asynchrones . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Protocoles de communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.1 Protocoles 2 et 4 phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.2 Codage des donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

1.4 Cellule de Muller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 Proprietes des circuits asynchrones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5 Mes Choix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Algorithmes de multiplication entiere 142.1 Generation des produits partiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Recodage de Booth-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.2 Recodage de Booth-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.3 Recodage de Booth-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2 Reduction des produits partiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.1 Reseau cellulaire de Braun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.2 Methode de Wallace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.2.3 Methode de Dadda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.2.4 Methode d’Oklobdzija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 Addition finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Protocole experimental 243.1 Hypotheses de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243.2 Le simulateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.3 Modification des algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3.1 Modification de la methode d’Oklobdzija . . . . . . . . . . . . . . . . . .263.3.2 Modification du reseau de Braun . . . . . . . . . . . . . . . . . . . . . . . . . .27

4 Resultats et analyse 284.1 Les tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.2 Simulation et resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.3 Analyse des resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Conclusions et perspectives 335.1 Conclusion sur la multiplication asynchrone . . . . . . . . . . . . . . . . . . . .335.2 Travail restant a faire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

Bibliographie 34

Introduction

L’operation de multiplication est tres largement utilisee dans les ordina-teurs, non seulement lors de calculs arithmetiques explicites dans les pro-grammes, mais aussi dans le calcul des fonctions elementaires (fonctions tri-gonometriques par exemple) lors d’evaluations de polynomes a l’aide d’unschema de Horner notamment.

Enfin dans des architectures de type Itanium, on utilise un seul operateurderive d’un multiplieur, le fused multiply and add calculant a × x + b, pourtoutes les operations arithmetiques [Mar00], dont la division et la racinecarree. Ceci prouve la necessite d’un operateur de multiplication rapide.

La proliferation des applications embarquees, par exemple les telephones,consoles portables et assistants personnels souleve le probleme de l’autono-mie. De ce point de vue les circuits synchrones ont un reel handicap : achaque cycle d’horloge, tous les elements logiques du circuit evaluent leursentrees, donc consomment, meme s’ils ne sont pas sollicites. Par contre, uncircuit asynchrone non sollicite se placera en attente d’un jeu d’entree va-lide, ce qui pour des technologies type CMOS (Complementary Metal OxydeSemiconductor, les circuits les plus courants dans les ordinateurs actuels)consomme beaucoup moins d’energie (on n’a pas de transitions, donc pas decourant de court-circuit, seulement un courant de fuite qui reste tres faibleen comparaison).

La notion de circuits asynchrones est presente des les tous premierssystemes informatiques, puis a laisse peu a peu place aux circuits synchrones.Dans les circuits synchrones, c’est un signal d’horloge distribue dans l’en-semble du circuit qui cadence les operations. Le fonctionnement est ainsiplus facile a analyser et a assurer. Malheureusement, l’evolution des proces-seurs, qui suit toujours la loi de Moore, fait doubler la vitesse des proces-seurs environ tous les 18 mois, imposant une distribution de plus en plusprecise du signal d’horloge a travers des processeurs dont la taille augmentede surcroıt. Cette distribution devient reellement problematique et couteuseen termes materiels et humains lors du developpement, car il faut resoudrede nombreux de problemes de course critique du signal, de routage et deconsommation de l’horloge.

Les circuits asynchrones ont etes reintroduits entre autres par Sutherlanden 1989 [Sut89] dans un article sur les micropipelines, puis en 1990 par Mar-tin [Mar90], principalement pour accelerer le calcul et pallier aux problemesde distribution d’horloge, puisque la synchronisation est assuree non plusglobalement, mais localement entre les differents elements logiques. Les cir-cuits asynchrones possedent d’autres proprietes interessantes detaillees plusloin.

Le but de ce stage etait d’etudier comparativement plusieurs algorithmesde multiplication adaptes aux circuits asynchrones afin d’en optimiser lesperformances en termes de vitesse/surface. Les etudes precedentes se sontsouvent contentees ”d’emprunter” directement des algorithmes synchroneset etudiaient surtout differentes methodes d’implantation des circuits asyn-

chrones afin d’en maximiser les performances ([Spa92] par exemple). Il n’existepas d’etude poussee des proprietes algorithmiques de la multiplication en cal-cul asynchrone comme on peut en trouver dans le cas synchrone : [Boo51],[Dad76], [Okl95], [Okl96-2], [Vui83], [Wal64] entre autres. C’est une lacunegrave pour un champ de recherche qui beneficie ces dernieres annees d’uninteret croissant.

Au cours du stage, j’ai etudie et adapte au calcul asynchrone plusieursalgorithmes de multiplication existants afin de comparer leurs performancesdans le domaine asynchrone pour une technique d’implantation courante.Etant donne les tailles d’operandes relativement faibles utilisees dans lesoperateurs arithmetiques (de 8 a 64 le plus souvent), une etude basee surla complexite asymptotique ne serait pas adaptee. On va plutot realiser uneserie de simulations au niveau d’une quasi-implantation materielle basee surune bibliotheque de portes specifique, avec toutefois plusieurs restrictionspresentees plus loin.

Dans une premiere partie, je presenterai le fonctionnement des circuitsasynchrones, puis detaillerai le protocole utilise pour mesurer et comparerles differents algorithmes, les choix realises pour cette etude et ce qui endecoule. L’etude des algorithmes proprement dits se decoupe en trois partiescorrespondant aux trois etapes de la multiplication que sont la generation desproduits partiels, la reduction par addition de ces produits et enfin l’additionfinale. Pour finir je presenterai les resultats obtenus lors des simulations etles commenterai.

Chapitre 1

Circuits Asynchrones

1.1 Generalites [Spa02]

Afin de pouvoir calculer correctement dans un circuit integre, il estnecessaire de disposer d’un mecanisme garantissant la validite de tout jeu dedonnees transmis entre elements de calcul. En effet, lorsqu’un element estsollicite pour un calcul, il lui faut un certain delai pour produire la bonnesortie. Pendant ce temps, les valeurs lues en sortie peuvent etre erronees.

Dans un circuit synchrone, la validite des donnees est assuree par uneattente correspondant au temps maximal pris pour l’evaluation d’une entreequelconque (temps au pire cas). On doit de plus ajouter une marge desecurite englobant les variations possibles causees par l’environnement, parmilesquelles la temperature et les variations de la tension d’alimentation, quipeut representer une part importante de l’attente totale. Il est aussi impor-tant d’assurer sur l’ensemble du processeur une distribution quasi-simultaneedu signal d’horloge, ce qui entraıne de nombreux problemes de conceptionet une grande depense d’energie.

Dans un circuit asynchrone, on va plutot se doter d’un protocole decommunication entre blocs logiques qui indiquera d’un part que les donneestransmises sont valides, et d’autre part que ces donnees ont ete prises encompte par le destinataire et que celui-ci est pret a en recevoir de nouvelles.

6

Dans un circuit synchrone, la synchronisation entre registres et blocs logiquessuccessifs est assuree par un signal d’horloge distribue simultanement dans

l’ensemble du circuit via un reseau complexe de portes logiques

Dans un circuit asynchrone, la synchronisation est assuree par les registres etblocs logiques entre eux grace a un protocole local de communication des donnees

L’utilisation d’un protocole de communication local permet d’aboutir dupoint de vue global a un ensemble fin d’horloges locales gerant les communi-cations entre elements, dephasees les unes par rapport aux autres et dont laperiode, non constante, depend des delais effectifs du circuit qui dependenteux-meme des donnees d’entree.

1.2 Classification des circuits asynchrones [Mar90]

Suivant les hypotheses faites sur les delais dans un circuit asynchrone, onpeut classifier celui-ci dans trois categories :

– un circuit de la classe DI (Delay-Insensitive) fonctionne correctementpour des delais positifs, bornes mais inconnus dans les portes et dansles fils. Ces circuits sont extremement robustes vis a vis des conditionsenvironnementales.Cependant Martin [Mar90] a montre que cette classe est trop limitee :seuls les circuits composes d’inverseurs et d’elements de Muller (presentesplus loin) sont DI.

– On est donc amenes a diminuer les contraintes du modele DI : en impo-sant d2 = d3, soit l’hypothese des fourches isochrones (une transitiond’un signal arrive simultanement en tous les points situes en aval de lafourche). On obtient la classe QDI (Quasi-Delay-Insensitive) qui estle modele le plus strict permettant de realiser tous les circuits dont onaura besoin.

– Enfin la classe SI (Speed-Independent) qui impose des delais nuls dansles fils (d1 = d2 = d3 = 0), hypothese peu realiste.

1.3 Protocoles de communication

1.3.1 Protocoles 2 et 4 phases

La synchronisation des elements du circuit est assuree par un protocolede communication qui permet un echange de donnees valides a l’aide de filsde requete et d’acquittement. Il existe deux protocoles courants, le premiera 4 phases et le second a 2 phases :

– Le premier protocole se deroule en 4 phases : (1) l’emetteur transmetses donnees et met le fil de requete a 1, (2) le destinataire absorbeles donnees et met le fil d’acquittement a 1, (3) l’emetteur repond enmettant le fil de requete a 0 (les donnees ne sont plus garanties valides),

et (4) le destinataire accuse reception en mettant le fil d’acquittementa 0, initialisant le cycle de communication suivant.

– Le protocole 2 phases evite les retours a zero du protocole 4 phases,puisque les informations des fils de requete et d’acquittement sont en-codees par des transitions et non plus par des valeurs booleennes.Ce protocole devrait etre plus rapide, mais l’implementation d’unmecanisme reagissant aux transitions plutot qu’aux valeurs logiquesdes fils de requete et d’acquittement resulte souvent en un surcoutmateriel qui nuit aux performances.

L’utilisation de l’un ou l’autre des protocoles depend de la technologie visee.

1.3.2 Codage des donnees

Il est possible de coder les donnees de facon classique sur un seul filtransportant une valeur booleenne (codage Single Rail). Cette methode im-pose alors l’existence d’un fil de requete separe indiquant la validite du jeude donnees.

Cependant il est aussi possible d’encoder le signal de requete avec la va-leur booleenne sur deux fils (Double Rail). Un signal est une pair {x.f, x.t},les pairs {x.f, x.t} = {1, 0} et {x.f, x.t} = {0, 1} representent des donneesvalides (le 0 et le 1 logiques) {x.f, x.t} = {0, 0} represente une donnee inva-lide (’E’), et {x.f, x.t} = {1, 1} n’est pas utilise. De cette facon, on imposeun passage par une valeur invalide entre deux donnees valides. Un jeu dedonnees est valide lorsque tous les signaux sont valides, et est reinitialiseseulement lorsque tous les signaux sont invalides.

Codage double rail des donnees pour les protocoles 2 et 4 phases

a) un canal de communication simple railb) protocole 4 phases simple railc) protocole 2 phases simple rail

protocole 2 phases double rail

protocole 4 phases double rail

1.4 Cellule de Muller [Mul63]

La garantie de validite des donnees impose la creation d’une nouvelleporte capable de memoriser celles-ci. Une porte de Muller est initialisee a0 ou 1 lorsque toutes ses entrees sont identiques a 0 ou 1 respectivement,et conserve la derniere valeur grace a une boucle de memorisation jusqu’asa prochaine initialisation. Cette cellule est essentielle pour construire ledemi registre (half-buffer) asynchrone qui permet comme en synchrone dememoriser des valeurs.

a) implantation materielle d’une cellule de Mullerb) half-buffer

La cellule de Muller est aussi utile pour signaler la completion d’uncalcul, c’est a dire le moment ou toutes les sorties sont valides et le resultatcorrect : par exemple pour un circuit logique a n sorties, on veut etre capablede signaler que toutes les sorties sont valides afin d’autoriser la suite du calcul(typiquement en sortie d’un operateur arithmetique n bits). Pour chaque bitdi code en double rail on va realiser di.t NOR di.f , puis on va composer lessorties dans une porte de Muller a n entrees. Au debut du calcul, toutesles sorties sont invalides, donc toutes les pairs {di.f, di.t} valent {0, 0} etles NOR sortent 1 de meme que la porte de Muller dont toutes les entreesvalent 1. Lorsque le circuit effectue son calcul, les bits de sorties deviennentvalides, les NOR passent a 0. Lorsque toutes les sorties sont valides, toutesles entrees de la porte de Muller sont a 0 et celle-ci passe a 0, signalant lacompletion du calcul.

1.5 Proprietes des circuits asynchrones [Spa02]

Les circuits asynchrones, en plus d’eviter en partie les problemes liesa l’utilisation d’une horloge globale, possedent d’autres proprietes avanta-geuses :

– Haute performance. Grace a la synchronisation locale, chaque etapede calcul dans un circuit asynchrone demarre des que l’etape precedenteest terminee, sans devoir attendre un signal d’horloge et independammentdu pire cas. Ceci se traduit par une vitesse de traitement accrue, carils calculent en temps moyen et non en temps de pire cas. De plusla synchronisation d’un circuit combinatoire est geree directement parcelui-ci, et plus par des elements de memorisation comme dans uncircuit synchrone (latch et flip-flop) qui imposent des marges pour as-surer un bon fonctionnement. Cependant cet avantage peut-etre enpartie annule par la generation des signaux de completion de calcul,et il est difficile de traduire ces variations locales de temps de calcul entermes de performances globales sur le temps de calcul d’une fonction,typiquement dans un compilateur.

– Faible consommation. Contrairement aux circuits synchrones ou achaque cycle d’horloge, tous les elements logiques du circuit evaluentleurs entrees, donc consomment, dans un circuit asynchrone chaqueelement non sollicite se placera en attente d’un jeu d’entree valide,reduisant l’activite au minimum (activite conditionnelle bas niveau).

– Robustesse vis a vis des conditions environnementales. Alorsqu’en synchrone on est oblige d’introduire dans le delai des marges desecurite pour pallier aux eventuelles variations des conditions environ-nementales, en asynchrone aucune hypothese n’est faite sur le delaide l’operateur. Un circuit asynchrone est capable grace a la synchro-nisation locale de calculer au maximum de sa capacite etant donneles variations de temperature, de tension d’alimentation et meme leseventuelles imperfections materielles.

– Faibles emissions electromagnetiques. Les operations locales s’ef-fectuent generalement de facon aleatoire dans le temps, repartissantles impulsions electromagnetiques creees par l’alimentation d’un com-posant et lissant le spectre electromagnetique du circuit, alors que l’ali-mentation ponctuee par l’horloge de l’ensemble d’un circuit synchronegenere un spectre particulier. De plus la repartition aleatoire des ponc-tions d’energie des portes tend a stabiliser la tension d’alimentation.Enfin ceci permet d’augmenter la securite des applications de crypto-graphie embarquees vis a vis des attaques par analyse de consomma-tion (Differential Power Analysis, tres dangereux contre les cartes apuce).

– Meilleure composabilite et modularite. La synchronisation lo-cale permet de considerer les elements d’un circuit comme des boitesnoires faciles a deplacer et a reutiliser puisque aucune assertion n’estfaite sur le delai et les conditions environnementales de fonctionne-ment.

– Plus de probleme de generation, de distribution d’horloge etde course critique. Il n’y a plus de signal a distribuer simultanementdans tout le circuit, ce qui est l’un des plus gros problemes des pro-cesseurs synchrones. Par exemple lors de la conception du processeurAlpha 21164 de DEC, plus de la moitie des effectifs de l’equipe deconception etait affectee aux problemes lies a l’horloge.

Cependant les circuits asynchrones presentent aussi plusieurs inconvenients.Le codage double rail implique un surcout en routage et en portes logiques,donc en surface de circuit. La recherche actuelle cherche a pallier a unmanque d’outils et de strategies de conception et de test dont souffrentles circuits asynchrones, peu repandus. Le calcul en temps variable suivantles donnees d’entree complique aussi l’ecriture des compilateurs destines aucalcul asynchrone.

1.6 Mes choix

Dans cette etude, nous utiliserons le modele QDI puisqu’il est souventpossible lors de la creation de circuits arithmetiques de controler les delaisdes fils pour satisfaire la condition des fourches isochrones. J’ai choisi aussile protocole 4 phases, plus simple a mettre en place, en combinaison avec lecodage double rail qui est couramment utilise.

Le choix du codage double rail simplifie les simulations d’une part en en-codant directement le signal de requete dans les valeurs booleennes, d’autrepart car ce codage garantit l’abscence de transitions parasites du signal lorsde calculs.

Chapitre 2

Algorithmes demultiplication entiere

La multiplication entiere ou virgule fixe peut etre decomposee en troisetapes successives qui se retrouvent dans une multiplication a la main : laformation des produits partiels, la reduction du tableau des produits par-tiels et l’addition finale. La formation des produits partiels correspond ala multiplication de chaque chiffre du multiplicateur par chaque chiffre dumultiplicande. C’est cette etape qui necessite de connaıtre les tables de mul-tiplication, implantees par une porte AND en binaire. On obtient alors untableau de chiffres de differents poids (le bitarray) que l’on doit additionnerpour obtenir le resultat final.

Pour aller plus vite, on utilisera une notation redondante pour les resultatsintermediaires.Une representation redondante [Avi61] est une representation dans une baseen utilisant plus de chiffre que necessaire pour representer tous les nombres.Par exemple une notation en base 2 avec l’ensemble de chiffres {−1, 0, 1} estune representation redondante.

Cette redondance permet entre autres de realiser l’addition sans pro-pagation de retenue, donc en temps constant, de deux nombres ecrits sousforme redondante, et a fortiori d’additionner en temps constant un nombreen base normale a un resultat intermediaire ecrit sous forme redondante.Ceci permet une reduction rapide des nombres du bitarray jusqu’a un seulresultat sous forme redondante.

On travaillera ici en carry-save, c’est-a-dire en notation redondante dansla base 2 avec l’ensemble de chiffres {0, 1, 2}. Chaque chiffre v d’un telnombre sera represente dans le circuit par deux valeurs binaires vc et vs,telles que v = vc + vs. La derniere etape est une addition classique permet-tant de convertir le resultat redondant en carry-save sous forme normale.

14

Addition en temps constant d’un nombre carry-save a = ac + as et d’un nombrebinaire b

2.1 Generation des produits partiels

Classiquement, on genere le bitarray simplement en multipliant le multi-plicande par chaque chiffre du multiplicateur. En binaire, cela correspond aune grille n×n de portes AND implantant la table de multiplication binairepour chaque produit partiel.

a) generation des produits partiels binaires sans recodage pour un multiplieur 4× 4b) bitarray et produit final ‘pour un multiplieur 16 bits sans recodage

Il est possible de generer un bitarray de taille reduite en recodant le mul-tiplicateur sous forme redondante de facon a annuler certains de ses chiffresa des places fixes connues. Ainsi des etages du bitarray seront toujours nuls,et on pourra les ignorer lors de la reduction. On peut ainsi d’une part reduirele cout materiel de l’etape de reduction, au prix d’un recodeur, et d’autrepart gagner en temps, puisque le bitarray est additionne plus rapidement,toujours au prix du temps perdu dans le recodeur. Cette perte de temps seramoins importante dans la pratique que lors des simulations, car c’est lors dela formation des produits partiels que la sortance est la plus importante, ondevra donc ajouter des circuits d’amplification qui pour le recodage seront

fondus dans le circuit de recodage. On verra qu’il faudra tester des solutionsqu’habituellement on ne retient pas pour le synchrone, et qui en asynchronepourraient etre beaucoup plus avantageuses.

2.1.1 Recodage de Booth-2 [Boo51]

Ici on recode le multiplicateur en notation de type chiffre signes dansl’ensemble {−2,−1, 0, 1, 2}, en assurant qu’au moins un chiffre sur deux soitnul, c’est a dire en eliminant un etage sur deux du bitarray pour gagner surle cout materiel de la reduction.Par exemple 10110001101 est recode en 10202010101, on annule bien unchiffre sur deux.

Bitarray et produit final pour un multiplieur 16 bits avec recodage Booth2.S est le signe du nombre par lequel on multiplie le multiplicande

Table de selection des produits partielsBits du multiplieur Selection

000 +0001 +multiplicande010 +multiplicande011 +2×multiplicande100 −2×multiplicande101 −multiplicande110 −multiplicande111 −0

Ce recodage se traduira en materiel par un circuit qui d’apres certainsbits du multiplicateur (ici trois) sera capable en temps constant de choisir lemultiple -1, 0 ou 1 du multiplicande cree au prealable. On note par la suiteM le multiplicande.

Dans l’etude on suppose une notation des nombres negatifs en complementa deux. Le bitarray obtenu voit sa hauteur ramenee a d(n + 2)/2e (ou n estle nombre de bits du multiplicateur) et sa forme modifiee. C’est le recodagele plus souvent utilise.

Generateur avec recodage Booth2 pour une ligne du bitarray dans un multiplieur16 bits

2.1.2 Recodage de Booth-3

Booth-3 consiste en un recodage dans l’ensemble de chiffres {−4,−3, · · · , 3, 4},et on elimine cette fois ci deux etages sur trois, soit un bitarray de hauteurd(n + 3)/3e en analysant pour chaque etage quatre bits du multiplicateur.Le circuit de codage est un peu plus complique, mais la raison pour laquellece recodage est rarement utilise en synchrone est la presence du multipletrois, qui ne peut pas etre obtenu avec un simple decalage du multiplicande,en temps constant. La generation de ce multiple ’difficile’ se fait a l’aide d’unadditionneur supplementaire calculant 2×x+x, qui rajoute un cout materielcorrespondant a un additionneur de taille n + 2. Grace aux proprietes descircuits asynchrones, on espere pouvoir pallier la perte de temps induite parcette addition. En effet, l’addition en synchrone prend un temps au pirecas en O(n), voire en O(log n) pour les meilleur additionneurs, alors qu’enasynchrone le temps moyen va pour un additionneur de type propagationde retenue de O(log n) a un theorique mais peu realisable O(log log n). Enpratique on utilisera un additionneur a saut de retenue presente dans [Tis97]qui calcule en O(

√log n).

D’autre part, on peut aussi gagner du temps dans la partie qui, a partirdu multiplicateur recode choisit le multiple qui sera dans le bitarray. Eneffet, si on sait que le multiple 3M n’est pas celui selectionne, la table detransition du AND pour un circuit asynchrone montre qu’il suffit qu’unedes deux entrees soit a 0 pour que la sortie bascule a 0. On n’a pas besoind’attendre la generation des multiples inutiles pour donner les donnees aubitarray, des que les fils de selection M, 2M et 3M ont une valeur valide. Si lemultiple est 3M, on est capable en asynchrone d’utiliser chacun des chiffresdu resultat aussitot qu’il est disponible independamment des autres, meme

s’ils ne sont pas encore calcules.

bitarray et produit final pour un multiplieur 16 bits avec recodage Booth3

Table de selection des produits partiels pour Booth3Bits du multiplieur Selection Bits du multiplieur Selection

0000 +0 1000 −4×multiplicande0001 +multiplicande 1001 −3×multiplicande0010 +multiplicande 1010 −3×multiplicande0011 +2×multiplicande 1011 −2×multiplicande0100 +2×multiplicande 1100 −2×multiplicande0101 +3×multiplicande 1101 −multiplicande0110 +3×multiplicande 1110 −multiplicande0111 +2×multiplicande 1111 −0

recodeur Booth3

2.1.3 Recodage de Booth-4

On poursuit la demarche, cette fois ci dans l’ensemble de chiffres {−8,−7, · · · , 7, 8}.Les multiples difficiles sont ici 3, 5 et 7 (6 se derive de 3 par un decalage entemps constant). 7 se calcule par une seule addition 8.x + (−x), car −x est

genere en temps constant. Le bitarray sera de hauteur d(n + 4)/4e, mais auprix d’un codeur de Booth encore plus complique, qui calcule toujours entemps constant, et de trois additionneurs de tailles n+2, n+3 et n+3 pourles multiples 3, 5 et 7 respectivement.

Je n’ai pas etudie les recodages suivants car pour Booth-5 les multiplesdifficiles sont 3, 5, 7, 9, 11, 13 et 15 parmi lesquels 11 et 13 necessitent 2additions successives.

Table de selection des produits partiels pour Booth4Bits du multiplieur Selection Bits du multiplieur Selection

00000 +0 10000 −8×multiplicande00001 +multiplicande 10001 −7×multiplicande00010 +multiplicande 10010 −7×multiplicande00011 +2×multiplicande 10011 −6×multiplicande00100 +2×multiplicande 10100 −6×multiplicande00101 +3×multiplicande 10101 −5×multiplicande00110 +3×multiplicande 10110 −5×multiplicande00111 +4×multiplicande 10111 −4×multiplicande01000 +4×multiplicande 11000 −4×multiplicande01001 +5×multiplicande 11001 −3×multiplicande01010 +5×multiplicande 11010 −3×multiplicande01011 +6×multiplicande 11011 −2×multiplicande01100 +6×multiplicande 11100 −2×multiplicande01101 +7×multiplicande 11101 −multiplicande01110 +7×multiplicande 11110 −multiplicande01111 +8×multiplicande 11111 −0

2.2 Reduction des produits partiels

Le bitarray genere precedemment doit a present etre reduit a un seulnombre, en carry-save la plupart du temps, car l’addition en carry-save sefait en temps constant en evitant la propagation de retenue de l’additionclassique. Le travail sur cette etape consiste a trouver l’organisation descellules full adder qui permettra la reduction la plus rapide du bitarray. Denombreuses tactiques existent qui sont developpees depuis les annees 60.

2.2.1 Reseau cellulaire de Braun [Bra63]

C’est le reseau le plus simple, qui correspond a la methode ’a la main’ :a chaque etage, on ajoute a l’accumulateur un nouveau produit partiel.Il en resulte un reseau extremement regulier a la fois du point de vuedu placement des cellules et du routage. Cependant, les produits partielssont generes simultanement alors qu’ils sont additionnes successivement, cequi veut dire que les derniers produits additionnes ’attendent’ pour etreajoutes au resultat intermediaire. Cette tactique est tres adaptee pour uneimplementation iterative, mais reste trop lente pour une multiplication hauteperformance.

un reseau de Braun pour une multiplication 5 bits

2.2.2 Methode de Wallace [Wal64]

De maniere generale, on va privilegier des reductions sous forme arbo-rescente plus rapides qui equilibrent les delais en additionnant ensemble lesresultats intermediaires du bitarray de facon plus judicieuse que Braun : onva additionner ensemble les bits sortant du generateur de produits partiels,disponibles au temps t, puis les resultats de ces additions, au temps t + 1et ainsi de suite. Chaque etage ainsi constitue reduit trois nombres en deux(soit un nombre carry save), donc reduit la hauteur h du bitarray a d3h/2e.La hauteur de l’arbre de reduction est proportionnelle au logarithme de lataille des operandes, avec un temps constant pour la traversee de chaqueetage. Le calcul en parallele permet d’avoir une reduction du bitarray entemps O(log n) contre O(n) pour un reseau de type Braun.

Une premiere methode, proposee par Wallace, utilise des structures ap-pelees arbres de Wallace, qui sont en fait des compteurs : un arbre de Wallace3 est un full adder, qui prend 3 bits de poids 0 et rend deux bits de poids0 et 1 correspondant a la somme des bits d’entree. Il est possible de creerun arbre de Wallace de n’importe quel ordre en composant des full adderset des half adders. Ces arbres calculent la somme de leurs bits d’entree entemps logarithmique.

a) Arbre de Wallace 3 (Full-adder)b) Arbre de Wallace 5

c) Arbre de Wallace 5 compose d’arbres de Wallace 3

Historiquement, un multiplieur de Wallace est un multiplieur compose desous multiplieurs 4×4 produisant un bitarray qui sera reduit par des arbresde Wallace. Pour que cette solution soit avantageuse, il faut bien entenduque les petits multiplieurs soient implantes directement en materiel.

Multiplieur de Wallace 16 bits

Semantiquement l’arbre de Wallace reduit les produits partiels du bitar-ray ’au plus tot’.

2.2.3 Methode de Dadda [Dad76]

A l’oppose, la methode de Dadda profite du fait que l’on connait le tauxde compression maximum d’un etage (soit d3h/2e) pour minimiser le nombrede composants utilises : Sachant que d’une hauteur de bitarray de 9 on va

reduire jusqu’a une hauteur de 6, on va faire ’le minimum’ pour obtenirune hauteur de 6. En appliquant cette tactique ’au plus tard’, on assure deminimiser le cout materiel.

a) reductions successives du bitarray par la methode de Dadda pour un multiplieur5 bits

b) Circuit de l’additionneur obtenu [Mul89]

2.2.4 Methode d’Oklobdzija

Oklobdzija a presente dans [Okl95] et [Okl96-2] une methode algorith-mique pour obtenir l’arbre de reduction de delai minimum : a chaque produitpartiel du bitarray on associe sa date theorique de generation, et on cherchea additionner ces bits en privilegiant ceux qui sont generes le plus tot. Ilen decoule deux nouveaux produits, apres un temps egal au delai d’une cel-lule full adder, que l’on ajoute dans le bitarray. En realisant ainsi l’arbrede reduction jusqu’a n’avoir plus que deux bits au maximum de chaquepoids, soit un resultat en carry-save, on assure avoir minimise le temps dereduction.

2.3 Addition finale

Le resultat de l’etape de reduction est un nombre en carry-save, soit deuxnombres binaires qu’il reste a additionner pour obtenir le resultat final. Pouroptimiser cette etape, on veut adapter l’addition finale au profil temporeld’arrivee des bits de differents poids afin de realiser l’addition le plus vitepossible. En synchrone, c’est un probleme difficile qu’on resout souvent encomposant plusieurs types d’additionneurs [Okl96-1], typiquement un addi-tionneur lent du type propagation de retenue, puis un additionneur rapide,generalement a anticipation de retenue et enfin un additionneur a selectionde retenue qui peut anticiper la retenue sortante de l’etape precedente.

En asynchrone par contre, il est possible d’anticiper les retenues lorsquedeux des trois bits additionnes sont identiques : si ils valent 0, la retenuevaudra toujours 0, et reciproquement pour 1. C’est cette propriete qui per-met de passer d’un temps en O(n) en calcul synchrone pour l’additionneur a

propagation de retenue a O(log n) de temps de calcul moyen en asynchrone.En brisant cette chaıne de dependance aux retenues precedentes, on arrivea un profil d’arrivee en sortie de l’additionneur ou tous les bits arrivent enmeme temps, alors qu’en synchrone les bits de poids fort arrivent apres lesbits de poids faible. Il n’est pas utile de composer plusieurs additionneursde types differents, un seul suffit.

On presente dans l’etude deux additionneurs asynchrones : l’additionneura propagation de retenue (Ripple-carry-adder, RCA) modifie pour le calculasynchrone, capable calculer les retenues au plus tot, et l’additionneur a sautde retenue presente par Tisserand dans [Tis97] (Carry-skip-adder, CSkA),capable de calculer en O(

√log n). Ces deux additionneurs sont suffisants,

car les additionneurs asynchrones plus rapides, capables de calculer jusqu’aune vitesse de O(log log n) [Che00], sont compliques a implanter et ne sontpas rentables pour des tailles d’operandes courantes a cause des grandesconstantes devant le terme log log n.

Structure d’un additionneur Carry-Skip

Chapitre 3

Protocole experimental

Dans un premier temps, je vais comparer les differents algorithmes sui-vant la vitesse et la taille de l’operateur obtenu. Pour des tailles d’operandesrealistes, de 8 a 64 voire 128 bits, la complexite asymptotique n’est pasinteressante et j’ai plutot choisi de realiser des simulations proches du materiel.

Dans un deuxieme temps, j’ai propose un nouvel algorithme derive dureseau de Braun, et des modifie les algorithmes existants pour les adapterau calcul asynchrone.

La contrainte de taille est elle aussi importante, puisque non seulement degrands circuits coutent plus cher en raison de la surface de silicium occupee,mais aussi parce qu’un circuit plus grand a plus de chance d’etre defectueuxlors de sa fabrication.

Une derniere grandeur a prendre en compte est la consommation d’energie,puisque celle-ci influe sur l’autonomie des appareils portables qui devientde plus en plus critique avec l’evolution des technologies. Pour des circuitsdouble rail non iteratifs tels que ceux consideres ici, chaque cellule realiseexactement une transition sur chacune de ses sorties quelles que soient lesvaleurs d’entree. La consommation depend donc directement du nombre decellules de l’operateur et de leur nature. On va chercher a la minimiser enprivilegiant les circuits requierant peu de portes.

3.1 Hypotheses de travail

La vitesse d’un operateur asynchrone est difficile a caracteriser, car letemps de calcul depend directement des donnees en entree. On va suppo-ser pour cette etude que les operandes sont aleatoires avec pour chaquechiffre binaire equiprobabilite d’obtenir un 0 ou un 1. Cette hypothese n’estpas toujours raisonnable dans un calcul sur ordinateur, particulierement sile multiplieur est destine au traitement du signal. Il suffira lors des testscomparatifs de generer des vecteurs adaptes a l’application. La vitesse estcaracterisee par le temps moyen de calcul, sa variance, son ecart-type etsa distribution. On calcule aussi l’intervalle de confiance pour chaque testrealise afin de verifier sa validite.

On va effectuer des simulations logiques, en supposant que les transitionsde signaux sont instantanees. L’utilisation du codage double rail garantit

24

l’abscence de transitions parasites (glitches). On va aussi ne pas prendreen compte le placement et le routage entre les portes, qui necessitent desoutils complexes. Dans les circuits arithmetiques etudies, les cellules sontsuffisamment proches et les fils assez courts pour que le delai qu’ils induisentsoit negligeable, et leurs effets comparables sur les different algorithmes.

Un dernier probleme serait la sortance, c’est-a-dire l’influence du nombrede cellules alimentees en sortie par une porte logique sur le delai de celle-ci,mais nous ne disposons pas d’outils adaptes a l’etude de ce parametre

3.2 Le simulateur

Il existe deux grands types de simulateurs pour les circuits : les simula-teurs electriques de type SPICE resolvent le systeme d’equations electriquesdu circuit. On obtient ainsi des resultats tres fins a la fois pour le delai desportes et la consommation d’energie. Cependant la resolution du systemecomplet est tres compliquee et ne permet pas le test de grands circuits.D’autre part le calcul en temps moyen impose une etude statistique du cir-cuit, au moins 10000 entrees pour un resultat precis, ce qui est irrealisableavec un simulateur electrique. Les simulateurs logiques existants quant a euxeffectuent une simulation logique plus rapide, mais ils utilisent des descrip-tions au format VHDL (Very high speed integrated circuit Hardware Des-cription Language), ce qui est trop rigide pour permettre des generationsautomatiques d’operateurs de taille et de composition variables. D’autrepart ils ne possedent pas, pour le moment, de bibliotheque de portes prevuepour la simulation des circuits asynchrones double rail. Enfin ils ne sonttoujours pas assez rapides pour une etude statistique.

Pour realiser des mesures statistiques des temps de calcul des differentsoperateurs, on a besoin d’un simulateur tres rapide qui permette aussi degenerer des operateurs de n’importe quelle taille avec differents recodages,arbres de reductions, et de modifier differents parametres.

Puisqu’on veut effectuer des simulations realistes d’un point de vuemateriel, on utilise une bibliotheque de portes developpee pour le codagedouble rail par Arnaud Tisserand.

J’ai donc ecrit un simulateur dedie en C++, de type evenementiel, c’esta dire qu’on y traite sequentiellement une liste triee chronologiquement detransitions du circuit, qui vont faire basculer des portes dans de nouveauxetats, entraınant de nouvelles transitions sur leurs sorties qui seront ajouteesa la liste d’evenements. Lorsque la liste est epuisee, le circuit est stable etl’evaluation terminee.

La totalite du code du simulateur represente 500 lignes, et les fonctionspour la generation des elements des differents multiplieurs plus de 2000lignes. Une bibliotheque de cellules simple comme celle utilisee representequant a elle 1600 lignes. Je n’ai pas repris le simulateur ecrit par NicolasBoullis [Bou01] destine au diviseurs asynchrones, qui etait trop rigide pourpermettre une generation rapide de multiplieurs de differentes compositionset des modifications rapides des parametres de la bibliotheque de portes.La programmation objet permet ici d’apprehender de facon plus intuitive la

structure des circuits decrits en C++.Le resultat d’une simulation est un fichier contenant les donnees statis-

tiques de l’operateur, vitesse et distribution des temps de calcul, sa surface,un fichier avec la courbe de repartition des temps de calcul pour l’operateuret un fichier avec la courbe des temps de calcul moyens pour chaque bit duresultat, qui permet de voir quels bits pourront par exemple etre exploitesle plus tot ou lesquels sont critiques pour la vitesse de l’operateur entier.

3.3 Modification des algorithmes

Pour tirer les meilleures performances d’un algorithme en asynchrone, onne cherche plus comme en calcul synchrone a minimiser le pire cas possible,qui represente une course critique, mais le cas moyen, c’est a dire les casles plus nombreux, parfois au detriment de cas lents plus rares qui serontrallonges. Par exemple pour l’additionneur a propagation sequentielle deretenue, la mise en place d’un mecanisme permettant de fournir les retenuesle plus tot possible complique la cellule, sans pour autant ameliorer les casdifficiles de l’additionneur synchrone (ceux ou les bits d’entree d’un memerang sont 0 et 1, donc qui demandent d’attendre la retenue precedente).Cependant ce mecanisme permet de briser la chaıne critique de propagationdes retenues dans les autres cas, c’est a dire quand il existe des couplesde bits identiques au meme rang, donc une possibilite de prevoir la retenuesuivante (generation de retenue a 0 ou 1). La longueur moyenne d’une chaınede propagation de retenue pour des operandes de taille n aleatoires avecequiprobabilite d’obtenir 1 ou 0 est proportionnelle a log2(n) : c’est la vitessemoyenne de l’additionneur a propagation de retenue asynchrone.

Le meme principe s’applique pour la multiplication. Pour cela les cellulesfull adder de la bibliotheque de portes ont ete declarees de facon a pouvoirfournir la retenue sortante aussi tot que possible, et j’ai fait de meme avectoutes les autres cellules : un AND est capable de sortir un 0 en sortie desqu’une de ses entrees vaut 0, sans attendre de connaıtre la valeur de l’autre,un OR fournit un 1 en sortie des qu’une de ses entrees vaut 1. En procedantainsi pour toutes les cellules de la bibliotheque on est capable de gagner untemps important par rapport a une simple transposition depuis le domainesynchrone.

Les valeurs obtenues lors de ces tests sont analysees au chapitre suivant.

3.3.1 Modification de la methode d’Oklobdzija

J’ai adapte directement les strategies de Braun, Wallace et Dadda danscette bibliotheque de portes, car celles-ci reposent sur des algorithmes fixeset non flexibles.Par contre la methode d’Oklobdzija etudie en calcul synchrone les tempsde propagation a travers l’arbre de reduction afin de les minimiser, tempsqui pour le calcul asynchrone ne sont plus constants : un full adder dontdeux entrees sont valides et identiques peut fournir une retenue sortantesans attendre la troisieme entree : son delai est donc variable.

A cause de cette dependance temporelle aux donnees au niveau memedes portes, le temps pris en compte dans le modele ne sera jamais exact, etl’arbre de reduction non optimal.

J’ai teste plusieurs manieres d’estimer de facon realiste ce temps, parexemple une simple moyenne arithmetique des temps extremes possibles,jusqu’a des calculs statistiques sur les probabilites d’obtenir 0 ou 1 a chaqueendroit de l’arbre. Cette derniere methode plus proche de la realite conduita une amelioration des performances, mais entraıne un surcout de calculimportant. Cependant, quelle que soit la methode choisie, il s’agit d’unemethode statistique dont on ne pent garantir qu’elle est optimale, car lesprobabilites d’obtenir 0 ou 1 dependent a la fois des vecteurs d’entree et dumode de generation des produits partiels (avec ou sans recodage).

Pour les tests, j’ai utilise la methode statistique analysant les probabilitesd’apparition des 0 et des 1 dans l’arbre de reduction.

3.3.2 Modification du reseau de Braun

Les performances mediocres du reseau de Braun, en synchrone et enasynchrone, viennent du fait que les multiples sont ajoutes sequentiellementau resultat intermediaire. J’ai modifie le routage du reseau sequentiel afind’obtenir un arbre de reduction fonctionnant en temps logarithmique, touten gardant la meme configuration materielle, donc un placement regulier. Ilsuffit d’additionner sur les premieres lignes tous les produits partiels, puis lesresultats suivants par strates successives jusqu’a obtenir un dernier nombreen carry-save. On appelera par la suite un tel arbre de reduction un reseaude Braun modifie

Cette methode pourtant simple arrive pour d’autres bibliotheques deportes materielles que celle utilisee dans les simulations a surpasser la methoded’Oklobdzija.

un reseau de Braun modifie pour une multiplication 5 bits

Chapitre 4

Resultats et analyse

4.1 Les tests

J’ai realise des tests sur plusieurs algorithmes : sans recodage, les reductionsde Braun, par arbres de Wallace, Braun modifie, Dadda et Oklobdzija. J’aiaussi teste ces trois dernieres reductions pour les recodages de Booth 2, 3 et4.

Tous les tests sont realises avec, dans les recodeurs et pour l’additionfinale, un additionneur a propagation de retenue sequentielle asynchrone carl’utilisation d’un additionneur a saut de retenue ne donne pas ici des resultatsrealistes pour plusieurs raisons : premierement les multiplexeurs des blocsde l’additionneur carry-skip ont du etre implantes a l’aide d’un AO22 (deuxAnd dont les sorties sont branchees sur les entrees d’un OR), alors qu’uncomposant specialise plus rapide permettrait de meilleures performances, lemultiplexeur etant un element cle de l’additionneur carry-skip. D’autre partles blocs de l’additionneur, qui additionnent 3 bits et permettent le sautde retenue, sont le plus souvent implantes au niveau du transistor dans labibliotheque de portes. Un additionneur carry-skip realise a l’aide de porteslogiques ne reflete donc pas la realite.

4.2 Simulation et resultats

Tous les algorithmes ont etes testes pour des tailles d’operandes de 8, 16,32 et 64 bits, sur 50000 jeux de donnees pour les operandes de taille jusqu’a32, 5000 pour les algorithmes multipliant 64 bits. On arrive a un facteur derisque inferieur au demi pourcent pour les tailles jusqu’a 32, inferieur a 2pourcents pour la taille 64.

Les tests se sont deroules en parallele sur plusieurs ordinateurs du labo-ratoire pendant un mois, et representent plusieurs mois de calcul sur un seulordinateur.

Les delais et surfaces sont exprimes en unites arbitraires bases sur lesvaleurs donnees dans la bibliotheque de portes asynchrones double rail d’Ar-naud Tisserand. Comme on l’a deja vu, en calcul asynchrone double rail, lasurface du circuit donne une indication la consommation. Une meilleure es-timation demanderait l’utilisation de methodes plus precises, typiquement

28

un solveur electrique de type SPICE, incompatible avec l’etude statistiquerealisee ici.

Si on considere un multiplieur, pour un meme recodage et un memeadditionneur final, alors les arbres de reductions de Dadda, Oklobdzija etBraun modifie, ainsi que le reseau de Braun couvrent la meme surface decircuit, au routage pres. La reduction par arbres de Wallace couvre une plusgrande surface car elle n’est pas optimale du point de vue du nombre decomposants.

Delai moyen/Taille des operandes sans recodage

Taille des Surface pour la Surface pour lesoperandes reduction par arbres autres strategies

de Wallace de reduction8 1431 140816 6275 614432 26247 2560064 106061 10448

Surface du multiplieur en fonction de la taille des operandes sans recodage

Delai moyen/Taille des operandes avec recodage Booth2

Le graphe obtenu est tres semblable pour les recodages Booth 3 et Booth4.En particulier l’ordre des arbres en termes de performances reste le meme :Oklobdzija le plus rapide, puis Braun modifie puis Dadda.

Surface en fonction du recodage pour une taille d’operandes de 32 bits

Delai en fonction du recodage pour une taille d’operandes de 32 bits, avec unereduction d’Oklobdzija

4.3 Analyse des resultats

On constate que le reseau de Braun sequentiel montre une progressionlineaire de sa vitesse qui le rend inutilisable en pratique.D’autre part l’algorithme d’Oklobdzija reste dans tous les cas le plus per-formant, avec une vitesse tres proche de celle du reseau de Braun modifie(les courbes de vitesse sont meme confondues dans le cas sans recodage), etla reduction de Dadda est legerement plus lente. L’augmentation de surfaceest exponentielle dans tous les cas, et semble inevitable pour un circuit noniteratif.

On remarque aussi que le recodage penalise les performances : ceci est duen partie au fait qu’on ne prend pas en compte les problemes de sortance, quien pratique ralentiraient les algorithmes sans recodage, alors qu’un circuitavec recodage peut inclure l’amplification des signaux dans le circuit derecodage. Lorsque la difference de vitesse entre les portes AND, OR et XORpar rapport au Full adder est plus marquee, le recodage Booth 2 permetd’ameliorer les performances de facon importante.

Le gain en surface est important quand on recode jusqu’a Booth3, puis lesurcout induit par le recodeur de Booth de plus en plus complexe et le circuitde selection des multiples plus grand, ainsi que les additionneurs calculantles multiples difficiles rend la surface totale plus grande qu’un algorithmesans recodage. Un recodage de Booth 4 est ici sans interet.

L’utilisation d’un recodage de Booth 2 me semble etre un bon compromis

entre vitesse et surface.D’autre part le choix de Braun modifie comme arbre de reduction peut

etre judicieux, car cet arbre est tres proche de la methode d’Oklobdzija pourles performances, et possede l’avantage d’etre extremement regulier, ce quiconstitue un avantage fort pour l’implantation materielle.

Chapitre 5

Conclusions et perspectives

5.1 Conclusion sur la multiplication asynchrone

Dans la bibliotheque de portes utilisee, la difference de vitesse etait peumarquee entre les portes logiques et le full adder, ce qui a penalise les per-formances du recodage. Cependant un recodage Booth 2 permet un gain desurface au prix d’une perte de vitesse peu importante.

Adapter la methode d’Oklobdzija pour le calcul asynchrone m’a demandebeaucoup de temps a cause des delais variables dans les composants, aux-quels il faut toujours penser en asynchrone, alors que l’algorithme beaucoupplus simple a concevoir du reseau de Braun modifie donne des performancestres proches, et possede un avantage pour le placement des composants.

5.2 Travail restant a faire

Il existe d’autres algorithmes de multiplication potentiellement interessanta etudier dans le cas asynchrone, par exemple les decompositions recursives(du type decrit dans [Vui83]). D’autre part il faudrait completer la bi-bliotheque double rail en y integrant des composants specialises performantspour l’additionneur carry-skip qui pourraient rendre plus interessant les re-codages Booth 2 et 3, trop lents, qui permettent une reduction importantede la surface du circuit.

La multiplication asynchrone en temps moyen est interessante en termesde performances, particulierement utilisee dans des algorithmes iteratifs.C’est le cas pour les calculs de fonctions elementaires, basees sur un schemade Horner dans tous les processeurs.

33

Bibliographie

[Avi61] A.Avizienis Signed-digit number representations for fast paral-lel arithmetic, IRE transactions on Electronic Computers 10(1961), p. 389-400, Reprinted in E. E. Swartzlander,Computer Arithmetic, Vol. 2, IEEE Computer SocietyPress Tutorial, 1990.

[Boo51] A.D. Booth A Signed Binary Muliplication Technique, Qar-terky J. Mechanical Applications in Mathematics, vol4, 1951, p.236-240.

[Bou01] N. Boullis Algorithmes de division pour les circuits asyn-chrones, Rapport de DEA, Ecole Normale Superieure deLyon, 2001.

[Bra63] E.L.Braun Digital Computer Design New York Academic,1963

[Che00] F.-C. Cheng, S.H. Unger et M. Theobald Self-TimedCarry-Lookahead Adders, IEEE Transactions on Compu-ters, Vol 49, juillet 2000, p. 659-672.

[Dad76] L. Dadda On Parallel Digital Multipliers Alta freq., vol 45,1976, p. 574-580.

[Erc03] M.D. Ercegovac et T. Lang Digital Arithmetic, MorganKaufmann Publishers, 2003.

[Mar90] A. J. Martin The limitations to delay-insensivity in asynchro-nous circuits, Sixth MIT Conference on Advanced Re-search in VLSI (W. J.Dally ed.), MIT Press, 1990, p.263-278.

[Mar00] P. Markstein IA-64 and elementary functions, Prentics-HallPTR, 2000.

[Mul63] D.E. Muller. Asynchronous logics and application to infor-mation processing, In H. Aiken and W. F. Main, edi-tors, Proc. Symp. on Application of Switching Theoryin Space Technology, Stanford University Press, 1963,p.289–297.

[Mul89] J.-M. Muller Arithmetique des ordinateurs, Masson, 1989.[Okl95] V.G. Oklobdzija et D. Villeger Improving Multiplier design

by Using Improved Column Compression Tree and OptimizedFinal Adder in CMOS Technology, IEEE Transactions onVLSI Systems, bol 3, juin 1995, p-292-300.

34

[Okl96-1] V.G. Oklobdzija et P.F. Stelling Design strategies for Op-timal Hybrid Final Adders in a Parallel Multiplier, Journal ofVLSI Signal Processing 14, 1996, p.321-333.

[Okl96-2] V.G. Oklobdzija, D. Villeger et S. S. Liu A Method forSpeed Optimized Partial Product Reduction and Generation ofFast Parallel Multipliers Using an Algorithmic Approach, IEEETransactions on Computers, vol 45, mars 1996, p. 294-305.

[Par00] B. Parhami Computer Arithmetic : Algorithms and hardwaredesigns, Oxford University Press, 2000.

[Spa92] J. Sparsø, C. D. Nielsen, L. S. Nielsen, J. Stauns-trup, Design of Self-timed Multipliers : A Comparison, Tech-nical University of Denmark, Department of ComputerScience Tech. Rep., 1992.

[Spa02] J. Sparsø, S.B. Furber, Principles of Asynchronous CircuitDesign : A Systems Perspective, Kluwer Academic Publi-shers, April 2002.

[Sut89] I.E. Sutherland Micropipelines, Communications of theACM, vol 32, juin 1989, p.720-738.

[Tis97] A. Tisserand Adequation arithmetique architecture : problemeset etudes de cas, These, Ecole Normale Superieure deLyon, 1997.

[Vui83] J. Vuillemin A very fast multiplication algorithm for VLSI im-plementation, Integration, the VLSI journal, 1983, p 39-52.

[Wal64] C.S. Wallace A Suggestion for a Fast Multiplier IEEE Tran-sactions on Electronic Computers, vol 13, 1964, p. 14-17