=0 cellpadding=10 cellspacing=0 width=100%>Yahoo! is not affiliated with the authors of this page or responsible for its content.
A Design Methodology for Physical Design for Testability
A Design Methodology for Physical Design for
Testability
Salahuddin A. Almajdoub
Dissertation submitted to the faculty of the
Virginia Polytechnic Institute and State University
in partial fulllment of the requirements for the degree of
DOCTOR OF PHILOSOPHY
in
Electrical Engineering
APPROVED:
Scott F. Midki, Chairman
James R. Armstrong
Hanif D. Sherali
Aicha A. Elshabini-Riad
Joseph G. Tront
July, 1996
Blacksburg, Virginia
Keywords: Physical Design for Testability, Bridging Faults, I
DDQ
Testing
c 1996, Salahuddin A. Almajdoub A Design Methodology for Physical Design for Testability
Salahuddin A. Almajdoub
Committee Chairman: Scott F. Midki
The Bradly Department of Electrical Engineering
(ABSTRACT)
Physical design for testability (PDFT) is a strategy to design circuits in a way to avoid or reduce
realistic physical faults. The goal of this work is to dene and establish a specic methodology for
PDFT. The proposed design methodology includes techniques to reduce potential bridging faults
in complementary metal-oxide-semiconductor (CMOS) circuits. To compare faults, the design
process utilizes a new parameter called the fault index. The fault index for a particular fault is
the probability of occurrence of the fault divided by the testability of the fault. Faults with the
highest fault indices are considered the worst faults and are targeted by the PDFT design process
to eliminate them or reduce their probability of occurrence.
An implementation of the PDFT design process is constructed using several new tools in addition
to other o-the-shelf tools. The rst tool developed in this work is a testability measure tool for
bridging faults. Two other tools are developed to eliminate or reduce the probability of occurrence
of bridging faults with high fault indices. The row enhancer targets faults inside the logic elements
of the circuit, while the channel enhancer targets faults inside the routing part of the circuit.
To demonstrate the capabilities and test the eectiveness of the PDFT design process, this
work conducts an experiment which includes designing three CMOS circuits from the ISCAS 1985
benchmark circuits. Several layouts are generated for every circuit. Every layout, except the rst
one, utilizes information from the previous layout to minimize the probability of occurrence for
faults with high fault indices. Experimental results show that the PDFT design process successfully
achieves two goals of PDFT, providing layouts with fewer faults and minimizing the probability
of occurrence of hard-to-test faults. Improvement in the total fault index was about 40 percent in
some cases, while improvement in total critical area was about 30 percent in some cases. However,
virtually all the improvements came from using the row enhancer; the channel enhancer provided
only marginal improvements. ACKNOWLEDGEMENTS
All gratitude are due to Allah, God the Almighty, who created me, who guides me, who provides
me with sustenance and whenever I fall ill, it is He who heals me.
I wish to express my sincere thanks to Dr. Scott F. Midki, my advisor and committee chair-
man for his continuous support and assistance. Without his patience and cooperation throughout
this research, it would not have been possible to nish this project. I will always be grateful to
Dr. Midki who taught me to always look at the big picture.
I would also like to thank Dr. James R. Armstrong, Dr. Aicha A. Elshabini-Riad, Dr. Hanif D.
Sherali, and Dr. Joseph G. Tront for serving on my committee and for their help. Special thanks
go to Dr. Sherali for his help on the optimization theory. Dr. Dong S. Ha served in the original
committee before his sabbatical and provided several corrections to the dissertation proposal.
I am grateful to Dr. F. J. Ferguson and Alvin Jee on the west coast for providing me with latest
version of CARAFE and for their prompt answering my questions by email. Also I would like to
thank K. Kozminski for providing the ISCAS 1985 benchmark circuits layout.
I also would like to thank my colleagues Mike Montgomery, David Lee, Rhett Hudson who helped
me demystify the UNIX operating system, and Todd Flemming for his help on C++ programming.
I dedicate this work to my wife and my mother. I am in debt to their unlimited support and
patience throughout the course of this work.
Finally, I thank all my friends in Blacksburg and back home who supported me with their love,
care and prayers.
This work was supported in part by the University of Bahrain.
iii TABLE OF CONTENTS
1
Introduction
1
2
Background and Motivation
5
2.1
Bridging Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.1.1
Fault Models for CMOS Circuits . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.1.2
Modeling Bridging Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.3
Classication of Bridging Faults
. . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.4
Extraction of Bridging Faults . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.5
I
DDQ
Test Generation for Bridging Faults . . . . . . . . . . . . . . . . . . . . 11
2.2
Design for Testability
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1
Testability Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2
Gate-Level Design for Testability . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3
Physical Design for Testability . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3
Statement of the Problem
26
3.1
Research Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2
The Concept of Physical Design for Testability . . . . . . . . . . . . . . . . . . . . . 27
3.2.1
Denition of Physical Design for Testability . . . . . . . . . . . . . . . . . . . 27
3.2.2
Goals of Physical Design for Testability . . . . . . . . . . . . . . . . . . . . . 28
3.2.3
Proposed Design Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4
CAD Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3
Scope of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
iv CONTENTS
4
Methodology
35
4.1
Design Flow Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1
A Multiple-Layout Cell library . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2
Logic Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.3
Placement and Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.4
Layout Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.5
Row Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2
Experimental Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3
Expected Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5
Bridging Controllability
42
5.1
Extension of Controllability Measures to Bridging Faults . . . . . . . . . . . . . . . . 43
5.1.1
CAMELOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1.2
SCOAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.1.3
COP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2
Bridging Controllability and Bridging Fault Classes . . . . . . . . . . . . . . . . . . . 45
5.2.1
Gate-Level Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2.2
Switch-Level Faults
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.3
Procedure for Calculating Bridging Controllability . . . . . . . . . . . . . . . . . . . 52
5.4
BRICON: A Bridging Controllability Program
. . . . . . . . . . . . . . . . . . . . . 52
5.5
BRICON Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.6
Comparison with Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.7
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6
The Channel Enhancer
60
6.1
The Yoshimura and Kuh Net Merging Algorithm . . . . . . . . . . . . . . . . . . . . 61
6.2
Resolving Cyclic Conicts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.1
Cycle Breaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2.2
Calculation of u and d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2.3
Connecting the Split Net
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.2.4
Restrictions on p and q
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
v CONTENTS
6.2.5
Conict Resolution Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.3
Track Assignment
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3.1
Formulation of the Track Assignment Problem . . . . . . . . . . . . . . . . . 73
6.3.2
Track Assignment Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.3.3
Eect of Net Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.4
Via Shifting Post-processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.5
Results and