Optimisation de chemins de données arithmétique

Définition du problème

Optimisation arithmétique dans le flot de conception VLSI

La Figure 4.1 présente le flot de conception VLSI. A partir d’une description haut niveau (i.e. description algorithmique), la phase de synthèse sert à obtenir une description bas niveau (i.e. une description structuelle en portes caractérisées d’une bibliothèque). Les phases de placement et routage servent à obtenir le dessin des masques. On connaît à ce stade la surface du circuit. Une extraction permet enfin d’obtenir une estimation de la chaîne critique. Différentes phases de vérification existent de façon à valider chaque étape.

Dans la Figure 4.2 est présentée en détail l’étape du flot qui nous intéresse plus particulièrement : la synthèse, telle qu’elle est décrite dans [Jac99]. Cette phase est découpée en trois étapes : synthèse haut-niveau, synthèse RTL et synthèse logique. La synthèse RTL est également découpée en trois étapes (symbolisées par des cadres en pointillés) : la compilation (passage d’une description comportementale synchrone en une série d’affectations concurrentes), l’optimisation (transformation des affectations concurrentes selon des critères) et la projection structurelle (passage d’une description en portes virtuelles à une description en portes caractérisées d’une bibliothèque).

Remarque

La synthèse RTL est différente pour la partie contrôle et la partie chemin de données d’un circuit. Nous ne nous intéressons dans cette thèse qu’à la synthèse de chemins de données et nous focalisons donc sur les affectations concurrentes combinatoires et arithmétiques avec registres. La Figure 4.2 permet également de voir à quel niveau se situe l’optimisation arithmétique : entre les phases de synthèse logique et de projection structurelle. L’optimisation arithmétique prend en entrée une description structurelle au niveau portes virtuelles qu’elle modifie.

Plus spécifiquement, elle prend une description structurelle hiérarchique de haut niveau, ce que nous appelons la description molle, car les opérateurs arithmétiques ne sont pas complètement spécifiés dans la façon de décrire le circuit. Elle fournit une description structurelle de bas niveau virtuelle i.e. description hiérarchique en portes logiques indépendantes de la technologie cible. Il y a donc une étape préliminaire à la projection structurelle consistant à faire la traduction entre la description structurelle de bas niveau virtuelle et la description structurelles en portes réelles qui sert de point d’entrée à la projection structurelle classique.

Approches choisies

Nous faisons ici un bref récapitulatif des différentes approches que nous avons traitées. Comme nous allons le voir, trois algorithmes ont été mis en place. Nous présentons également les différentes solutions possibles pour prendre en compte les soustractions, solutions qui ont effectivement été développées et comparées.

 Dans le but d’initialiser un chemin de données arithmétique en redondant dès que possible, la première approche qui nous a paru naturelle est d’encapsuler notre savoirfaire arithmétique dans des règles consistant à trouver des motifs dans le circuit et de les remplacer par d’autres afin de modifier sa structure. Typiquement, un motif est un regroupement d’opérateurs, et la règle est la façon de le remplacer par un autre motif utilisant l’arithmétique redondante, dans lequel les opérateurs ont donc de meilleures performances.

Algorithme de labellisation Dans un second temps, nous avons mis en place un algorithme dit de labellisation qui transforme systématiquement tous les signaux possibles en représentation redondante. De cette façon les opérateurs arithmétiques d’un circuit sont systématiquement transformés en leur équivalent redondant ou mixte. Cette approche est moins flexible que la précédente étant donnée qu’elle ne modifie pas la structure du circuit. Cependant, l’algorithme correspondant est théoriquement plus rapide à exécuter, ce qui est un point important. Allocation optimale L’initialisation en redondant dès que possible apporte un gain substantiel.

L’avantage d’une telle approche est d’avoir un outil rapide qui garantit la plus faible surface et une diminution de la chaîne longue. Cependant, cette approche n’apporte pas le chemin critique optimal, comme nous avons pu le voir dans la Section 1.1.1. Reprenons l’exemple présenté dans la Figure 4.3 : • la chaîne critique de la Figure 4.3.a contient deux additionneurs classiques et un multiplieur classique, • l’initialisation en redondant dès que possible réduit cette chaîne critique à un multiplieur avec sortie redondante, un additionneur redondant et un additionneur classique, comme montré dans la Figure 4.3.b, • étant donné qu’un additionneur classique est plus rapide qu’un multiplieur avec sortie redondante, l’addition de E et F peut s’effectuer en parallèle avec la multiplication sans que cela ne détériore la chaîne critique. Ne pas transformer cet additionneur en redondant modifie l’additionneur redondant de la chaîne critique en un additionneur mixte, c’est pourquoi la chaîne est alors raccourcie, comme montré dans la Figure 4.3.c