ES102/PC3 : énoncé et corrigé

T B

Description

• mémoire
• cours magistral

Ecole Nationale Supérieure de Techniques Avancées ES102/PC3  T. Bernard — 30/09/2011 16:15 Page 1 sur 6 ES102/PC3 : énoncé et corrigé 1) Synthèse de portes CMOS élémentaires (~1h00) Il s'agit ici de dériver les portes NAND et NOR de leur représentation BDD. Cette technique de « synthèse » va s'avérer simple et directe, mais pas minimale en nombre de transistors.

• structure périodique
• appelée mapping en anglais
• unique chemin
• bdd
• transistor
• montage
• cellules
• cellule
• portes
• porte
• chemin
• chemins
• travaux
• travail

Sujets

• Mémoire
• Cours magistral
• École nationale supérieure de techniques avancées
• Chemin
• Unique
• Transistor
• Cellule
• Anglais
• Publication périodique
• Travail
• Montage

Informations

• Publié par: nechir
• Nombre de lectures: 36
• Langue: Français

Extrait

 

 EcoleNationale Supérieure de Techniques Avancées

ES102/PC3 : énoncé et corrigé

1)Synthèse de portes CMOS élémentaires (~1h00) Il sagit ici de dériver les portes NAND et NOR de leur représentation BDD. Cette technique de  synthèse » va savérer simple et directe, mais pas minimale en nombre de transistors. 1a)Rappeler la structure en transistors MOS et le fonctionnement dun multiplexeur 2 vers 1. Cf. cours magistral CM3. 1b)Dessiner le BDD ordonné (variable a puis b) et réduit correspondant à la porte NAND(a,b). Voir la figure a ci-dessous. 1c)Remplacer un à un les MUX du BDD ci-dessus par leur implantation en transistors MOS, vue en cours. Puis supprimer les transistors inutiles du fait quun chemin ne véhiculant que du 0 (respectivement que du 1) peut être contrôlé par un unique transistor nMOS (respectivement pMOS), au lieu dune porte de transfert complète. Voir la figure (b) ci-dessous. Les transistors apparaissant en trait pointillé sont ceux qui peuvent être supprimés.

 1d)Partant du montage précédent, séparer les transistors n des transistors p, en mettant masse en bas, alimentation en haut, et la sortie à mi-niveau entre les deux. Cette transformation fait mieux ressortir comment sont réalisées les valeurs 0 et 1 de la fonction implantée. Voir la figure (cdf) ci-dessus. La transformation réalisée maintient les chemins entre sortie et masse, via des transistors n, et les chemins entre sortie et alimentation, via les transistors p. Il y a équivalence fonctionnelle entre les 2 montages (la sortie se comporte de la même manière) mais pas équivalence structurelle (le graphe d’interconnexion des transistors a changé). 1e)Dans le montage précédent, considérer chaque chemin reliant la sortie soit à la masse soit à lalimentation et létiqueter par lensemble des couples (a,b) pour lesquels ledit chemin est 2 passant. Utiliser la notation ensemblisteα β ={ (a,b)∈a=B /αb= etβ },α etβêtre pouvant égaux à 0, 1, ou  – » pour  indifférent ». Par exemple–1= { (0,1) , (1,1) }. Pour information, 2 cesα βsont les  sous-cubes » de B , notion présentée en CM4, analogue à celle de sous-espace n affine de Bvu comme espace vectoriel. Voir la figure (cdf) ci-dessus. 2 1f)Vérifier que le jeu densembles obtenu ci-dessus constitue une partition de B. Que signifie cette propriété quant à la réalisation de la fonction souhaitée, et doù provient-elle ?

 ES102/PC3T. Bernard 30/09/2011 16:15

Page 1 sur 6

 

 EcoleNationale Supérieure de Techniques Avancées

2 Les ensembles 11, 0– et 10 constituent effectivement une partition de B. Cela signifie que quelles que soient les valeurs prises par les entrées, il existe un et un seul chemin vers masse ou alimentation qui soit passant. Cette propriété provient de la structure même des BDD : quand on part du sommet du BDD (qui correspond à la sortie), les MUX définissent un unique chemin vers l’une des feuilles (chacune correspond à la masse ou l’alimentation). L’existence d’un chemin passant pour chaque configuration des variables d’entrée garantit que la sortie n’est jamais en l’air (état de haute impédance). L’unicité assure quant à elle que la sortie n’est jamais connectée à la fois à la masse et à l’alimentation. Mais, comme la question suivante va le montrer, c’est une propriété trop forte car elle est incompatible avec la minimisation du nombre de transistors nécessaires pour réaliser la porte souhaitée. 1g)A chaque ensemble déterminé ci-dessus, associer sa fonction caractéristique. Cest une fonction booléenne que lon appelle état passant» du chemin considéré. Quel lien doit-il y avoir entre ces états passants et la fonction réalisée ? Vérifier concrètement ce lien. Voir la figure (cdf) ci-dessus. C’est par connexion à l’alimentation que le montage réalise les 1 de la fonction implantée. Celle-ci doit donc être égale au OU des états passants des chemins liant sortie et alimentation. On vérifie en effet que a’+ab’ =(a’+a’b’)+ab’ =a’+(a’b’+ab’) = a’+b’=(ab)’, en enchaînant absorption, associativité, distributivité, puis loi de DeMorgan. D’autre part, c’est par connexion à la masse que le montage réalise les 0 de la fonction. Celle-ci doit donc aussi être égale au complémentaire du OUdes états passants des chemins liant sortie et masse, ce que l’on vérifie trivialement. 1h)Dans le dernier montage obtenu pour la porte NAND, il est possible de supprimer un transistor. Lequel ? Quelles sont les conséquences sur les états passants et leurs supports ? En prenant la question précédente à l’envers, on constate que pour réaliser les 1 de la fonction (ab)’= a’+b’, il suffit de deux chemins liant sortie et alimentation, l’un d’état passant a’, l’autre d’état passant b’, ce qui correspond à la figure (g) ci-dessus. Les nouveaux états passants sont donc ab, a’b et’, dont les supports sont 11, 0– et –0. Ces ensembles ne 2 constituent plus une partition de B , mais uniquement un recouvrement (intersection 2 à 2 pas toujours vide). Ainsi, il n’y a plus forcément un chemin unique reliant la sortie à la masse ou à l’alimentation. Sur le montage de la figure (g), il y a 2 chemins passants entre sortie et alimentation lorsque a=b=0. Cela ne fait aucune différence fonctionnelle: on dit que c’est un montagesémantiquement équivalent.En revanche, d’un point de vuestructurel, on a économisé un transistor. On note aussi que, du côté des transistors pMOS, le montage reflète désormais la symétrie intrinsèque de l’opérateur NAND. En imposant le choix d’un ordre sur les variables, l’approche BDD avait rompu cette symétrie. 1i)Quel montage pour une porte NAND3 (NAND à 3 entrées) ? Et pour une NANDn ? Il suffit de mettre n transistors en série ou en parallèle là où il n’y en avait que 2. 1j)Reprendre les questions précédentes pour porte NOR (à sauter sil est plus de 11h).

 ES102/PC3 30/09/2011 16:15T. Bernard

Page 2 sur 6



 

 EcoleNationale Supérieure de Techniques Avancées

2)Addition sur GA (~0h45) Les structures périodiques sont assez fréquentes sur circuit intégré. On en trouve notamment de type linéaire (1D) au sein des unités arithmétiques utilisées pour les calculs sur les nombres. Il en existe aussi de type matriciel (2-D) tels les bancs mémoire, ainsi que lesmatrices de portes appeléesGate Arraysanglais. Ces enGA sontde structure périodique. Ici le motif périodique, appelécellule, sera réduit à une porte élémentaire : ce sera dabord un multiplexeur 2 vers 1, puis une porte NAND. Par leur universalité, ces portes vont permettre la réalisation de fonctions booléennes f arbitraires en connectant judicieusement plusieurs cellules entre elles. Pour cela, il faudra procéder en 3 phases : • exprimer f sous la forme dun schéma nutilisant que le type de porte disponible dans le GA. Cette phase est appeléemappingen anglais. Un nombre plus ou moins grand de portes, donc de cellules, sera nécessaire, selon la complexité de f. •placerf, cest-à-dire choisir sur le GA quelles cellules – parmi toutes celles présentes dans la matrice – vont servir à limplantation de f. •routerf, cest-à-dire interconnecter entre elles les entrées/sorties des cellules retenues par le placeur selon le schéma défini à létape 1. Le routage est dautant plus court et simple que les cellules retenues sont voisines et judicieusement placées les unes par rapport aux autres. Physiquement, le routage consiste à mettre en place des connexions par fils métalliques circulant au-dessus de la matrice de portes. En fait, les phases 2 et 3 sont très interdépendantes et donc traitées ensemble au sein de ce que lon appelle lopération deplacement-routage. La dernière question de lexercice en fournira un exemple. 2a)On sintéresse dabord à limplantation dun Full Adder sur un GA dont la cellule périodique est constituée dun simple multiplexeur. Quest-ce que lemappingdans ces conditions ? Les deux sorties d’un FA sont les fonctions s et cout des variables a, b et cin.Mapper ces fonctions sur des MUX revient simplement à les exprimer sous forme de BDD. 2b)Partant dun arbre binaire de MUX à trois étages (cin côtéracine,b côtéfeuilles), connecter chaque feuille à la masse ou à lalimentation pour obtenir la retenue sortantecout. Simplifier.

 L’arbre obtenu apparaît en haut à gauche sur la figure ci-dessus. Le symbole rectangulaire contenant 0 et 1 représente un multiplexeur 2 vers 1 avec signal de commande sur le côté. Les multiplexeurs d’un même étage sont commandés par la même variable. Il s’agit du BDD brut de

 ES102/PC3 30/09/2011 16:15T. Bernard

Page 3 sur 6

 

 EcoleNationale Supérieure de Techniques Avancées

la fonction parité a⊕b⊕cin. Un tel BDD se réduit en 3 temps comme vu en cours. Le résultat obtenu représente de manière unique la fonction majorité, l’ordre des variables étant choisi.

2c)Exploiter maintenant la version BDD ( f(x,Y) = MUX[x,f(1,Y),f(0,Y)] ) du principe dexpansion de Boole pour établir les BDD correspondant à la retenue (fonction majorité) et à la somme (fonction parité): f(x,Y) = MUX[x,f(1,Y),f(0,Y)]. Arrêter chaque branche dès quapparaît une variable seule, la masse (0), ou lalimentation (1). En profiter au passage pour identifier la manière dont certains opérateurs booléens usuels sont implantés au moyen dun (ou deux) MUX.

 2d)A sauter sil reste moins de 15 mn avant la fin de la PC. Voici ci-contre un autre circuit à base de MUX qui implante un additionneur binaire complet. Vérifier son fonction- nement. Quel rapport y a-t-il avec les BDD ? On reconnaît les portes XOR implantées par MUX, à gauche et à droite, d’après la question précédente. Pour le MUX du centre, on vérifie que cout = MUX(a⊕b,cin,b) = a’bcin + ab’cin + ab, qui est une expression booléenne de la fonction majorité. Il s’agit donc bien d’un additionneur binaire complet. Il n’utilise que 5 MUX au lieu des 7 dont nous avions besoin dans la question précédente. Pour abaisser ainsi le coût, il y a une astuce: la variable de contrôle des 2 MUX situés en haut n’est pas une variable d’entrée, mais une fonction, en l’occurrence a⊕b. Ainsi, ce circuit sort du cadre strict des BDD. Il n’en est pas moins intéressant en vue de l’implantation sur la matrice de MUX. Pour information, ce circuit n’a pas été conçu par un être humain mais découvert par un ordinateur ayant brutalement passé en revue tous les montages possibles par ordre croissant du nombre de MUX. Deux implantations du FA avec seulement 5 MUX ont été trouvées au bout de plusieurs jours de calcul par une station de travail du milieu des années 90.  La figure ci-dessous montre une petite portion de FPGA à base de portes NAND, cest-à-dire une matrice périodique de portes NAND dont entrées et sorties peuvent être connectées arbitrairement (dans certaines limites) via à un réseau de communication associé. Les canaux de communication possibles apparaissent en trait fin. Physiquement, ce sont des pistes (fils) métalliques. Canaux horizontaux et canaux verticaux courent à des niveaux différents et ne se touchent donc pas quand ils se croisent. Les portions utilisées des canaux sont indiquées en trait gras. Les points noirs indiquent des  soudures » entre canaux horizontaux et verticaux. Ces soudures peuvent être réalisées au moyen de fusibles ou dantifusibles que lon fait griller ou claquer (technologie programmable une seule fois). La connexion électrique assurée par soudure peut aussi lêtre par des multiplexeurs pilotés logiciellement (technologie reprogrammable). On parle alors deFPGA, pourField Programmable Gate Arrays.

 ES102/PC3T. Bernard 30/09/2011 16:15

Page 4 sur 6

 

 EcoleNationale Supérieure de Techniques Avancées

 2e)mapping »,Un concepteur a déjà fait le travail de de placement et de routage de la cellule FA. Vérifier son travail et en commenter la qualité, notamment dans la perspective de limplantation dadditionneurs série. La vérification du mapping consiste à s’assurer que les portes NAND utilisées ont bien été connectées de manière à calculer les fonctions cout et s. Une méthode systématique, amorcée sur la figure ci-dessous, consiste à établir la fonction booléenne calculée par chaque porte.

  Mais c’est un peu fastidieux. Fort d’une analyse partielle du montage, on peut aussi tenter de se mettre à la place du concepteur et deviner sa démarche. Or un résultat important de la PC2 était justement une cellule FA optimisée en vitesse, avec la porte NAND privilégiée pour sa rapidité. Le schéma de cette cellule est rappelé ci-dessous à gauche et c’est effectivement lui qui a servi de point de départ au mapping.

 ES102/PC3T. Bernard 30/09/2011 16:15

Page 5 sur 6

 

 EcoleNationale Supérieure de Techniques Avancées

 Partant de ce montage, il a fallu implanter porte OR et porte XNOR avec des portes NAND, ce qui se fait facilement grâce aux lois de De Morgan (ou bien en jouant avec les bulles). En effet a+b = (a’b’)’(x et⊕y)’= xy+x’y’ =( (xy)’ (x’y’)’). Une porte XNOR s’implante finalement au moyen de 3 portes NAND en disposant des entrées complémentées, comme le montre la figure ci-dessus à droite. Par ailleurs, un inverseur est obtenu simplement en connectant entre elles les deux entrées d’une porte NAND. C’est en suivant ces principes que la cellule FA a été  mappée » en portes NAND. Revenant à la figure qui présente l’implantation sur le FPGA, des lettres apparaissent dans certaines portes NAND afin de pouvoir les désigner. On identifie désormais facilement les triplets RST et XYZ qui implantent chacun une porte XNOR. On les reconnaît grâce à leur entrées croisées complémentées: chacune des deux entrées va telle quelle vers une porte NAND et complémentée vers l’autre. Les deux portes U et V constituent la chaîne de propagation de la retenue au sein du FA, coeur du travail de la PC2. Les autres portes NAND sont utilisées en inverseur. Il reste à commenter le travail de placement-routage. La cellule  full adder » a été implantée de façon compacte (sans trou) au sein d’un rectangle de taille 6X2. Cette forme rectangulaire aplatie est bien adaptée à l’aboutement de plusieurs FA les uns aux dessus des autres afin d’implanter facilement un additionneur série. D’ailleurs, les retenues entrante et sortante sont déjà positionnées pour que cet aboutement se fasse naturellement. Le placement des cellules a été fait de manière à rendre le routage le plus court possible et, de fait, les connexions établies ne servent presque qu’à relier entre elles des portes NAND immédiatement voisines.  Il est à noter que les GA les plus en vue désormais sont justement les FPGA, où la matrice de portes est surmontée dun réseau de communication programmable logiciellement. Ce réseau permet détablir, dans certaines limites, toutes les liaisons souhaitées entre entrées et sorties de toutes les cellules. Ces composants font de lélectronique numérique une discipline informaticienne, vue de lutilisateur. Ils sont adaptés au prototypage dapplications, à la production en moyenne série, et aussi à la recherche en architecture et à lenseignement de ème lélectronique numérique, notamment en 3année à lENSTA. Le motif périodique, cest-à-dire la cellule, est bien plus complexe quune simple porte élémentaire. On y trouve typiquement une bascule D, élément de base de la logique séquentielle, des ressources combinatoires programmables permettant dobtenir nimporte quelle fonction booléenne de 4 voire 5 ou 6 variables, et des ressources de routage internes et externes bien plus sophistiquées que celles envisagées ci-dessus. La complexité dune telle cellule est de lordre du millier de transistors. Les plus gros FPGA offrent désormais plusieurs millions de cellules. 

 ES102/PC3 30/09/2011 16:15T. Bernard

Page 6 sur 6