Synthesis and mapping on programmables devices and ASICs

• Main Author: Bosco, Gilles
• Other Authors: Institut d'Informatique et de Mathématiques Appliquées de Grenoble (IMAG), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique de Grenoble - INPG, Gabrièle Saucier
• Format: Doctoral or Postdoctoral Thesis
• Language: French
• Published: HAL CCSD 1996
• Subjects: Etude théorique; Synthèse circuit; Conception circuit; Circuit intégré; Réseau porte programmable; Circuit à la demande; Additionneur; Modélisation; Ordonnancement; Optimisation; Macrogénérateur; Hypergraphe; Algèbre Boole; Arbre décision; Arbre binaire; Conception assistée; Décomposition technologique; [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation; Orca
• Online Access: https://theses.hal.science/tel-00346210; https://theses.hal.science/tel-00346210/document; https://theses.hal.science/tel-00346210/file/Bosco.Gilles_1996_these.pdf

Cette thèse s'intéresse d'une part au problème de décomposition technologique orienté surface sur des réseaux programmables de type FPGAs (Field Programmable Gate Arrays) et d'autre part à la synthèse des macro-générateurs sur ASICs et plus précisément de la synthèse des additionneurs. La décomposition s'articule autour de deux axes essentiels: tout d'abord, il s'agit d'optimiser la taille de la représentation des fonctions booléennes. Les représentations de base choisies ici sont les ROBDDs (Reduced Ordered Binary Decision Diagrams) ainsi qu'une structure dérivée, les ITE (If Then Else). La deuxième étape concerne la décomposition proprement dite. Les technologies cibles sont ici des FPGAs à base de LUT-k (Look Up Table), en particulier les FPGAs XC5200 de Xilinx et Orca de AT&T. Les deux méthodes de décomposition technologique orienté surface proposées permettent une décomposition hétérogène en prenant en compte non pas une seule configuration mais un ensemble de configurations possibles de la cellule cible. La première méthode est fondée sur un parcours descendant et optimisé du ROBDD. La seconde méthode s'appuie sur une modélisation en recouvrement d'hypergraphe du problème de décomposition technologique. Dans les deux méthodes, le coût exact en terme de surface finale du circuit est pris en compte à chaque étape de la décomposition. L'étude menée dans la deuxième partie de la thèse sur la macro-génération conduit dans un premier temps à l'exploration de l'espace des solutions possibles puis à l'optimisation d'une solution sélectionnée par un algorithme de dérivation discrète. L'utilisation d'un filtre permet la restriction de l'espace des solutions à explorer et d'autre part guide le processus de dérivation en éliminant les solutions trivialement médiocres. La combinaison des processus d'exploration et de dérivations permet la génération de macros dont les caractéristiques physiques sont les plus proches possibles de celles fixées par un utilisateur potentiel. Ces méthodes ont été intégrées au sein d'un ...