NDLI: Satisfiability-Based Automatic Test Program Generation and Design for Testability for Microprocessors

Content Provider	IEEE Xplore Digital Library
Author	Lingappan, L. Jha, N.K.
Copyright Year	1993
Abstract	In this paper, we present a satisfiability (SAT)-based framework for automatically generating test programs that target gate-level stuck-at faults in microprocessors. The microarchitectural description of a processor is first translated into a unified register-transfer level (RTL) circuit description, called assignment decision diagram (ADD), for test analysis. Test generation involves extraction of justification/propagation paths in the unified circuit representation from an embedded module's input-output (I/O) ports to primary I/O ports, abstraction of RTL modules in the justification/propagation paths, and translation of these paths into Boolean clauses in conjunctive normal form (CNF). Additional clauses are added that capture precomputed test vectors/responses at the embedded module's I/O ports. An SAT solver is then invoked to find valid paths that justify the precomputed vectors to primary input ports and propagate the good/faulty responses to primary output ports. Since the ADD is derived directly from a microarchitectural description, the generated test sequences correspond to a test program. If a given SAT instance is not satisfiable, then Boolean implications (also known as the unsatisfiable segment) that are responsible for unsatisfiability are efficiently and accurately identified. We show that adding design for testability (DFT) elements is equivalent to modifying these clauses such that the unsatisfiable segment becomes satisfiable. Test generation at the RTL also imposes a large number of initial conditions that need to be satisfied for successful detection of targeted stuck-at faults. We demonstrate that application of the Boolean constraint propagation (BCP) engine in SAT solvers propagates these conditions leading to significant pruning of the sequential search space which in turn leads to a reduction in test generation time. Experimental results demonstrate an 11.1X speedup in test generation time for test generation at the RTL over a state-of-the-art gate-level sequential generator called MIX, at comparable fault coverages. An unsatisifiability-based DFT approach at the RTL improves this fault coverage to near 100% and incurs very low area overhead (3.1%). Unlike previous approaches that either generate a test program consisting of random instruction sequences or assume the existence of test program templates, the proposed approach constructs test programs in a deterministic fashion from the microarchitectural description of a processor
Sponsorship	IEEE Computer Society Association for Computing Machinery (ACM)/SIGDA IEEE Computer Society Technical Committee on Design Automation
Starting Page	518
Ending Page	530
Page Count	13
File Size	486981
File Format	PDF
ISSN	10638210
Volume Number	15
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-05-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Automatic testing Design for testability Microprocessors Circuit testing Circuit faults Microarchitecture Sequential analysis Fault detection Business continuity Engines test program microprocessor satisfiability test generation
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Automatic test pattern generation with branch testing

Autoscan: a scan design without external scan inputs or outputs

Testability Considerotions in Microprocessor-Based Design

Initialization-Based Test Pattern Generation for Asynchronous Circuits

Efficient Design for Testability Solution Based on Unsatisfiability for Register-Transfer Level Circuits

Combinational automatic test pattern generation for acyclic sequential circuits

An efficient algorithm for sequential circuit test generation

On generating tests that avoid the detection of redundant faults in synchronous sequential circuits with full scan

Instruction-Based Self-Testing of Delay Faults in Pipelined Processors

Satisfiability-Based Automatic Test Program Generation and Design for Testability for Microprocessors

Similar Documents

Automatic test pattern generation with branch testing

Autoscan: a scan design without external scan inputs or outputs

Testability Considerotions in Microprocessor-Based Design

Initialization-Based Test Pattern Generation for Asynchronous Circuits

Efficient Design for Testability Solution Based on Unsatisfiability for Register-Transfer Level Circuits

Combinational automatic test pattern generation for acyclic sequential circuits

An efficient algorithm for sequential circuit test generation

On generating tests that avoid the detection of redundant faults in synchronous sequential circuits with full scan

Instruction-Based Self-Testing of Delay Faults in Pipelined Processors

Satisfiability-Based Automatic Test Program Generation and Design for Testability for Microprocessors