Exploration des optimisations temps / surface

Approche Allocation optimale

Dans [UKL99] est présenté un algorithme en temps polynomial qui, à partir d’une expression arithmétique, a pour but de déterminer la structure optimale de CSA minimisant la chaîne longue. Cela part de la constatation de base que la chaîne critique d’un circuit est le critère le plus important à améliorer.
Les résultats présentés sur différentes opérations (mêmes conditions que pré-cédemment) montrent une amélioration significative du temps et de la surface par rapport à la version classique, par exemple, -23% en temps et -39% en surface pour une somme de 9 nombres, -25% en temps et -20% en surface pour l’opération A B+C D+E F+G H.
Un nouveau concept est de plus présenté ici, appelé auxiliary port. C’est une solution au problème de hiérarchie dans les circuits. Le postulat de base est que la conception de gros circuits se fait en utilisant la hiérarchie (exemple dans la Figure 3.2.a). Optimiser chaque sous-circuit séparément amène à une réalisation qui n’est pas optimale pour le circuit complet à cause des convertisseurs CS ! NR en sortie de chaque sous-circuit, comme montré dans la Figure 3.2.b.
Le concept présenté consiste en la création d’un nouveau port appelé auxiliary port. Dans l’exemple présenté, il consiste en remonter la sortie du circuit a à l’entrée du convertisseur, comme montré dans la Figure 3.2.c. La sortie de ce circuit devient donc en représentation CS, c’est pourquoi un deuxième port est nécessaire. Suite à cela, une nouvelle optimisation peut être faite (cf. Figure 3.2.d).
Les résultats présentés se font, entres autres, sur un circuit contenant 9 opérateurs répartis en 3 sous-circuits.
Ce concept améliore le temps de -25% par rapport à une synthèse classique, et -17% par rapport à une optimisation « classique ». Pour la surface, les valeurs sont de -14% et -5%. Les performances obtenues sont donc meilleures grâce à ce nouveau concept.

Gestion des blocs non arithmétiques et des multiplieurs

Trois concepts sont présentés dans [KU00a] et [KU00b] : l’optimisation à travers la hiérarchie (notion restreinte de [UKL99]), celle à travers les multiplexeurs et celle à travers les multiplieurs.
Les algorithmes précédents étant limités à des circuits purement arithmétiques, le concept d’optimisation à travers les multiplexeurs permet de surmonter cette limitation.
Trois étapes sont effectuées, comme montré dans la Figure 3.3 :
1. move-up (remontée des opérations avant le multiplexeur, cf. Figure 3.3.b),
2. l’optimisation des blocs arithmétiques (cf. Figure 3.3.c),
3. move-down (les convertisseurs finaux de chaque arbre sont redescendus après le multiplexeur, on obtient donc un seul convertisseur, mais deux multiplexeurs, cf. Figure 3.3.d).
a. Cellule
b. Remontée c. Optimisation d. Descente
FIG. 3.3 – Optimisation à travers les multiplexeurs
Le concept d’optimisation à travers les multiplieurs a pour but quant à lui de com-penser le fait qu’un multiplieur ne puisse être qu’une feuille des arbres d’additions formés.
Dans la Figure 3.4 sont présentées une cellule (a) et sa version optimisée (b). L’ad-ditionneur final du multiplieur a bien été optimisé, mais il n’a pas été possible d’opti-miser l’additionneur d’entrée de la cellule. L’idée est donc de faire glisser le multiplieur en entrée de façon à élargir la portion d’additionneurs, comme montré dans la Figure 3.4.c. L’additionneur pourra de cette façon être transformé en CSA.
Il est cependant conseillé de n’effectuer cette solution que lorsque les contraintes de temps sont primordiales, car l’augmentation en surface est alors très importante.
a. Cellule b. Optimisation possible c. Glissement
FIG. 3.4 – Optimisation à travers les multiplieurs
Les résultats présentés comparent ces nouvelles approches à des synthèses RTL classiques ainsi qu’à la précédente approche présentée dans [KJT98b].
Ils se résument à une amélioration systématique du temps critique grâce à l’intro-duction de ces nouveaux concepts, et des performances en surface tantôt meilleures, tantôt moins bonnes.
Remarques :
1. Le principe des deux nouveux concepts présentés s’apparente au principe de glis-sement que nous avons présenté dans la Figure 1.8.
2. Dans notre approche, nous prévoyons d’utiliser les multiplieurs redondant et mixte. Les multiplieurs ne sont donc pas contraints d’être des feuilles des arbres à optimiser. Ce principe de glissement ne nous est donc pas utile en ce qui concerne les mutliplieurs.

Compromis Surface/Délai

Le problème de limitation de type donnée est de nouveau traité dans [KK01] dans lequel il est fait une étude du compromis entre temps et surface.
Trois optimisations sont comparées :
1. optimisation des arbres séparément,
2. optimisation des différentes opérations indépendamment, sans partage de res-sources,
3. optimisation des opérations avec partage de ressources.
Le principe présenté s’apparente au principe de dédoublement de la donnée déjà ex-posé. L’étude faite ici montre l’intérêt de ce principe par rapport aux autres approches possibles, principalement l’optimisation sans partage de ressource, ce qui n’avait pas été envisagé jusque-là.
Les architectures des différentes optimisations possibles d’un circuit sont présen-tées dans la Figure 3.5 et leurs performances respectives dans le Tableau 3.2.
Ces résultats montrent que l’optimisation sans partage de ressources est la moins performante du point de vue de la surface. En effet, il y est fait moins d’optimisations que dans les deux autres.
Les meilleures performances en temps sont obtenues avec l’optimisation sans par-tage de ressources. En effet, le nombre de portes traversées est le même que pour celle effectuant un compromis, mais la traversée des portes est plus rapide du fait que chaque opérateur a sa sortie connectée à un seul autre opérateur, et a donc une capa-cité de sortie moindre. Le surcoût en surface avec cette optimisation la rend cependant difficilement utilisable.
C’est donc l’optimisation avec partage de ressource qui est présentée comme étant la meilleure, car elle génère le meilleur rapport temps/surface.

Prise en compte de la vue physique

Dans [UK02], Kim s’intéresse à la vue physique des circuits.
Le postulat de base est que le temps de propagation dans les fils d’interconnexion devient au fur et à mesure des années de plus en plus important par rapport au temps de propagation des portes. De nouveaux phénomènes existent avec les nouvelles technologies telles que la diaphonie.
L’idée directrice est toujours de se baser sur l’utilisation des CSA, mais le but est ici de rendre les interconnexions les plus régulières possibles.
L’algorithme présenté se déroule en deux phases :
1. synthèse optimale d’un algorithme avec utilisation des CSA (optimisation au ni-veau mot),
2. raffinement des interconnexions au niveau du bit.
La synthèse est celle qui a déjà été présentée. Le raffinement est une optimisation au niveau bit qui ne modifie pas la topologie faite par la phase 1 au niveau mot. Il est constitué de deux méthodes.
La première est la fusion de deux demi-additionneurs (noté HA pour half-adder) en un FA (en effet, des HA ont pu être instanciés lors de la première phase à la place de FA pour les CSA additionnant des nombres de tailles différentes par exemple).
La seconde est le réordonnancement des entrées d’un FA, de façon à rendre plus régulier le positionnement des entrées en fonction du dessin en masque du FA.
Les résultats présentés comparent cette nouvelle approche à une approche effec-tuant elle aussi une optimisation du temps au niveau bit [SMOR98], montrant que la nouvelle approche améliore le chemin critique.

Extension de la représentation Carry-Save

Les travaux de Alan N. Willson Jr. ont la particularité d’effectuer des modifications de la représentation Carry-Save pour élargir les possibilités d’optimisation.

Optimisation des CSA au niveau bit

Dans [KYW99] est présentée une optimisation au niveau bits. Une nouvelle repré-sentation est introduite, appelée la représentation relax carry-save (notée RCS), étant donnée qu’elle permet à chaque bit d’un nombre d’être codé sur 1, 2 ou 3 termes. Lors de l’addition de nombres n’ayant pas la même taille, plutôt que d’instancier systéma-tiquement des FA pour les bits de poids faible et des HA pour les bits de poids fort (additionnant 2 bits au lieu de 3 pour les bits pour lesquels on dépasse la taille d’un des 2 opérandes), l’idée est de trouver la configuration optimale entre ces deux cellules.
L’algorithme présenté construit une matrice K 2 N, N étant la taille du plus grand nombre à sommer, et K le nombre d’opérandes à sommer. Pour chaque élément de la matrice il définit quelle porte utiliser entre le HA et le FA. La contrainte est de respecter la notation Carry-Save classique à la sortie de la matrice de façon à pouvoir effectuer la conversion finale CS ! NR.
Des résultats sont présentés, comparant les coûts de différents filtres utilisant soit une instanciation de CSA classique, soit cette nouvelle approche. Ils montrent que la nouvelle approche donne de meilleures performances, avec des coûts améliorés de 15% à 30%.

Signaux multiple vecteurs

Les problèmes traités dans [YYW01] sont le traitement des registres (principes de operation forward et operation backward), et celui des sorties multiples (principes de opera-tion duplicate et operation merge).
Ces problèmes sont traités avec une nouvelle notion, celle de signaux dits multiple vecteurs i.e. une extension de la notation Carry-Save qui propose de coder les nombres sur plus de 2 termes. Les résultats présentés comparent trois architectures pour différents circuits : une avec le nouvel algorithme présenté, une autre classique, et enfin une qui n’utilise pas ce nouveau principe [YKW00].
Par rapport à une architecture classique, le temps est toujours amélioré (jusqu’à -45.5%) et la surface toujours dégradée (jusqu’à +60.3%). Par rapport à une architec-ture utilisant la représentation Carry-Save, mais pas de signaux multiple vecteurs, les conclusions sont les mêmes (jusqu’à -56% en temps et +15% en surface).
On peut en déduire que cette nouvelle approche permet d’améliorer encore plus le temps au détriment de la surface.

Réorganisation des graphes

Ordonnancement de graphe

Les travaux de Paolo Ienne se basent sur la modification de graphes de façon à ce que les outils de synthèse puissent utiliser les CSAs au mieux.
L’idée directrice est que le frein principal à une bonne utilisation des CSAs réside dans la présence d’opérateurs non arithmétiques. L’algorithme présenté dans [IV04] a donc pour but d’aggrandir les portions d’additionneurs chainés de façon à maximiser l’usage des CSAs.
Cet algorithme a pour entrée un DAG G(V; E) représentant le circuit à optimiser.
V correspond à l’ensemble de opérateurs, et E, l’ensemble des signaux. Les nœuds du graphe G sont ordonnés de telle façon que pour chaque arc (u; v) de G, u apparaisse avant v dans l’ordonnancement. La fonction Ord() donne la position d’un nœud. De plus, une fonction Class() est définie, qui renvoie la classe d’un nœud : A si c’est un opérateur arithmétique, L sinon.
Le but de l’algorithme est décrit comme suit : Etant donné un graphe G, un graphe H équivalent est créé (i.e. représentant un circuit avec le même comportement que le circuit représenté par G) pour lequel tous les nœuds u et v tel que Class(u) = A et Class(v) = L vérifient Ord(u) < Ord(v) ou Ord(v) < Ord(u). Le graphe H est dit trié.
Le graphe obtenu a séparé les blocs arithmétiques des autres, et est donc apte à être optimisé. Cet algorithme n’est cependant pas toujours applicable. Une solution est donc présentée, consistant à trier un graphe autant que possible. En définissant le nombre de couches d’un graphe comme étant le nombre de transition A=L et L=A, le second algorithme présenté permet d’obtenir le graphe H avec le nombre minimum de couches.
Dans la Figure 3.6 est présenté un exemple. A partir d’un graphe non ordonné contenant deux couches (cf. Figure 3.6.a : Class(1) = A, Class(5) = L et Class(7) = A, or, Ord(1) < Ord(5) < Ord(7)), on obtient un graphe ordonné contenant le minimum de couches possible, une seule (cf. Figure 3.6.b).
Les résultats présentés comparent les performances de circuits synthétisés, avec optimisation ou non du graphe original. Pour certains circuits, une implantation faite à la main est également présentée.
Ces résultats montrent que le délai est amélioré (jusqu’à -43%) pour tous les circuits testés sauf un (+8%) par rapport à la synthèse directe et que les différences de surface varient entre -20% et +33%. Pour les circuits créés manuellement, le délai est moins bon, et la surface plus petite.