Path-Delay Fault Simulation and False Path Removal

Dr. Vishwani D. Agrawal
Bell Labs
Murray Hill, NJ 07974 USA
va@research.bell-labs.com

Singly-untestable paths in a digital circuit cannot be tested but can affect
the timing of the circuit.  We will define these as false paths.  Redesign
of a circuit to eliminate false paths allows reliable test and improved speed.
Some false paths are caused by redundant stuck-at faults.  Removal of those
stuck-at faults automatically eliminates such paths from the circuit.
There are other false paths that are not associated with any redundant
stuck-at fault.  All segments of such a false path are shared with other
testable paths.  We focus on the elimination of this type of false paths.
We first describe a non-enumerative path delay fault simulator using the
path status graph (PSG) data-structure.  The simulation algorithm relies on
path-counting and can efficiently deal with path complexity.  It is used as
a tool for false-path removal.  The simulator duplicates selected gates to
separate the detected and undetected path delay faults.  The expanded
circuit may contain new redundant stuck-at faults, corresponding to
undetected paths that are false.  This happens because the expanded circuit
has some new interconnects with only false paths passing through them,
and they become sites for new redundant stuck-at faults.  Removal of these
redundant faults eliminates false paths.  The reported results show that the
quality of the result may depend on the coverage of testable paths by
vectors that are simulated.  Results on several circuits will be discussed
to illustrate the benefits of improved circuit speed and high path-delay
testability, and the disadvantage of the overhead.  A correspondence between
the presented method and the critical false path elimination procedure of
Kuetzer, Malik and Saldanha is also explained.

This work was jointly done with M. A. Gharaybeh, Synopsys, M. L. Bushnell,
Rutgers University, and C. G. Parodi, Lucent Technologies.  The talk is
based on Gharaybeh's PhD dissertation at Rutgers and a recent paper in
the Journal of Electronic Testing: Theory and Applications, October 2000.
-----------

Vishwani D. Agrawal is a Distinguished Member of Technical Staff at Bell
Labs, Murray Hill, New Jersey, USA, and a Visiting Professor at Rutgers
University, New Brunswick, New Jersey, USA.  He received a BSc degree from
Allahabad University, Allahabad, India, in 1960, BE degree from University
of Roorkee, Roorkee, India, in 1964, ME degree from the Indian Institute of
Science, Bangalore, India, in 1966, and a PhD degree from the University of
Illinois at Urbana-Champaign in 1971.  In 1986, he was elected an IEEE Fellow
for his contributions to ``probabilistic testing of integrated circuits.''
In 1993, University of Illinois honored him with their Distinguished Alumnus
Award.  In 1998, he received the Harry H. Goode Award of the IEEE Computer
Society for ``innovative contributions to the field of electronic testing.''
He has published 250 papers and five books, and has received five best paper
awards.  His recent text-book, Essentials of Electronic Testing for Digital,
Memory and Mixed-Signal VLSI Circuits, co-authored with M. L. Bushnell has
been published in November 2000.  He holds thirteen U.S. patents.  He has
co-directed 12 PhD theses at major universities.  In 1991 he co-founded
the International Conference on VLSI Design.  He is a former editor-in-chief
(1985-87) of the IEEE Design & Test of Computers and the founding editor-in-
chief (since 1990) of the Journal of Electronic Testing: Theory and
Applications.  He was the program chair for the Fourth IEEE Asian Test
Symposium.  He serves on the ECE Alumni Board of the University of Illinois
and the ECE Advisory Board of the New Jersey Institute of Technology.