WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



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

«Center for TECHNICAL Reliable REPORT Computing Diversity Techniques for Concurrent Error Detection Subhasish Mitra 00-7 Center for Reliable Computing ...»

-- [ Page 1 ] --

Center for TECHNICAL

Reliable

REPORT

Computing

Diversity Techniques for Concurrent Error Detection

Subhasish Mitra

00-7 Center for Reliable Computing

Gates Building 2A, Room 236

Computer Systems Laboratory

June 2000 Dept. of Electrical Engineering and Computer Science

Stanford University

Stanford, California 94305

Abstract:

This technical report contains the text of Subhasish Mitra’s PhD thesis “Diversity Techniques for Concurrent Error Detection.”

Funding:

This research was supported by the Advanced Research Projects Agency under Contract No. DABT63-97-C-0024.

Copyright © 2000 by Subhasish Mitra.

All rights reserved, including the right to reproduce this report, or portions thereof, in any form.

DIVERSITY TECHNIQUES FOR

CONCURRENT ERROR DETECTION

A DISSERTATION

SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING

AND THE COMMITTEE ON GRADUATE STUDIES

OF STANFORD UNIVERSITY

IN PARTIAL FULFILLMENT OF THE REQUIREMENTS

FOR THE DEGREE OF

DOCTOR OF PHILOSOPHY

By Subhasish Mitra May 2000 ii Copyright © by Subhasish Mitra 2000 All Rights Reserved iii I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.

_________________________________

Edward J. McCluskey (Principal Advisor) I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.

_________________________________

Giovanni De Micheli I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.

_________________________________

Bernard Widrow Approved for the University Committee on Graduate Studies _________________________________

–  –  –

Concurrent error detection (CED) techniques are widely used to ensure data integrity in digital systems. Data integrity guarantees that the system outputs are either correct or an error is indicated when incorrect outputs are produced. This dissertation presents the results of theoretical and simulation studies of various CED techniques. The CED schemes studied are based on diverse duplication, simple duplication of identical implementations, and error-detection techniques like parity checking. The study aimed at (1) a quantitative comparison of the effectiveness of different CED schemes, and (2) developing design techniques for efficient concurrent error detection.

A CED scheme based on diverse duplication compares the outputs of two different implementations of the same function and indicates an error when a mismatch occurs. The idea of such a CED technique is derived from the general concept of design diversity. The conventional notion of design diversity is qualitative and relies on independent generation of different implementations. In this dissertation, a metric to quantify design diversity is presented and used for analyzing CED schemes based on diverse duplication.

A comparative study of different CED schemes by means of simulation experiments and theoretical analysis concludes that, in the worst-case, diverse duplication provides significantly better data integrity against multiple failures compared to other CED schemes. This result is especially significant in the context of Common-Mode Failures (CMFs). CMFs undermine the data integrity of any system with CED and belong to a special class of multiple failures whose probability of occurrence can be as high as that of single failures.

New techniques and synthesis algorithms have been developed for the first time to efficiently design systems based on diverse duplication. New fault models for CMFs are proposed and the possible failure mechanisms for the modeled CMFs are analyzed. In addition, techniques for designing CED-based systems with guaranteed data integrity in the presence of modeled CMFs are described.

vi ACKNOWLEDGMENTS

I am deeply grateful to my advisor, Prof. Edward J. McCluskey, for his constant guidance, support, and encouragement throughout my years at Stanford. He modeled the qualities of an ideal teacher and an outstanding researcher that I aspire to emulate in my career. I would also like to thank Mrs. Lois Thornhill McCluskey.

I would like to thank Prof. Bruce Wooley, my associate advisor, Prof. Bernard Widrow, my committee chairman, for reading my dissertation, and Prof. Giovanni DeMicheli for many interesting discussions and also for agreeing to be the fourth member of my committee.

I would like to thank my colleagues (RATs) at the Center for Reliable Computing (CRC) for helpful discussions, and companionship through the years: Mehmet Apaydin, LaNae Avra, Jonathan Chang, Santiago Fernandez-Gomez, Vlad Friedman, Robert Huang, Rajesh Kamath, Chat Khunpitiluck, Moon-jung Kim, Wern-Yan Koe, James Li, Siyad Ma, Samy Makar, Rob Norwood, Nahmsuk Oh, Nirmal Saxena, Philip Shirvani, Rudy Tan, Nur Touba, Chao-wen Tseng, Sanjay Wattal, Yoonjin Yoon and Catherine Yu. Special thanks to Dr. Nirmal Saxena for his advice and guidance. I also thank Siegrid Munda for her administrative support. Thanks to my professors at Stanford and the CRC visitors Prof. Jacob Abraham, Prof. Bella Bose, Prof. Miroslaw Malek, Prof.





Mohammed Niamat and Prof. Dhiraj Pradhan for many interesting discussions.

I wish to thank my professors (especially, Prof. P. Bhattacharya, Prof. T. K. Dey, Prof. A. K. Majumdar, Prof. P. Pal Chaudhuri, Prof. D. Sarkar of Indian Institute of Technology, Kharagpur and Prof. D. Ghosh Dastidar and Prof. R. Dattagupta of Jadavpur University, Calcutta) and teachers in India. I would also wish to thank my friends for their support over the years that ranged from useful advice to frequent invitations over the weekends. Thanks to Prof. P. Banerjee and Dr. R. K. Roy for their support during the application process for my graduate studies in the United States.

I am very grateful to my parents for their continued love, support and encouragement. I dedicate this thesis to them. I also thank my relatives and familyfriends in India for their continuing encouragement and support.

My research work at Stanford was supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. DABT63-94-C-0045 and DABT63-97-C

–  –  –

Abstract

Acknowledgments

Table of Contents

List of Figures

List of Tables

Chapter 1: Introduction

1.1 Background

1.2 A Brief Background on Concurrent Error Detection

1.3 Concurrent Error detection and Diversity

1.4 Contributions

1.5 Outline

Chapter 2: A Design Diversity Metric and Analysis of Redundant Systems............ 11

2.1 D: A Design Diversity Metric

2.2 Reliability Analysis

2.3 Results Demonstrating the Effectiveness of Diversity

2.4 Conclusions

Chapter 3: Comparison of Various Concurrent Error Detection Techniques......... 19

3.1 Concurrent Error Detection

3.2 An Overview of Various Concurrent Error Detection Techniques

3.2.1 Concurrent Error Detection using Duplex Systems

3.2.2 Concurrent Error Detection through Parity Prediction

3.2.3 Concurrent Error Detection using Unidirectional Error Detecting Codes...... 22

3.3 Vulnerability to Multiple Failures and CMFs: Simulation Results

3.4 Conclusions

Chapter 4: Self-Testability of Duplex Systems

4.1 Self-Testability

viii

4.2 Identification of Non-Self-Testable Fault Pairs

4.3 Self-Testability Enhancement Using Test Points

4.3.1 Control Test Points

4.3.2 Observation Test Points

4.4 Simulation Results

4.5 Conclusions

Chapter 5: Combinational Logic Synthesis Techniques for Diversity

5.1 Problem Formulation

5.2 Two-level Logic Synthesis

5.3 Multi-level Logic Synthesis

5.3.1 Single-Cube Extraction

5.3.2 Double-Cube Extraction

5.3.3 Re-substitution

5.3.4 Elimination

5.3.5 Simplification

5.4 Conclusions

Chapter 6: Common-Mode Failure Models and Redundant System Design............ 44

6.1 Common-Mode Fault Models

6.2 Redundant System Design

6.2.1 Redundant Systems Protected Against IR-CMF-1

6.2.2 Redundant Systems Protected Against IR-CMF-2

6.3 Conclusions

Chapter 7: Concluding Remarks

Publications from this Dissertation

References

Appendix A: Common-Mode Failures in Redundant VLSI Systems: A Survey..........

(To appear in the IEEE Transactions on Reliability, 2000) Appendix B: A Design Diversity Metric and Analysis of Redundant Systems.............

(Technical Report, CRC-TR-99-4, Center for Reliable Computing, Stanford University:

http://crc.stanford.edu. An extended version of "A Design Diversity Metric and Reliability Analysis of Redundant Systems," Proceedings of International Test Conference, pp. 662-671, 1999) ix Appendix C: Which Concurrent Error Detection Scheme to Choose ?

(To appear in the Proceedings of International Test Conference, 2000) Appendix D: Fault Escapes In Duplex Systems (Technical Report, CRC TR-00-1, Center for Reliable Computing, Stanford University:

http://crc.stanford.edu. An extended version of "Fault Escapes in Duplex Systems," Proceedings of VLSI Test Symposium, pp. 453-458, 2000) Appendix E: Combinational Logic Synthesis For Diversity In Duplex Systems (To appear in the Proceedings of International Test Conference, 2000) Appendix F: Word-Voter: A New Voter Design For Triple Modular Redundant Systems (An extended version of "Word-Voter: A New Voter Design for Triple Modular Redundant Systems," Proceedings of VLSI Test Symposium, pp. 465-470, 2000) Appendix G: Design of Redundant Systems Protected Against Common-Mode Failures (Technical Report, CRC-TR-00-2, Center for Reliable Computing, Stanford University, 2000 http://crc.stanford.edu) x

LIST OF FIGURES

Figure 1.1.

General architecture of a concurrent error detection scheme

Figure 1.2.

A Duplex System for Concurrent Error Detection

Figure 2.1.

Example of diversity

Figure 2.2.

A discrete time model of the system

Figure 2.3.

Common-Mode failure affecting both modules of a duplex system............. 14 Figure 2.4. Data integrity of a duplex system against common-mode failures............... 15 Figure 2.5. Effect of diversity vs. time (for common-mode failures)

Figure 3.1.

General architecture of concurrent error detection………………………….20 Figure 3.2. A Duplex System

Figure 3.3.

A Concurrent Error Detection technique using a single parity bit................ 21 Figure 3.4. Multiple parity bits for concurrent error detection

Figure 3.5.

Concurrent Error Detection Using Berger Codes

Figure 3.6.

Concurrent error detection using Bose-Lin codes

Figure 3.7.

Venn diagram showing yi,j and zi,j

Figure 3.8.

Systems with CED

Figure 4.1.

Control Test Points

Figure 4.2.

Applications with testing phases

Figure 5.1.

Illustration of Single-Cube extraction

Figure 5.2.

Illustration of double-cube extraction

Figure 6.1.

Conventional TMR

Figure 6.2.

TMR implementation protected against IR-CMF-1

Figure 6.3.

The basic scheme for the second module in a duplex system

xi LIST OF TABLES

Table 2.1.

Simulation results

Table 3.1.

Comparison of area overhead of different CED schemes

Table 3.2.

Detection probability of erroneous outputs for different CED schemes........ 26 Table 3.3. Improvement of detection probability of incorrect outputs using diverse duplication over other schemes

Table 4.1.

Self-testing properties of duplex systems

Table 4.2.

Comparison of control and observation test points

Table 4.3.

Test points for 100% self-testability

Table 4.4.

Execution time using different techniques on Sun Ultra-Sparc-2.................. 36 Table 6.1 Truth tables (a) Network N (b) Network N1 (c) Network N2

Table 6.2.

An example logic function

Table 6.3.

Transformation T

Table 6.4.

Specification of N2

xii xiii

Chapter 1

Introduction



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


Similar works:

«College of DuPage DigitalCommons@C.O.D. Philosophy Scholarship Philosophy 10-1-2012 Dialectic and Dialogue in Plato: Revisiting the Image of Socrates-as-Teacher in the Hermeneutic Pursuit of Authentic Paideia James Magrini College of DuPage, magrini@cod.edu Follow this and additional works at: http://dc.cod.edu/philosophypub Part of the Education Commons, and the Philosophy Commons Recommended Citation Magrini, James, Dialectic and Dialogue in Plato: Revisiting the Image of Socrates-as-Teacher...»

«COUNTERING MURPHY’S LAW: THE USE OF ANTICIPATION AND IMPROVISATION VIA AN EPISODIC MEMORY IN SUPPORT OF INTELLIGENT ROBOT BEHAVIOR A Dissertation Presented to the Academic Faculty by Yoichiro Endo In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the School of Interactive Computing College of Computing Georgia Institute of Technology December 2008 Copyright © 2008 by Yoichiro Endo COUNTERING MURPHY’S LAW: THE USE OF ANTICIPATION AND IMPROVISATION VIA AN...»

«Creation from Gaza Three late fifth-century thinkers from Gaza defended Christian ideas about creation against arguments for the eternity of the world in contemporary Neoplatonism. This paper explores connections between Aeneas, Zacharias and Procopius and Neoplatonists including Proclus, Hierocles and Ammonius. It identifies relationships between the Gazan contributions and later sixth-century controversies, particularly Philoponus’ arguments, and suggests some implications for understanding...»

«STUDY OF RADIATIVE PROPERTIES OF THIN FILMS AND NEAR-FIELD RADIATION FOR THERMOPHOTOVOLTAIC APPLICATIONS A Dissertation Presented to The Academic Faculty by Jesse I. Watjen In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the George W. Woodruff School of Mechanical Engineering Georgia Institute of Technology May 2016 Copyright © Jesse I Watjen 2016 STUDY OF RADIATIVE PROPERTIES OF THIN FILMS AND NEAR-FIELD RADIATION FOR THERMOPHOTOVOLTAIC APPLICATIONS Approved...»

«Descartes' Evil Genius O. K. Bouwsma The Philosophical Review, Vol. 58, No. 2. (Mar., 1949), pp. 141-151.Stable URL: http://links.jstor.org/sici?sici=0031-8108%28194903%2958%3A2%3C141%3ADEG%3E2.0.CO%3B2-K The Philosophical Review is currently published by Cornell University. Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have...»

«Murderous Visions of Relativity In the Novels Das Parfum and Oceano mare Mattia Marino by BEYOND MOURNING Social rites attempt to fill in the bodily gaps left by death. The aesthetic rituals of the novels Das Parfum (1985) by Patrick Süskind and Oceano mare (1993) by Alessandro Baricco come to terms with death in representations of murder which convey a relativist conception of being as presence, based on creative and critical dissent from the social resentment revolving around the dualist...»

«Philosophy, the Handmaiden of Theology Albert Henrichs T that philosophy should serve as the handmaiden of HE MAXIM theology was frequently proclaimed by scholastic theologians in the Middle Ages. They expressed it in these terms: Philosophia theologiae ancilla. 1 Whether or not the subordination of philosophy to theology, which is implied in this formula, can be supported by reasonable argument will not be touched upon in this essay. It is the origin rather than the doctrinal aspect of this...»

«LANGUAGE OUTCOMES IN SCHOOL-AGED CHILDREN ADOPTED FROM EASTERN EUROPEAN ORPHANAGES by Susan D. Hough B.A. Pennsylvania State University, 1976 M.A. University of Pittsburgh, 1979 Submitted to the Graduate Faculty of Education in partial fulfillment of the requirements for the degree of Doctor of Philosophy University of Pittsburgh 2005 UNIVERSITY OF PITTSBURGH SCHOOL OF EDUCATION This dissertation was presented by Susan D. Hough It was defended on April 25, 2005 and approved by Dr. Naomi...»

«LINGUISTIC TRANSFER IN ANDEAN SPANISH: SYNTAX OR PRAGMATICS? BY ANTJE MUNTENDAM DISSERTATION Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Spanish in the Graduate College of the Urbana, Illinois University of Illinois at Urbana-Champaign, 2009 Urbana, Illinois Urbana, Illinois Doctoral Committee: Assistant Professor Karlos Arregui-Urbina, Chair Professor Rakesh Bhatt Professor Silvina Montrul Professor Pieter Muysken, Radboud University Nijmegen...»

«ABSTRACT Title of Dissertation: ON THE DEVELOPMENT OF POSTURAL STABILITY DURING INFANCY AS A PROCESS OF GROWTH AND ACTIVE, EXPLORATORY SENSORIMOTOR TUNING Jason S. Metcalfe, Doctor of Philosophy, 2007 Dissertation directed by: Professor Jane E. Clark, Ph.D. Department of Kinesiology The process by which humans stabilize bipedal stance represents a confluence of changes associated with musculoskeletal maturation and experience-based sensorimotor learning. While investigations have documented a...»

«UNIVERSITY OF CALIFORNIA Los Angeles High-Impedance Electromagnetic Surfaces A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Electrical Engineering by Daniel Frederic Sievenpiper The dissertation of Daniel Frederic Sievenpiper is approved. University of California, Los Angeles ii TABLE OF CONTENTS 1 Introduction 1.1 Electric Conductors 1.2 High Impedance Surfaces 2 Surface Waves 2.1 Dielectric Interfaces 2.2 Metal Surfaces 2.3...»

«A COLD OF THE HEART: JAPAN STRIVES TO NORMALIZE DEPRESSION by George Kendall Vickery BA, College of William and Mary, 1986 Submitted to the Graduate Faculty of Arts and Sciences in partial fulfillment of the requirements for the degree of Doctor of Philosophy University of Pittsburgh 2005 UNIVERSITY OF PITTSBURGH FACULTY OF ARTS AND SCIENCES This dissertation was presented by George Kendall Vickery It was defended on August 1, 2005 and approved by Dr. Joseph S. Alter Dr. Richard Scaglion Dr....»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

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.