Du codage des automates en vue de la synthèse sur silicium :
comparaison systématique et critique des approches existantes
 
 

Ludovic Jacomme et Frédéric Pétrot
Équipe Architecture du laboratoire LIP6
Université Pierre et Marie Curie
4, place Jussieu, 75252 Paris cedex 05
{jacomme,petrot}@asim.lip6.fr

Résumé
Nous nous intéressons dans ce travail au problème concret du codage des états d'une machine à états en vue de la synthèse multi-niveaux vers un réseau booléen. Ce problème, NP-complet, consiste à assigner un code à chacun des états de sorte que le réseau booléen résultant soit minimal. Un travail théorique et pratique très important a été mené depuis les années 1985 sur le sujet, afin de fournir un `` bon '' codage pour l'implantation de grosses machines à états sur le silicium. Nous avons mené une étude systématique consistant à faire calculer par chacun des principaux algorithmes connus le codage qu'il considère optimal pour un ensemble significatif d'automates, puis à placer et router le circuit résultant, afin de comparer les performances en délais et surface. Nous concluons qu'en moyenne, la méthode de codage la plus efficace est aussi la plus triviale : un registre 1 bit code 1 état.
  • Introduction
  • Présentation du problème
  • Les techniques de codages d'états
  • Comparaisons
  • Conclusion
  • Annexe
  • About this document ...

    • Introduction

    Dans le cadre de la conception de circuits VLSI, il est très courant de trouver des parties formalisées sous forme d'automates d'états. C'est en particulier le cas des parties d'un micro-processeur qui contrôlent l'enchaînement des instructions, les étages d'un pipe-line, les accès à la mémoire parfois. Le nombre d'états est généralement assez grand : 49 pour le petit processeur RISC Dlxm, 125, avec une pile de profondeur trois, pour le 6800 par exemple. Une recherche exhaustive ou un codage manuel sont impossible dans ces conditions. Bref, le champs d'application est vaste, et la qualité des résultats de la synthèse critique : il n'est pas rare que ce soit l'une de ces partie qui impose le temps de cycle du circuit. Aussi, de nombreux chercheurs se sont intéressés au problème, en tâchant de minimiser la logique réalisant un automate grâce à un codage judicieux, recherchant ainsi des performances maximales pour une surface de silicium minimale.

    Dans ce papier, nous présentons une récapitulation des approches existantes qui se veut tout à fait pragmatique : nous faisons un état de l'art rappelant les principales techniques, et donnons des résultats chiffrés après génération de la vue physique du silicium réalisant l'automate. Ceci doit permettre de déterminer l'algorithme le plus efficace après synthèse, et de détecter d'éventuelles corrélations avec des particularités de l'automate.

    Dans un premier temps, le paragraphe 2 pose le problème. Le paragraphe 3 expose dans les grandes lignes les techniques publiées. Nous détaillons les points forts et les points faibles de ces approches.

    Ensuite, nous faisons une utilisation systématique de ces algorithmes sur une soixantaine de circuits, et comparons les résultats sur les fonctions de coût minimisées, et sur les circuits physiques obtenus après synthèse.


    Présentation du problème

    Notations : on utilisera $a \cdot b$ pour le et logique ($a\wedge b$), $a + b$ pour le ou logique ($a \vee b$) et $\overline{a}$ pour le not ($\neg a$). Un littéral est l'occurence d'une variable boolénne $a$ ou de son inverse $\overline{a}$ dans une expression booléenne.

    Un automate, comme celui représenté par son graphe d'états de la figure 1, est très simplement transformable en l'implantation matérielle générique représentée figure 2. Les automates aussi bien de Moore, c.-à-d. dont la valeur des sorties ne dépend que de l'état, que les automates de Mealy, dont les sorties dépendent à la fois de l'état courant et des entrées -- trait en pointillé sur la figure 2 --, peuvent être implantés de la sorte.


     
    \psfig {figure=fsm.eps,height=6cm,silent=}

     
     
    Figure 1: Automate sous forme de graphe d'états.
    \psfig {figure=automate.eps,height=8cm,silent=}
    Figure: Architecture générique d'implantation des automates
    Formellement, un automate est défini par un quintuple $\{I, O, S, \Theta, \Gamma\}$, ou $I$ est l'ensemble des entrées, $O$ l'ensemble des sorties, $S$ l'ensemble des états, $\Theta$ l'ensemble des fonctions de transition tel que $\Theta : I\times S\rightarrow S$, et $\Gamma$ l'ensemble des fonctions de génération tel que $\Gamma : S\rightarrow O$ pour les automates de Moore, et $\Gamma : I\times S\rightarrow O$ pour les automates de Mealy. Les éléments de $I, O\/$ et $S$ sont constitués de symboles. Pratiquement, on fait ressortir l'état courant des fonctions : $\{\theta \in \Theta \mid \theta_{ij} = S_i\cdot t_{ij}\}$, et identiquement, $\{\gamma \in \Gamma \mid \gamma_{ij} = S_i\cdot g_{ij}\}$. Ce choix est dû à la manière dont les concepteurs décrivent leurs machines à états. On peut en effet représenter un automate sous forme de graphe orienté noté $G(V, E)$, ou $V$, l'ensemble des n\oe uds du graphe, représente les états, et $E$ l'ensemble des arcs du graphe, représente les transistions permettant de passer d'un état à un autre. Les arcs sont annotés avec les fonctions $t_{ij}$ et $g_{ij}$, comme indiqué figure 1.

    Du point de vue de la réalisation, on distingue deux parties combinatoires disjointes qui implémentent $\Theta$ et $\Gamma$, et qui dépendent donc du codage des éléments de $I, O\/$ et $S$. Dans le cadre qui nous intéresse, l'ensemble des valeurs possibles des éléments de $I$ et $O$ est connu a priori : elles sont dictées par l'interface du circuit réalisant l'automate avec le monde extérieur. Par contre, l'ensemble $S$ ne contient dans la description initiale que des symboles. Le problème est d'affecter à chacun des éléments de $S$ un code unique. Lorsque tous les $S_i$ ont une valeur, on a alors un `` codage ''.

    Un `` bon '' codage est un codage qui minimise les équations booléennes intervenant dans les deux parties.


    Les techniques de codages d'états

    Soit $n = \mid\!\!S\!\!\mid $. On dit, par abus de language, que si l'on est dans l'état $S_i$, alors $S_i = 1$. Dans ces conditions, déterminer quand l'état $S_i$ peut être atteint, c'est écrire :
    \begin{displaymath}S_i \Leftarrow \sum_{j=1}^{n} S_j \cdot t_{ji}\end{displaymath} (1)
    Le graphe d'états n'est en général pas complet, donc si l'on note $p$ le nombre de n\oe uds prédecesseurs de $S_i$, il n'existe que $p$ fonctions $t_{ji}$ non nulles.

    De même, affecter une sortie, c'est écrire :

    \begin{displaymath}O_i = \sum_{j=1}^{n} S_j \cdot g_{ji}\end{displaymath} (2)
    Si $q$ est le nombre d'états qui mettent à 1 cette sortie, alors il n'y a que $q$ fonctions $g_{ji}$ non nulles.

    Deux approches orthogonales sont employées. L'une consiste à dire que le registre $R_i$ code l'état $S_i$, c.-à-d. $R_i = 1$ implique que la machine est dans l'état $S_i$, avec la condition que $\{\forall i \leq n, \exists ! i \mid R_i = 1\}$. Ainsi, on code de manière mutuellement exclusive un état dans un registre. L'autre consiste à encoder les $n$ symboles dans ${\lceil\log_2{n}\rceil}$ registres, un symbole étant codés par un produit de ces registres, $S_i = r_{{\lceil\log_2{n}\rceil}}\cdot r_{{\lceil\log_2{n}\rceil}-1}\cdotsr_2\cdot r_1$, ou $r_i$ est un littéral.

    On peut envisager des codages sur $m$ bits, ${\lceil\log_2{n}\rceil} \leq m \leq n$, et pour autant que nous sachions, le seul travail expérimental publié sur le sujet est Muse [#!muse!#].

    Codage simple

    Dans le cas où l'on affecte un registre et un seul par état, nommé one-hot encoding dans la littérature [#!one-hot!#], la formule (1) s'écrit :
    \begin{displaymath}S_i \Leftarrow \sum_{j=1}^{n} R_j \cdot t_{ji}\end{displaymath} (3)
    car un seul $R_i$ peut être actif (à 1) par définition, car on ne traîte que des automates déterministes.

    L'affectation dans les registres de codage va suivre la même logique, et l'on peut directement substituer $S_i$ par $R_i$ dans (3).

    \begin{displaymath}R_i \Leftarrow \sum_{j=1}^{n} R_j \cdot t_{ji}\end{displaymath} (4)
    Le choix d'affecter tel registre à tel symbole ne se pose pas : toutes les solutions sont identiques, car les registres sont interchangeables.

    L'équation (2) concernant les sorties devient :

    \begin{displaymath}O_i = \sum_{j=1}^{n} R_j \cdot g_{ji}\end{displaymath} (5)
    La logique permettant d'implémenter les $t_{ji}$ et $g_{ji}$ n'est pas influencé dans cette technique. Ce sera donc aux outils de minimisation logique d'optimiser le réseau booléen.

    La crainte sous-jacente à cette approche est que pour de grands automates la surface occupé par les registres devienne très importante : en effet, une cellule de type registre est 5 à 6 fois plus grosse que les portes logiques de base.

    Encodage sur $\log_2{n}$ bits

    On note $s_j$ le code de l'état $S_j$, et on a $\mid\!\!s_j\!\!\mid ={\lceil\log_2{n}\rceil}$. Pour $1 \leq j \leq n$ et $1 \leq k \leq{\lceil\log_2{n}\rceil}$, on défini$\pi(j,k)$ tel que
    \begin{displaymath}\pi(j,k) = \left\{\begin{array}{ll}1 & \mbox{si le $k^{\rm\......t de $s_j$\ vaut $1$,}\\0 & \mbox{sinon}\end{array}\right.\end{displaymath}


    On note

    \begin{displaymath}r_{jk} = \left\{\begin{array}{ll}r_k & \mbox{si $\pi(j,k) = 1$}\\\overline{r_k} & \mbox{ sinon}\end{array}\right.\end{displaymath}

    Le code de $S_j$ s'écrit :

    \begin{displaymath}s_j = \prod_{k=1}^{{\lceil\log_2{n}\rceil}}r_{jk}\end{displaymath} (6)
    Si l'on cherche à encoder, le calcul de l'état suivant va se reécrire ainsi, en substituant dans  (1) le$s_j$ de l'équation (6) :
    \begin{displaymath}S_i \Leftarrow \sum_{j=1}^{n}\big(\!\!\!\prod_{k=1}^{{\lceil\log_2{n}\rceil}}r_{jk}\big)t_{ji}\end{displaymath} (7)
    L'affectation du bit $b$ du registre d'état sera :
    \begin{displaymath}R_b \Leftarrow \sum_{l=0}^{n}\Big[\sum_{j=1}^{n}\big(\!\!\......{\lceil\log_2{n}\rceil}}r_{jk}\big)t_{jl}\Big]\times\pi(l,b)\end{displaymath} (8)
    On suppose que dans le pire cas ${\lceil\log_2{n}\rceil} = \log_2{n}$, ce qui produit un codage complet et qui implique que chaque registre est activé pour un état sur deux. Ceci est traduit par le fait que probabilité que$\pi(l, b)$ pour $b = \mbox{\it constante}$ vaut $\frac{1}{2}$.

    Pour l'affectation des sorties, nous aurons pareillement, en substituant l'expression de $s_j$ dans (2) :

    \begin{displaymath}O_i = \sum_{j=1}^{n}\big(\!\!\!\prod_{k=1}^{{\lceil\log_2{n}\rceil}}r_{jk}\big)g_{ji}\end{displaymath} (9)
    Avec cette seconde approche, les équations contiennent à première vue plus de littéraux. Le pari qui la justifie est qu'une partie importante de la logique va être partagée pour activer les différents registres et/ou sorties. On cherche donc à coder de façon aussi proche que possible, au sens de la distance de Hamming, $\Delta$, des états ayant telle ou telle propriété.

    Mustang

    Deux stratégies sont implémentées dans Mustang [#!mustang!#]. La première, orientée sortie, tente de coder de façon aussi proche que possible les états qui ont les mêmes prédecesseurs, et/ou qui affectent les mêmes sorties. Pour chaque couple d'états, un coût $C(S_i, S_j)$ est calculé sous forme de somme pondéré. Dans la seconde stratégie, orientée entrée, deux états ont une intéraction d'autant plus importante qu'ils ont les mêmes états suivant et/ou les mêmes conditions de transistion entrantes. De même, pour chaque couple d'états un coût est calculé.

    Une heuristique, dite wedge clustering, est utilisé pour trouver les codes minimisant la somme :

    \begin{displaymath}\forall i \not= j, \sum_{i=1}^{n}\sum_{j=1}^{n}C(S_i, S_j)\times\Delta(s_i, s_j)\end{displaymath}

    À chaque étape, on choisi un état $S_i$ et un ensemble d'états $\sigma \subset S$ tel que la somme $\sum_{S_j \in \sigma}C(S_i, S_j)$ soit maximal. L'algorithme impose $\mid\!\!\sigma\!\!\mid = {\lceil\log_2{n}\rceil}$.

    Jedi

    Jedi [#!jedi!#] emploie dans les grandes lignes des techniques similaires à Mustang. Là aussi il existe deux approches, basées sur l'expression des$\theta_{ij}$ et $\gamma_{ij}$ sous forme de sommes de produits. Lorsque l'on est orienté sortie, on cherche à regrouper les états qui font intervenir les mêmes littéraux dans la forme normale disjonctive qui les affectent, sans se soucier de l'état qui utilise ces littéraux. Ainsi, on couple fortement les états dont les fonctions de transition entrantes ont un grand nombre de littéraux en commun.

    Dans le cas orienté sortie, l'intéraction entre $S_i$ et $S_j$ est d'autant plus importante qu'il existe de $t_{ij}$ et de $g_{ij}$ contenant des termes faisant apparaître $S_i$ et $S_j$.

    Lors du codage proprement dit, on affecte un code à un seul état à la fois, en fonction de ses intéractions avec les états précédemment codés. La fonction à minimiser est la même que pour Mustang.

    Nova

    Nova [#!nova!#] vise une implémentation deux-niveaux, qui s'avère bien fonctionner pour des cibles multi-niveaux. Nova travaille sur une forme normale-disjonctive, avec les particularités suivantes : L'attribution des codes se fait de manière identique à Mustang et Jedi.

    Asp

    Une approche très différente est utilisé dans Asp [#!asp!#]. Au lieu d'assigner un code par état à chaque étape, on positionne 1 bit dans l'ensemble des états en une fois. Asp crée des groupes d'états qui partagent certaines propriétés, telles que ceux des $S_i$ qui partagent les mêmes combinaisons d'entrées, ou ceux des $S_j$ qui apparaissent dans les$t_{ij}$ et $g_{ij}$, etc. Le premier bit de codage permet de séparer les codes des états du premier groupe, le deuxième bit sépare les codes des états du deuxième groupe, et ainsi de suite. S'il n'y a plus de bit disponible, alors une technique `` à la Mustang '' est employée sur la partie des états restant à coder.

    Améliorations itératives

    La recherche d'un codage optimal par algorithme génétique est proposé dans [#!mit!#]. Les résultats sont très encourageant en ce qui concerne la minimisation de la fonction de coût de Mustang. Malheureusement, cette fonction de coût n'est pas fidèle vis-à-vis du résultat d'une synthèse logique optimisée.

    Sarwary [#!chaker!#] propose une autre fonction de coût censée représenter plus fidèlement la synthèse optimisée, basée sur les graphes d'expressions factorisées. La technique utilisée est alors un codage aléatoire suivie d'une optimisation par descente de gradient locale. Dans cette situation, les $\Delta(s_i,s_j)$ n'apparaissent pas explicitement.

    Bien que meilleur que celle de Mustang, cette fonction de coût n'est pas telle que le signe de sa dérivée en tout point est identique au signe de la dérivée du coût réel, ce qui indique que minimiser cette fonction n'est pas minimiser la réalité. De plus, le temps de création des graphes d'expressions factorisées est trop long pour envisager son utilisation dans un recuit simulé ou un algorithme génétique.

    Comparaisons



     
     
     

    Les entrées notées `` $\star$ '' sont décrites dans un format que les outils de Berkeley ne comprennent pas : ce sont des automates appartenant à des circuits développés dans notre laboratoire en utilisant un sous-ensemble du langage VHDL. Les entrées `` $\dagger$ '' sont dues à une non terminaison d'un des outils de génération.


    Nombre de littéraux

    L'atome de mesure standard en synthèse logique est le nombre de littéraux. Une première estimation de la qualité d'un algorithme est donnée par ce nombre, qui doit être le plus petit possible. La table 2 présente les résultats obtenus pour cette métrique. Nous noterons que dans les tests publiés, c'est cette unique mesure qui est faite.
    Table 2: Nombre de littéraux produits par les différents algorithmes.
    Automate entrées sorties états one-hot Asp Mustang Jedi Nova
    dk15 3 5 4 121 90 90 84 82
    lion 2 1 4 36 24 23 23 19
    mc 3 5 4 39 34 29 32 34
    train4 2 1 4 25 18 18 18 18
    s8 4 1 5 98 65 99 91 83
    bbtas 2 2 6 40 31 33 32 33
    s27 4 1 6 80 28 43 28 62
    beecount 3 4 7 111 105 100 86 100
    dk14 3 5 7 153 178 175 164 124
    dk27 1 2 7 33 30 27 30 34
    dk17 2 3 8 85 77 93 92 79
    ex6 5 8 8 206 219 223 195 199
    shiftreg 1 1 8 36 12 27 9 10
    ex5 2 2 9 93 134 117 108 131
    lion9 2 1 9 67 98 130 72 94
    bbara 4 2 10 127 83 139 140 94
    ex3 2 2 10 95 130 127 116 132
    ex7 2 2 10 96 152 119 136 149
    opus 5 6 10 127 136 151 131 186
    r3auto 12 7 10 121 124 136 $\star$ $\star$
    r3ioc 17 12 11 231 265 296 $\star$ $\star$
    train11 2 1 11 78 125 147 90 126
    modulo12 1 1 12 61 42 54 46 49
    s386 7 7 13 159 203 222 200 231
    ex4 6 9 14 95 163 141 111 150
    dk512 1 3 15 72 89 94 73 76
    mark1 5 16 15 133 142 138 139 162
    bbsse 7 7 16 171 238 258 213 188
    cse 7 7 16 284 442 403 393 395
    kirkman 12 6 16 287 279 410 277 207
    sse 7 7 16 171 238 258 213 188
    log 9 24 17 106 218 233 226 297
    s208 11 2 18 141 127 184 173 118
    s420 19 2 18 141 127 184 181 118
    ex2 2 2 19 174 267 288 200 281
    keyb 7 2 19 392 359 479 369 492
    ex1 9 19 20 420 597 787 580 646
    s1 8 6 20 416 583 637 416 678
    s1a 8 6 20 281 419 408 259 462
    tma 7 6 20 246 505 564 494 535
    donfile 2 1 24 192 299 311 114 177
    pma 8 8 24 552 1000 1080 925 1073
    fetch 9 15 25 98 226 190 189 230
    s820 18 19 25 404 661 565 504 487
    s832 18 19 25 391 539 516 517 662
    dk16 2 3 27 269 442 414 324 378
    nucpwr 13 27 29 137 356 289 272 365
    rie 9 26 29 168 355 305 307 472
    styr 9 10 30 621 1098 1030 946 927
    sand 11 9 32 705 883 863 932 1000
    tbk 6 3 32 1163 1468 1540 1092 1769
    dvram 8 15 35 162 287 396 381 364
    s510 19 7 47 292 584 470 427 552
    planet 7 19 48 604 1021 1047 1034 1062
    s1488 8 19 48 697 918 958 1001 955
    s1494 8 19 48 698 1011 972 996 1043
    dlxm 19 38 51 1448 1341 1450 $\star$ $\star$
    sync 19 7 52 297 534 544 507 743
    ramtest 16 24 72 372 857 1012 902 1279
    scf 27 56 121 790 1705 1741 2027 2062
    6800 23 58 125 23091 8972 8765 $\star$ $\star$
    s298 3 6 218 3246 3654 5260 3840 3982
    % 61% 14% 5% 10% 10%


    Clairement, la suprématie du one-hot ne fait aucun doute, dès que les automates ont plus d'une dizaine d'états. Ce résultat est assez surprenant, car c'est là que l'on commence à avoir ${\lceil\log_2{n}\rceil} \ll n$. Cela prouve simplement qu'en pratique la combinatoire nécessaire pour créer l'encodeur passant de $n\rightarrow{\lceil\log_2{n}\rceil}$ et le décodeur de ${\lceil\log_2{n}\rceil}\rightarrow n$ ne se noie pas bien dans la combinatoire des $t_{ij}$ et $g_{ij}$, et coûte aussi cher à réaliser que ces fonctions et $n$ registres.

    Si les fonctions $t_{ij}$ et $g_{ij}$ sont simples ou similaires, on peut les mettre en facteur et espérer minimiser les équations (1) et (2). Notamment, si le nombre d'entrées est faible, la probabilité d'avoir des fonctions factorisable est grande, et on aura cette propriété.


    Surface

    Dans le monde des designers de circuits intégrés, le nombre de littéraux n'a s'intérêt que s'il permet effectivement de caractériser un circuit. Une mesure plus intéressante, mais aussi beaucoup plus longue à obtenir, est la surface de la logique générée après placement et routage. Les résultats sont présentés dans la table 3.

    On constate en moyenne une bonne corrélation entre la surface et le nombre de littéraux. (Il existe bien sûr des cas pathologiques, comme celui du 6800, ou encore tbk pour lequel une faible différence en nombre de littéraux produit une surface très différente : le nombre de littéraux n'est pas représentatif de la complexité du routage à tous les coups). On remarque que, pour 1 circuit donné, si un algorithme a trouvé le plus petit nombre de littéraux, il y est très probable que ce soit le même algorithme qui produise le silicium le plus petit.
     
     

    Table 3: Surface en $mm^2$ après synthèse, optimisation et placement/routage.
    Automate entrées sorties états  one-hot Asp Mustang Jedi Nova
    dk15 3 5 4 0.22 0.14 0.16 0.13 0.12
    lion 2 1 4 0.07 0.05 0.06 0.06 0.05
    mc 3 5 4 0.07 0.06 0.06 0.06 0.06
    train4 2 1 4 0.05 0.03 0.03 0.03 0.03
    s8 4 1 5 0.15 0.11 0.16 0.14 0.13
    bbtas 2 2 6 0.07 0.06 0.06 0.05 0.06
    s27 4 1 6 0.16 0.06 0.08 0.06 0.11
    beecount 3 4 7 0.19 0.18 0.15 0.17 0.23
    dk14 3 5 7 0.31 0.33 0.36 0.31 0.22
    dk27 1 2 7 0.09 0.06 0.06 0.06 0.06
    dk17 2 3 8 0.19 0.14 0.16 0.20 0.17
    ex6 5 8 8 0.32 0.36 0.33 0.33 0.34
    shiftreg 1 1 8 0.09 0.04 0.05 0.03 0.03
    ex5 2 2 9 0.14 0.24 0.19 0.21 0.24
    lion9 2 1 9 0.15 0.21 0.27 0.16 0.16
    bbara 4 2 10 0.23 0.16 0.26 0.24 0.15
    ex3 2 2 10 0.17 0.26 0.24 0.23 0.24
    ex7 2 2 10 0.17 0.24 0.20 0.23 0.26
    opus 5 6 10 0.23 0.24 0.29 0.24 0.32
    r3auto 12 7 10 0.22 0.21 0.25 $\star$ $\star$
    r3ioc 17 12 11 0.46 0.46 0.56 $\star$ $\star$
    train11 2 1 11 0.19 0.28 0.29 0.20 0.25
    modulo12 1 1 12 0.15 0.09 0.10 0.12 0.11
    s386 7 7 13 0.30 0.37 0.42 0.38 0.40
    ex4 6 9 14 0.22 0.27 0.25 0.20 0.27
    dk512 1 3 15 0.18 0.18 0.21 0.14 0.17
    mark1 5 16 15 0.26 0.26 0.25 0.26 0.30
    bbsse 7 7 16 0.32 0.55 0.47 0.43 0.41
    cse 7 7 16 0.55 0.90 0.69 0.81 0.69
    kirkman 12 6 16 0.42 0.48 0.52 0.48 0.39
    sse 7 7 16 0.34 0.50 0.50 0.45 0.43
    log 9 24 17 0.27 0.33 0.36 0.42 0.42
    s208 11 2 18 0.32 0.23 0.37 0.34 0.22
    s420 19 2 18 0.30 0.26 0.34 0.37 0.23
    ex2 2 2 19 0.35 0.52 0.55 0.40 0.58
    keyb 7 2 19 0.82 0.58 0.86 0.61 0.72
    ex1 9 19 20 0.77 1.09 1.94 1.14 1.42
    s1 8 6 20 0.94 1.73 1.86 0.97 2.17
    s1a 8 6 20 0.62 0.97 0.82 0.64 0.90
    tma 7 6 20 0.54 0.94 1.28 1.07 0.95
    donfile 2 1 24 0.47 0.72 0.82 0.26 0.41
    pma 8 8 24 0.76 1.62 2.32 1.76 2.20
    fetch 9 15 25 0.26 0.49 0.37 0.33 0.49
    s820 18 19 25 0.87 1.48 1.44 1.09 1.04
    s832 18 19 25 0.71 1.36 1.31 1.38 1.63
    dk16 2 3 27 0.67 1.18 1.08 0.83 1.09
    nucpwr 13 27 29 0.36 0.69 0.49 0.46 0.70
    rie 9 26 29 0.45 0.63 0.57 0.52 1.02
    styr 9 10 30 1.42 2.73 2.78 2.41 2.27
    sand 11 9 32 1.49 2.10 2.50 2.75 3.15
    tbk 6 3 32 4.13 4.47 4.48 1.66 4.31
    dvram 8 15 35 0.44 0.60 0.98 0.85 0.75
    s510 19 7 47 0.88 1.85 1.25 1.03 1.41
    planet 7 19 48 1.91 3.34 3.35 3.62 3.94
    s1488 8 19 48 1.98 2.94 3.47 3.37 3.02
    s1494 8 19 48 2.03 3.60 3.63 3.22 3.53
    dlxm 19 38 51 3.33 4.01 5.16 $\star$ $\star$
    sync 19 7 52 0.87 1.57 1.51 1.42 2.40
    ramtest 16 24 72 1.12 2.74 3.03 3.01 3.27
    scf 27 56 121 2.74 5.15 4.58 6.05 7.01
    6800 23 58 125 32.16 44.33 35.53 $\star$ $\star$
    s298 3 6 218 12.49 29.54 57.31 $\dagger$ 37.46
    % 61% 11% 7% 10% 11%


    Délais

    Il n'est pas rare que le chemin critique d'une machine soit dans un de ses automates, et néanmoins aucun des articles qui proposent des algorithmes ne présente des comparaisons en délais. Pourtant, elles sont édifiantes, comme on peut le constater dans le tableau 4.

    Là encore le one-hot est brillant. En pratique, le nombre de prédecesseurs d'un état n'est jamais très grand, (sauf les cas de reset, mais alors la $t_{i\rightarrow\ reset}$ est triviale), ce qui fait que l'équation (4) est une somme sur peu de registres, et est calculée très rapidement. A contrario, les techniques qui cherchent à factoriser vont produire des arbres qui vont être long à évaluer.
     
     

    Table 4: Chemin critique en pico-secondes après extraction de la vue physique en transistor.
    Automate  entrées  sorties  états  one-hot Asp  Mustang  Jedi  Nova
    dk15 3 5 4 7897 9171 9679 8456 7822
    lion 2 1 4 5426 6319 7088 7175 5456
    mc 3 5 4 4744 7688 5308 5869 6144
    train4 2 1 4 5406 4822 4810 5138 5721
    s8 4 1 5 7444 7999 11938 9764 8650
    bbtas 2 2 6 5295 5636 6164 5663 7066
    s27 4 1 6 8160 6466 7350 6486 8442
    beecount 3 4 7 9573 12404 8430 9829 10638
    dk14 3 5 7 9687 11403 12525 12564 10522
    dk27 1 2 7 4243 6023 6225 5768 6897
    dk17 2 3 8 7371 9662 10982 10288 9912
    ex6 5 8 8 12331 13644 12686 12097 14175
    shiftreg 1 1 8 3917 6128 6564 3434 5270
    ex5 2 2 9 6323 12176 11760 10637 10808
    lion9 2 1 9 5516 9806 11550 9692 10649
    bbara 4 2 10 9594 8419 11200 12576 9651
    ex3 2 2 10 7023 14094 11804 10673 12922
    ex7 2 2 10 6868 12038 11241 11744 11974
    opus 5 6 10 8335 10930 12109 9752 14486
    r3auto 12 7 10 9229 11305 10803 $\star$ $\star$
    r3ioc 17 12 11 10149 11174 14071 $\star$ $\star$
    train11 2 1 11 6636 12145 12186 12067 11392
    modulo12 1 1 12 3907 6578 7856 9754 8028
    s386 7 7 13 9155 12520 15672 12401 15281
    ex4 6 9 14 5687 10867 10586 9471 10578
    dk512 1 3 15 5146 10351 10931 9998 9748
    mark1 5 16 15 8432 9798 10438 10537 10429
    bbsse 7 7 16 9927 14054 13473 13532 12930
    cse 7 7 16 11661 16719 16130 15811 14913
    kirkman 12 6 16 13699 12844 17466 12619 10433
    sse 7 7 16 9981 12903 12816 13582 13799
    log 9 24 17 4985 11973 12507 13612 13969
    s208 11 2 18 11822 10077 13385 12717 9706
    s420 19 2 18 11904 10062 12757 12572 9944
    ex2 2 2 19 8352 14635 16311 12187 16067
    keyb 7 2 19 14438 15103 18631 16770 20326
    ex1 9 19 20 13289 20823 20281 18029 19549
    s1 8 6 20 12767 18833 21205 20660 21272
    s1a 8 6 20 11330 17635 17662 16600 17588
    tma 7 6 20 10202 17661 21473 19872 16309
    donfile 2 1 24 11544 16438 16910 12225 15628
    pma 8 8 24 12380 20155 22574 20650 24914
    fetch 9 15 25 4290 14332 11887 12633 14414
    s820 18 19 25 11550 22029 18476 18350 20025
    s832 18 19 25 11570 18575 18488 20364 18965
    dk16 2 3 27 8944 18648 19474 15148 16345
    nucpwr 13 27 29 4684 14290 14158 12838 16112
    rie 9 26 29 7212 16212 16186 14623 20211
    styr 9 10 30 14786 28521 24222 23745 25636
    sand 11 9 32 18987 22964 23597 23312 24823
    tbk 6 3 32 26300 40328 37689 24800 35625
    dvram 8 15 35 9449 14321 19149 17710 16750
    s510 19 7 47 19061 21666 18450 17166 22905
    planet 7 19 48 17684 26935 27819 25676 26801
    s1488 8 19 48 22255 22473 26291 26904 24210
    s1494 8 19 48 22914 25158 24302 27139 27048
    dlxm 19 38 51 20048 32706 31310 $\star$ $\star$
    sync 19 7 52 16923 21502 20381 20880 26354
    ramtest 16 24 72 10832 24042 28398 29253 29141
    scf 27 56 121 14646 32098 29917 35257 41527
    6800 23 58 125 79948 95897 132586 $\star$ $\star$
    s298 3 6 218 36270 94182 154772 $\dagger$ 119749
    % 80% 3% 3% 7% 7%

    Conclusion

    Dans ce travail, nous avons étudié systématiquement les algorithmes de codage d'automates présenté dans la littérature, en poussant l'expérimentation jusqu'au placement/routage et à l'extraction du chemin critique. Contre toute attente, l'approche la plus triviale est celle qui donne le meilleur résultat. Dès lors que $n \geq 10$, le codage one-hot donne quasiment toujours les meilleurs résultats en surface et en délais. Nous proposons que les études sur le codage des automates possédant un grand nombre d'états prennent comme référence non pas un codage aléatoire ou Mustang, mais le one-hot, et que les comparaisons soient faites en surface et en délais, et non en nombre de littéraux.
    Pourquoi faire simple quand on peut faire compliqué!

    Annexe

    Les réseaux booléens obtenus sont optimisés par l'outil logic. La projection structurelle est faite également par logic, et l'optimisation des temps en prenant en compte la bibliothèque cible par netoptim. La bibliothèque sclib est une bibliothèque de cellules précaractérisée pour une technologie 1.0 $\mu$m.

    Le placement et le routage sont fait à l'aide de scr. Cette phase nous fourni l'aire des différents circuits.

    Les interconnexions sont extraites au niveau des transistors par l'outil lynx, et l'analyse de performance effectuée par tas.

    Ces outils sont disponibles sur http://www-asim.lip6.fr

    About this document ...

    This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

    Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
    Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

    The translation was initiated by Ludovic JACOMME on 2000-04-17
     

    Ludovic JACOMME

    2000-04-17