The Use of Hierarchy in Test Generation, Fault Simulation, and Testability Analysis Algorithms
Rogers, William Arthur
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69389
Description
Title
The Use of Hierarchy in Test Generation, Fault Simulation, and Testability Analysis Algorithms
Author(s)
Rogers, William Arthur
Issue Date
1988
Doctoral Committee Chair(s)
Abraham, Jacob A.
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Abstract
In the discipline of digital circuit design two activities are extraordinarily compute-intensive: fault simulation and automatic test pattern generation. Historically, since design was done on a single level, simulators and other design tools evolved for single-level circuits. More recent design techniques have incorporated hierarchical methodologies, but the design tools have not followed by exploiting this hierarchy. This thesis extends prior work by incorporating the design hierarchy into a fault simulator and exploiting the hierarchy to achieve improved simulator performance. The hierarchical fault simulator developed in this work is named CHIEFS, which stands for concurrent hierarchical and extensible fault simulator. It is unique in that it stimulates directly from the hierarchical circuit description without flattening the circuit to a single level.
Hierarchy-based fault partitioning techniques are shown to increase simulator performance by substituting high-level functional models for fault-free parts of the circuit, reducing the computation required to perform fault simulation. Examples show that this speedup can range from a factor of 2 for highly sequential circuits to a factor of 180 for large combinational circuits; greater speedup is expected in even larger circuits. A performance model is presented which shows that hierarchical concurrent fault simulation can run in O(n logn) time.
In contrast to CHIEFS, which uses the circuit hierarchy for partitioning, HAT, which stands for heuristic adviser for testability, uses the circuit design hierarchy as contextual information. The hierarchical context is used to refine the testability estimate predicted from a SCOAP-style testability estimator. This approach allows HAT to generate much more accurate testability predictions with little additional computation. HAT shows that the structural information used by many testability analysis tools is too localized and therefore prone to error. HAT also shows that higher-level information can be used to dramatically increase the accuracy of these testability measures.
A hierarchical test generation approach, named SHAMAN, is presented which promises to significantly reduce the computation requirements for test generation with mechanisms similar to those demonstrated for fault simulation in CHIEFS. This approach is based on using functional properties of high-level modules to permit hierarchical circuit reconfiguration and hierarchical test generation.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
