WWW.BOOK.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Books, dissertations, abstract
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 29 |

«Von der Fakultät Informatik, Elektrotechnik und Informationstechnik der Universität Stuttgart zur Erlangung der Würde eines Doktors der ...»

-- [ Page 1 ] --

Boolean Reasoning for Digital Circuits

in Presence of Unknown Values

Application to Test Automation

Von der Fakultät Informatik, Elektrotechnik und Informationstechnik der

Universität Stuttgart zur Erlangung der Würde eines Doktors der

Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung

Vorgelegt von

Michael Andreas Kochte

aus Hoyerswerda, Deutschland

Hauptberichter: Prof. Dr. rer. nat. habil. Hans-Joachim Wunderlich

Mitberichter: Prof. Xiaoqing Wen, Ph.D.

Tag der mündlichen Prüfung: 22. Mai 2014 Institut für Technische Informatik der Universität Stuttgart Contents Acknowledgements 1 Abbreviations and Notation 3

Abstract

5 Zusammenfassung 7 1 Introduction 9

1.1 Boolean Reasoning in Electronic Design Automation........... 9

1.2 Unknown Values and Pessimism of Logic Simulation........... 10

1.3 VLSI Circuit Testing.............................. 13

1.4 Handling of Unknown Values in Testing.................. 13

1.5 Impact of Pessimistic Boolean Reasoning.................. 15

1.6 Objectives and Contributions of this Work................. 15 2 Sources of Unknown Values 19

2.1 Undefined and Unknown Values....................... 19

2.2 Unknown or Unspecified Values in System and Design Models...... 20

2.3 Unknown Values in System Operation and Test.............. 22 3 Boolean and Pseudo-Boolean Algebras 25

3.1 Boolean Algebras and Functions....................... 25

3.2 Multi-Valued Boolean and Pseudo-Boolean Algebras............ 27 3.2.1 Three-, Four- and Nine-valued Algebras for Modeling and Simulation................................. 27 3.2.2 Multi-Valued Algebras for Hazard Timing Analysis......... 29 3.2.3 Logic Algebras for Fault Simulation and Test Generation..... 31 Contents 4 Representations of Logic Functions and Circuit Modeling 35

4.1 Representation of Logic Functions...................... 35 4.1.1 Representation as Formula...................... 35

–  –  –

It is my pleasure to thank everyone who supported me during the past years. I would like to thank Prof. Hans-Joachim Wunderlich for his professional supervision and for sharing interesting ideas in countless discussions. I would also like to thank Prof. Xiaoqing Wen for his unconditional support during my stay at the Kyushu Institute of Technology in Japan, and for accepting to be the second adviser of my thesis. Both Prof. Wunderlich and Prof. Wen have been extremely supportive during the finalization of the thesis when time was running short.

In addition, I am grateful to Prof. Bernd Becker, Prof. Seiji Kajihara, Prof. Sandip Kundu, and Prof. Kohei Miyase for critical and fruitful discussions all over the world.

I very much enjoyed the work with colleagues and students who were at some time involved in my activities in Stuttgart. Sorry, I cannot list everyone here, you are not forgotten! I’d like to acknowledge those with whom I spend a lot of time in cooperations or personally: Rafał Baranowski, Lars Bauer, Claus Braun, Melanie Elm, Stefan Holst, Michael Imhof, Chang Liu, Eric Schneider, Hongyan Zhang, and Christian Zöllin. A special appreciation for our great cooperation goes to Dominik Erb, Stefan Hillebrecht, and Matthias Sauer from the University of Freiburg. Dominik Erb and Christian Zöllin, thanks for your speedy and thorough proof-reading of this thesis!

A work like this is not possible without administrative and technical assistance: Thank you, Mirjam Breitling, Helmut Häfner, Lothar Hellmeier, and Wolfgang Moser!

A big thank-you also to Kazunari Enokimoto, Kohei Miyase, and Yuta Yamato for making my stay in Japan such an unforgettable experience.

Finally, I thank my parents for their enduring support and encouragement.

–  –  –

Abstract The exponential growth in digital VLSI design scale and complexity has been enabled by comprehensive adoption of design automation tools. In the digital domain, design automation from design entry over synthesis, validation, verification to test preparation is based on reasoning about logic functions and their manipulation.

Limited knowledge about the circuit behavior may require that nodes in the circuit are modeled as having an unknown value, for instance when using incompletely specified design models. Circuit nodes also need to be modeled as unknown if their values cannot be controlled during operation or test, or if their value during operation is not known at the time of modeling.

To reflect such unknown values in design automation tools, the algorithms typically employ logic algebras with a special symbol ’X’ denoting the unknown value. However, the reasoning about functions based on such algebras results in an overestimation of unknown values in the model, and an accurate or optimal solution cannot be found.

This pessimism in presence of unknown values causes additional costs at different stages of the design and test process and may even reduce product quality.





This work proposes novel, efficient approximate and accurate algorithms for the analysis of the behavior of digital circuits in presence of unknown values. Heuristics and formal Boolean reasoning techniques are combined to achieve short runtimes. The algorithms allow accurate logic and fault simulation as well as accurate automatic test pattern generation in presence of unknown values. The implications to the overhead and effectiveness of design-for-test structures are studied. The proposed algorithms are the first to completely overcome the pessimism of conventional algorithms found in today’s VLSI design automation tools also for larger circuits.

Experiments on benchmark and industrial circuits investigate the pessimism in conventional algorithms and show the increased accuracy achieved by the proposed algorithms. The results demonstrate the benefits of approximate and accurate reasoning in different applications in the VLSI design process, especially in the test automation domain.

Zusammenfassung Das exponentielle Wachstum der Entwurfskomplexität integrierter Schaltungen wird durch die durchgängige Verwendung von Werkzeugen zur Entwurfsautomatisierung ermöglicht. Für digitale Schaltungsanteile basiert die Entwurfsautomatisierung von der Eingabe über die Synthese, Validierung, Verifikation bis hin zur Testvorbereitung auf der Analyse und Manipulation von Logikfunktionen.

Ist das Schaltungsverhalten nur partiell bekannt, zum Beispiel bei Verwendung unvollständig spezifizierter Modelle, kann über die Werte gewisser Signale keine Aussage getroffen werden. Dies erfordert, dass im Schaltungsmodell entsprechende Signale mit unbekannten Werten modelliert werden. Ebenso müssen Werte von Signalen als unbekannt modelliert werden, wenn ihr Wert während des Betriebs oder der Testdurchführung nicht gesteuert werden kann und zum Zeitpunkt der Modellierung unbekannt ist.

Um diese unbekannten Werte in Entwurfswerkzeugen zu behandeln, verwenden die Algorithmen typischerweise Algebren, die unbekannte Werte mit einem gesonderten Symbol ’X’ darstellen. Allerdings führt die Auswertung und Analyse von Funktionen mit solchen Algebren zu einer Überschätzung von Signalen mit unbekannten Werten im Modell, so dass die exakte oder optimale Lösung im Anwendungsbereich nicht gefunden werden kann. Dieser Pessimismus bei Betrachtung von unbekannten Werten verursacht zusätzliche Kosten während des Entwurfs und des Testprozesses.

Im schlimmsten Fall kann sogar die Produktqualität darunter leiden.

In der vorliegenden Arbeit werden effiziente approximative und exakte Algorithmen für die Analyse des Verhaltens digitaler Schaltungen in Gegenwart von unbekannten Werten vorgestellt. Diese Algorithmen verbinden Heuristiken und unterschiedliche formale Analysetechniken, um niedrige Laufzeiten zu erreichen. Die entwickelten Algorithmen erlauben die exakte Logik- und Fehlersimulation, als auch die exakte Testmustererzeugung in Gegenwart von unbekannten Werten. Weiterhin werden die Folgen für den prüfgerechten Entwurf untersucht. Die vorgeschlagenen Algorithmen Zusammenfassung erlauben erstmals, den Pessimismus in vorherrschenden Algorithmen der Entwurfsautomatisierung vollständig auch für größere Schaltungen zu beseitigen.

Mittels Experimenten anhand von Benchmark- und industriellen Schaltungen wird der Pessimismus in aktuellen Algorithmen untersucht. Die Ergebnisse belegen die Vorteile einer exakten Schaltungsanalyse während des Entwurfs und insbesondere im Bereich der Testautomatisierung.

1 Introduction

The tremendous success of digital integrated circuits is based on the increase of integration scale and density over the past decades, as well as ubiquitous design support by electronic design automation (EDA) tools. EDA tools have been developed to overcome the design complexity gap, the test challenge, and the challenge of reliable design for low power circuits.

The core of most EDA algorithms at gate level is the reasoning about Boolean functions and their manipulation. In the majority of state-of-the-art algorithms, the reasoning about Boolean functions in presence of unknown values is pessimistic and overestimates the number of signals with unknown value. This results in inaccurate and non-optimal solutions with higher costs.

This chapter briefly introduces the reader to the importance of Boolean reasoning in EDA tools. The handling of unknown values in various application fields of EDA tools is also discussed. This motivates the development of novel algorithms to increase accuracy in presence of unknown values. Finally, the organization and contribution of this work are presented.

1.1 Boolean Reasoning in Electronic Design Automation

A large fraction of EDA algorithms requires the representation and manipulation of Boolean functions. Figure 1.1 outlines the design flow of a hardware module comprising the specification and design entry, logic synthesis and optimization, design-for-test integration, as well as physical synthesis. Validation, verification, debug and diagnosis span the whole design process and provide feedback to the single design steps to find and correct design errors as well as manufacturing issues as early as possible. During and after manufacturing, the individual chips are tested for defects. Thorough testIntroduction ing with a high coverage of potential defects is a crucial requirement, especially in safety-critical applications such as the aerospace or automotive industry.

–  –  –

Figure 1.1: Design and manufacturing flow of a hardware module; shaded steps benefit from Boolean reasoning with increased accuracy as proposed in this work.

In Figure 1.1, logic synthesis, validation, verification, debug and diagnosis techniques, as well as test generation fundamentally require algorithms to reason about Boolean functions and to manipulate them. In consequence, the accuracy of the reasoning algorithms critically determines the quality of the solution in the corresponding task.

This work focuses on increasing the accuracy of Boolean reasoning in presence of unknown values with immediate benefits for these design steps.

1.2 Unknown Values and Pessimism of Logic Simulation Unknown values (X-values) describe an unknown state of signals or sequential elements in a circuit or its model. Their value may be undetermined during the design

–  –  –

process, e.g. due to incompletely specified models, or unknown and principally indeterminable during operation.1 Figure 1.2 depicts the various sources of X-values in the design models and during operation and test.

Partial knowledge in the design process Partial knowledge during operation/test

–  –  –

Sources of unknown values to be considered in design analysis, optimization and test Figure 1.2: Origin of unknown values during the design process, operation and test.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 29 |


Similar works:

«Nanoimprint lithography as an alternative fabrication technique: towards applications in optics (Die Nanoprägelithographie als eine alternative Technologie im Hinblick auf die Herstellung von optischen Bauelementen) Im Fachbereich Elektrotechnik, Informationstechnik und Medientechnik der Bergischen Universität Wuppertal genehmigte Dissertation zur Erlangung des akademischen Grades eines Doktors der Ingenieurwissenschaften -Dr.-Ing.vorgelegt von Dipl-Ing. Sergiy Zankovych aus Nikolaev, Ukraine...»

«TECHNISCHE UNIVERSITÄT DRESDEN FAKULTÄT FORST-, GEOUND HYDROWISSENSCHAFTEN INSTITUT FÜR GEOGRAPHIE Diplomarbeit zur Erlangung des akademischen Grades Diplom-Geograph Bodenerosion als Funktion veränderter Landnutzungsstruktur – Modellierung der Entwicklung am Beispiel der Nationalparkregion Sächsische Schweiz vorgelegt von: Sebastian Wolf geboren am: 25.12.1978 in Dresden Betreuer: Prof. Dr. Dr. rer. nat. habil. Arno Kleber Institut für Geographie, Technische Universität Dresden Dr....»

«Das elektrische Betriebsverhalten eines PEMBrennstoffzellensystems DIPLOMARBEIT Institut für Elektrische Anlagen und Hochspannungstechnik Abteilung Elektrische Anlagen an der Technischen Universität Graz Leiter der Abteilung: Univ.-Prof. Dipl.-Ing. Dr.techn. Lothar Fickert Begutachter: Ao. Univ. Prof. Dipl.-Ing. Dr. techn. Manfred Sakulin Betreuung: Ass. Prof. Dipl.-Ing. Dr. techn. Herwig Renner Vorgelegt von: Christian Kitz Graz, im Dezember 2002 Danksagung Dieses Projekt wurde in einer...»

«Technische Universität Darmstadt Fachbereich Bauingenieurwesen Institut für Wasserbau und Wasserwirtschaft Fachgebiet Wasserbau Erstellung und Anwendung eines numerischen Simulationsmodells zur Berechnung der Dynamik einer hochkonzentrierten Suspension kohäsiven Feinsediments Diplomarbeit Autor: Marian Brenda Datum: 29. August 2011 Professor: Prof. Dr.-Ing. U. Zanke Betreuer: Dr.-Ing. A. Wurpts Erklärung zur Diplomarbeit gemäß §23, Abs. 7 APB Hiermit versichere ich, die vorliegende...»

«Amorphe Siliziumoxidschichten zur Oberflächenpassivierung und Kontaktierung von Heterostruktur-Solarzellen aus amorphem und kristallinem Silizium Von der Fakultät für Elektrotechnik und Informationstechnik der Rheinisch-Westfälischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Ingenieurwissenschaften genehmigte Dissertation vorgelegt von Diplomingenieur Florian Einsele aus Nürtingen Berichter: Universitätsprofessor Dr. rer. nat. habil. Uwe Rau...»

«Fakult¨t fur Informatik a¨ CSR-09-05 Considerations on Technical Sketch Generation from 3D Scanned Cultural Heritage Christian H¨rr · Elisabeth Lindinger · Guido Brunnett o September 2009 Chemnitzer Informatik-Berichte Considerations on Technical Sketch Generation from 3D Scanned Cultural Heritage Christian H¨rr1, Elisabeth Lindinger2, and Guido Brunnett1 o Chemnitz University of Technology, Germany {hoerr, brunnett}@cs.tu-chemnitz.de Archaeological Heritage Service of Saxony, Dresden,...»

«Components and Mechanisms in Diagnosis and Therapy of Hymenoptera Venom Allergy Dissertation zur Erlangung des Doktorgrades der Naturwissenschaften der Fakultät für Mathematik, Informatik und Naturwissenschaften der Universität Hamburg vorgelegt von Simon Blank aus Stade Hamburg 2009 i The experimental part of this work was performed from November 2005 until November 2009 in the group of Prof. Dr. Reinhard Bredehorst at the Department of Chemistry, Institute for Biochemistry and Molecular...»

«Kinderstimmen Eine methodologische Untersuchung zum multiperspektivischen Erfassen kindlichen Mediennutzungsverhaltens und Medienerlebens – Ein Beitrag zur frühkindlichen Medienbildungsforschung Dissertation zur Erlangung der Doktorwürde (Dr. phil.) durch den Promotionsausschuss der Technischen Universität Dortmund, Fakultät Kulturwissenschaften vorgelegt von Marion Weise, M.A. Betreuerin: Prof. Dr. Gudrun Marci-Boehncke Zweiter Gutachter: Prof. Dr. habil. Matthias Rath Eidesstattliche...»

«June 2014 Working with Embroidery Settings School is out and the summer months are here! Winter is behind us, and it’s time to relax, take vacations or picnic by the lake. Summer is a wonderful time to regroup from the long school year and put behind hectic schedules that may have limited time for creativity. The featured technique in this month’s issue of Embroidery Made Easy provides more insight into the capabilities of the Editing software. This month you’ll learn more about...»

«TECHNISCHE UNIVERSITÄT MÜNCHEN INSTITUT FÜR LUFTUND RAUMFAHRT Lehrstuhl für Flugantriebe Design and Experimental Study of Injection Systems in a Supersonic Combustion Chamber Sara Rocci Denis Vollständiger Abdruck der von der Fakultät für Maschinenwesen der Technischen Universität München zur Erlangung des akademischen Grades eines Doktor-Ingenieurs genehmigten Dissertation. Vorsitzender: Univ.-Prof. Dr. rer. nat. U. Walter Prüfer der Dissertation: 1. Univ.-Prof. Dr.-Ing. H.-P. Kau...»





 
<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.