Arithmetic Built-in Self-Test for Embedded Systems Janusz Rajski Mentor Graphics Corporation, Wilsonville, Oregon Jerzy Tyszer Poznan University of Technology, Poland To join a Prentice Hall PTR Internet mailing list, point to: http://www.prenhall.com/mail_lists/ ISBN 0137564384, October 1997 Prentice Hall PTR Upper Saddle River, NJ 07458 Contents Preface vii 1 Built-in Self-Test 1 1.1 Introduction 1 1.2 Design for Testability 4 1.2.1 Controllability and Observability 4 1.2.2 Ad Hoc Techniques 6 1.2.3 Scan Designs 8 1.2.4 Boundary-Scan Architecture 12 1.2.5 Test Point Insertion 14 1.3 Generation of Test Vectors 17 1.3.1 Exhaustive Testing 17 1.3.2 Pseudo-Exhaustive Testing 17 1.3.3 Pseudo-Random Testing 19 1.3.4 Weighted Patterns 23 1.3.5 Reseeding of Linear Feedback Shift Registers 24 1.3.6 Diffraction 28 1.3.7 Pattern Mapping 30 1.3.8 Scan-Encoded Patterns 30 1.4 Compaction of Test Responses 32 1.4.1 Objectives and Requirements 32 1.4.2 Compaction Schemes 33 1.4.3 Error Models and Aliasing 35 1.5 BIST Schemes for Random Logic 38 1.5.1 Design Rules for BIST 38 1.5.2 Serial BIST Architectures 42 iv Contents 1.5.3 Parallel BIST Architectures 44 1.5.4 BIST controllers 47 1.5.5 Modular BIST 49 1.5.6 Automation of BIST 52 1.6 BIST for Memory Arrays 53 1.6.1 Schemes Based on Deterministic Tests 55 1.6.2 Pseudo-Random Testing 57 1.6.3 Transparent BIST 57 Generation of Test Vectors 61 2.1 Additive Generators of Exhaustive Patterns 61 2.1.1 Basic Notions 62 2.1.2 Optimal Generators for Single Size Subspaces 65 2.1.3 Operand Interleaving 70 2.1.4 The Best Generators for Subspaces Within a Range of Sizes 72 2.2 Other Generation Schemes 76 2.2.1 Emulation of LFSRs and CAs 76 2.2.2 Weighted Patterns . 77 2.2.3 Generators for Delay Testing 79 2.3 Two-Dimensional Generators 81 Test-Response Compaction 87 3.1 Binary Adders 88 3.2 l's Complement Adders 90 3.2.1 Steady State Analysis 90 3.2.2 Transient Behavior 93 3.2.3 Detection of Internal Faults 100 3.3 Rotate-Carry Adders 101 3.3.1 Fault-Free Operation . 102 3.3.2 Test-Response Compaction 104 3.3.3 The Compaction Quality 108 3.4 Cascaded Compaction Scheme 112 Fault Diagnosis 117 4.1 Analytical Model 117 4.2 Experimental Validation 121 4.3 The Quality of Diagnostic Resolution 122 4.4 Fault Diagnosis in Scan-Based Designs 126 Contents v 5 BIST of Data-Path Kernel 135 5.1 Testing of ALU 135 5.1.1 Generation of Test Vectors 137 5.1.2 Test Application Phase 137 5.1.3 Compaction of Test Responses 139 5.1.4 Experimental Validation 139 5.2 Testing of the MAC Unit 140 5.3 Testing of the Microcontroller 141 6 Fault Grading 147 6.1 Fault Simulation Framework 148 6.2 Functional Fault Simulation 150 6.2.1 Ripple-Carry Adder 152 6.2.2 Subtracter 153 6.2.3 Carry-Lookahead Adder 153 6.2.4 Arithmetic and Logic Unit 154 6.2.5 Multiplexor 154 6.2.6 Array Multiplier 154 6.2.7 Booth Multiplier 159 6.3 Experimental Results 163 6.3.1 Performance of Building Block Models 164 6.3.2 High-Level Synthesis Benchmark Circuits 165 6.3.3 Comparison with PROOFS 166 7 High-Level Synthesis 173 7.1 Implementation-Dependent Fault Grading 174 7.1.1 Ripple-Carry Adder 174 7.1.2 Carry-Lookahead Adder 174 7.1.3 Carry-Skip Adder 175 7.2 Synthesis Steps 176 7.3 Simulation Results 178 8 ABIST at Work 185 8.1 Testing of Random Logic 185 8.1.1 Pseudo-Random Testing 185 8.1.2 Deterministic Testing 187 8.2 Memory Testing 192 8.2.1 Test program 192 8.2.2 Memory Array Faults 194 8.2.3 Read and Write Logic Faults 194 8.2.4 Address Decoder Faults 195 8.2.5 Multiple Faults 195 vi Contents 8.3 Digital Integrators 196 8.3.1 Testing of the Unmodified Integrator 197 8.3.2 Modified Integrator 199 8.3.3 Register File-Based Integrator 203 8.4 Leaking Integrators 207 8.4.1 Unidirectional Faults 209 8.4.2 Bidirectional Faults 215 8.4.3 An Improved Compaction Scheme 218 9 Epilog 223 A Tables of Generators 227 B Assembly Language 245 Bibliography 249 Index 265 Preface The semiconductor industry, driven by ever-increasing demands for higher performance and reliability, as well as greater functionality and speeds, continuously introduces new higher density technologies and new integrated circuits. These circuits, like any other complex systems, not only have to meet the performance and functionality requirements, but they also have to be man- ufacturable. In particular, they have to be highly testable in order to meet extremely high and constantly growing quality requirements. The quality of testing is often defined as the number of faulty chips that pass the test for one million chips declared as good. Many microelectronics companies have already set their testing quality goals to less than 100 dpm (defects per million), and there is intensive ongoing research to lower this number to less than 10 dpm as targeted in the six sigma project pioneered by Motorola. Many integrated circuits are produced in large volume and very often operate at high speeds. Since their manufacturing yield strongly depends on the silicon area, and their performance is directly related to the delays on critical paths, it is essential that the testing strategy provides a high fault coverage without a significant area overhead and performance degradation in order to build reliable and competitive products. It is a well-known fact that the costs associated with detecting faults rise over thousands of times from the time the product is specified to the time the product is released to customers. This is why the most effective way to prevent costly prototyping turns is to consider testing issues as early in the design cycle as possible. Tremendous practical importance of this problem generated an immense amount of research in an attempt to develop testing schemes of the ultimate quality. The increasing complexity of VLSI circuits, in the absence of a corresponding increase in the number of input and output pins, has made structured design for testability (DFT) and built-in self-test (BIST) two of the most important concepts in testing that profoundly Vlll influenced the area in recent years [16]. Scan design is a good example of structured DFT where, in the test mode, all memory elements are connected in scan chains, through which the test vectors can be shifted in and out. This solution enhances the controllability and observability of the circuit, and, as far as testing of combinational stuck-at faults is concerned, the circuit can be treated as a combinational network. In BIST, the original circuit designed to perform the system function is ap­ pended with additional modules for generation of test patterns and compaction of test responses [16]. Thus, the BIST approach can be applied at all levels of testing, starting from wafer and device to system and field testing. It is widely accepted that appending these modules to the original circuit satisfies the high fault coverage requirement while reducing the dependence on expensive testing equipment. However, it is also agreed that this solution compromises a circuit's area and performance as it inevitably introduces either a hardware overhead or additional delays and increased latency. These delays may be excessive for high-speed circuits used in several new applications such as broadband packet switching, digital signal processing (DSP) for the asynchronous transfer mode (ATM), new generations of floating point processors, and others. Therefore, BIST schemes are evaluated thoroughly on the basis of the fault coverage they provide, area overhead they require, and the performance penalty they intro­ duce. A more detailed survey of existing DFT and BIST schemes is provided in Chapter 1. Further information can be found in [2], [6], [7], and [16]. With the cost of testing becoming a significant part of the cost of new mi­ croelectronics products, with inevitably upcoming challenges of new deep sub- micron technologies, with the increasing role of the hardware-software codesign, and last but not least, with ever-changing customer expectations, a demand for new solutions and tools appears to be relentless. In particular, an un­ questionable proliferation of high-performance data-path architectures clearly demonstrates how inadequate existing BIST schemes can be if they are to entail non-intrusive and at-speed testing and yet guarantee a portability of test pro­ cedures. Paradoxically, although the vastness of data-path architectures consist of powerful building blocks such as adders, multipliers, or arithmetic and logic units (ALUs) offering a very high computational potential, existing data-path BIST schemes are unfortunate examples of having sophisticated modules on the chip but remaining unable to translate this advantage into efficient nonintrusive testing schemes. The approach presented in Chapters 2 through 8 is fundamentally different from the solutions introduced so far. It uses several generic building blocks, which are already in the data path, as well as its very flexible and powerful con­ trol circuitry to generate patterns and compact test responses. This permits de­ sign of complex software-based, and thus very portable, BIST functions. These functions produce test vectors in the form of control signals, such as the type Preface IX of ALU operation, the addresses of registers, the input to shifters, etc., rather than data, as it is done in all other systems. In such an environment, the need for extra hardware is either entirely eliminated or drastically reduced, test vec­ tors can be easily distributed to different modules of the system, test responses can be collected in parallel, and there is virtually no performance degradation. Furthermore, the approach can be used for at-speed testing, thereby provid­ ing a capability to detect failures that may not be detected by conventional low-speed testing. These characteristics make this method an exceptionally at­ tractive testing scheme for a wide range of circuits including high performance DSP systems, microprocessors, and microcontrollers. In the following chapters we will discuss several new fundamental concepts and practical scenarios concerned with test generation, test application, and test-response compaction performed by means of building blocks of high perfor­ mance data paths. We will show that even the simplest modules provide a very high potential for the integration of their features into a new generation of effi­ cient and portable BIST schemes. As described techniques rest predominantly on arithmetic operations, these schemes will be jointly referred to as arithmetic built-in self-test (ABIST) methodology. We will demonstrate that the ABIST paradigm virtually eliminates a traditional dichotomy between the functional mode and the testing mode, as testing will be based on regular operations and with no interference into the circuit structure. It can be expected that it will create a next integration platform where off-line and on-line BIST schemes will be merged together. Chapter 2 introduces several test generation schemes that can be easily implemented in data paths based on adders, multipliers, and ALUs. These schemes may replace commonly used LFSR-based test-pattern generators, and consequently allow it to mimic several commonly used generation techniques. In particular, a new approach to generate pseudo-exhaustive test patterns by means of arithmetic operations is described. The resultant test patterns provide a complete state coverage on subspaces of contiguous bits. The Accumulator-Based Compaction (ABC) scheme for parallel compaction of test responses is the subject of Chapter 3. We will demonstrate that the ABC scheme offers a quality of compaction similar to that of the best compactors based on multiple input signature registers (MISRs) or cellular automata (CA) of the same size. The presented characteristics can be used to estimate the fault coverage drop for a given circuit under test (CUT) characterized by its detection profile. The impact of the compactor's internal faults on the compaction quality is also examined. Compaction schemes can be also used to perform fault diagnosis. Faults, especially single ones, can be easily identified by collecting signatures and com­ paring them with a dictionary of precomputed signatures. Chapter 4 examines the relationship between the size of the compactor, the size of the circuit which