La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Détermination des bornes de l'activité de commutation des ...

303 pages
Université de Montréal
Détermination des bornes de
l’activité de commutation des
circuits logiques
par
Jindrich Zejda
Département d’Informatique et de Recherche Opérationnelle
Faculté des Arts et des Sciences
Thèse présentée à la Faculté des études supérieures
en vue de l’obtention du grade
de Philosophiæ Doctor (Ph. D.)
en Informatique
Mars, 1999
© Jindrich Zejda, 1999 University of Montreal
Bounding of Switching Activity in
Logic Circuits
by
Jindrich Zejda
Department of Computer Science and Operational Research
Faculty of Arts and Sciences
Thesis presented to the Faculty of Graduate Studies
in partial fulfillment of the requirements to obtain the grade
of Philosophiæ Doctor (Ph. D.)
in Computer Science
March, 1999
© Jindrich Zejda, 1999 Université de Montréal
Faculté des études supérieures
Cette thèse intitulée:
Détermination des bornes de
l’activité de commutation des
circuits logiques
présente par
Jindrich Zejda
a été évaluée par un jury composé des personnes suivantes:
El Mostapha Aboulhamid . . . . . . . . . président-rapporteur
Eduard Cerny . . . . . . . . . . . . . . . . . . directeur de recherche
Nicolas C. Rumin . . . . . . . . . . . . . . . co-directeur de recherche
Marc Feeley . . . . . . . . . . . . . . . . . . . membre du jury
John P. Hayes . . . . . . . . . . . . . . . . . . examinateur externe
Thèse acceptée le: Abstract
Electronic systems became an essential component of our lives. The demand for
increased functionality is satisfied by higher integration ...
Voir plus Voir moins
Université de Montréal Détermination des bornes de l’activité de commutation des circuits logiques par Jindrich Zejda Département d’Informatique et de Recherche Opérationnelle Faculté des Arts et des Sciences Thèse présentée à la Faculté des études supérieures en vue de l’obtention du grade de Philosophiæ Doctor (Ph. D.) en Informatique Mars, 1999 © Jindrich Zejda, 1999 University of Montreal Bounding of Switching Activity in Logic Circuits by Jindrich Zejda Department of Computer Science and Operational Research Faculty of Arts and Sciences Thesis presented to the Faculty of Graduate Studies in partial fulfillment of the requirements to obtain the grade of Philosophiæ Doctor (Ph. D.) in Computer Science March, 1999 © Jindrich Zejda, 1999 Université de Montréal Faculté des études supérieures Cette thèse intitulée: Détermination des bornes de l’activité de commutation des circuits logiques présente par Jindrich Zejda a été évaluée par un jury composé des personnes suivantes: El Mostapha Aboulhamid . . . . . . . . . président-rapporteur Eduard Cerny . . . . . . . . . . . . . . . . . . directeur de recherche Nicolas C. Rumin . . . . . . . . . . . . . . . co-directeur de recherche Marc Feeley . . . . . . . . . . . . . . . . . . . membre du jury John P. Hayes . . . . . . . . . . . . . . . . . . examinateur externe Thèse acceptée le: Abstract Electronic systems became an essential component of our lives. The demand for increased functionality is satisfied by higher integration which, however, make the design process more complex and introduces new problems. These problems must be considered in every step involved in the design of electronic systems. One of these steps is verification - checking, whether what is manufactured will work properly. Among several properties that must be verified, power consump- tion is becoming more important than ever before. In the most commonly used CMOS technology a considerable amount of power is consumed due to switching which is described by switching activity. Switching activity in its broad sense is a measure of topological and temporal distribution of signal transitions for given operating environment of the circuit. This thesis addresses the problem of estima- tion of switching activity. The thesis presents algorithms, implementation, and results of a new method based on constraint resolution for finding an upper bound on switching activity in the combinational part of a synchronous sequential circuit. The obtained switching activity is the major component for computing circuit power consumption (peak power) and several reliability parameters (e.g., voltage drops in power busses, electromigration). It is a static (input-pattern independent) method. The constraint system representing the circuit is built of constraints defined by gates and the oper- ating environment of the circuit. The variables of the constraint system are all pos- sible waveforms abstracted into four classes and expressed as sets of transitions for each unit of discrete time. The constraints of the constraint system are derived from the gates. Each gate is translated into a projection function which constrains each of its terminals based on the values on all other terminals independently of the netlist distinction between gate inputs and outputs. The method rapidly com- v putes an upper bound on the switching activity. The bound is further tightened by case analysis. The constraint system captures only local relations between nets and gates. Two major techniques were used to capture a global picture of the circuit and use this acquired information to speed up or improve the analysis. They are reconvergent region analysis and global learning. The method has two major applications: estimation of peak power and estimation of peak current. Both application were tested with our C++ implementation on ISCAS’85 benchmark circuits and the quality of the results for different heuristics was compared. The results show that each heuristic is more suitable for a different type of circuit. The method achieved values of about 1.5 to 3x, and 1.3 to 4x for the ratio of the upper and lower bounds of the switching and peak switching activ- ity, respectively. The method was also compared with exhaustive simulation on a 1set of MCNC circuits. The exact value of peak switching activity (peak current) was obtained for all tested MCNC circuits. The exact value of switching activity (power) was obtained on most of the tested MCNC circuits. The current implementation supports the fixed gate delay model and shares most of the code with a timing verification method based on constraint resolution. The performance is further improved by a parallel implementation of the case analysis on a network of inexpensive workstations. The parallel configuration consists of one master and many slaves. The master is responsible for maintaining the current state of the search space, dynamically deciding which parts must be searched, and distributing jobs to slaves. The scheduling algorithm is slave-failure safe and the master performs periodic state saving for recovery from its own eventual failure. Our C++ implementation shows speedup of 8 on a homogeneous network of 10 workstations, and 47 on a heterogeneous network of 87 workstations. 1. “Exact value” means that the lower bound from the simulation is equal to the upper bound (under the fixed delay gate model). Résumé Les systèmes électroniques sont devenus une partie essentielle de notre vie. On peut les trouver partout, que ce soit dans les systèmes de contrôle de feux d’inter- section, les systèmes de navigation pour avions et satellites, les systèmes de télé- communication ou les ordinateurs de haute performance. La réponse à la demande de nouvelle fonctionnalité et de plus grande performance nécessite une plus grande intégration. Cette grande intégration génère de nouveaux problèmes - qui ont pu être négligés jusqu’alors. Mais aujourd’hui on doit considérer tout ces problèmes dans chaque étape du processus de développement des systèmes électroniques. Une de ces étapes est la vérification - étape qui assure qu’une fois le produit est fabriqué, il fonctionne correctement. Parmi les propriétés que l’on doit vérifier, la consommation du courant devient plus importante que jamais. Pour la technologie la plus utilisée aujourd’hui - CMOS - la plus importante partie du courant est cau- sée par la commutation des signaux logiques qui est décrite par l’activité de com- mutation. L’activité de commutation est une mesure de distribution de transition temporelle et spatiale dans le circuit sous une condition d’environnement donnée. Cette thèse s’adresse au problème d’estimation de l’activité de commutation. La thèse présente les algorithmes, l’implémentation, et les résultats d’une nouvelle méthode pour trouver une borne supérieure d’activité de commutation dans la par- tie combinatoire d’un circuit synchrone séquentiel basée sur une résolution de con- traintes. L’activité de commutation est un composant majeur pour le calcul de consommation du courant d’alimentation du circuit, et pour plusieurs paramètres de fiabilité (par exemple chute de voltage dans des réseaux de distribution du cou- rant, ou electromigration). La méthode est statique, c’est à dire que son résultat est indépendant des vecteurs de test sur les entrées du circuit. ˙ ˙ ˙ ˙ ˙ ˙ ˙ ˙ vii L’idée de base de la méthode Ensemble de transitions Temps discret Temps i correspond à l’inter-L’ensemble de transitions est la suivante: Le circuit valle [r , r ) du temps réeldans la classe 00 dans i i + 1 l’intervalle numéro 2 électronique est considéré -1012348 comme un système de con- c00 c01Nœud du circuittrainte. Les portes logiques et Classes de c10 ondes c11l’environnent du circuit sont FIGURE 1: Onde abstraite représentés par des con- traintes. Les signaux du circuit sont représentés par les variables du système de contraintes. Toutes les ondes de signaux sur un nœud du circuit sont groupées en quatre classes et représentés par une ensemble de transitions pour chaque intervalle de temps (Figure 1). Les classes sont indépendantes - si une onde réelle est représentée par un sous-ensemble de classe, elle ne peut avoir aucune transition dans n’importe quelle autre classe. Cette propriété est utilisée dans l’analyse des cas décrit plus tard. Chaque porte logique intro- x gS 21 1 g S Circuit1duit des relations entre les 3 x g2 S2 3 ondes abstraites qui contraig- Le système nent tous ses terminaux. La de contraints -1-1 gAW gI 21 -1valeur de chaque nœud est g S =AW g (S ,S )2 1 I 1 2 3 S1 -1Sg S =AW g (S ,S )exprimée comme l’intersec- 3 2 I 1 1 31 S2 g S = g (S ,S )3 3 1 1 2tion de la valeur du nœud AW g -1 -1 -1 -1I 1 g g (...) g (...)3 2 3 courant et les fonctions de S variable opération dépendance portes, dans les deux direc- FIGURE 2: Le système de contraints tion - sorties à entrée, et entrée à sorties (Figure 2). Cette méthode permet de calculer rapidement une borne supérieure de l’activité de commutation. viii Dans la thèse, la méthode est 0 85illustrée par un petit circuit - 1 7c17. Si le circuit est une partie 2 6 combinatoire d’un circuit 3 10 4 9séquentiel, les entrées peuvent 0 -101234 8 -101234 c00 c00 c01 c01changer seulement par temps c10 1 -101234 5 -101234 7 -101234 c10 c11 c11c00 c00 c00 d’horloge (zero, observées les c01 c01 c01 2 -101234 c10 c10 c10 c00 c11 c11 c11ondes sur nœuds 0 jusqu’à 4 c01 c10 3 -101234 6 -101234 9 -101234 c11dans Figure 3). Les autres c00 c00 c00 4 -101234 c01 c01 c01 10 -101234 c10 c10 c10c00 c00ondes sont le résultat de propa- c01 c11 c11 c11 c01 c10 c10 c11 c11gation de ces contraintes FIGURE 3: Circuit c17 - propagation nationale (Figure 3). Dans cet exemple toutes les portes ont un délai unité. Les ondes abstraites contiennent tout les ondes réelles possibles. Donc, l’activité de commutation (nombre de transitions pendant une période d’horloge) est cal- culée comme la somme de nombre de transitions, pour chaque onde abstraite. Dans le Figure 3 c’est 15. En utilisant la librairie physique cette valeur peut être convertie à la consommation de courant. Pour évaluer la fiabilité du cir- Nombre de Transitions cuit, il est important de cal- 4 3culer le courant maximal dans 2le réseau. Le courant maximal 1peut être calculé à partir du Temps 0profil d’activité de commuta- 0 10 20 30 40 50 FIGURE 4: Circuit c17 - profile d’activité de tion qui est obtenu en comp- commutation tant les transitions de toutes les ondes pendant chaque intervalle de temps individuellement (Figure 4). ix Ensuit, la borne supérieure est améliorée par une analyse de cas basée sur l’indépendance des classes d’ondes dans les ondes abstraites. Dans cet exemple, l’analyse de cas a déterminé que la borne supérieure est 14 transitions pour une période d’horloge. Le nombre de transitions maximale pour un intervalle du temps n’était pas amélioré: la valeur initiale est la valeur exact. Le système de contraintes exprime En avant: seulement la relation locale entre des A=0 B=0A B portes et nœuds du circuit. Deux autres En arrière: B=1 A=1 techniques ont été introduites pour uti- FIGURE 5: L’apprentissage sur valeurs liser plus d’information sur le circuit: Booléennes l’analyse de régions de reconvergence et l’apprentissage global (Figure 5). La méthode implémentée en C++ a été testée sur l’ensemble de circuits benchmark ISCAS’85 et l’efficacité de plusieurs heuris- tiques a été comparée. Les résultats ont démontrés que l’efficacité de chaque heu- ristique dépend de la topologie et de la fonctionnalité du circuit. La borne supérieure était de 1.5 à 3x la borne inférieure de l’activité de commutation (con- sommation) et 1.3 à 4x de l’activité de commutation maximale (courant maximal). D’autres propriétés de la méthode ont été testées sur les circuits MCNC et circuits ISCAS’85 avec délais de portes d’une librairie industrielle lsi_10k. Nous avons 1obtenu la valeur exacte sur la majorité des circuits. L’implémentation qui a été testée supporte des modèles de portes avec délais fixes et elle partage une grande partie du code avec une méthode de vérification tempo- relle basée sur la résolution de contraintes. La performance est ensuite améliorée par l’analyse de cas sur un réseau de stations de travail. La configuration parallèle est centralisée (étoile). La station au centre maintient l’espace de recherche, anal- yse, décide quelle parties sont intéressantes, et distribue les tâches aux autres (esclave). L’algorithme de répartition est résistant aux fautes sur les esclaves et la 1. “La valeur exacte” c’est à dire que la borne inférieurs obtenu par simulation est égale à la borne supérieure (sous les modèles de portes avec délais fixes). x station au centre préserve périodiquement son état sur un disque. Notre implémen- tation parallèle a démontré l’accélération d’un facteur 8 sur 10 stations de travail et 47 sur un réseau hétérogène de 87 stations.
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin