Test Generation of Crosstalk Delay Faults in VLSI Circuits

S. Jayanthy · M. C. Bhuvaneswari

Test Generation of Crosstalk Delay Faults in VLSI Circuits

Test Generation of Crosstalk Delay Faults in VLSI Circuits

S. Jayanthy M. C. Bhuvaneswari •

Test Generation of Crosstalk Delay Faults in VLSI Circuits

123

S. Jayanthy Department of Electronics and Communication Engineering Sri Ramakrishna Engineering College Coimbatore, Tamil Nadu, India

M. C. Bhuvaneswari Department of Electrical and Electronics Engineering PSG College of Technology Coimbatore, Tamil Nadu, India

ISBN 978-981-13-2492-5 ISBN 978-981-13-2493-2 https://doi.org/10.1007/978-981-13-2493-2

(eBook)

Library of Congress Control Number: 2018954035 © Springer Science+Business Media Singapore 2019 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd. The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore

Preface

This book describes the various test generation algorithms for testing crosstalk delay faults in VLSI circuits. Testing is an essential part of any integrated circuit manufacturing system. The problem of test generation is NP-complete problems, and it is becoming more and more difficult as system-on-chip designs have approached the deep submicron era. In addition to the propagation delay, deep submicron technology (DSM) effects will create severe signal integrity problems. Timing-related defects and signal integrity problems are introduced by imperfect manufacturing process, process variations, electromigration, voltage drop in power lines, crosstalk noise, and crosstalk delay which will cause the chip to fail. Crosstalk delay and crosstalk noise are caused due to the increased coupling capacitance. As more number of transistors are integrated on a chip, there is an increase in their aspect ratio and a decrease in the spacing between the interconnects, and thus, the interconnect coupling capacitances become larger. This increases the ratio between the coupling capacitance and the total capacitance leading to an increase in capacitive coupling noise. Crosstalk will become the major contributor to the interconnect delay in the near future. It is impossible to estimate the timing faults due to crosstalk delay in the design stage due to process variations and manufacturing defects. Hence, there is a need for automatic test pattern generation (ATPG) algorithms that can generate test vectors for testing the chips for crosstalk delay faults to ensure quality. Crosstalk delay fault is induced in the circuit if the victim and aggressor lines have simultaneous transitions. Crosstalk is most frequently observed for long nets which may have multiple fanouts. Thus, a long net is capacitively coupled with multiple aggressors. Hence, test pattern generation algorithms need to generate test vectors to activate multiple aggressors coupled to a victim. This book provides an introduction to the various crosstalk effects and describes the deterministic and simulation-based methods for testing crosstalk delay faults.

v

vi

Preface

Organization of the Book The content of this book is divided into ten chapters. The first three chapters focus on the existing crosstalk delay models, test generation algorithms for delay faults, and crosstalk delay faults. The remaining chapters deal with the deterministic algorithms and simulation-based algorithms applied for testing crosstalk delay faults. The experimental results for the algorithms and analysis are given. Chapter 1 focuses on the current scenario in VLSI testing and provides an insight into the crosstalk effects. The existing crosstalk delay fault models are discussed. Chapter 2 discusses the delay fault testing in VLSI circuits. It describes various delay fault models and test application schemes for the delay fault testing. It gives a survey of existing test generation and simulation-based algorithms for testing the delay faults in combinational and sequential circuits. Chapter 3 discusses the existing test generation techniques for crosstalk delay faults. Both deterministic and simulation-based techniques are discussed. Chapter 4 describes the static timing analysis for the identification of crosstalk delay faults. It deals with efficient ATPG for crosstalk delay faults based on the modified PODEM and modified FAN. Experimental results for ISCAS’85 combinational circuits, enhanced scan version of ISCAS’89 sequential circuits, and ITC’ 99 benchmark circuits are presented. Chapter 5 focuses on the application of genetic algorithms for crosstalk delay fault testing. Test results for four crossover operators, namely one-point, two-point, uniform, and weight-based crossover operators, are reported for ISCAS’85 combinational circuits, several enhanced scan version of ISCAS’89 sequential circuits, and ITC’99 benchmark circuits. The results obtained are compared with the previous works. Chapter 6 describes a crosstalk delay fault test generation methodology using single-objective particle swarm optimization (PSO). The experimental results are presented and discussed. Chapter 7 deals with multiobjective genetic algorithms WSGA, NSGA-II, and NSGA-II with redundancy for test generation for crosstalk delay faults. The experimental results are presented and discussed. Chapter 8 gives an introduction to fuzzy delay model. The fuzzy delay model-based simulation algorithm for asynchronous circuits is presented. The simulation-based test generation results for random patterns are presented for SIS benchmark circuits. Chapter 9 explains a simulation-based method for test generation for crosstalk delay faults in asynchronous sequential circuits. GA-based ATPG, WSGA-based ATPG, and NSGA-II-based ATPG for crosstalk delay faults in asynchronous sequential circuits are presented. Experimental results for SIS benchmark circuits are reported. Chapter 10 deals with the overall summary of the research discussed in each of the chapters and the future research prospects of crosstalk delay fault testing. Coimbatore, India

S. Jayanthy M. C. Bhuvaneswari

Contents

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

1 1 2 4 5 8 10 13 13

. . . . . . . . . . . Model . ...... ...... ...... ......

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

15 15 16 16 17 19 19 20 21 22 24 25 25 29 34 34

Test Generation Algorithms for Crosstalk Faults . . . . . . . . . . . . . . 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Test Generation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 38

1

Introduction . . . . . . . . . . . . . . . . . . . . . . 1.1 Introduction . . . . . . . . . . . . . . . . . . 1.2 VLSI Design Flow . . . . . . . . . . . . . 1.3 VLSI Testing . . . . . . . . . . . . . . . . . 1.4 Test Challenges for Deep Submicron 1.5 Crosstalk Effects . . . . . . . . . . . . . . . 1.6 Crosstalk Fault Models . . . . . . . . . . 1.7 Conclusion . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

2

Delay Fault Testing of VLSI Circuits . . . . . . . . . . 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Delay Fault Models . . . . . . . . . . . . . . . . . . . 2.2.1 Transition Fault Model . . . . . . . . . . . . 2.2.2 Gate Delay Fault Model . . . . . . . . . . . 2.2.3 Line Delay Fault Model . . . . . . . . . . . 2.2.4 Path Delay Fault Model . . . . . . . . . . . 2.2.5 Segment Delay Fault Model . . . . . . . . 2.3 Test Application Schemes . . . . . . . . . . . . . . . 2.3.1 Standard Scan Circuits . . . . . . . . . . . . 2.3.2 For Non-Scan Circuits . . . . . . . . . . . . 2.4 Test Generation Methods for Path Delay Fault 2.4.1 Path Delay Fault Simulation . . . . . . . . 2.4.2 Test Generation for Path Delay Faults . 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

3

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . Technologies . ........... ........... ........... ........... . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

vii

viii

Contents

3.3

Test Generation for Crosstalk Pulses . . . . . . . . . . . . . . 3.3.1 Deterministic Algorithms . . . . . . . . . . . . . . . . . 3.3.2 Simulation-Based TG . . . . . . . . . . . . . . . . . . . . 3.4 Test Generation Techniques for Crosstalk Delay Faults . 3.4.1 Deterministic Algorithms . . . . . . . . . . . . . . . . . 3.4.2 Simulation-Based Test Generation . . . . . . . . . . . 3.5 Delay Testing of Asynchronous Sequential Circuits . . . 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

5

6

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

42 42 44 46 46 50 51 53 53

An Automatic Test Generation Method for Crosstalk Delay Faults Using Modified FAN Algorithm . . . . . . . . . . . . . . . . . 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Static Timing Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Identification of Target Crosstalk Faults . . . . . . . 4.3 Seven-Valued Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Procedure for Modified PODEM-Based Test Generation . 4.5 Procedure for Modified FAN-Based Test Generation . . . . 4.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

57 57 58 58 60 62 65 67 74 77

ATPG for Crosstalk Delay Faults using Single-Objective Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Test Generation Using GA . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Chromosome Encoding . . . . . . . . . . . . . . . . . . . 5.3.2 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Crossover Operators . . . . . . . . . . . . . . . . . . . . . . 5.4 Crosstalk Delay Fault Simulator . . . . . . . . . . . . . . . . . . 5.5 GA-Based Crosstalk Delay Test Generation Algorithm . . 5.5.1 Phase I: Pseudorandom Generation of Initial Test Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.2 Phase II: GA-Based Test Generation . . . . . . . . . . 5.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

79 79 80 82 82 83 83 85 86

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

87 87 88 96 96

ATPG for Crosstalk Delay Faults Using Particle Swarm Optimization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . 6.3 PSO Algorithm-Based Test Generation Algorithm . .

. . . .

. . . .

. . . .

. . . .

. 99 . 99 . 100 . 102

. . . .

. . . .

. . . .

Contents

ix

6.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7

8

9

ATPG for Crosstalk Delay Faults Using Multi-objective Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Weighted Sum-Based ATPG . . . . . . . . . . . . . . . . . . 7.3 Optimization Using NSGA-II . . . . . . . . . . . . . . . . . 7.3.1 Elitism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 Non-dominated Sorting . . . . . . . . . . . . . . . . 7.3.3 Crowding Strategy . . . . . . . . . . . . . . . . . . . . 7.4 NSGA-II-Based ATPG with Redundancy . . . . . . . . . 7.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Simulation of Asynchronous Sequential Circuits Using Fuzzy Delay Model for Crosstalk Delay Faults . . . . . . . . . . . . . . . . . 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Races, Oscillations, and Non-confluence . . . . . . . . . . . . . 8.3 Delay Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Types of Delay Models . . . . . . . . . . . . . . . . . . . . 8.4 Fuzzy Delay Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.1 Fuzzy Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.2 Logic Gate Model . . . . . . . . . . . . . . . . . . . . . . . . 8.4.3 Representation of Fuzzy Delay . . . . . . . . . . . . . . . 8.5 Discrete Event-Driven Logic Simulation Based on Fuzzy Delay Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5.1 Component State . . . . . . . . . . . . . . . . . . . . . . . . . 8.5.2 State Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5.3 Event . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5.4 Processing of Events . . . . . . . . . . . . . . . . . . . . . . 8.6 Crosstalk Delay Fault Simulation Algorithm . . . . . . . . . . . 8.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simulation Based Test Generation for Crosstalk Delay Faults in Asynchronous Sequential Circuits . . . . . . . . . . . . . . . . . . . . 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Feedback Identification . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Crosstalk Delay Fault Simulator for Asynchronous Sequential Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

109 109 110 112 112 113 113 115 117 123 123

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

125 125 126 127 127 129 130 130 131

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

131 132 132 133 134 135 137 138 138

. . . . 141 . . . . 141 . . . . 142 . . . . 142

x

Contents

9.4

GA-Based ATPG . . . . . . . . . . . . . . 9.4.1 Experimental Results . . . . . . 9.5 WSGA- and NSGA-II-Based ATPG 9.5.1 Experimental Results . . . . . . 9.6 Conclusion . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

143 143 145 146 150 150

10 Summary and Suggestions for Future Research 10.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Suggestions for Future Research . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

151 151 155 155

. . . . . .

. . . . . .

. . . . . .

. . . . . .

About the Authors

Dr. S. Jayanthy is Professor in the Department of Electronics and Communication Engineering, Sri Ramakrishna Engineering College, Coimbatore, India. She received her master’s and Ph.D. from PSG College of Technology, Coimbatore, and Anna University, Chennai, respectively. Her research interests are in VLSI design and testing, genetic algorithms, and embedded systems. With more than 20 years of teaching experience, she has published 2 chapters and more than 40 research papers in journals and national and international conferences and has organized a number of workshops and national conferences in the areas of VLSI, embedded systems, and IoT. She is a life member of Indian Society for Technical Education and Institution of Electronics and Telecommunication Engineers. Dr. M. C. Bhuvaneswari is Associate Professor in the Department of Electrical and Electronics Engineering, PSG College of Technology, Coimbatore, India. She received her B.E. in electronics and communications engineering from Madras University and her M.E. and Ph.D. from Bharathiar University. Her research interests include applied electronics, VLSI design and testing, genetic algorithms, digital system design, and microprocessors. She has published a book on VLSI and embedded systems (2015) and authored more than 90 research papers in journals and national and international conferences. She is a life member of Indian Society for Technical Education, Institute of Engineers (India), Computer Society of India, and Systems Society of India. She was honored with Dakshinamoorthy Award for Teaching Excellence instituted by PSG College of Technology in the year 2010.

xi

Chapter 1

Introduction

1.1 Introduction Rapid advances in integrated circuit (IC) technology have made it possible to fabricate digital circuits with large number of devices on a single chip. The advantages of integrated circuits are reduced system cost, better performance, and reliability. These advantages would be lost unless integrated circuit devices can be economically tested. Testing is one of the important fields, which validates the functionality of any manufacturing process. The testing process detects the physical defects produced during fabrication. The problem of test generation belongs to a class of NP-complete problems, and it is becoming more and more difficult as the complexity of IC increases. Scaling of process technologies could be limited if testability issues are not addressed adequately. This is because defect sizes have not reduced in proportion with shrinking geometries. The major factors that affect the functionality in deep submicron technologies (DSM) are process variations, manufacturing defects, and noise. Process variations can have a major affect on chip’s failure to meet the specified performance. Delay defects which are caused by interconnect defects and noise sources such as crosstalk, power supply noise, and substrate noise will result in chips failing to meet the timing specifications. In order to guarantee optimal performance of DSM chips, their functional correctness as well as timing behavior needs to be tested. Hence, current test and verification techniques need to be improved. More detailed fault models are required to model the behavior of faulty deep submicron chips. Therefore, efficient test techniques are needed to detect such defects and eliminate them before products are shipped (Datta et al. 2009).

© Springer Science+Business Media Singapore 2019 S. Jayanthy and M. C. Bhuvaneswari, Test Generation of Crosstalk Delay Faults in VLSI Circuits, https://doi.org/10.1007/978-981-13-2493-2_1

1

2

1 Introduction

1.2 VLSI Design Flow VLSI is a field which involves packing of millions of components on the same chip. Due to the significant improvements in the IC manufacturing, the capability of IC has increased in terms of computational power, utilization of available area, and yield. The design of such ICs has become a complicated and time-consuming process. Therefore, there is a necessity for the development of powerful design tools and software systems that help a VLSI design engineer to produce a fault-free IC chip. The various steps in IC design and manufacturing are shown in Fig. 1.1. A design specification is formulated based on a customer or project need. Specifications describe the functionality, interface, and overall architecture of the IC to be designed. This idea is casted into the model which captures the function that the circuit will perform. Design engineers create a behavioral-, logical-, or circuit-level model of the specification. Design typically starts at very high levels of abstraction using some high-level hardware description language (HDL) (Bhuvaneswari and Sivanandam 2001). Design verification is done to ensure that the design will perform the required functions when manufactured. A logical-level implementation is synthesized from the HDL specifications which should be verified to ensure that the final design meets timing, area, and power specifications. When design error is found, modifications are done and design verification is repeated. As a result, design verification is considered as a form of testing. The logical-level description is transformed into physical-level description to obtain the placement and interconnection of the transistors in the VLSI device. This physicallevel description is verified for timing and specified operating frequency specifications, and then, the design is fabricated. At the same time, test engineers develop a test procedure based on the design specification and fault models associated with the fabrication technology. The unavoidable statistical flaws in the materials and masks used to fabricate ICs result in defects during the fabrication process. Hence, the ICs fabricated on the wafer are tested for fabrication faults to determine which devices are defective. The chips that pass wafer-level test are extracted and packaged. The packaged devices are further tested for any damages in the packaging process. Finally, devices pass through final quality test before going to market. This includes measurement of input/output timing specifications, voltage, and current (Wang et al. 2006). Better electronic design automation (EDA) tools, advanced technology IC manufacturing, and design flow methodology are required for successful delivery of finished products. The EDA tools and design flow methodology are directly affected when there is a change in IC technology. The deep submicron IC manufacturing technology has had a direct influence on both the EDA tools and design flow methodology. As design moves from the architectural level to the physical representation or fabrication, the complexity of the design increases. There could be several iterations of each phase during the IC development to ensure quality and performance. During the various iterations, several computer-aided design (CAD) tools assist in translating the design into an IC. The CAD techniques have reached good level of maturity

1.2 VLSI Design Flow Fig. 1.1 Typical design flow of IC

3

Design

Architectural design

Functional verification and testing Logical design

Logical verification and testing Physical design

Physical layout verification Fabrication

Chip

in many areas. But as technology moves into nanometer age, in order to keep up with the Moore’s law, many new technologies and circuit design techniques must be devised and adopted. This may give rise to severe test challenges that must be solved concurrently. When the feature size becomes less than 100 nm, a small defect would result in a faulty transistor or an interconnection. But this one faulty transistor or interconnection is enough for improper functioning of the entire chip with respect to its operation or timing. But these small defects during the manufacturing process cannot be avoided, and it is required to test all the products whether it is a VLSI device or a system consisting of many VLSI devices. During manufacturing process, testing is done at various stages. Testing electronic devices includes testing at the various manufacturing stages that are during IC fabrication, during PCB

4

1 Introduction

layout, during system integration, and during system operation. Testing is used to find the fault-free devices during these stages. The source of defects is analyzed at the various stages of manufacturing to improve production yield. Periodic testing of systems is also performed to ensure that system operates as per requirements, and as and when faults are detected, corrective action is initiated. VLSI testing is important in all stages viz design, production, testing, manufacturing, and at field.

1.3 VLSI Testing Tests may fall into two main categories, the functionality test and manufacturing test. The functionality tests are usually done early in the design cycle to verify whether the IC performs its intended function. Manufacturing test involves development of test patterns to ensure ICs operate correctly before being delivered to customers. This is an important stage of IC development as it affects the quality of the product. In any manufacturing process, fabrication defects are invariably introduced. Common defects are shorts, opens, improper doping profiles, mask alignment errors, and poor encapsulation (Abramovici et al. 1990). The testing process detects the physical defects produced during fabrication of an integrated circuit chip. Testing of a die/chip can occur at the wafer level, packed chip level, board level, system level, or in the field. The cost of identifying a faulty component is lowest before it is packed (Hurst 1998). This cost increases as component becomes a part of a larger system. Due to the complexity of the IC manufacturing process, a number of defects might occur during fabrication and hence no process can guarantee 100% yield. If these test issues are not solved, in future the cost of testing a transistor might become more than the cost of designing the transistor. Therefore, testing is an important aspect of any integrated circuit manufacturing system. Testing is a process which validates the functionality of any manufacturing process. Testing a product after manufacturing is essential to reduce the risk of shipping a defective product and is a process where circuit inputs are exercised using certain patterns and the resulting response is compared to the golden response to eliminate the defective parts. Automatic test generation refers to the test generation algorithms that, given a model of the system, can generate tests for it. Covering all the faults would be very difficult and would require an inordinate number of test vectors. Therefore, automatic test generation tools operate on an abstract representation of defects referred as faults and model a subset of potential faults. The faults in digital circuit are referred as logic or parametric faults. A logic fault causes the logic function of the circuit, on an output signal to be changed to some incorrect function. Parametric faults are the faults, which alter the magnitude of the circuit parameters causing changes in speed of operation or the levels of voltages and currents. The effects of manufacturing defects are represented at the logic level using a fault model. Fault models can describe the faults at different abstraction levels. The common abstraction level is the gate level. Most fault models assume that the circuit contains only a single fault, as the number of potential multiple fault combinations

1.3 VLSI Testing

5

is so large that test generation becomes infeasible. The widely used gate-level fault model for digital circuits is the single stuck-at fault model. This model assumes that any physical defect in a digital circuit results in a node in the circuit being fixed either at logic 0 or at logic 1 and appropriately called stuck-at-0 and stuck-at-1, respectively. It can be considered as a direct connection between a node and power (stuck-at-1) or ground (stuck-at-0). These faults occur most frequently in complementary metal oxide semiconductor (CMOS) process technology due to thin oxide shorts, that is, in a n-transistor gate may be shorted to V ss and in the p-transistor gate may be shorted to V dd or metal to metal shorts. The stuck-at fault model has several advantages. The advantages include simplicity, logical behavior, tractability, and measurability. In multiple stuck-at fault model, a circuit with m signal can have (3m − 1) possible faults since each signal can be s-a-0, s-a-1, or fault free. This is a very large number even for relatively small circuits. For simplicity, it is assumed that only one stuck-at fault will be present at any given time. In the single stuck-at (SSA) fault model, a circuit with m signals can have at most 2m faults. The number of faults to be explicitly analyzed can be further reduced by fault collapsing techniques. Fault collapsing can be done by two methods: fault equivalence and fault dominance. Fault-free operation of a logic circuit requires not only performing the logic function correctly but also propagating the correct logic signals along paths within a specified time limit. A delay fault causes excessive delay along a path such that the total propagation delay falls outside the specified limit. Delay faults have become more prevalent with decreasing feature sizes.

1.4 Test Challenges for Deep Submicron Technologies The advent of nanometer technology has paved way for a significant increase in the level of integration and performance of VLSI chips. As more number of transistors is fabricated on a single chip, the cost per transistor reduces. However, testability becomes a significant factor for achieving acceptable reliability levels for modern VLSI chips. This is because the defect size has not scaled down in proportion to shrinking geometries. Further increase in wiring levels and wire delay demands new fault models. Moreover, signal integrity problems such as crosstalk noise, excessive voltage drop, and substrate and thermal noise cause devices to violate performance specifications. Process variations also can have a considerable influence on a chip’s failure to meet specified performance. The noise sources and process variations cause timing-related defects that change the timing of the circuit. The advent of systemon-chip (SOC) architectures, high-frequency circuits, and microelectromechanical (MEMSs) circuits and programmable gate arrays further heightens these issues. As semiconductor process technologies size down toward nanometer era, feature size continues to shrink. Although lesser transistor size could result in lesser circuit delay, a smaller feature size for interconnects does not reduce the signal propagation delay. This is because the cross section becomes smaller due to reduced feature size and hence increases the line’s resistance. To reduce the resistance, the aspect

6

1 Introduction

ratio is made larger than one while maintaining high horizontal interconnect density, but this increases the coupling capacitance. Further, the spacing between interconnecting lines is smaller. Hence, the effective capacitance increases. This along with the increase in line resistance increases the RC time constant and hence the circuit delay. Thus, the signal propagation delay in interconnects has become a major factor in determining the delay of a circuit. To solve these problems, low-resistivity lines and low-permittivity dielectric materials can be used to reduce capacitance. Another solution is reverse scaling of the upper levels of interconnects, presenting a greater cross section. But these two solutions increase the inductive coupling, which depends on the return current path, and do not scale proportionally with capacitance and resistance. The upper levels which form the global interconnects are little further from substrate and hence have higher characteristic impedance. This is called as signal integrity problem which will have a significant adverse effect on the proper functioning and performance of VLSI systems. Simultaneous switching of digital gates produces spikes which cause simultaneous switching noise, which is known as power supply noise, or ground/power bounce. The supply voltage pin of the IC package produces a series resistance and inductance in the path from the external power supply to the on-chip power supply. Considering a single gate, the voltage at any instant at the power supply due to these effects will be supply voltage subtracted by the voltage drop across the resistance and inductance in the on-chip supply voltage. The return path of current passes through the ground pin of the package thus closing the loop and generating a positive spike at the onchip ground pin. The overall effect is a transient reduction in the on-chip power supply voltage. The time derivative of the current is proportional to the input rise or fall time and the transistors’ maximum saturation current. When a number of gates switch simultaneously, the combination of individual switching currents increases the amount of SSN. To improve system performance and maximize clock frequency, path delay distribution of different propagation paths is made as narrow as possible. This increases simultaneity because nearly all paths have similar delays, and the gates along those paths switch almost simultaneously and increase SSN. For deep submicron designs with frequency in the gigahertz range and high circuit density, the power supply voltage drop caused by instantaneous change in current is comparable to IR drop. Therefore, the on-chip power supply is not the same across the chip. This has caused power integrity problem which can affect reliability and performance of VLSI circuits. This power supply noise can reduce the actual output voltage of a device, which in turn can increase the cell and interconnection propagation delay, causes false switching of logic gates, and affects the performance of the analog and RF sections of mixed signal integrated circuits (Wang et al. 2006). Substrate noise has become an important problem in mixed digital/analog circuits. Noise sources include switching devices, substrate contacts, and switching interconnects. Receiving device is affected through parasitic capacitances and body effect. Regarding the propagation path, CMOS technology uses two different types of substrates. Digital technologies use highly conductive substrates with a thin epitaxial layer at the top. In these substrates, noise penetrates the upper layer and propagates on top of the conductive layer. High-frequency analog circuits use substrates that have

1.4 Test Challenges for Deep Submicron Technologies

7

a uniform high resistivity. Here, noise current densities are higher near the surface, decreasing more deeply inside the low-conductive substrate. Results in mixed signal circuits show that first type of substrate propagates noise three times as substrates with uniform resistivity. Special packaging and grounding techniques can reduce the substrate noise. To reduce substrate noise, sensitive circuitry is designed so that it is immune to noise. The amount of noise generated and injected into the substrate is reduced, and the noise is prevented from reaching the critical parts by using either inert barriers or noise sinking. With significant advances in IC technology, precise control of the silicon process has become difficult. There are two types of process variations: variations within the same fabrication plant and between fabrication plants. The variations between chips manufactured in the same fabrication plant include line-to-line, wafer-to-wafer, inter-die, and intra-die variations. Process variations which influence the entire chip or functional block are inter-die variations. These are caused due to process gradient effects over the wafer. Process variations which are not uniform over the entire die are called intra-die variations. Because of these effects, channel length of the transistor has become difficult to control, variation in thickness of interconnects, gate length variation, random placement of dopant in channel. These variations result in delays of wires and gates within a chip. Different fabrication plants use different cell libraries, and hence, the resulting synthesized circuitry causes variations between chips. However, latter is rarely used and hence does not produce a significant effect. This is a process variation problem as design approaches submicrons. These variations cause distributed delay faults in the chip, which in turn give rise to small delay faults on multiple gates in a given path to accumulate and result in the path failing to meet performance specifications, which may affect the yield and performance of devices. Productivity gap results due to this timing inaccuracy, as both EDA tools and design flow methodology break as they cannot change rapidly with the changes in IC technology in deep submicron designs. Hence, new fault models and test methods are to be developed concurrently with the development of new nanotechnologies and circuit designs and placed in the various stages of design to reduce the productivity gap. With increasing system complexity, current test and verification techniques need to be improved. Fault models like stuck-at-fault model, which correctly modeled the behavior of defective chips earlier, are not effective to adequately represent the majority of IC defects and new failure mechanisms in deep submicron technologies. Existing design for test, fault simulation, and ATPG tools must move to more realistic fault types to meet increased quality expectations. Before the chip is fabricated on silicon, there is a need to check for functional design errors, timing errors, and design rule violations. Only a model-based design is verified and detailed modeling of circuits increases computational cost. Hence, a structured technique for testing becomes necessary to locate and rectify any design error in first silicon. Testing of a chip requires analysis of its both internal behavior and external behavior under known stimuli. The analysis is repeated and the responses obtained are compared with a set of expected responses to locate design errors. Faults in design are located and rectified by repeating the design cycle before the final chip is manufactured.

8

1 Introduction

When feature sizes are reduced, the observability of chips for timing violations becomes difficult. For optimum yield, the chips should have both functional and timing correctness. With decrease in feature sizes, delay faults in chips have become a significant problem. The Semiconductor Industry Association (SIA) has published an International Technology Roadmap for Semiconductors (ITRS) which includes the updates on test and test equipment trends for nanometer designs. The long-time challenges for nanometer designs with feature size less than or equal to 45 nm include the full spectrum of test technology trends which include new automatic test equipment (ATE) interfaces, test methodologies, improved defect analysis, failure analysis, and device technologies (Wang et al. 2006).

1.5 Crosstalk Effects Noise is one of the most significant factors that affect the deep submicron VLSI designs. Among the various noise sources, problems related to crosstalk noise between circuit interconnects have become a dominant source of noise in deep submicron circuits (Gal 1995). High-speed digital circuits to a great extent use the dynamic logic family. Dynamic circuits with their two phases of operations are more susceptible to crosstalk noise compared to the static logic (Heydari and Pedram 2001). Line capacitance and load capacitance dominate circuit behavior for submicron process. For deep submicron technologies, cross-coupling capacitance dominates due to decrease in spacing between conductors, the increase in height to width ratio of each conductor, the raise in length of adjoining conductors, and increase in metal layers. The coupling capacitance becomes a significant contributor to signal integrity problem Bhuvaneswari and Jayanthy (2015). Coupling causes insertion of noise into near lines from active lines. This method of noise coupling is called crosstalk. With the intensive scaling in process technology and increase in switching speed, the problem of modeling gate delays becomes further difficult. In deep submicron VLSI designs, the part of delay contributed by gates reduces while interconnect delay becomes dominant. This is due to the fact that the scaling of interconnect lengths is not in proportion to the shrinking size of transistors that make up the gates. Further as operating frequencies increase, on-chip inductance and cross-coupling capacitance between the interconnect lines also increase. Inductances in a wire are of low magnitude value. It becomes significant only at very high frequencies in global lines such as ground and power supply lines and is important only in power circuits. Hence, the cross-coupling capacitance or crosstalk noise effects are considered to have a predominant effect in digital circuits that may result in improper functioning of a chip (Aragones et al. 2002). Crosstalk noise may cause unwanted effects including excessive overshoot, undershoot, glitches, additional signal delay, and even a decrease in signal delay. These effects can lead to possible circuit malfunction and increased power dissipation.

1.5 Crosstalk Effects Fig. 1.2 a Positive pulse, b negative pulse

9

(a)

(b)

Static 0

Static 1

Victim-line Aggress or-line Rising transition

Victim-line Aggressorline Falling transition

There are two main types of crosstalk effects: crosstalk-induced pulses and crosstalk-induced delay. Given a pair of nodes with capacitive crosstalk interaction, there is always one of them that act as affecting node or aggressor and the other as affected or victim node. A crosstalk glitch is a pulse that is induced by coupling effects among interconnect lines. The amplitude and the width of the glitch depend on relative switching time of the aggressors, the amount of coupling capacitance, line-to-ground capacitance, and the relative transition times of the aggressors. When aggressor nodes are applied a transition signal and the stable signals applied to victim node, the stable signal may experience coupling noise due to transition in the aggressor nodes. In Fig. 1.2, the victim line remains in a static 0 state and one aggressor line has a rising transition. The aggressor creates a positive pulse on the victim line, which depending on its amplitude and width will have an effect on the circuit performance (Moll and Rubio 1992). In the second case, victim line remains in a static 1 state and one aggressor line has a negative transition, which creates a negative pulse on the victim line. Crosstalk delay is a signal delay induced by the identical coupling effects, that is, simultaneous transitions among interconnect lines. Crosstalk causes a delay in addition to normal gate delay and interconnect delay. Hence, it is difficult to estimate the correct circuit delay which may lead to severe signal delay problems (Wang et al. 2006). These unexpected changes in signal propagation delays cause delay faults which cause the delay of paths in a chip to be larger than expected resulting in the output of a chip to deviate from the expected behavior, in spite of the chip being functionally correct. As shown in Fig. 1.3, the victim and aggressor have transitions in the opposite direction, and hence, signal delay increases and speed of circuit decreases. In the second case, if the transitions are in the same direction, signal delay decreases thus increasing the speed of the circuit. These changes in signal propagation delays can cause faulty behaviors of digital circuits. When designing fault analysis tools, these delays have to be taken into consideration. Several physical designs (Vittal and Marek-Sadowska 1997; Elgamel et al.

10 Fig. 1.3 a Crosstalk slowdown, b crosstalk speedup

1 Introduction

(a)

(b)

Victimline

Victimline

Aggresso r-line

Aggresso r-line

2005; Hunagund and Kalpana 2010) and analysis tools (Agarwal et al. 2006; Kaushik and Sarkar 2008; Palit et al. 2009; Shahin and Pedram 2010) are being developed to aid in designs that minimize crosstalk. But during manufacturing, process variations and manufacturing defects may aggravate crosstalk effects (Chen et al. 1998). Hence, it is necessary to develop new crosstalk fault models and testing techniques for manufacturing defects that produce crosstalk effects.

1.6 Crosstalk Fault Models There are three important delay fault models at logic level: transition fault model, gate delay fault model, and path delay fault model. Transition and gate delay models represent delay defects lumped at gates, and path delay model represents defects that are distributed over several gates. Some researchers Chen et al. (1998, 1999, 2002) Sinha et al. (2003, 2008) have used transition fault model, whereas the others Li et al. (2003, 2005, 2006), Chun et al. (2009), Aniket and Arunachalam (2005) have used path delay fault model. Combined transition and path delay fault model is used by Lee and Tehranipoor (2008). Crosstalk fault models were first developed by Gao et al. (1990) for lossy transmission line system. In this model, the coupled transmission lines were first decoupled into a set of independent transmission line equations by linear transformations. Then, the solutions of this decoupled equation were represented by a set of timevarying equivalent circuits. This circuit model was implemented in a spice simulator. Although these models were quite effective for the specific cases of high-speed Gallium Arsenide integrated circuits, they are not applicable to VLSI circuits because of the complexity of the circuit model and high computation time. Further, they provide little insights into the coupling mechanism. A simplified lumped RC model (Rubio et al. 1994) is assumed for crosstalk pulse fault between a pair of coupled lines. Assuming a small wire resistance, the dis-

1.6 Crosstalk Fault Models Fig. 1.4 Circuit showing source of crosstalk due to capacitive coupling

11

A

Ai

Aout

Cc Vout Vi

V

tributed capacitance was modeled by a coupling capacitance between the aggressor line denoted as A-line and victim line denoted as V-line. A layout tool is used to find the coupling capacitance and aggressor line-to-ground capacitance. From this value, the strength of aggressor lines which affect the victim lines was found to derive a list of target crosstalk faults. However, crosstalk delay faults where both lines have transitions had not been considered which is necessary for high-performance system. To overcome this limitation, a model is developed by Chen et al. (1999) to evaluate the effect of parasitic coupling crosstalk where inputs to one or both coupled lines have transitions with arbitrary transition times and directions. All CMOS logic gates were modeled as equivalent inverters, and then, the output response of crosstalk noise was calculated through this gate using the transfer function of the equivalent inverter. Figure 1.4 shows the source of crosstalk due to capacitive coupling. CC denotes the coupling capacitance between the A-line and V-line. The lumped model of coupling capacitance is shown in Fig. 1.5. The resistances Ra1 and Ra2 are the line resistance and on-channel resistance associated with the line driver, respectively. C 1 and C 2 denote line capacitance and gate capacitance of the load driven by the line, respectively. The coupling network consists of C C , C 1 , and C 2 . Figure 1.5 consists of three stages: input stage, a driver stage made of pulling resistances, and the coupling network. Laplace transform is used for all three stages, and an expression is obtained in the frequency domain, which can be transformed to time domain. From these equations, the crosstalk effects that should be considered for validation and test generation are identified. This model had been used for both crosstalk pulse and delay analysis (Chen et al. 1997). However, this model is very computationally intensive and takes a long time to simulate a small circuit. Maximum aggressor (MA) fault model is suggested by Rubio et al. (1994) for crosstalk which takes only the coupling capacitances into account. All aggressors are assumed to make simultaneous transitions in the same direction while the victim makes an opposite transition. A constrained path delay fault (CPDF) model is used in Krstic et al. (2001). In this model, the fault is defined as the critical path and a set of interconnects coupled to it. Critical paths are paths whose delay is longer than a specified percentage of the longest propagation delay in the circuit. A statistical timing analysis framework was used for target fault selection phase. In statistical timing analysis, the delays of cells/interconnects are modeled as correlated random variables with known proba-

12

1 Introduction

Ra1

Fig. 1.5 Capacitive coupling model

A

Ai

C1 Ra2

Cc

Vi

V

C2

bility density functions. Using the cell delays, the cell-level net list and the clock period, statistical timing analysis can derive the probability density functions of the signal arrival times, required times, and slacks at internal signals and primary outputs. Using this information, the noise sources resulting in sensitivity higher than a certain threshold are found. By intersecting the obtained noise sources and the set of critical paths chosen without taking into account noise effects, set of crosstalk faults is obtained. Each crosstalk fault consists of a path and a set of noise sources interacting with the path. Exact delay information was not available in the CPDF model. Hence, the time of transitions and the sub-paths from which the aggressor transitions can be activated are unknown. A coupled transition fault model (CTF) is used by Takahashi et al. (2005). A single victim/aggressor crosstalk fault is considered. Four possible crosstalk delay faults are considered. They are simultaneous rising or falling which are crosstalk-induced speedup faults, one rising and another falling, and vice versa, which is crosstalkinduced slowdown faults. This model uses a slow-fast-slow clock method to test crosstalk delay faults in sequential circuits. The sequential circuit is expressed as an iterative array model. In this model, crosstalk fault was induced in the victim line when necessary conditions to excite the fault occur on the aggressor line. To calculate the number of target faults, the static timing analysis algorithm uses structural and timing information. False crosstalk faults that need not be tested were identified. A single precise crosstalk-induced path delay fault model (S-PCPDF) is developed by Li et al. (2006). In this path delay fault model, only robust paths are considered. Crosstalk delay faults associated with robust path are taken as target faults. A crosstalk fault is a path delay fault that is caused by a coupling effect between A-line and a V-line on path denoted as p, such that there exists a sub-path denoted as sp-A starting from the primary input and ending at line A-line and a sub-path denoted as sp-V ending at V-line, satisfying the following conditions: 1. The difference in delay of the sp-V and sp-A should be within a specified interval. 2. The parity of the number of inverter gates on sp-A is different from the parity of the number of inverter gates on sp-V.

1.6 Crosstalk Fault Models

13

An S-PCPDF can be represented using a 4-tuple (p, sp-A, V-line, A-line), while p is usually a critical path, A-line is the aggressor line, V-line is the victim line, and sp-A is the sub-path that propagates the aggressor transition to A-line. A single precise crosstalk-induced path delay fault model (S-PCPDF) was developed by Li et al. (2005) for non-robust paths.

1.7 Conclusion The current scenario in VLSI testing and the test challenges in deep submicron technologies is discussed in this chapter. The phenomena of unwanted crosstalk pulses, crosstalk models at circuit level and gate level, and the various crosstalk delay faults have also been presented.

References M. Abramovici, M.A. Breuer, A.D. Friedman, Digital Systems Testing and Testable Design (Computer Science Press, New York, 1990) K. Agarwal, D. Sylvester, D. Blaauw, Modeling and analysis of crosstalk noise in coupled RLC interconnects. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 25(5), 892–901 (2006) Aniket, R. Arunachalam, A novel algorithm for testing crosstalk induced delay faults in VLSI circuits, in Proceedings of International Conference on VLSI Design, pp. 479–484 (2005) X. Aragones, J.L. González, F. Moll, A. Rubio, Noise generation and coupling mechanisms in deep-submicron ICs 2002. IEEE Des. Test Comput. 19(5), 27–35 (2002) M.C. Bhuvaneswari, and S. Jayanthy Cross-Talk Delay Fault Test Generation, in Application of Evolutionary Algorithms for Multi-objective Optimization in VLSI and Embedded Systems, (2015). ISBN 978-81-322-1958-3 M.C. Bhuvaneswari, S.N. Sivanandam, Development of new algorithms for test generation and simulation of stuck-at-faults in logic circuits. Ph.D. dissertation, Bharathiar University (October 2001) W.Y. Chen, S.K. Gupta, M.A. Breuer, Analytic models for crosstalk delay and pulse analysis for non ideal inputs, in Proceedings of the International Test Conference, pp. 809–818 (1997) W.Y. Chen, S.K. Gupta, M.A. Breuer, Test generation for crosstalk-induced delay in integrated circuits, in Proceedings of International Test Conference, pp. 191–200 (1999) W.Y. Chen, S.K. Gupta, M.A. Breuer, Test generation in VLSI circuits for crosstalk noise, in Proceedings of International Test Conference, pp. 641–650 (1998) Y. Chen, S.K. Gupta, and M.A. Breuer, Test Generation for Crosstalk Induced Faults: Framework and computational results, J. Electron. Test. Theor. Appl. 18, 17–28 (February 2002). S. Chun, T. Kim, S. Kang, ATPG-XP: test generation for maximal crosstalk-induced faults. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 28(9) (2009) R. Datta, A. Sebastine, R. Gupta, W.J. Townsend, J.A. Abraham, Test and Debug in Deep-Submicron Technologies. http://www.cerc.utexas.edu (May 2009) M.A. Elgamel, A. Kumar, M.A. Bayoumi, Efficient shield insertion for inductive noise reduction in nanometer technologies, in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 13, no. 3, pp. 401–405 (March 2005) L. Gal, On-chip cross talk—the new signal integrity challenge, in Proceedings of IEEE Custom Integrated Circuit Conference (1995)

14

1 Introduction

H.S. Gao, A.T. Yang, S.M. Kang, Modeling and simulation of interconnection delays and crosstalk in high-speed integrated circuits, in IEEE Transaction on Circuits and Systems, vol. 37 (January 1990) P. Heydari, M. Pedram, Analysis and reduction of capacitive coupling noise in high-speed VLSI circuits, in Proceedings of International Conference on Computer Design (2001) P.V. Hunagund, A.B. Kalpana, Analytical noise modeling for shielding to reduce crosstalk noise in on-chip interconnects. Int. J. Comput. Sci. Netw. Secur. 10(11), 19–23 (2010) S.L. Hurst, VLSI Testing: Digital and Mixed Analogue /Digital Techniques, Inst. Electron. Eng. London, (1998) B.K. Kaushik, S. Sarkar, Crosstalk analysis for a CMOS-gate-driven coupled interconnects. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 27(6), 1150–1154 (2008) J.-J. Krstic, Y.-M. Liou, Jiang, K.-T. Cheng, Delay test considering crosstalk-induced effects, in Proceedings of International Test Conference, pp. 558–567 (2001) J. Lee, M. Tehranipoor, A novel pattern generation framework for inducing maximum crosstalk effects on delay-sensitive paths, in International Test Conference (IEEE, 2008) H. Li, Y. Zhang, X. Li, Delay test pattern generation considering crosstalk-induced effects, in Proceedings of Asian Test Symposium, pp. 178–183 (2003) H. Li, P. Shen, X. Li, Non-robust test generation for precise crosstalk induced path delay faults, in Proceedings of Asian Test Symposium, pp. 120–125 (2005) H. Li, P. Shen, X. Li, Robust test generation for precise crosstalk induced path delay faults, in Proceedings of VLSI Test Symposium, pp. 300–305 (2006) F. Moll, A. Rubio, Spurious signals in digital CMOS VLSI circuits: a propagation analysis. IEEE Trans. Circ. Syst. II Analog Digital Signal Process. 39(10), 749–752 (1992) A.K. Palit, S. Hasan, W. Anheier, Decoupled victim model for the analysis of crosstalk noise between on-chip coupled interconnects, in Proceedings of 11th Electronics Packaging Technology Conference, pp. 1–9 (2009) A. Rubio, N. Itazaki, X. Xu, K. Kinoshita, An approach to the analysis and detection of crosstalk faults in digital VLSI circuits, in IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vo1. 13, pp. 387–394 (March 1994) N. Shahin, M. Pedram, Analysis of crosstalk-affected propagation delay of VLSI interconnect in nanometer technologies. Int. J. Electron. (2010) A. Sinha, S.K. Gupta, M.A. Breuer, An enhanced test generator for capacitance induced crosstalk delay faults, in Proceedings of the 12th Asian Test Symposium (2003) A. Sinha, S.K. Gupta, M.A. Breuer, A multi-valued algebra for capacitance induced crosstalk delay faults, in 17th Asian Test Symposium (IEEE, 2008) H. Takahashi, K.J. Keller, K.T. Le, K.K. Saluja, Y. Takamatsu, A method for reducing the target fault list of crosstalk faults in synchronous sequential circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 24(2), 252–263 (2005) A. Vittal, M. Marek-Sadowska, Crosstalk reduction for VLSI. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 16, 290–298 (March 1997) L.-T. Wang, C.-W. Wu, X. Wen, VLSI Test Principles and Architectures: Design for Testability (Morgan Kaufmann, San Francisco, CA, USA, 2006)

Chapter 2

Delay Fault Testing of VLSI Circuits

2.1 Introduction The advances in VLSI technology have resulted in devices with millions of transistors thus creating new test challenges. Moore’s law states that the scale of ICs has doubled every 18 months. Reduction in feature size increases the speed of integrated circuits, thus increasing the probability that a manufacturing defect in the IC will result in a faulty chip. Some manufacturing defects do not change the steady-state logical operation of a system, but they may affect the timing behavior of a system and degrade overall system timing performance and hence industry is forced to test timing anomalies in circuits. The purpose of delay testing is to identify timing defects so that the design adheres to the desired performance specifications. The need for delay testing is further expected to grow with the current design trend of moving toward deep submicron devices. Imprecise delay modeling, statistical variations of the parameters during the manufacturing process, and physical defects in integrated circuits can sometimes degrade circuit performance without altering its logic functionality. Delay testing has been a topic of extensive research both in industry and in academia. Earlier delay defects could be detected using tests for gross delay defects. Aggressive timing requirements of high-speed designs have introduced the need to test smaller timing defects and distributed faults caused by statistical timing variations. The problems in delay fault testing are as follows: • Testing of sequential circuits results in high area overhead and large execution times. • Requirement of high-speed testers. • Small distributed defects require path delay model which requires testing of very large number of paths for complex, large circuits. • Critical path selection.

© Springer Science+Business Media Singapore 2019 S. Jayanthy and M. C. Bhuvaneswari, Test Generation of Crosstalk Delay Faults in VLSI Circuits, https://doi.org/10.1007/978-981-13-2493-2_2

15

16

2 Delay Fault Testing of VLSI Circuits

• All paths cannot be sensitized and hence will result in a poor fault coverage. • Design and synthesis techniques result in high area and large number of primary inputs. The reasons for timing failures in combinational circuits are excessive propagation delay, correct output appears later than specified, inadequate propagation delay, correct output appears sooner than specified and static or dynamic hazards may appear at the outputs. The basis for timing failures in sequential circuits are excessive propagation delay, setup time (long path) violation, inadequate propagation delay and hold time (short path) violation.

2.2 Delay Fault Models Delay fault testing is back-end process which ensures that the product quality meets established standards in terms of performance and physical defects. Defects in the manufacturing process often result in propagation delays to fall outside the design requirements. The effect of these performance degrading effects can be presented using logical fault models. It is very important that these fault models clearly and adequately understand the environment under which defects manifest. Delay fault models can be primarily categorized into five types.

2.2.1 Transition Fault Model This model considers a gross delay in every gate terminal in the circuit and assumes that the additional delay is large enough to cause a logic failure (Waicukauski et al. 1987). The transition fault model is similar to the stuck-at fault model. There are two types of transition delay faults: a slow-to-fall fault and slow-to-rise fault associated with each gate. A slow-to-rise fault means that any transition from 0 to 1 on a node does not produce the correct result when the device is operating at its maximum operating frequency. Likewise, a slow-to-fall fault means that a transition from 1 to 0 does not produce the correct result at the desired frequency. In a fault-free circuit, each gate has a nominal rise and fall delay. If there are delay faults, then the nominal delay will increase. The size of the gate-level delay fault must be such that it exceeds the slack of at least one path from the fault site to the primary output or scan flip-flop such that the fault can be observed at the output. The main advantage of the transition fault model is that the number of faults in the circuit is small. Further, the existing test generation and fault simulation tools for stuck-at faults can be modified for testing transition delay faults. A test for a transition fault is a pair of input vectors which consists of one initialization vector to set up the initial state of a transition and the second vector activates

2.2 Delay Fault Models

17

X,0 a

0,1

f

b e

o

X,1 c

X,1 d

g

Fig. 2.1 Circuit with transition fault

the fault and propagates its effect to some primary output. The propagation vector is identical to the pattern that detects the corresponding stuck-at fault. The transition fault coverage is a measure of the efficiency of the delay test in detecting large delay variations. Transition faults are a special case of gate delay faults because the delay due to the defect is large enough to cause a logical failure when propagated along any path through the site of the fault. The disadvantage is that the assumption that one gate in the circuit is effected is not realistic. Several delay faults together may be large enough to affect the performance of the circuit. The transition fault model is normally used as a qualitative delay model, and circuit delays are not considered in deriving tests. It is known that a rising (falling) transition fault is detected if and only if: (i) The first pattern places a 0/1 at the fault site and (ii) the second pattern detects a stuck-at-0 (stuck-at-1) fault at the transition fault site. In the circuit as shown in Fig. 2.1, to detect a slow to rise fault in node b, vector 1: sets node b to 0, vector 2: sets the node b to 1 (to detect s-a-0). So if there is fault in node b, the node will not change to 1. Now, when the output e is read, the output will not change to 1. It will remain at 0. Hence, a slow-to-rise fault manifests itself into a stuck-at-0 fault when a two vector test is applied and if the delay fault is large enough. Further, the observation time at the primary output should be longer than a predefined interval.

2.2.2 Gate Delay Fault Model The gate delay fault model assumes that the delay fault is lumped at one gate in the circuit. A localized timing failure at a gate causes the propagation delay of at least one path in the circuit through the fault site to exceed the specified cycle time. This model assumes that delays of logic gates are known with some precision. On the other hand, the gate delay fault model does not assume that the increased delay will affect the performance independent of the propagation path through the fault

18

2 Delay Fault Testing of VLSI Circuits

(a)

(b)

5

S0

4 Fig. 2.2 a Circuit not considering timing, b circuit with timing information 0 A

1 E

2

6 2

C

F 2

2

B

2 6

0

8

10

12

D 1

Fig. 2.3 Circuit with delay fault at the output

site. It assumes that only long paths through the fault model will cause performance degradation. It is a quantitative model that takes the circuit delays into account. The number of faults is linear to the number of gates in the circuit. Similar to a transition fault model, the disadvantage of this model is that the test may fail to detect delay faults that are sum of several small delay effects. Figure 2.2a shows the AND gate. If the information about the gate delays is not available, it is assumed that a static hazard may prevent the propagation of some fault. If the information of the delays are available and if the arrival time of the signals at the input are as shown in Fig. 2.2b, the output will have a stable 0 which may propagate some fault to the primary output (Krstic and Cheng 1998). Figure 2.3 shows the problem with gate delay modeling. The delays of the gate are as shown in the figure. At C, there is a slow-to-rise fault. As the value of C rises to 1, the output becomes high through shortest path with a delay of 6 time units. After a delay of 2 time units, through the lower NOR gate the output goes back to logic 0 because output of NOR gate is logic 0. Again output goes to logic 1 taking the critical path through the circuit at 10 time units as output of upper OR gate becomes logic 1. Hence, a delay as large as time of observation of 12 units at output F is detectable. A dynamic hazard is observed at the output due to different delays of the gates. Here, only longest path through the circuit is considered. But a small gate delay fault is difficult to detect because of hazards.

2.2 Delay Fault Models

19

2.2.3 Line Delay Fault Model Line delay fault model tests a rising/falling delay fault on a given line in the circuit and propagates the fault through the longest sensitizable path in the circuit. It can detect some distributed delay defects on the propagation paths. The number of faults is equal to twice the number of lines in the circuits. Only one propagation path through each line is considered.

2.2.4 Path Delay Fault Model A path delay fault is associated with each logical path and is said to present if the delay of any of its paths exceeds a specified limit. The delay of the path is the sum of the delays of the gates and interconnections on that path. The model can detect small distributed defects caused by statistical process variations. A delay fault caused by a local defect, such as a resistive open or short, can only be detected by testing a path through it, and testing the longest path through it can detect the smallest local delay defect. The path delay fault specification consists of a physical path and a transition that will be applied at the beginning of the path. This model is highly effective in covering delay faults, but has a limitation because the number of paths in the circuit can be very large. Process variation and noise can result in the longest path through a gate varying from chip to chip or across operating conditions. Therefore, testing only one critical path through each gate cannot guarantee the detection of the smallest local delay faults. Testing the N longest paths through a fault site increases the fault detection probability. The longest paths are selected because delay defects on shorter paths might not be large enough to affect the circuit performance; moreover, even if the defects on short paths are large and it could affect the circuit performance, that defects could be detected by transition or gate delay tests. But in performanceoptimized designs almost all paths have long delays and most of the paths cannot be tested. For performance-optimized circuits with aggressive timing necessities, small process variations can lead to failures at the system clock rate. These defects can be detected using tests for path delay faults (Wang et al. 2006). This model overcomes the disadvantage of transition fault model in that the other faulty gates may compensate for the delay of a faulty gate. Hence, path delay fault tests are more likely to detect small delay defects. The path delay fault model can be broadly classified into: (i) non-robust (NR) path delay fault and (ii) robust path delay fault. Non-robust (NR) path delay fault: This class of paths is statically sensitizable and guarantees to detect the delay fault on the targeted path only if no other path delay is increased. A more proper definition of NR tests is: A vector pair {v1, v2} is said to detect a path P non-robustly, if and only if:

20

2 Delay Fault Testing of VLSI Circuits

g f X0

a b d

S1

e

c

Fig. 2.4 A robustly testable path

(i) The vector pair launches a transition (rising/falling) at the beginning of the path and (ii) All the off-paths inputs along the paths have a non-controlling value (NCV) for v2. Robust path delay faults: These types of paths can be tested independently of side path delays. It is a more constrain form of non-robust test. A vector pair {v1, v2} is said to detect a path P robustly, if and only if: (i) The vector pair {v1, v2} should be an NR test for p and (ii) Whenever the on-path input of a gate g is along the path transitions from a NCV to a controlling value (CV), then all the off-path inputs of g should be held at a steady NCV. Robust tests are difficult to generate, and a large number of paths in a circuit are usually robustly untestable. In Fig. 2.4, the falling transition on path ↓ bdeg is sensitizable irrespective of the side path delays in the circuit. Hence, it is taken as the target path. The slow-to-fall fault on b will not be prevented to be propagated to primary output even if there is delay on primary input a. Hence, this path is robustly testable. But for some paths, robust or non-robust tests may not exist. However, such functional paths can be tested using functional sensitization.

2.2.5 Segment Delay Fault Model It makes the assumption that delay affects several gates in a given region where it occurs. The segment delay fault list consists of all segment of given length L and all paths of length less than L which represents the delays distributed across the chip. The model is a trade-off between transition fault model and path delay fault model. Practically, many segments along path can be tested but the entire path may not be testable. Further, it is more realistic than transition fault model. The upper bound on the length of the segment is the maximum number of gates in the longest path.

2.2 Delay Fault Models

21

Transition, gate and line delay fault models are used to represent delays lumped at gates, whereas path and segment delay fault models are used to represent delays distributed across the chip. Path delay model is closest to ideal model. Most of the path delay faults cannot be sensitized, but these paths might degrade the circuit performance. Developing an accurate fault model and selection of critical paths that are sensitive to process variations, defects, and signal coupling effects are important research problems.

2.3 Test Application Schemes Delay testing is closely tied to test application strategy, type of circuit, and speed of testing equipment. High-speed testers are costly. Testing high-speed design on slower testers requires special test application and test generation strategies. Combinational circuits require a vector pair {v1, v2}. The first vector is used to initialize the circuit, and the second vector produces the desired transition. During normal operation, a clock signal with a period T c is used for controlling both the latches. Whereas, in test mode, two different clocks of period T s larger than T c and having a skew equal to T c is used to control the input and output latches as shown in Fig. 2.5. The first vector, v1, is applied at time t 0 , and the second vector, v2, is applied at time t 1 at the primary inputs of the circuit under test. After application of vector v1, the time required for the signals to become stable is assumed to be T s  t 1 − t 0 . Then, the second vector v2 is applied and the circuit stabilizes at time t 2, where t 2 − t 1  T c . The logic value observed at the primary output is compared with fault-free circuit response to check for a defect. The same scheme shown in Fig. 2.5 applies even if the input and output clocks are the same. T s could be equal to or larger than T c , and no skew will be present between the input and the output clocks. The rising edges of the respective clock pulses are synchronized with timing of application of input vectors and observation of output. Delay fault testing of sequential circuits is more difficult than testing delay faults in combinational circuits, because random vector pair cannot be applied to non-scan or standard scan sequential circuits. Figure 2.6 shows the model of a sequential circuit, represented as an iterative array of the combinational logic. Each copy of the combinational logic is called as a time frame. The present state values of the current time frame are equivalent to the next state values of the previous time frame. In case of a sequential circuit, vector pattern (v1 , v2 ) is represented as (i1 + s1 , i2 + s2 ) where i1 and i2 are the primary inputs and s1 and s2 are values of the present state values. There are number of methods used for delay testing of sequential circuits (i) For standard scan circuits: Enhanced Scan Testing, Functional Justification, and Scan Shifting (ii) For non-scan or partial scan circuits: Fast slow strategy and at-speed strategy

22

2 Delay Fault Testing of VLSI Circuits

Combinational circuits

Input latches

Output latches

Clock C1

Outputs

Clock C2

Clock C1

Clock C2

TC

TS

t0

t1

t2

Fig. 2.5 Testing scheme for combinational circuits

2.3.1 Standard Scan Circuits Test generation for delay faults in scan-based sequential circuit requires representing sequential circuit in two time frames. All the lines corresponding to primary inputs and present states are fully controllable in the first time frame, whereas only the primary inputs are fully controllable in the second time frame. Enhanced Scan In enhanced scan, testing vectors v1 and v2 are shifted into the scan flops during the shift process. These two values are stored in the enhanced scan flops at a time. Once the vectors are shifted in, enable inputs of the scan flip-flops are made low. When the clock is pulsed two times, response is shifted out. Any arbitrary vector can be applied to the combinational part of the sequential, circuit and high fault coverage is obtained in this method. Since the technique uses scan flip-flops, it has a high overhead. Test application times are also very long and hence are not used widely in application-specific integrated circuit area. However, in areas which require custom designs such as microprocessors and other high-performance circuits, enhanced scan designs are used. In custom designs, the circuit often is not fully decoded; hold scan cells are used to prevent contention in the data being shifted and also prevent excessive power dissipation in the circuit during the scan shift phase. In addition, the diagnostic

2.3 Test Application Schemes

23

Primary input PI

Combinational. Logic(C1)

Primary Output

PS

NS

FFs

PI

C1

PO

PS

PI

C1

NS

time-frame n-1

PO

PI

C1

PS

time-frame n

PO

NS

time-frame n+1

Fig. 2.6 Testing scheme for sequential circuits

capability associated with scan design for test is improved because the part in which only the scan logic failed can often be retrieved. Hence, for high-performance designs enhanced scan technique is preferred. Functional Justification The most common delay fault testing is functional justification. In this method, vector v1 is scanned into the circuit during shift process and vector v2 is derived as circuit’s response to the first vector. This technique is called functional justification because the second vector is the functional response of the first vector. This method is also called as broadside test or launch from capture. The broadside approach is cheaper to implement compared to skewed-load approach. Launch from Shift This is also called as ‘Transition Shifting’ technique or skewed-load approach. In skewed-load approach, both the vectors are shifted through the scan cells. The advantage of skewed-load approach is test patterns with higher fault coverage are obtained than broadside approach. Test pattern sets generated by the broadside approach are usually larger than those generated by the skewed-load approach. For generating test vectors for functional justification technique, a sequential ATPG that considers two full time frames is required. On the other hand, for the skewed-load approach test vectors can be obtained by a combinational ATPG with slight modification. Hence, test generation cost is higher for the broadside approach.

24

2 Delay Fault Testing of VLSI Circuits

In skewed-load approach, the second vector is obtained by shifting the contents of the scan chain by one bit after application of the first vector. In this technique, the second vector is no more the functional response of the circuit because the second vector is shifted version of the first vector. The first vector is shifted, the system clock is given, and the scan-enable is made low. The scan-enable is again made high after the launch clock, and the capture clock is given. This method gives improved fault coverage as compared to functional justification because the second vector is partially controllable. But the drawback is that the scanenable has to switch its state exactly after the launch clock edge and before the capture clock edge which is not always easy. To meet this timing, the scan-enable signal should be driven by a complicated buffer tree, that is, a costly and time constraint design requirement. Hence, this technique is infrequently used in the MUX-Scan architecture. It is easier to use this technique in level-sensitive scan design (LSSD), where the launch and capture clocks are separately controlled.

2.3.2 For Non-Scan Circuits For non-scan circuits, slow fast slow and at-speed scan are used. Slow Fast Slow Method Delay fault testing in non-scan sequential circuits requires a sequence of vectors which are applied in three phases in fault generation process: fault initialization, fault activation, and fault propagation. In the fault initialization phase, vectors are applied to set signal values in order to activate the fault. In the fault propagation phase, the activated fault is propagated from an intermediate node to the primary output. Test sequence is required for fault initialization and fault propagation, whereas the fault activation phase requires a vector pair. The presence of delay defects in the initialization and propagation phases can affect the observation of the fault. A common solution is to apply a slow fast slow clock testing strategy. In this scheme, circuit under test is considered fault free in initialization and propagation phase and hence the clock is applied at a slow speed. In the activation phase, the first test vector is applied under the slow clock while the second vector is applied at the rated speed. Using this method simplifies test generation process since a slow clock is used during fault initialization and fault propagation phases. On the other hand, two clocks, slow and fast clocks, are needed which make difficult the test generation process. Single fault assumption is usually not applicable for testing delay faults in partial scan circuits. Therefore, during the end of fault activation phase, in slow fast slow testing method more than one flip-flop latches a faulty value. The test generator has to take account of this possibility during the fault propagation phase. At-Speed Scan At-speed testing strategy assumes fast clock which is used to initialize, activate, and propagate the fault. Therefore, delay faults are present in all the three phases. Some

2.3 Test Application Schemes

25

faults that cannot be testable in the slow fast slow clock testing scheme can become testable under the at-speed scheme and vice versa. The circuit is tested under its normal operation conditions. The fault coverage for at-speed testing is lower. Important factor in test application for delay faults is testers speed. Speed of testers is less compared to the speed of new designs. Hence, new techniques have to be developed that would allow high-speed design testing on slower testers.

2.4 Test Generation Methods for Path Delay Fault Model Recently, scan-based structured techniques are used to test delay faults in digital logic circuits. This is because less time is required to develop them, and it is relatively easier to debug them. To reduce time complexity, test engineers use multiple parallel scan chains as the number of flip-flops increases in long serial scan chains. But with large circuit designs, test equipments cannot support the depth and large number of scan chains. The difficulty of using structured scan-based techniques is the increase in silicon area with the reduction in performance. Another approach for testing delay faults is logic built-in self-test (BIST). In this approach, test pattern generation and output response comparison functions are built into the same chip (Hetherington et al. 1999). With a BIST-only approach, high coverages have been reported (Kusko et al. 2001). To have a reduced test vectors and high fault coverage, hybrids of logic BIST and deterministic ATPG techniques have been proposed (Dorsch and Wunderlich 1998; Kiefer et al. 2000; Das and Touba 2000). The disadvantages of BIST are as follows: area overhead for the BIST controller, the requirement of additional pins, routing complexity, and reduced access times. Further, to have compatibility with commercial BIST tools, the clock distribution and clock tree balancing tasks become more complicated (Hsu et al. 2001). Another approach to test delay faults is ATPG. Efficient and powerful ATPG can alleviate high costs of DFT. There are two types of ATPG methods for generating tests for delay faults: deterministic- and simulation-based test generation algorithms. Deterministic-based test generators produce tests by processing a structural model of the circuit. Simulation-based techniques typically involve generation of random vectors.

2.4.1 Path Delay Fault Simulation A path can start at a primary input or a flip-flop and end at either a primary output or a flip-flop. A path delay fault will cause the time of propagation of a signal through the path to exceed the clock period. There are three steps in path delay test generation, namely initialization, path activation, and propagation. One or more input vectors are generated for each phase. The activation phase requires two test vectors to initiate

26

2 Delay Fault Testing of VLSI Circuits

a signal transition at the source of the path and propagate it to the end of the path. Path testing concepts in combinational circuits and scan-based sequential circuits are applicable to this phase. There are two approaches for path delay fault testing based on the way the path is activated. In the fully transitional path approach, the entire path is sensitized at each gate by both the vectors. In the next approach only during the second vector, the path is fully sensitized. But the first vector sensitizes the path only through gates that propagates non-controlling values along the path. Smith (1985) has developed a system for identifying paths that are testable independent of gate delays. The six-valued logic used in his method represents two vectors. The supported values are static 0, static 1, rising transition, falling transition, 0X where the first vector is 0 and second vector is unknown value and 1X where the first vector is 1 and second vector is unknown value. Input vectors are generated to the circuit, and inputs are set to any one of logic values except the unknown values. The values are propagated through the circuit. Any path with the correct transition direction and with the value of rising or falling transition is flagged as tested and removed from path list. In this method, the delay of the gates along the path is not considered during delay fault testing. This fault model is capable of modeling all delay faults of any size. The time complexity of the test generation algorithm is approximately a linear function of the number of gates and the number of paths. Schulz et al. (1989) have a proposed a fast fault simulator for path delay faults. Parallel test patterns are used for fault simulation-based test generation. Their simulator could not test large number of paths under the restrictive condition of robustness. They devised a four-valued algebra using Smith’s (1985) six-valued algebra for simulating robust and non-robust path delay faults. A data structure called the path tree was employed to accommodate the large number of paths. The path tree stores parts of paths that are common to several paths from a distinct primary input to primary output only once rather than explicitly carrying them along for each path separately. But explicit representation of all physical paths can consume more memory to store the path tree for large circuits. Pomeranz and Reddy (1992) have proposed a method for estimating the path delay fault coverage without enumerating the paths. The three properties used in their work for estimating the delay fault coverage without enumerating the paths are as follows: (i) The number of paths in a circuit can be computed in time by making one backward pass of the circuit. (ii) When a single test pattern is used, one forward pass of fault-free logic simulation will determine which lines in the circuit belong to path whose delay faults are covered by the test. The number of paths found equals the number of path delay faults covered by the test. Enumerating all the paths can be avoided. (iii) Assuming a random test pattern, some of the faults detected by that test pattern would have been detected by an earlier test pattern. Hence, only new faults detected for the first time should be counted for calculating the fault coverage. So new lines, which are logical lines (each line associated with rising or falling transition) that are not already included in the previously detected list of path delay faults, are calculated. The number of new path delay faults the particular

2.4 Test Generation Methods for Path Delay Fault Model

27

test pattern detects can be approximately calculated by counting the number of path delay faults detected by the test pattern such that each path delay fault counted includes at least one new line. These faults calculated can be added with faults already detected to estimate the fault coverage. The set of paths were divided into subsets by partitioning the circuit such that every path passes through one line of the cut. A better estimate of fault coverage is obtained as the number of partitions is increased. The estimate is always pessimistic as the estimated fault coverage is lower than the actual fault coverage. The execution time of the algorithm is equal to the number of lines in the circuit. Heragu et al. (1995) have developed a new statistical technique for calculating delay fault coverage in combinational circuits. Fault-free simulation of randomly selected test vectors is done, and fault detection probability of each vector pair is calculated. A thirteen-valued algebra is used for simulation. After simulation of chosen vector, pair’s backward pass is done for observability calculation. The product of the rising (falling) controllability and rising (falling) observability of line l gives the rising (falling) fault detection probability of a path fault originating at l. Once detection probabilities are computed, the fault coverage is obtained. Only a fixed number of sampled paths are considered for fault coverage computation, and hence, an error of statistical estimates will result. But the computation time is smaller compared to fault simulators. Results given for largest ISCAS-85 (c7552) and full-scan versions of the ISCAS-89 benchmark circuits show that the savings in CPU time by vector sampling and fault simulation is much significant. Bose et al. (1993b) have proposed a path delay fault simulator for sequential circuits. Only the active paths are considered. Active paths are those that actually propagate the transition during a given input vector. The number of active paths depends on previous and current vectors and is a dynamic property of the circuit and input vectors. After simulation, the algorithm calculates the highest ranked sensitized path in the subtrees present at all nodes of the circuit. This information is maintained in one-bit flag, and an integer identifier called as maxpath is used to represent the path. If the flag is true then a sensitized path from that node to output exists and the maxpath uses the path count values available at each node of the circuit. The paths are computed using depth-first search algorithm. The fault simulator gives robust and non-robust fault coverage. For robust simulation, six-valued algebra is used and a new update rule (optimistic update theorem) is used for updating latches. Results for ISCAS benchmark circuits indicate that path pruning effectively decreases the number of faults to be scanned per vector. Gharaybeh et al. (1996) have proposed a path delay fault simulator for combinational circuits which does not enumerate all the paths of a circuit. They have used a data structure, called the path status graph (PSG), to efficiently hold the status of each path delay fault using flags in the circuit to represent whether or not the fault is tested. The status of a path delay fault is ‘true,’ if all path edges are ‘true,’ and ‘false,’ if at least one path edge is ‘false’. PSG retains all or part of the reconverging fanout structure of the circuit. Hence, the PSG eliminates the need for tracing individual paths. Instead, fanout-free sub-paths are traced. Experimental results indicate bet-

28

2 Delay Fault Testing of VLSI Circuits

ter efficiency of fault coverage for singly testable path delay fault using non-robust detection criteria. Kapoor (1995) has proposed a delay fault simulator for calculating exact fault coverage. He has used a set of consecutively numbered path delay faults which can be represented as a closed interval over a pair of integers. A tree-based data structure is used to store and manipulate these intervals. During the path delay fault simulation, newly tested path delay faults, represented as intervals, are merged into existing intervals thus reducing the memory requirement efficiently. Although their algorithm has worst-case performance, the simulator is efficient in the sense the memory and time requirement is O (1). Pomeranz et al. (1992) have proposed a simulator for path delay faults in sequential circuits where test sequences are applied under multiple clocking schemes, allowing fast simulation for a given test sequence. The circuit is initialized to the desired state using a slow clock, and fault is activated using a fast clock, and if fault is present, the faulty values are observed at the primary outputs or latched in the memory elements using slow clock. They have used a path representation scheme in which all paths need not be enumerated. When a new path delay is detected, the number associated with the path is computed and compared with the list of numbers already stored, and the number is stored if it is not found in the list of tested faults. Thus, comparison of sequences of line numbers is avoided when determining the fault coverage of a test set. Their simulator simulates in parallel the set of all clocking schemes with a single fast clock cycle in each for a given input sequence. The simulator also determines the minimal number of clocking schemes, using multiple fast clock cycles to achieve maximum fault coverage for a given input sequence. This allows the algorithm to maximize the fault coverage and minimize the clocking schemes. Majhi et al. (1996) have developed a path delay fault simulator for delay testing of combinational logic circuits. Their simulator generates both robust and non-robust tests for path delay faults. They have used a rule-based approach to identify all robust and non-robust paths tested by two pattern test, while backtracking from primary outputs to primary inputs in a depth-first manner. Rules are formed to identify likely glitches which propagate through the circuit. Chakraborty et al. (2000) have proposed simulator for path delay faults in sequential circuits. They have suggested separate algorithms for the variable clock and rated clock modes. In the variable clock mode, a fault is designated by three items: path, transition type, and vector number at which the transition propagates through the path. A separate fault effect is produced at each activation of a path. In the ratedclock mode, all the activations of a path are treated as effects of the same fault. Based on various assumptions about the initial states of flip-flops, two fault models are suggested for fault simulation of path delay faults. They have used a differential fault simulator and thirteen-valued algebra. Their simulator has been used to select test points in self-test circuits to increase the path delay fault coverage of pseudorandom vectors. Using the binary fault simulator developed by Majni et al. (1996), the Jayanthy et al. (2008) have developed genetic algorithm-based ATPG for path delay faults. First step in path delay fault simulator is to identify the total number of primary

2.4 Test Generation Methods for Path Delay Fault Model

29

inputs and outputs. After this, level of the circuit and total number of gates in that are obtained. Next, the total number of paths in the circuit is calculated using the depth-first search algorithm which uses recursive search procedure. The entire circuit paths are examined using the tree data structure. This tree takes the primary input as a parent then the next level as its child. This process continues until it reaches the primary output. The paths of the circuit are saved in a text file. For finding the robustness of the path, it is necessary to trace backwards that is from primary output to primary input. So with this tree structure, the backward trace is also done. Test vector pairs were generated using genetic algorithm, and the number of robust and non-robust paths is found out. The number of logical path delay faults modeled is twice the number of physical paths present in the circuit since the rising and falling transitions are considered at the source of each path. Once a path fault is detected by a vector pair, it is added to the list of detected faults to keep track of the fault coverage. Figure 2.7 shows the flowchart of GA-based test generation algorithm. Fitness is a quantity related to the chromosome, which serves to enable comparison between chromosomes. The fitness function F1 is used.   F1  [µnew ]/ µtotal − µpast

(2.1)

µnew includes path delay fault tests detected only by the test vector pair applied at present, µtotal includes the total number of path delay faults and µpast includes the path delay faults detected at past. The delay fault simulator and genetic algorithm-based test generator are implemented in Visual C++. For evaluation, ISCAS85 benchmark circuit c17 and the circuit shown in Fig. 2.8 were used. For GA, rank-based selection method is used. In all the experiments, the default crossover probability is assumed to be 2 and the mutation probability is assumed as 0.02. The default size of population is assumed to be 10. The initial population is generated randomly, and then, GA is used to optimize the population for 9 generations and the total number of applied test applied test vector pairs is 9 * 5  45 vector pairs. Experimental results gave 100% fault coverage for the c17 (total path delay faults  22) with an execution time of 0.01 s. 100% fault coverage is achieved in the second generation itself, and for circuit shown in Fig. 2.8 (total path delay faults  24), fault coverage 100% is achieved with simulation time of 0.047. For larger benchmark circuits, simulation algorithm takes high execution times.

2.4.2 Test Generation for Path Delay Faults Most test generators use a modified version of PODEM. Lin and Reddy (1987) have proposed a five-valued logic for generating robust tests for path delay faults. They have proposed a five-valued logic to represent the two

30

2 Delay Fault Testing of VLSI Circuits

Start

Generate random iniƟal populaƟon of test vector pairs

Perform a simulaƟon using Binary logic PDF simulator

Any new PDF detected by the test vector pair enter into the resulted test set

Yes

Is the stop condition saƟsfied?

End Calculate the fitness for every test vector pair in the population

Generate next generation of population using genetic operation

Fig. 2.7 Flowchart of simulation-based test generation algorithm

vectors and used a branch-and-bound algorithm to find a robust test, for a given fault. They have formulated necessary and sufficient conditions for robust testing of path delay faults in circuits consisting of simple gates. They have devised that existence of fully transitional path test is neither necessary nor sufficient for robust testing of a path delay fault. Patil and Reddy (1989) have used PODEM-like algorithm and the heuristics specified by Lin and Reddy (1987) to derive tests for path delay faults. The path delay test generation algorithm by Lin and Reddy (1987), using multiplevalued logic to find robust tests, has been further improved by Fuchs et al. (1991). They have proposed automatic test generation algorithm for path delay faults based

2.4 Test Generation Methods for Path Delay Fault Model

31

Fig. 2.8 Circuit for evaluating the fault coverage

on a ten-valued logic. Their test generator is capable of detecting both robust and non-robust faults. A new path sensitization procedure is used, which is capable of efficiently identifying large numbers of path faults as redundant. If a given subset of paths is not testable, the algorithm switches to the next set of faults and thus generates tests for all testable path delay faults and also identifies redundant paths. They have also proposed a new path selection procedure which exploits value assignments in order to select paths that can be sensitized. The advantage of their method is that their algorithm is the fastest branch-and-bound procedure reported for path delay fault test generation. The disadvantage is that large memory is required for storing path tree for large circuits. This method is very effective in poorly testable circuits, but many faults have to be dealt with separately in those circuits that are highly testable. Bhattacharya et al. (1992) have proposed a new test generation technique for path delay faults in circuits employing scan hold-type flip-flops. They have used reduced ordered binary decision diagrams (ROBDDs) as the main data structure to represent the behavior of any sub-circuit of the circuit as well as to represent the fault detection constraints. General path activation conditions presented by Lin and Reddy (1987) are used to generate the single input transition tests and non-robust tests. The test generation process consists of manipulation of Boolean functions and does not require enumeration of input patterns. The authors have considered only scan-holdtype latches and hence have considered only two time frames in which transition occurs. Two faults are considered for each path in the circuit. For each fault, two constraint functions, corresponding to the two time frames that constitute a transition, are evaluated. These constraint functions which are represented as reduced ordered binary decision diagrams are then manipulated using Boolean algebraic operations. If the constraint function in the second time frame is non-null, then the algorithm does a robust test generation for the path delay fault. A robust test can be fully transitional path tests or single input transition tests. If a robust test cannot be found, then test generation algorithm proceeds with finding non-robust test for path delay faults as in Lin and Reddy (1987). Boolean algebraic manipulation of the constraint functions guarantees that if neither robust nor non-robust tests exist, the fault is undetectable. Since test generation process consists of manipulation of Boolean functions, the

32

2 Delay Fault Testing of VLSI Circuits

method is faster than branch-and-bound algorithms. The disadvantage is the memory requirement for storing the binary decision diagrams may be high for large circuits. Pomeranz et al. (1993) have proposed a non-enumerative test generation method for path delay faults in combinational circuits. They have not considered all the paths; instead, only single lines are considered. By propagating transitions robustly through parts of the circuit, a large number of path delay faults can be detected. Their algorithm identifies sub-circuits which have large numbers of paths going through them that can be tested at the same time. This is done by using labeling techniques that consider only lines and not paths of the circuit under test. The labeling algorithm backtraces the circuit from primary outputs to primary inputs, assigning label to every line l that is equal to the number of paths from line l to the primary outputs. The sum of the labels assigned to the primary inputs gives the number of paths. Once the sub-circuit is selected, test generation objectives are found. Once satisfied, these objectives are used to generate a test that detects a large number of path delay faults. The fault simulation algorithm used in Pomeranz et al. (1992) is used to find the number of path delay faults detected by a two-pattern test. The advantage of their test generator is that it can be used to test circuits with large numbers of detectable path delay faults. The disadvantage is that their method provides a pessimistic estimate of robust path delay fault coverage. Further, the algorithm is most useful in highly testable circuits, but may not succeed in finding delay faults in poorly testable circuits. Bose et al. (1993a) have proposed compact delay tests for path delay faults. They have used a twenty-three-valued logic system. This logic system is complete, and the signals can have minimum restrictions for satisfying path activation requirements. They have used the path numbering scheme which is used in Bose et al. (1993b). The test generation is similar to PODEM-like branch-and-bound search for test. Test generation technique consists of selecting an untested fault and generating a twovector sequence to sensitize the fault. This fault is called as primary fault. If any input is unspecified or partially specified, then it is assigned a basic or composite value that is a subset of the currently assigned composite value such that they can test the secondary faults also. The inputs thus give tests for both the primary and secondary fault. Thus, the test generation algorithm makes a cautious choice of secondary faults for further sensitization. The disadvantage of the proposed algorithm is multivalued algebra which is used as the only guiding mechanism. There is no thought for circuit connectivity. For few circuits, the number of backtraces is greater than the number of secondary faults that are detected. Fuchs et al. (1994) have proposed a recursive selection and sensitization algorithm for path delay faults for combinational- and scan-based sequential circuits. The authors have shown that their algorithm can generate tests for path delay faults effectively in both highly testable and poorly testable circuits. Their algorithm makes use of the fact the paths in a circuit usually have sections in common. To reduce the number of value assignments during path sensitization, the common sub-paths are sensitized only once. Without enumerating all the paths of the circuit, the untestable faults are identified. Five test classes are introduced, and the algorithm derives a composite logic system for each class such that the conflicting values assignments are detected early. The authors have made a comparison with the other existing algo-

2.4 Test Generation Methods for Path Delay Fault Model

33

rithms and showed that their algorithm detects a significantly larger number of path delay faults in a lesser amount of time. The disadvantage is that since the algorithm still depends on path sensitization and backtracing, it can have evaluation conflicts and thus requires iteration several times. Agrawal et al. (1992) have suggested a test generation for delay faults in non-scan circuits. Their algorithm augments the circuit net list such that the single stuck fault testing is the same as testing of the path delay fault. The logic that is added to the net list consists of combinational gates that are driven by the signals feeding the gates on the path and a pair of flip-flops. In this logic, a stuck-at-1 fault is activated and its effect is latched into the destination flip-flop of the path only when all signals along the path are set to the states as required for a path delay test. The fault effect is then propagated to a primary output. Their algorithm combines a path generation technique and modified version of sequence test generator (Ghosh et al. 1991). The disadvantage of their technique is that for large sequential circuits the execution time is high. Chakraborty et al. (1992) have suggested a test generation method for path delay faults in random logic sequential circuits. The authors have used a thirteen-valued algebra to compute robust and non-robust tests. An additional hazard condition is introduced which represents multiple transitions between vectors thus the tests are independent of gate delays. Three path delay fault models are proposed and examined based on the assumptions on the initial state of the flip-flops for a given vector sequence. The advantage of the algorithm is that it can test any type of sequential circuit irrespective of its structure. Their complexity of test generation is reduced as clock is run at rated speed only during path activation. They have implemented the delay test generation algorithm by modifying an existing test generation algorithm, Gentest (Cheng and Chakraborty 1989). Chakraborty et al. (1997) have proposed variable clock method for test generation of path delay faults where only one vector that propagates the transition through the path is applied with rated clock. All other vectors are applied at slow speed to guarantee fault-free initialization and fault effect observation. The advantage is that the generation of tests is simplified since the slow clock allows the faulty circuit to behave like a fault-free circuit. But the disadvantage is that the test application time becomes large. Bose et al. (1998) have suggested a rated-clock test method for delay fault test generation. Three-vector algebra is used to activate the fault from input to output, and a forty-one-valued algebra is used for effective backward justification. Results have been given for much larger benchmark circuits compared to their previous work (Bose and Agraval 1995). A difficulty with this technique occurs when the rated-clock speed exceeds the capability of the test equipment. Yihe and Qifa (2001) have suggested a path delay fault test generation technique using fault simulation and genetic optimization. They have used a parallel vector fault simulator for simulating several vectors simultaneously. The algorithm uses a fourvalued logic path status graph for representing the circuit structure. An optimized test pattern is obtained by using genetic algorithm for searching the test vector space. Comparison with other test generation algorithm shows that this technique detects

34

2 Delay Fault Testing of VLSI Circuits

more path delay faults in reduced time. But the disadvantage of the algorithm is that in later stage of test generation when the delay fault coverage is high the efficiency of genetic algorithm is not obvious. A combination of fault simulation and genetic algorithm-based test generation methods with deterministic test generation will give better results.

2.5 Conclusion Various delay fault models along with their relative advantages and disadvantages are discussed. The test application schemes for delay faults in combinational and sequential circuits are presented in this chapter. Prior work on test generation and simulation of path delay faults for combinational and sequential circuits is presented.

References P. Agrawal, V.D. Agrawal, S.C. Seth, A new method for generating tests for delay faults in non-scan circuits, in Proceedings of 5th International Conference VLSI Design, pp. 4–11 (Jan 1992) D. Bhattacharya, P. Agrawal, V.D. Agrawal, Delay fault test generation for scan hold circuits using Boolean expressions, in Proceedings of 29th Design Automation Conference, pp. 159–164 (June 1992) S. Bose, V.D. Agrawal, Sequential logic path delay test generation by symbolic analysis, in Proceedings of the Asian Test Symposium, Bangalore, India, pp. 353–359 (Nov 1995) S. Bose, P. Agrawal, V.D. Agrawal, Generation of compact delay tests by multiple path activation, in Proceedings of IEEE International Test Conference, pp. 714–723 (1993a) S. Bose, P. Agrawal, V.D. Agrawal, Path delay fault simulation of sequential circuits. IEEE Trans. VU2 Syst. 1(4), 453–461 (1993b) S. Bose, P. Agrawal, V.D. Agrawal, A rated-clock test method for path delay faults. IEEE Trans. VLSI Syst. 6, 323–331 (1998) T.J. Chakraborty, V.D. Agrawal, M.L. Bushnell, Delay fault models and test generation for random logic sequential circuits. Des. Automat. Conf. 165–172 (1992) T.J. Chakraborty, V.D. Agrawal, M.L. Bushnell, Path delay fault simulation of sequential circuits. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 8(2) (2000) T.J. Chakraborty, V.D. Agrawal, M.L. Bushnell, On variable clock methods for path delay testing of sequential circuits. IEEE Trans. Comput. Aided Des. 16, 1,237–1,249 (1997) W.-T. Cheng, T.J. Chakraborty, Gentest: an automatic test generation system for sequential circuits. Computer 22, 43–49 (1989) D. Das, N. Touba, Reducing test data volume using external/LBIST hybrid test patterns, in Proceedings of IEEE International Test Conference, pp. 115–122 (Oct 2000) R. Dorsch, H.-J. Wunderlich, Accumulator based deterministic BIST, in Proceedings of IEEE International Test Conference, pp. 412–421 (Oct 1998) K. Fuchs, F. Fink, M.H. Schulz, Dynamite: an efficient automatic test pattern generation system for path delay faults. IEEE Trans. Comput. Aided Des. 10, 1323–1335 (1991) K. Fuchs, M. Pabst, T. Rossel, RESIST: a recursive test pattern generation algorithm for path delay faults considering various test classes. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 13(12) (Dec 1994)

References

35

A. Gharaybeh, M.L. Bushnel, V.D. Agrawal, An exact non-enumerative fault simulator for path delay faults, in Proceedings of IEEE International Test Conference (Oct 1996) A. Ghosh, S. Devadas, A.R. Newton, Test generation and verification for highly sequential circuits. IEEE Trans. CAD, 10(5), 652–667 (1991) K. Heragu, V.D. Agrawal, M.L. Bushnell, Fault coverage estimation by test vector sampling. IEEE Trans. Comput. Aided Des. Integ. Circ. Syst. 14(5) (1995) G. Hetherington, T. Frayars, N. Tamarapalli, M. Kassab, A. Hassan, J. Rajski, Logic BIST for large industrial designs: real issues and case studies, in Proceedings of IEEE International Test Conference, pp. 458–466 (Sept 1999) F.F. Hsu, K.M. Butler, J.H. Patel, A case study of the Illinois scan architecture, in Proceedings of IEEE International Test Conference, pp. 538–547 (2001) S. Jayanthy, M.C. Bhuvaneswari, T. Kavitha, Simulation based ATPG for path delay faults in digital circuits using genetic algorithm, in Proceedings of the National Conference on Adaptive Sensors and Intelligent Systems NCASIS’08, pp. 80–84 (Nov 21st and 22, 2008) B. Kapoor, An efficient method for computing exact path delay fault coverage, in Proceedings of EuroDAC, pp. 516–520 (Mar 1995) G. Kiefer, H. Vranken, E.J. Marinissen, H.-J. Wunderlich, Applications of deterministic logic BIST on industrial circuits, in Proceedings of IEEE International Test Conference, pp. 105–114 (Oct 2000) A. Krstic, K.T. Cheng, Delay Fault Testing for VLSI Circuits (Kluwer Academic Publishers, Boston, Dordrecht, London, 1998) M.P. Kusko, B.J. Robbins, T.J. Koprowski, W.V. Huott, 99% AC test coverage using only LBIST on a 1 GHz IBM S/390 z Series 900 Microprocessor, in Proceedings of IEEE International Test Conference, pp. 586–592 (Oct–Nov 2001) C.J. Lin, S.M. Reddy, On delay fault testing in logic circuits. IEEE Trans. CAD. 6, 694–701 (1987) A.K. Majhi, J. Jacob, L.M. Patnaik, V.D. Agarval, A novel path delay fault simulator using binary logic. VLSI Des. Int. J. Cust. Chip Des. Simulat. Test. 4(3), 167–180 (1996) S. Patil, S.M. Reddy, A test generation system for path delay faults, in Proceedings of International Conference on Computer Design, pp. 40–43 (1989) I. Pomeranz, S.M. Reddy, An efficient non-enumerative method to estimate path delay fault coverage. Proc. Int. Conf. Comput. Aided Des. (1992) I. Pomeranz, L.N. Reddy, S.M. Reddy, SPADES: a simulator for path delay faults in sequential circuits, in Proceedings of Euro-DAC, pp. 428–435 (Sept 1992) I. Pomeranz, S.M. Reddy, P. Uppaluri, NEST a Non-Enumerative Test Generation Method for Path Delay Faults in Combinational Circuits (1993) M.H. Schulz, K. Fuchs, F. Fink, Parallel pattern fault simulation of path delay faults, in Proceedings of 26th DAC, pp. 357–363 (June 1989) G.L. Smith, Model for delay faults based upon path, in Proceedings of IEEE International Test Conference, pp. 342–349 (Nov 1985) S. Yihe, W. Qifa, FSIMGEO: a test generation method for path delay fault test using fault simulation and genetic optimization. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 225–229 (2001) J.A. Waicukauski, E. Lindbloom, B. Rosen, V. Iyengar, Transition Fault Simulation IEEE Design and Test, pp. 32–38 (April 1987) L.-T. Wang, C.-W. Wu, X. Wen, VLSI Test Principles and Architectures: Design for Testability (Morgan Kaufmann, San Francisco, CA, USA, 2006)

Chapter 3

Test Generation Algorithms for Crosstalk Faults

3.1 Introduction Several design techniques such as repeater insertion, shielding techniques, device sizing, and net ordering have been proposed for elimination and minimization of crosstalk. The most commonly known method is shield insertion. In this design technique, the victim and aggressor are separated from each other using shield wires which are tied to either ground or power supply (Kolodny 2006). In order to reduce noise and unpredictable delays, ground or power lines are placed at the sides of a victim. This design technique, however, results in more power consumption, increases routing area, and increases complexity in routing interconnects. Buffer/repeater insertion technique is used to reduce delay between the interconnects, thus minimizing the coupling effects. The delay of a signal wire is related to the length of the wire; hence in order to reduce the wire lengths, buffers are inserted. Buffer can also be used to decouple coupling effects, thus reducing crosstalk noise. But splitting the wire into shorter segments makes the delay rise linearly. Buffer insertion is usually done during the post-layout stage. To optimize the performance, if the number of buffers inserted is increased, it becomes impractical to insert hundreds of thousands of buffers when the entire routing region is occupied by routing wires. In device sizing technique, drivers of the aggressor wires are downsized for noise reduction, utilizing the interconnect information extracted from the routed layouts. But downsizing degrades robustness of the device. Upsizing drivers increase power dissipation. Further, it is not possible to predict beforehand the full range of process variations and manufacturing defects which could aggravate the capacitance coupling effects. Redesign could also be very costly in terms of design effort (Ganeshpure and Kundu 2007a). Further crosstalk effects along with weak spot defects produce timing errors that need to be addressed during testing. Hence, there is a necessity to develop testing techniques for manufacturing defects that produce crosstalk effects. Accurate modeling and test generation of intercon-

© Springer Science+Business Media Singapore 2019 S. Jayanthy and M. C. Bhuvaneswari, Test Generation of Crosstalk Delay Faults in VLSI Circuits, https://doi.org/10.1007/978-981-13-2493-2_3

37

38

3 Test Generation Algorithms for Crosstalk Faults

nect delay due to crosstalk become increasingly important in the design of highperformance integrated circuits (Chen et al. 2002a).

3.2 Test Generation Algorithms Techniques used to detect the delay faults can be broadly classified into indirect test methods (correlation based) and direct methods. However, aggressive scaling of CMOS technology with reductions in supply voltage, threshold voltage, and effective channel length makes indirect methods less effective. There has been increased focus on direct test techniques which rely on (i) ATEs with improved capabilities/higher frequencies and (ii) on-chip test logic like built-in self-test (BIST), design for testability (DFT), on-chip timing analysis, and delay fault testing circuitry for device under test (DUT) chip for improved testability. The use of on-chip testing circuitry allows for at-speed testing which is required to ensure exact performance in terms of timing and characterization of chips. Incorporation of the self-test capability increases the silicon area required to implement the chip, thus escalating the cost of manufacturing chips. Also, the hardware added to the circuit increases the delays of the usual circuit path reducing the speed of the normal operation of the circuit. Hence, testing for delay defects using ATE appears to be the better alternative, since it gives a minimum set of test patterns required to test the circuit under a particular fault model. Testing consists of applying a set of test vectors to the inputs of the circuit under test and analyzing the output responses of the circuit. Any discrepancy in the output response indicates the presence of fault. Given today’s very large designs, the test process heavily relies on automation. Various test pattern generation (ATPG) and pattern grading tools have been used to reduce the product time to market (Cheng and Krstic 1999). The objective of ATPG is to obtain a set of test vectors that will detect the defects that arise during the manufacturing process. A fault simulator is used to evaluate the quality of tests in terms of fault coverage, number of transitions, etc. ATPG for digital circuits is a major research topic. Both deterministic and simulation-based algorithms have been proposed. Deterministic test generation can be fault oriented or fault independent. In a fault-oriented test generator, tests are generated for specified faults of a fault universe. Fault-independent test generator works without targeting individual faults. In a deterministic algorithm, tests are generated based on a model of the circuit and a given fault model. Efficient test generation algorithms have been devised for crosstalk delay faults in combinational circuits. Most of the test generators incorporate a modified path-oriented decision making (PODEM) algorithm at gate level to generate test vectors for crosstalk delay faults between local interconnects. Test vectors were generated to activate the required signal transitions at the victim and aggressor pairs and propagate the fault effects to the circuit outputs.

3.2 Test Generation Algorithms Table 3.1 Eleven-valued logic

39 Symbols

Description

S0

Steady 0

S1

Steady 1

T1

Rising transition

T0

Falling transition

P0

Positive pulse

P1

Negative pulse

SU T1

Speedup rising transition

SU T0

Speedup falling Transition

SD T1

Speed-down rising transition

SD T0

Speed-down falling transition

X

Unknown value

Chen et al. (2002a) have used a deterministic algorithm using a modified version of PODEM to detect crosstalk faults. The objective of their ATPG is to generate test vector pairs that produce the required crosstalk effect and propagate the effect to the primary output to produce either a logic error or the maximum noise effect, under given timing assumptions and requirements. They have developed capacitive coupling model to estimate the crosstalk effects based on certain circuit parameters and signal timing properties. Using static timing analysis, the timing window of transitions on the aggressor line (A) and the victim line (V) is obtained. They have considered crosstalk slowdown effects only. The symbol values used in their system are given in Table 3.1. The five objectives in creating a crosstalk slowdown effect are as follows: a weak signal on the victim line, a slow rising/falling transition on the aggressor line, a strong signal on the aggressor line, a falling/rising transition in the victim line, and a path that propagates the crosstalk effect to the primary output. Based on these objectives, conditions are determined for maximizing the crosstalk effect. When both the aggressor and victim lines have transitioned at the same time, then maximum crosstalk slow down occurs. A late transition is created on the victim line, which is delayed due to crosstalk, and propagated through the critical path to a primary output to cause a timing delay. The pseudo-code for test generation algorithm is shown in Fig. 3.1. Simulation plays a crucial role in the design and test of integrated circuits. Digital logic simulation involves the construction of a computer model of the hardware that is being designed and execution of the model for a set of input signals and observation of output signals. Simulation can be done at various levels of abstraction: device level, circuit level, switch level, gate level, register transfer level, and system level. The basic methods to simulate a circuit at the gate level are compiler-driven simulation and event-driven simulation. The output of any physical gate will take some time to change after an input has changed. Delays effect the correct functioning of the circuit (Gerez 1999). Compiler-driven simulation is the one that executes a

40

3 Test Generation Algorithms for Crosstalk Faults

Test generation(fault list) Begin Check the transition Timing windows do if(the desired transition is set on the aggressor line and side fanins are set and if desired transition is set on the victim line ) begin

if(can a timing violation be created at PO) begin

Crosstalk effect observed; record the vector; update the values of gates on the propagation path for branch & bound purpose if(Are all PI combinations covered?) begin if(any vector recorded) list there corded vectors else else

end

noise effect undetectable

begin Backtrack and change PI assignments Imply( ) end

else

end If(noise is dropped due to branch & bound?) If(Can the initial objective line under current assigned value of PI be selected?) begin Set the objectives( ) Backtrace( ) Imply( ) end else begin Backtrack and change PI assignments Imply( ) end else

Fig. 3.1 Pseudo-code for test generation algorithm

3.2 Test Generation Algorithms

41 begin Set the objectives( ) Backtrace( ) Imply( ) end

end else begin if( Can the initial objective line under current assigned value of PI be selected?) begin Set the objectives( ) Backtrace( ) Imply( ) end else begin Back track and change PI assignments Imply( ) end while (fault count!=0))

Fig. 3.1 (continued)

compiled code model and is quite faster. But it deals only with limited delay models. An event-driven simulator uses a structural model of a circuit to propagate events and can deal with very general delay models at the expense of computer time. In event-driven simulation, only those signals that are changing are computed. Fault simulator consists of simulating the circuit in the presence of fault. It is used to determine the ability of a test to detect faults for a given fault model of the design under consideration. Fault list is created for the design based on the fault model. Then, reduced set of fault list is obtained. The faults from the target fault list are injected into the model by the fault simulator, and after simulating the given tests, the fault coverage is repeated. If the fault coverage is high, the process is terminated. If the desired fault coverage is not obtained, the ineffective tests are discarded and the new tests are added. In some cases, the existing tests are modified and new tests are specifically written for hard to test faults in the design. The general simulation techniques are serial, parallel, deductive, and concurrent. The serial simulation is the simplest method of simulating faults, and it consists of transforming the model of fault-free circuit M into a faulty model MF by introducing the fault F and simulating MF. The entire process is repeated for each fault in the fault list. That is, the faults are simulated one at a time in a given time frame work. The other three techniques—parallel, deductive, and concurrent—simultaneously simulate the fault-free circuit and set of faults {MF}.

42

3 Test Generation Algorithms for Crosstalk Faults

Chary and Bushnell (2006) have proposed a simulation-based ATPG system, with a multiple-delay sequential fault simulator which uses three logic values (0, 1, and X) with glitch detection, for detecting crosstalk delay faults. The crosstalk fault list obtained consists of all possible interconnect pairs. Static timing analysis was used to find the target fault list because some of the faults cannot be tested. The circuit extractor is used for parasitic extraction of resistance and capacitance. An analog macro-model is used to provide analog effects due to faults during digital simulation. The fault list included the aggressor and victim names, fault type, capacitance per unit length, coupling capacitance value, and impedance of drivers and loads of both lines. Signals on a path have two delays, namely switching and propagation delay. The time for an input signal to reach output of a gate is called as the switching delay. The time taken by a signal transition at a gate output to reach the input of a fanout gate is the propagation delay of the signal. A multiple-delay model is used where each gate is assigned a rising and a falling delay. To obtain these delays, each gate type is simulated using the Cadence SpectreTM analog simulator. Normally, a zero delay or unit delay simulator produces glitch in the output, but since gate delays are considered, the simulator removes glitches that are narrower than the gate delay. For calculating the propagation delay, they have considered fanout nodes that transmit the signal from the stem to each branch with some delay. Thus, if a stem has n fanouts, it will have n delays. The ATPG algorithm is shown in Fig. 3.2. An analog macro-model is used to find the delay that is to be injected into the simulator, and logic simulator is delayed by the injected delay. Faults are read from the fault list, and circuit is simulated. The output for faulty circuit and fault-free circuit is observed. During propagation, the signal may get delayed and cause an incorrect value to be observed at the primary output or a pseudo-primary output. Those faults are considered to be detected and removed from fault list. The test generation continues till all the remaining faults are tested for all the test sequences.

3.3 Test Generation for Crosstalk Pulses 3.3.1 Deterministic Algorithms In generating test patterns for a crosstalk pulse fault, the logical value change 0-to-1 or 1-to-0 is applied to the affecting line, and the interference pulse at the affected signal line is propagated to primary outputs after the transition point. Therefore, to detect a crosstalk fault, two successive test vectors are required for all the test generation algorithms and the algorithm becomes complex. The two vectors can be generated separately, or a different logic system can be used such that the vectors can be derived concurrently with a single copy of the circuit. When the two vectors are generated separately, three-valued logic is used where the value of each signal will be 0, 1, or X. If two vectors are to be generated simultaneously, a

3.3 Test Generation for Crosstalk Pulses

43

Start Simulate the fault free circuit and find out the clock period.

End Yes No

Read the next fault from the target fault list

Simulate fault free and faulty circuit

No

End of test sequences?

Yes Is fault list empty

Read the next test vector

Get the skew and pass it to the macromodel

Fault injection by the amount of delay from macromodel

If faults are detected remove from fault list

Fig. 3.2 Fault simulation-based ATPG

value system different from the three values system can be used to represent values over two vectors. S0 and S1 are signal values which represent steady logic ‘0’ and steady logic ‘1’ in the first and second test vectors, respectively. T0 represents logic ‘1’ in the first test vector and logic ‘0’ in the second test vector. T1 represents logic ‘0’ in the first test vector and logic ‘1’ in the second test vector. These vectors are required to produce a weak driver on the victim line, a fast signal transition on the affecting line, and a propagation path that sustains/increases the noise effect until it reaches an output. In most of the papers (Chen et al. 1997, 1998; Rubio et al. 1994), a modified version of PODEM algorithm is run as the core to obtain a two-vector test in VLSI circuits for a crosstalk pulse fault by forcing values to the victim and aggressors nodes and propagating the possible interference to the primary output nodes. Rubio et al. (1991) have generated test patterns for logic crosstalk faults in combinational circuits. An algebraic method is applied to generate a two-vector test to test crosstalk faults. An input sequence is derived that forces a determinate value to the affected nodes and incites a transition of the affecting lines allowing the propagation of the possible interference to the primary output nodes. Rubio et al. (1994) had presented a test generation algorithm using a simplified lumped RC model for crosstalk between a pair of coupled lines. In their case, the crosstalk effect manifests as a pulse on the line whose input is held constant. These models characterize crosstalk effects as static hazards having a full voltage swing and result in an overestimation of noise strength. Since crosstalk is a finite energy

44

3 Test Generation Algorithms for Crosstalk Faults

transient effect, test vectors generated using the above-said models may not truly propagate the noise to POs or flip-flops because of the inertia inherent to gates. To obtain a larger crosstalk effect at the output a model is proposed by Chen et al. (1997). They have started with a model in the frequency domain to obtain a closed form voltage transfer function quantifying the dependence of the pulse maximum amplitude, width, energy, and timing on the values of circuit parameters. This is then transformed to get expressions in the time domain. These expressions also characterize the speedup or slowdown of transitions due to crosstalk. These expressions show that the crosstalk pulse is directly proportional to the coupling capacitance and the ratios of the strengths of the drivers driving the two lines. They have showed that while the maximum amplitude of the crosstalk pulse reduces quickly as the rise–fall time of the input increases, the energy of the pulse is nearly independent of the input rise–fall time for a practical range of rise–fall time values. They have also discussed how test patterns can be derived for crosstalk pulse and crosstalk delay faults. In Chen et al. (1998), the same authors have proposed a mixed signal test generator that generates a two-vector test for crosstalk-induced effects, such as pulses, signal speedup and slowdown, in digital combinational circuits. They have developed a test generator that has static values in the side fanin like in PODEM as well as dynamic signals such as transitions and pulses, and timing information such as signal arrival times, rise–fall times, and gate delay. They have also used an analog cost function to guide the search process. Even when several objectives are to be satisfied for the detection of fault their test generation algorithm processes only one objective at time. This causes unnecessary backtracks and reduces ATPG efficiency, particularly when the limit on the number of backtracks is low. Multiple crosstalk effects have been ignored.

3.3.2 Simulation-Based TG Test generation using this deterministic algorithm is highly complex and timeconsuming. Simulation-based test generation has been used to evade lengthy execution times of deterministic algorithms and to reduce complexity of test generation. In particular in simulation-based approach, processing occurs in the forward direction only. Complex component types can be easily handled. Development time is greatly reduced. Fault simulator is used in Itazaki et al. (1997a), Phadoongsidhi et al. (2002), Itazaki et al. (1997b), and Phadoongsidhi and Saluja (2003) to develop test vectors for crosstalk pulse faults in synchronous sequential circuits. In all the papers, the combinational model for a sequential circuit is constructed by regenerating the feedback signals from earlier time copies of the circuit. Thus, the timing behavior of the circuit is approximated by iterative combinational level. The simulators take an aggressor as a primary input, primary output, or output of a gate in the circuit. The victim can only be a flip-flop. All the simulators use three-valued logic.

3.3 Test Generation for Crosstalk Pulses

45

Itazaki et al. (1997a) have considered crosstalk fault as unexpected strong capacitive coupling between one data line and clock lines because generated crosstalk pulses on data lines can be eliminated by a clocking. They have assumed two crosstalk faults. One is the crosstalk fault from one data line to one clock line of every FF, and the other is the crosstalk fault from one data line to all clock lines for all FFs. The simulator uses the concept of waveform simulation to store the changes in logic values of a node that occur within a time frame. Logic value at each time step is recorded in a bitmap buffer. For each time frame after good circuit simulation, waveform buffers associated with the fault are examined to determine whether the target is a crosstalk pulse fault. If the pulse-generating condition is satisfied, simulation of subsequent time frames of faulty machines is done until resulting fault is observed in one or more primary outputs. Fault is captured on the data line and simulated to the primary output using test sequences similar to stuck-at faults. Since their scheme uses a unit delay for gates, critical timing conditions will change according to physical conditions or practical differences such as temperature or variations of delay time for each gate. They have used all combinations of coupling faults, and test vectors are also random vectors. Excessive time is required to simulate most of the benchmark circuits. A simple update of this simulator with modifications suitable for crosstalk fault diagnosis tool is described in Takahashi et al. (2001). A hold time is introduced to determine the value that is captured in the flip-flop. The method compares observed responses and simulated outputs at primary outputs to locate an actual fault. If the simulated output and observed responses are the same, then the simulated fault is added to the list of suspected faults. Suspected faults are a list of faults which are consistent with the observed responses of the circuit. If not, simulated fault is removed from set of suspected faults. In order to reduce CPU time, they have used stored state information of previous time frames to calculate primary output values of present time frame. The CPU time is still high for most of the benchmark circuits The limitations of the above simulators are alleviated by Phadoongsidhi et al. (2002) who have proposed a concurrent simulation technique for detection of crosstalk-induced pulse faults. Gates are assumed to have unit delay. Each node in a circuit has a 32-bit buffer which stores values for fault-free simulation and values of faulty simulation. Hence, multiple faults are concurrently processed in each time frame, and faulty machines could be dropped and added at any time during the course of simulation. But then memory is very high. Further, the large number of crosstalk faults took a large amount of CPU time. Vectors provided by FASTEST are used for generating test sequences. Thus, their simulation algorithm leads to a significant reduction in simulation time with higher memory consumption as a trade-off. Itazaki et al. (1997b) have proposed a combined algorithmic test generator with the fault simulator for crosstalk faults. They have used FASTEST as the base test generation algorithm to generate the setup and propagation patterns. In order to check the validity of patterns, logic simulation is performed for the propagation pattern generated by FASTEST. However, they have not considered multiple aggressors. The fault coverage is also very low. Phadoongsidhi and Saluja (2003) have proposed a fault simulation method based on event-driven simulation. All the papers discussed above have logic waveform sen-

46

3 Test Generation Algorithms for Crosstalk Faults

sitization on each line which is computationally complex and results in more memory usage. Hence, in their work logic event-driven simulation is extended for fault excitation and fault grouping. Events lists are separated according to the direction of transition. Good circuit simulation is done, and candidate fault group is formed by determining the victim aggressors which satisfy a set of transformation rules and which are able to cause capturing of a faulty value at the output of victim flip-flop. Faults from candidate fault group are simulated, and faults are said to be detected if there exists at least one primary output at which good and faulty machines have different values. But since the test vectors generated were by FASTEST and HITEC, the fault coverage was less and CPU time was still high.

3.4 Test Generation Techniques for Crosstalk Delay Faults Many automatic test generation algorithms are developed for generating tests for crosstalk faults. The objective of test generation for crosstalk fault is to generate a twovector pair that should be applied to the primary input of integrated circuit to identify the faults that affect the functionality of the device due to fast signal transitions in the adjacent interconnects. The two vectors can be generated separately, or a multiple logic system may be used such that the two vectors can be derived concurrently with a single copy of the circuit. When the two vectors are generated separately, three-valued logic systems can be used. If two vectors are to be generated together, a multiple-valued system can be used to represent values over two vectors. Both deterministic and simulation-based algorithms have been proposed for testing crosstalk delay faults. Deterministic test generators produce tests by processing a model of the circuit. This model is the structural model of the design. The structural test generation algorithms employ heuristics to guide the search space. Simulation-based techniques normally involve generation of random vectors and employ the results provided by the fault simulator to investigate the search space. Simulation-based test generation has been used to avoid long execution times of deterministic algorithms and to lessen the complexity of test generation. Test generation time can be decreased using efficient fault simulators. Simulation-based technique can generate test for any circuit and any type of fault that can be simulated. Circuit timing can be taken into account. The disadvantage of this method is that it is not capable of identifying redundant or untestable faults. Another problem was in finding good heuristics to generate test vectors, and the test sets generated were much larger.

3.4.1 Deterministic Algorithms In most of the approaches, a modified version of PODEM algorithm is used for backtracing and sensitizing the path for propagation of fault effect to the primary output. Almost all the approaches use multi-valued logic.

3.4 Test Generation Techniques for Crosstalk Delay Faults

47

The mixed signal test generation algorithm developed by Chen et al. (1999) uses analytical models for timing analysis to find the target crosstalk faults. Before processing the test generation objectives for victim and aggressor, a timing-oriented backtrace is performed to check for compatible patterns at the gate inputs which create single transition within the specific timing windows. An eleven-valued logic is used. A branch-and-bound technique was proposed to reduce the search space as the algorithm implicitly explores all primary input combinations. Test vectors were generated for both types of capacitive coupling crosstalk noise, namely crosstalk pulse and crosstalk delay. However, this approach only generates patterns for a single aggressor affecting a target path. So it cannot propagate a maximal crosstalk-induced effect on a critical path. Further, their method was computationally complex. The same test generator is enhanced as XGEN by Chen et al. (2002b) which uses the same analytical models described in Sect. 1.5 for timing analysis and backtrace. Additionally, a cost function is evaluated that can guide the search for primary input assignments and as well as find a path from victim to primary output. The cost function consists of digital and analog part. In the digital part, controllability and observability measures are used to decide the paths. The analog part consists of measurement of gate strength, transistor gain, and load capacitance. The calculation of cost starts with primary output and traverse backward. The path chosen for propagating the noise delay has the lowest cost. But the authors have manually selected pairs of target faults. The entire fault universe was not taken into consideration. Only about 100 faults were selected for finding the efficiency of the test generation algorithm. In the enhanced version of XGEN suggested by Sinha et al. (2003), the propagating conditions were increased by including hazardous and non-hazardous values in the multi-valued logic. The method is computationally intensive. Hence, the test generation time is very high, and fault coverage increased only marginally. Sinha et al. (2008) have further enhanced their previous test generator by deriving a new fifty-seven-valued algebra. The modified ATPG procedure increases the fault coverage and proves more faults as being untestable. The method considers single element values called basis values, as well as many composite values made of multiple basis values. The assignment of a composite value to a circuit node indicates that any of the basis values comprising the composite value was possible. The use of composite values allows their ATPG method to postpone making a decision until one was absolutely necessary. This makes the search for a test pattern more efficient as it reduces backtracking by reducing the number of assignments that cause conflicts. The disadvantage of this method is that the test generation time is high. Further, the algorithm has considered only a single pair of victim line and aggressor line and hence cannot propagate a maximal crosstalk-induced effect along a critical victim path, which is more likely to cause delay test failure. A test pattern generation based on waveform sensitization is developed by Li et al. (2003) in which the signal on each line is assumed to be a waveform that consists of multiple transitions at different times. Static hazards and dynamic hazards are implied in waveforms. Nine-valued logic was used. For the fault to be propagated to the primary output, two parts of the circuit have to be sensitized. One is the longest path and the other is the subpath from the primary input to the aggressor line that is

48

3 Test Generation Algorithms for Crosstalk Faults

coupled with the longest path. The longest paths and critical paths are sensitized, and then, justification was done. Testing a path delay fault usually should not specify all the primary input values. Hence, the unspecified primary input values can be used to generate necessary inputs for crosstalk noises. But their fault coverage is very low. Only single victim/single aggressor pairs were considered. Further waveform sensitization method cannot generate tests for large benchmark circuits. A hybrid structural SAT-based solution developed by Bai et al. (2003) is used for multiple aggressor crosstalk problems. An implication graph is constructed that consists of logic variables and structural information to check for logic conflicts. The conflicts arise due to the values assigned to the victim lines, the aggressor’s lines, and the propagation path. If a logic conflict occurs, the algorithm will repeatedly search for the best subset of suitable aggressors based on weights assigned to aggressors. Once a set of aggressors are identified, a modified version of PODEM algorithm was used to generate test vectors that can justify the required logic value for the victim, activate the aggressors, and sensitize a propagation path for the fault to be propagated to the primary output. Shen et al. (2005) have proposed a non-robust test generation for crosstalk delay faults based on S-PCPDF model explained in Sect. 1.5. Using static timing analysis, a set of crosstalk delay faults is derived. The non-robust path delay test generation was modified to generate tests for crosstalk delay faults. Li and Li (2005) have suggested a test generation for crosstalk delay faults based on S-PCPDF model. A path delay conventional ATPG is enhanced to generate tests for crosstalk delay faults by adding constraints in the sub-paths. The number of target faults is reduced by two ways: one is based on constraints for on-path inputs and another based on prespecified states during generation of critical paths. Li et al. (2006) have proposed a robust test generation technique based on a single precise crosstalk-induced path delay fault model, S-PCPDF model. A ten-valued logic is used in test pattern generation. Fanout-weighted delay model is used for experimental evaluation. However, this approach only generates patterns for a single aggressor affecting a target path. So it cannot propagate a maximal crosstalk-induced effect on a critical path. Further, the algorithm is computationally complex. An aggressor maximization algorithm is proposed by Aniket and Arunachalam (2005) that maximizes the crosstalk effect by suitably activating the aggressors—victim pairs lying along any critical path. For a robust sensitizable path, the associated multiple aggressors/victim pairs are activated in a manner that will maximize the influence of the aggressor on the path to induce maximum crosstalk slowdown along a path. In their algorithm, backtracing is considered successful only if the collective crosstalk delay effects of the activated aggressor lines were greater than the collective delay effects of the deactivated aggressor lines. If the backtrace was successful, then the primary input assignment is accepted. The results obtained for benchmark circuits show that if their aggressor maximization algorithm is integrated into the test generation algorithm, the total crosstalk induced slowdown and speedup increase and decrease, respectively, for all the circuits. However, static timing analysis procedure used in their work does not use timing information.

3.4 Test Generation Techniques for Crosstalk Delay Faults

49

An ATPG in which a stuck-at fault ATPG is combined with a 0–1 integer linear program (ILP) for zero gate delay is developed by Ganeshpure and Kundu (2007b). The maximal aggressor activation is formulated as a linear programming problem, while the fault effect propagation was treated as an ATPG problem. The problems are separated by min-cut circuit partitioning technique. Single victim/multiple aggressors were considered. Both the logic circuit and the maximal aggressor weight equations were represented as ILP equations. Then, an ILP solver was used to solve simultaneous logic constraints for maximal aggressor switching requirement. The test generator was enhanced to incorporate integer gate delays Ganeshpure and Kundu (2007a). However, the selection of crosstalk faults is random. Palit et al. (2008) have developed a test generator for crosstalk delay faults where the test patterns were generated to activate both aggressor and victim individually and to propagate the crosstalk effect to at least one primary output. For example, if a 0 to 1 transition is required at aggressor line, vectors were derived for exciting both logic 0 and 1 separately. Once the vectors are derived for victims, aggressors, and propagation paths, the common vectors were collected separately before transition and after transition. Combining the vectors gave the transition test vector for crosstalk delay fault. The randomly chosen faults were manually injected into the circuit using Xilinx simulator. But the problem is collecting common transition vector to excite all aggressors concurrently was impossible. A test pattern generation procedure that combines path delay and transition delay fault test pattern generation using test points on nearby nets is suggested by Lee and Tehranipoor (2008). The test generation algorithm increases the crosstalk effects on delay sensitive paths by producing transitions in adjacent wires which are identified using the parasitic information derived from the layout. The set of final vectors generated for each delay sensitive path is compressed using a compaction scheme. These vectors increase the switching activity on the adjacent wires. Chun et al. (2009) have proposed a test generation method for crosstalk-induced delay effects, where multiple aggressor crosstalk faults were considered to maximize the noise of the victim line. The proposed algorithm uses parasitic information, such as coupling capacitance between a victim and an aggressor, and static timing windows to reduce many false aggressors and handle multiple possible aggressors coupled to a victim lying along a path. A conventional path delay ATPG was used to generate the test patterns, and don’t care values in the test patterns were given appropriate values to activate more number of aggressors to produce maximum crosstalk effect at the output. Hence, the test generation algorithm can reduce the search space of the backward implication of the aggressor’s constraints, thus reducing time. Hasan et al. (2010) have proposed an ATPG for detecting both crosstalk glitches and crosstalk-induced delay faults. Generated test patterns were compressed using pattern matching and fault chaining algorithms. Test patterns were generated by considering the coupling capacitance, timing, and functional incompatibilities between the victim and aggressor nodes. Zhang et al. (2011) have proposed a path delay test generation method for crosstalk delay effects. They have used a crosstalk-induced path delay fault model. The critical paths are identified by transition map-based timing analysis instead of timing window.

50

3 Test Generation Algorithms for Crosstalk Faults

The rise and fall transitions are characterized by two transition maps. Each transition map was expressed as a bitmap structure, in which a bit denotes a time area. The arrival time of the signals was recorded in the two transition maps. The target crosstalk faults were selected by overlapping analysis between transition maps of aggressor lines and victim lines. Then, a deterministic method is used to generate the robust test patterns for crosstalk delay faults. A modified FAN out-Oriented (FAN)-based deterministic algorithm is proposed by Jayanthy et al. (2012) for test generation of crosstalk delay faults. Seven-valued logic system has been used. Static timing analysis is used to derive a set of target crosstalk delay faults. The results obtained using modified FAN-based ATPG give a better fault coverage with reduced number of transitions for almost all the benchmarks compared to results obtained using modified PODEM-based ATPG. The number of backtraces is reduced in FAN-based ATPG, and hence, the CPU execution time of modified FAN-based ATPG is also less compared to modified PODEM-based ATPG.

3.4.2 Simulation-Based Test Generation A genetic algorithm-based test generation for crosstalk-induced faults has been proposed by Krstic et al. (2001). The constrained path delay faults are derived by statistical timing analysis. The genetic algorithm generates test that not only sensitizes the target path but also produces large crosstalk delay by producing required transitions on the identified coupled interconnects. However, the test generation time is high. Sathe and Bushnell (2002) have developed a simulation-based test generation for crosstalk-induced delay faults. A crosstalk candidate reduction algorithm is used to get a set of target crosstalk delay faults by filtering out redundant faults. 10000 random test vectors are used for all the benchmark circuits to simulate the faults. 2000 vectors were simulated at a time, and five passes of random vector generation and compaction were run. The fault simulator was a multiple-delay fault simulator in which gates are assigned a rise delay and fall delay. A fanout-weighted delay model was used for the propagation delay. An analog macro-model was developed to get the required delay to be injected into the digital fault simulator. But the fault coverage obtained is very less. A delay fault generator was developed to generate delay fault tests for both resistive and capacitive crosstalk delay faults (Chary and Bushnell 2006). The fault model is layout dependent. A circuit extractor is used for parasitic extraction. The crosstalk delay fault is generated from the parasitic capacitance between interconnect pairs. The bridging fault is generated from the resistance between the interconnect pairs. The set of target crosstalk delay faults and resistive bridging faults were got by using reduction algorithms. Simulator used was a multiple-delay fault simulator. But the disadvantage was that random test vectors are used which necessarily do not activate the worst case noise effects. Further single aggressor/victim fault is taken into consideration.

3.4 Test Generation Techniques for Crosstalk Delay Faults

51

A crosstalk delay fault simulator for sequential circuits is developed by modifying the basic time wheel-based event-driven simulator (Phadoongsidhi and Saluja 2005). The event-driven simulator is modified to activate, inject, and propagate crosstalk delay faults to the primary output. The simulator handles single victim/multiple aggressors. Gates are assumed to have a unit delay, and the crosstalk-induced delay value to be injected is also assumed to be one. For small circuits, the input fault list consists of every combination of victim/aggressor pair. The input test vectors were generated using HITEC (Niermann and Patel 1991) and the FASTEST, which were shorter test sequences. Hence, the fault coverage obtained is relatively low. All the above works on simulation-based test generation are ad hoc with numerous heuristics. There is no underlying well-defined algorithmic framework for simulation-based test generation such as genetic algorithm or simulated annealing for generating tests for crosstalk delay faults. A simulation-based test pattern generator based on optimization algorithms, namely single-objective genetic algorithm (Jayanthy and Bhuvaneswari 2011a) and multi-objective genetic algorithm (Jayanthy and Bhuvaneswari 2011b) which is used for detecting crosstalk delay faults for combinational, enhanced scan version of sequential circuits, was proposed and developed. Better fault coverage with lower transition times is obtained using these algorithms.

3.5 Delay Testing of Asynchronous Sequential Circuits Due to their many benefits, asynchronous systems are viewed as an alternative to purely synchronous systems. Asynchronous circuits have high-performance gains and low power when compared to their synchronous counterparts. But the testing of asynchronous circuits is a difficult task because of the following two reasons: (i) absence of global clock and (ii) the correct operation of asynchronous circuits which is obtained by introducing redundancies, that is, by sacrificing testability (Ghavami et al. 2009). The types of error to be tested in asynchronous circuits are stuck-at fault errors and delay faults. The latter can disrupt proper operation of the circuit. The problem with asynchronous test generation is that the test patterns must guarantee not only that the deterministic fault effect is captured correctly, but also that the fault effect is not overwritten and does not disappear during the subsequent operations. This complicates the fault simulation and automatic test pattern generation processes significantly. Kishinevsky et al. (1998) have shown that delay testing of asynchronous circuits can be reduced to a problem of test pattern generation for a related combinational circuit. The first step was to find all the global feedback loops and to convert asynchronous circuit into an asynchronous net. An asynchronous net consists of only local feedback loops, simple gates, and latches. Then, a set of equations is formulated to find paths whose delay was within the permissible limits. Initialization of asynchronous net was done by converting it into an iterative combinational array

52

3 Test Generation Algorithms for Crosstalk Faults

with initial values if pseudo-primary inputs are assumed to be don’t cares. Then, a robust path delay fault testing similar to that of combinational circuit testing is used to generate test vectors for path delay faults. Sur-Kolay et al. (2000) have designed a serial fault simulator for testing gate delay faults and transition faults in asynchronous circuits. They have used min-max timing analysis to compute the bounds on signal delays. The asynchronous circuit was unfolded into time frames, and the unfolded circuit is simulated. Fundamental mode of operation is assumed. Identification of frame boundaries involves breaking feedback loops. The feedback algorithm uses depth-first search approach. Simulations are done frame after frame. Initially, the feedback inputs are set to logic 0. When initialized, the current frame was simulated using min-max timing analysis and using the first test vector as primary input values. When the primary output results become stable, the pseudo-primary outputs are given as pseudo-primary inputs for the next time frame. For a gate delay fault, the time stamps for the primary output signals at the end of each time frame are checked to see if the minimum delay bound is lower than the corresponding maximum bound for the fault-free simulation. A design for test technique is developed by Shi et al. (2006) for testing delay faults in asynchronous handshake circuits. There are two types of delay faults in handshake circuits, one that occurs in the control block which causes performance degradation and the other one which occurs in the data path which causes logic errors. A multiplexer-based full-scan method is suggested for testing these delay faults in asynchronous handshake circuits. Favalli (2005) has proposed fuzzy model for path delay fault detection. The delay faults are modeled using a path delay fault model. Non-robust testing is used to detect delay faults. A fuzzy delay model was used to find the quality of non-robust tests by finding the number of gates featuring robust test conditions, the timing of the gates not satisfying robust test conditions, and the paths ability to propagate the effects of a transition under non-robust conditions. Monte Carlo simulation was used to evaluate test pairs which detect delay faults, and this data was compared with the ranking obtained from fuzzy model implemented in a path delay fault simulator. The results obtained for combinational circuits have shown that fuzzy delay for non-robust detection of delay faults is more accurate. An ATPG based on multi-objective genetic algorithm for testing crosstalk delay faults in asynchronous sequential circuits has been proposed and developed by Jayanthy et al. (2013). The asynchronous circuit is unfolded into time frames, and the unfolded circuit is simulated. Fundamental mode of operation is assumed. Identification of frame boundaries involves breaking feedback loops. A fuzzy delay model is used to model the gate delay (Jayanthy and Bhuvaneswari 2015). A multiobjective non-dominated sorting genetic algorithm (NSGA-II) is used for generating optimized test patterns for testing crosstalk delay faults in asynchronous sequential circuit. Two objectives, fault coverage and power consumption, are simultaneously optimized using these algorithms. The experimental results obtained demonstrate that the NSGA-II-based ATPG with redundancy is effective in providing a better fault coverage and minimum power dissipation for most of the SIS benchmark circuits.

3.6 Conclusion

53

3.6 Conclusion Deterministic and simulation-based test generation algorithms for both crosstalk pulses and delays are discussed. Finally, delay testing of asynchronous circuits is discussed, and a multi-objective genetic algorithm for crosstalk delay testing of asynchronous circuits is proposed.

References Aniket, R. Arunachalam, A novel algorithm for testing crosstalk induced delay faults in VLSI circuits, in Proceedings of International Conference on VLSI Design, pp. 479–484 (2005) X. Bai, S. Dey, A. Krstic, HyAC: a hybrid structural SAT based ATPG for crosstalk, in International Test Conference, pp. 112–121 (2003) S. Chary, M.L. Bushnell, Automatic path delay fault test generation for combined resistive vias, resistive bridges, and capacitive crosstalk delay faults, in Proceedings of the International Conference on VLSI Design (2006) W.Y. Chen, S.K. Gupta, M.A. Breuer, Analytic models for crosstalk delay and pulse analysis for non ideal inputs, in Proceedings of the International Test Conference, pp. 809–818 (1997) W.Y. Chen, S.K. Gupta, M.A. Breuer, Test generation in VLSI circuits for crosstalk noise, in Proceedings of International Test Conference, pp. 641–650 (1998) W.Y. Chen, S.K. Gupta, M.A. Breuer, Test generation for crosstalk-induced delay in integrated circuits, in Proceedings of International Test Conference, pp. 191–200 (1999) W.-Y. Chen, S.K. Gupta, M.A. Breuer, Analytical models for crosstalk excitation and propagation in VLSI circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 21(10), 1117–1131 (2002a) Y. Chen, S.K. Gupta, M.A. Breuer, Test generation for crosstalk induced faults: framework and computational results. J. Electron. Test. Theor. Appl. 18, 17–28 (2002b) K.T. Cheng and A. Krstic, Current Directions in Automatic Test Pattern Generation, IEEE Design and Test of Computers, pp. 58–64, (November 1999) S. Chun, T. Kim, S. Kang, ATPG-XP: test generation for maximal crosstalk-induced faults. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 28(9) (Sept 2009) M. Favalli, A fuzzy model for path delay fault detection. IEEE Trans. VLSI Syst. 13(8), 943–956 (2005) K.P. Ganeshpure, S. Kundu, On ATPG for multiple aggressor crosstalk faults in presence of gate delays, in Proceedings of IEEE International Test Conference, pp. 1–7 (Oct 2007a) K. Ganeshpure, S. Kundu, Automatic test pattern generation for maximal circuit noise in multiple aggressor crosstalk faults, in Design Automation and Test in Europe (2007b) S.H. Gerez, Algorithms for VLSI Design Automation, John Wiley and Sons (1999) B. Ghavami, A. Tajary, H.-R. Zarandi, H. Pedram, High-level fault simulation methodology for QDI template-based asynchronous circuits, in TENCON (2009) S. Hasan, A.K. Palit, W. Anheier, Test pattern generation and compaction for crosstalk induced glitches and delay faults, in Proceedings of the 23rd International Conference on VLSI Design (2010) N. Itazaki, Y. Idomoto, K. Kinoshita, A fault simulation method for crosstalk faults in synchronous sequential circuits, in IEICE Transaction on Information and System, vol. E80-D, no. 1, pp. 38–43 (Jan 1997a) N. Itazaki, Y. Matsumoto, K. Qnoshita, An Algorithmic Test Generation Method for Crosstalk Faults in Synchronous Sequential Circuits (IEEE, 1997b)

54

3 Test Generation Algorithms for Crosstalk Faults

S. Jayanthy, M.C. Bhuvaneswari, Simulation based Low power Test Generation for Crosstalk delay Faults, in International Journal of Modelling and Simulation, vol. 31, no. 3, pp. 234–242 (2011a). ISSN: 0288-6203 S. Jayanthy, M.C. Bhuvaneswari, An efficient multi-objective genetic algorithm for low power testing of crosstalk delay faults in VLSI circuits. Adv. Model. Anal. 54(2), 28–48 (2011b) S. Jayanthy, M.C. Bhuvaneswari, Fuzzy Delay Model Based Fault Simulator for Crosstalk Delay Fault Test Generation in Asynchronous sequential circuits. Sadhana Indian Academy of Sciences, vol. 40, part 1, pp. 107–119 (Feb 2015) S. Jayanthy, M.C. Bhuvaneswari, S. Keesarapalli, Test generation for crosstalk-induced delay faults in VLSI circuits using modified FAN algorithm. VLSI Des. 2012, 10 p (2012) (Article ID 745861). https://doi.org/10.1155/2012/745861 S. Jayanthy, M.C. Bhuvaneswari, M. Prabhu, Simulation based ATPG for low power testing of crosstalk delay faults in asynchronous circuits. Int. J. Comput. Appl. Technol. 48(3), 241–252 (2013). ISSN: 1741-5047 A. Kolodny, An effective technique for simultaneous interconnect channel delay and noise reduction in nanometer VLSI design, in 2006 IEEE 24th Convention of Electrical & Electronics Engineers in Israel (11/2006) M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Saldanha, A. Taubin, Partial-scan delay fault testing of asynchronous circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 17(11), 1184–1199 (1998) A. Krstic, J.-J. Liou, Y.-M. Jiang, K.-T. Cheng, Delay test considering crosstalk-induced effects, in Proceedings of International Test Conference, pp. 558–567 (2001) J. Lee, M. Tehranipoor, A novel pattern generation framework for inducing maximum crosstalk effects on delay-sensitive paths, in International Test Conference (IEEE, 2008) H. Li, Y. Zhang, X. Li, Delay test pattern generation considering crosstalk-induced effects, in Proceedings of Asian Test Symposium, pp. 178–183 (2003) H. Li, X. Li, Selection of crosstalk-induced faults in enhanced delay test. J. Electron. Test. Theor. Appl. 21, 181–195 (2005) H. Li, P. Shen, X. Li, Robust test generation for precise crosstalk induced path delay faults, in Proceedings of VLSI Test Symposium, pp. 300–305 (2006) T.M. Niermann, J.H. Patel, HITEC: a test generation package for sequential circuits, in Proceedings of European Conference Design Automation (EDAC), pp. 214–218 (1991) A.K. Palit, K.K. Duganapalli, W. Anheier, Test Pattern Generation for Crosstalk Fault in DSM chips using Modified PODEM, TuZ, pp. 41–45 (2008) M. Phadoongsidhi, K.K. Saluja, Event-centric simulation of crosstalk pulse faults in sequential circuits, in IEEE International Conference on Computer Design, pp. 42–47 (2003) M. Phadoongsidhi, K.K. Saluja, SCINDY: logic crosstalk delay fault simulation in sequential circuits, in Proceedings of International Conference on VLSI Design, pp. 820–823 (Jan 2005) M. Phadoongsidhi, K.T. Le Kewal, K. Saluja, A concurrent fault simulation for crosstalk faults in sequential circuits, in Proceedings of the 11 th Asian Test Symposium (ATS’02) (2002) A. Rubio, J.A. Sainz, K. Kinoshita, Test pattern generation for logic crosstalk faults in VLSl circuits, in IEEE Proceedings G-Circuits, Devices and Systems, vol. 138, no. 2 (April 1991) N. Rubio, X. Itazaki, X. Xu, K. Kinoshita, An approach to the analysis and detection of crosstalk faults in digital VLSI circuits. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 13, 387–394 (1994) A.D. Sathe, M.L. Bushnell, Analog macromodelling of capacitive coupling faults in digital circuit interconnect, in Proceedings of the International Test Conference, pp. 375–383 (2002) P. Shen, H. Li, Y.-J. Xu, X. Li, Non-robust test generation for precise crosstalk-induced path delay faults, in Proceedings of Asian Test Symposium, pp. 120–125 (2005) F. Shi, Y. Makris, Testing delay faults in asynchronous handshake circuits, in ICCAD’06 (November 5–9, 2006) A. Sinha, S.K. Gupta, M.A. Breuer, An enhanced test generator for capacitance induced crosstalk delay faults, in Proceedings of the 12th Asian Test Symposium (2003)

References

55

A. Sinha, S.K. Gupta, M.A. Breuer, A multi-valued algebra for capacitance induced crosstalk delay faults, in 17th Asian Test Symposium (IEEE, 2008) S. Sur-Kolay, M. Roncken, K. Stevens, P. Chaudhuri, R. Roy, Fsimac: a fault simulator for asynchronous sequential circuits, in Proceedings of the 9th Asian Test Symposium, pp. 114–119 (2000) H. Takahashi, M. Phadoongsidhi, Y. Higami, K.K. Saluja, Y. Takamatsu, Simulation-based diagnosis for crosstalk faults in sequential circuits, in Proceedings of 10th Asian Test Symposium, pp. 63–68 (2001) M. Zhang, H. Li, X. Li, Path delay test generation toward activation of worst case coupling effects. IEEE Trans. Very Large Scale Integr. VLSI Syst. 19(11), 1969–1982 (2011)

Chapter 4

An Automatic Test Generation Method for Crosstalk Delay Faults Using Modified FAN Algorithm

4.1 Introduction Many automatic test generation algorithms are developed for generating tests for crosstalk delay faults. Both deterministic (Chen et al. 2002; Sinha et al. 2008; Chun et al. 2009) and simulation-based algorithms (Sathe and Bushnell 2002) have been proposed. Experiments have shown that in some circuits, the simulation-based approach gave better results than the deterministic methods, while in other circuits the performance of the deterministic algorithms was better. Deterministic algorithms are effective in deriving tests for control dominant circuits and in identifying untestable faults. For data-dominant circuits, the simulation-based algorithms were much effective (Saab et al. 1992; Srinivas and Patnaik 1993; Rudnick and Greenstein 1997). Deterministic test generators produce tests by processing the model of the circuit. The model is typically the structural or symbolic model of the design. Typical steps in a deterministic test generation algorithm are fault excitation, fault propagation to the primary output, and state justification through time processing (Hsiao et al. 1996). The complexity of test generation for crosstalk delay faults is rather high due to the multiple objectives that are to be satisfied. Most of the deterministic test generators for crosstalk delay faults are based on modified path-oriented decision-making algorithm (PODEM)-based (Goel 1996) test generation which is run as the core to obtain a two-vector test in combinational circuits by forcing values to the victim and aggressor nodes and propagating the possible delay to the primary output nodes. In this chapter, an automatic test generation algorithm based on modified FAN for crosstalk delay faults is proposed. The first section of this chapter presents static timing analysis to derive a set of target crosstalk delay faults. Signal values used in test generation are defined. The test generation algorithm based on modified PODEM is presented followed by the discussion on the proposed modified FAN-based test generation algorithm. The effectiveness of the proposed approach is demonstrated by experimental results on combinational and enhanced scan version of sequential circuits. © Springer Science+Business Media Singapore 2019 S. Jayanthy and M. C. Bhuvaneswari, Test Generation of Crosstalk Delay Faults in VLSI Circuits, https://doi.org/10.1007/978-981-13-2493-2_4

57

58

4 An Automatic Test Generation Method …

4.2 Static Timing Analysis Static timing analysis is one of the techniques available to verify the timing of a digital design. It is faster and simpler way of checking and analyzing all the timing paths in a design for timing violations. The analysis of the design is carried out statically and does not depend upon the data values applied at the input pins. One other approach of verifying timing is based on timing simulation but it cannot handle the effects of crosstalk, noise and on-chip variations. In this research work, static timing analysis is used at gate level for digital circuits to derive a list of target faults caused due to crosstalk delay effects. A crosstalk delay fault is caused between an aggressor line denoted as A-line and victim line denoted as V-line. A crosstalk delay fault is induced in the V-line during a test when the necessary signal changes occur in A-line. The numbers of crosstalk faults between all possible combinations of A-lines and V-lines in a digital VLSI circuit are very large and impractical to detect for large complex circuits. Therefore, static timing analysis is used to get a reduced set of crosstalk delay faults. In order to obtain a reduced list of crosstalk delay faults, classes of false crosstalk faults that need not be tested have to be identified and should not be included in the target fault list. The static timing analysis used in this research work uses logical-level implementation of the circuit and does not require layout information (Takahashi et al. 2005). Using both the topological and timing information of digital circuits, static timing analysis derives a set of target crosstalk delay faults. This method without using layout information is more amenable to the time to market need of the designs.

4.2.1 Identification of Target Crosstalk Faults The entire paths in the circuit are analyzed using the tree data structure. The total number of paths in the circuit is calculated using depth-first search algorithm which employs recursive search procedure. From the total number of paths, a set of critical paths whose delay is the largest of all the paths in the circuit is found. The victim lines are lines that lie on the critical path. The selection of critical paths, number of victims in the critical path, and the total number of target crosstalk delay faults found using static timing analysis are described in the procedure given below. The procedure for finding target crosstalk faults consists of two phases. In the first phase, the earliest transition time and latest transition time of each line are calculated. By using this information, the longest paths (critical paths) are found. From the critical paths, the set of victim lines is derived. In the second phase, the procedure determines whether the timing window of victim line overlaps with the timing window of the aggressor line (Jayanthy et al. 2013). The conditions for victim and aggressor to form a crosstalk target fault are:

4.2 Static Timing Analysis

59

• The victims should lie in the longest path. • The relationship between transition time at the victim line Tvic and transition time at the aggressor line Tagg should satisfy the inequality Tvic − τ ≤ Tagg ≤ Tvic + τ where value of τ is assumed to be 1 unit delay. The transitions are limited to timing window τ to cause slowdown on the V-line. Phase 1 Step 1: For each line in the circuit, the latest transition time and earliest transition time are calculated. Latest transition time at a line is the maximum delay on any path from any primary input. The latest transition time for line L is calculated recursively as follows. • If line L is a primary input or pseudo-primary input. Latest transition time for L  one unit delay. • If L is an output of a gate G having n inputs I 1 , I 2 , I 3 …I n . Latest transition time for L  MAX {latest transition time for I j , j  1, 2,…, n} + delay of the gate. • If line L is a fanout branch. Latest transition time for L  latest transition time for the fanout stem. Earliest transition time at a line is the minimum delay on any path from any primary input. The earliest transition time for line L is calculated recursively as follows. • If line L is a primary input or pseudo-primary input. Earliest transition time for L  one unit delay. • If L is an output of a gate G having n inputs I 1 , I 2 , I 3 …I n Earliest transition time for L  MIN {earliest transition time for I j , j  1, 2,…, n} + delay of the gate. • If line L is a fanout branch Earliest transition time for L  earliest transition time for the fanout stem. The earliest transition time and latest transition time of all the lines are calculated. Step 2: Using the maximum value of the latest transition time, the longest paths in the circuit are identified. Step 3: Every primary input or pseudo-primary input or gate outputs in the longest path are the victims. The lines in the longest path form the set of victim lines. Phase 2 Step 1: A V-line from the set of victim lines is selected. The timing windows of victim and aggressor lines are calculated. The A-line has a timing window of [earliest transition time, latest transition time]. The timing window of V-line is calculated as [latest transition time − τ unit delays, latest transition time + τ unit delays].

60

4 An Automatic Test Generation Method … 1[1, 1]

22[3, 4]

10[2, 2] 2[1, 1] 16[2, 3]

3[1, 1]

6[1, 1]

11[2,2]

7[1, 1]

23[3, 4] 19[2, 3]

Fig. 4.1 Example circuit c17

Step 2: The timing window of the selected V-line is compared with timing windows of A-lines. Aggressor’s lines are other primary inputs or gate outputs. If the timing windows of V-line overlap with the timing window of a particular A-line, then the crosstalk-induced transition fault caused by the selected (A-line, V-line) pair is added to the target crosstalk fault list. The method is illustrated by using the circuit c17 as shown in Fig. 4.1. Phase 1 for Example Circuit C17 The earliest and latest transition times for each line in circuit c17 as indicated by line number [earliest transition time, latest transition time] are shown in Fig. 4.1. The longest paths for c17 circuit are indicated by bold lines in Fig. 4.1. The victims in the longest path form a set [3, 6, 11, 16, 19, 22, and 23]. Phase 2 for Example Circuit C17 Select V-line 3 from the victim set. Victim 3 is compared with A-line 1. The timing window of 1 (earliest transition time  1, latest transition time  1) overlaps with the timing window of 3 (latest transition time − 1= 0, latest transition time + 1  2). Hence (3, 1) form a target crosstalk fault. Considering the pair (3, 22), the timing window of 3 (0, 2) does not overlap with timing window of 22 (3, 4). Hence (3, 22) form a false crosstalk fault and hence should not be included in the target fault list (Bhuvaneswari and Jayanthy 2015). The number of target crosstalk faults for benchmark circuit c17 is 42. The input fault list for the test generator is the reduced set of crosstalk faults.

4.3 Seven-Valued Logic The objective of test generation for crosstalk delay fault is to generate a two-vector pair that should be applied to the primary input of fabricated IC to detect the delay

4.3 Seven-Valued Logic

61

faults caused due to crosstalk. The two vectors can be generated separately, or a different logic system may be used such that the two vectors can be derived simultaneously with a single copy of the circuit. When the two vectors are generated separately, three-valued logic is used where value of each signal will be 0, 1, or X. If two vectors are to be generated together, a value system different from the three values system can be used to represent values over two vectors. Seven-valued logic system has been used in this research work. S0 and S1 are signal values which represent steady logic ‘0’ and steady logic ‘1’ in the first and second test vectors, respectively. T0 represents logic ‘1’ in the first test vector and logic ‘0’ in the second test vector. T1 represents logic ‘0’ in the first test vector and logic ‘1’ in the second test vector. P0 represents the signal value which is logic ‘0’ in the first test vector and becomes logic ‘1’ at the beginning of the second test vector because of the crosstalk fault and goes back to logic ‘0’ after a definite time. P1 is reverse of P0. The different signals in the seven-valued logic are shown in Table 4.1 (Aniket and Arunachalam 2005). Tables 4.2 and 4.3 show the truth tables for 2 input AND and OR gates, respectively. Similar tables can be derived for NAND, NOR, and XOR gates.

Table 4.1 Seven-valued logic

Table 4.2 AND gate truth table

Signal

Description

S0

Steady 0

S1

Steady 1

T1

Rising transition

T0

Falling transition

P0

Glitch on a 0 signal

P1

Glitch on a 1 signal

X

Unknown value

AND S0 S1 T0 T1 P0 P1 X

S0 S0 S0 S0 S0 S0 S0 S0

S1 S0 S1 T0 T1 P0 P1 X

T0 S0 T0 T0 P0 P0 T0 X

T1 S0 T1 P0 T1 P0 T1 X

P0 S0 P0 P0 P0 P0 P0 X

P1 S0 P1 T0 T1 P0 P1 X

X S0 X X X X X X

62

4 An Automatic Test Generation Method …

Table 4.3 OR gate truth table OR S0 S1 T0 T1 P0 P1 X

S0 S0 S1 T0 T1 P0 P1 X

S1 S1 S1 S1 S1 S1 P1 S1

T0 T0 S1 T0 P1 T0 P1 X

T1 T1 S1 P1 T1 T1 P1 X

P0 P0 S1 T0 T1 P0 P1 X

P1 P1 S1 P1 P1 P1 P1 X

X X S1 X X X X X

Note Tables 4.1, 4.2, and 4.3 reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation

4.4 Procedure for Modified PODEM-Based Test Generation The fundamental steps in generating a test for a fault in fault-oriented test generation algorithm are: • Activate the fault: This is a line justification problem which deals with finding an assignment of primary input values those results in a desired value on specified node of the circuit. It is a recursive process in which a value of a gate output is justified by values of the gate inputs until primary inputs are reached. • Propagate the resulting error to the primary output: To propagate the error to the primary output, the path from that node to the primary output needs to be sensitized. The error propagation problem is transferred to line justification problem. PODEM (Goel 1996), a test generation algorithm for stuck-at faults, is characterized by a direct search process, in which decisions consist only of primary inputs. PODEM treats a value to be justified for a node as an objective to be achieved via primary input assignments. Values are assigned only by simulating primary input assignments. For test generation of crosstalk delay faults, PODEM algorithm is used, similar to stuck-at fault test generation for activating the crosstalk delay fault and sensitizing the path for propagation of fault effect to the primary output. But in case of test generation for crosstalk delay faults, for each crosstalk delay fault to be detected, multiple objectives have to be satisfied. The primary objectives in creating a crosstalkinduced delay fault are: Objective 1: A rising transition or falling transition in the victim line. Objective 2: A transition in the aggressor lines opposite to that of the victim line to create a slowdown effect. Objective 3: Setting the off-path inputs along the target path to suitable logic values in order to propagate the transition in the victim line to the primary output. The path chosen for propagation is the path with the longest path delay from current site to the primary output.

4.4 Procedure for Modified PODEM-Based Test Generation

63

The first step in PODEM for generating tests for stuck-at faults is to excite the fault, that is, target fault is set opposite to stuck value. For crosstalk delay faults, PODEM has to excite both victim and aggressors for opposite transitions. Since transitions have to be set on the victim node and aggressor nodes, two vectors have to be generated. In this research work, a multi-valued logic where two vectors are represented by a single variable is used. For stuck-at fault, the excited fault is propagated from the fault site to primary output along the best path. The path which can easily be sensitizable is taken as best path. In case of crosstalk delay fault, the path chosen is the longest path from the fault site to primary output. That longest path has to be sensitizable. Backtracing to primary inputs and reversing decisions in case of conflicts are similar to stuck-at faults. For stuck-at faults, conflicts occur between the target fault and the propagation path objectives. In crosstalk delay fault, conflicts occur between victim, activated aggressors, and on-path objectives. The conditions used to set the off-path sensitizing inputs are as follows: • If the transition at the gate input along the path has a controlling to non-controlling transition value, any of the three values are allowed at the side inputs: a static noncontrolling value, a controlling to non-controlling transition and glitch. • If the transition at the gate input along the path has a non-controlling to controlling transition value, any of the three values are allowed at the side inputs: a static controlling value, a non-controlling to controlling transition, and glitch. The focus is on combinational and enhanced scan version of sequential circuits whose inputs are primary inputs or pseudo-primary inputs and outputs are primary outputs or pseudo-primary outputs. The pseudo-code for modified PODEM-based test generation algorithm is shown in Fig. 4.2. The input to the test generator is the target fault list derived from static timing analysis. A single victim and multiple aggressors associated with the victim are taken from the fault list. Desired values on the victim line and aggressor lines are set to excite the crosstalk delay fault. From timing analysis of the circuit, the longest path from the victim node to a primary output is selected to propagate the fault. The off-path inputs along the target path are then set to suitable logic values. The remaining lines are set to logic value X. Since multiple objectives have to be satisfied, the objectives are first checked for contradiction because objectives have local conflict with other objectives. Then, the aggressors which cause the conflict are removed from the objective list. The victim is propagated along the chosen target path. During the propagation phase, if there is a conflict between the victim objective and on-path objective, then the next longest path is considered until all longest paths are tried. If there is a conflict between the aggressors and other objectives, then the aggressors which cause the conflict are removed from the objective list. The final list of objectives is obtained. If all aggressors are removed, then test is not possible and the next target fault is chosen. The final objectives are extracted one by one from the objective list, and a modified PODEM algorithm is used to search for vectors justifying the multiple objectives. Each objective is backtraced. Backtrace will search and return an unassigned primary input variable. Primary input is assigned a logic value. Simulation is done, and if

64

4 An Automatic Test Generation Method …

Test generation (Fault list) begin do select victim/aggressors from fault list Set primary objectives ( ); /*find all the primary objectives to be justified*/ set all other lines to X if (there is conflict between two or more objectives on the fan-out branches of the same stem) then begin drop the aggressor objectives; if (all aggressors objectives dropped) begin then test not possible exit end end Imply ( ) /*with respect to the victim and other inputs*/ Propagate ( ) /*Propagate the victim along the chosen target path*/ if( there is conflict between the implied values and on path objectives) then begin drop the target path if (all paths dropped) then begin test not possible exit ( ) end end else ( there is conflict between the implied values and aggressors) begin drop the aggressor objectives; if (all aggressor objectives dropped) then begin test not possible exit ( ) end end do remove one entry from the current objective Backtrace ( )/*backtrace to primary inputs*/ Imply ( ); Success=Imply () if (success==0) Reverse decision Back trace () while (current objective count! =0) Propagate ( )/*check if fault detected at primary output*/ if(fault detected )then fault count -while (fault count!=0) end Fig. 4.2 Pseudo-code for modified PODEM-based test generation algorithm for crosstalk delay faults

4.4 Procedure for Modified PODEM-Based Test Generation

65

there is a conflict with earlier assignment, reversal of decision is done at the primary input till all the objectives are satisfied. The unassigned primary inputs are assigned static values S0 and S1. Finally, the assigned primary inputs are propagated to the primary output. If fault effect is detected at the primary output, the victim/aggressor pairs are removed from the target list and fault count is decremented. The procedure is repeated until target fault list is empty. The primary inputs are assigned only S0, S1, RT, and FT. All gates are assumed to have zero delay.

4.5 Procedure for Modified FAN-Based Test Generation In test generation for crosstalk delay fault, the number of objectives to be satisfied is larger compared to test generation of stuck-at faults. PODEM targets one objective at a time. Hence, the decision process may sometimes be too localized and miss the global picture. Hence, a modified FAN algorithm is used for test generation for crosstalk delay faults. The multiple backtrace procedure adopted in FAN algorithm concurrently traces more than one path and is more efficient than the backtrace along a single path. In PODEM, the assignments are done at the primary inputs which results in excessive decision points. In FAN algorithm, the assignment is done at the fanout points, and hence, in case of contradiction, fruitless computation is avoided. Hence, the number of backtraces is reduced. Therefore, test generation will be relatively faster compared to PODEM-based test generation. The FAN algorithm (Fujiwara and Shimono 1980) introduces two extensions to the backtracing concept of PODEM. • Backtracing in FAN stops at internal fanout lines, rather at the primary inputs. • FAN uses multiple backtrace procedure that attempts to simultaneously satisfy a set of multiple objectives. The pseudo-code for modified FAN-based test generation algorithm is shown in Fig. 4.3. The steps in the algorithm are explained below. The final list of objectives is obtained as described in Sect. 4.4 for PODEM-based ATPG. The multiple backtrace procedure which is the most important aspect of the algorithm is applied to backtrace from primary outputs toward primary inputs in a breadth-first manner to satisfy the multiple primary objectives. The multiple backtrace returns values for primary inputs. The unassigned primary inputs are assigned static values S0 and S1. The assigned primary inputs are propagated to the primary output to find if a delay effect is observed. If delay is observed at the primary output, the victim/aggressor pairs are removed from the target list. The procedure is repeated until target fault list is empty. The pseudo-code for multiple backtrace of modified FAN-based generation algorithm is shown in Fig. 4.4. In multiple backtrace procedure, highest level objectives generate the next objective. Backtracing stops at the fanout point to check for contradictions with the already assigned value and the required logic value. If conflict

66

4 An Automatic Test Generation Method … Test generation (Fault list) begin do select victim/aggressors from fault list Set primary objectives ( ); /*find all the primary objectives to be justified*/ Set all other lines to X if (there is conflict between two or more objectives on the fan-out branches of the same stem) then begin drop the aggressor objectives; if (all aggressors objectives dropped) begin then test not possible exit end end Imply ( ) /*with respect to the victim and other inputs*/ Propagate ( ) /*Propagate the victim along the chosen target path*/ /* A transition observability cost is computed for each longest path and longest path with minimum observability cost is selected to propagate the crosstalk delay fault */

if( there is conflict between the implied values and on path objectives) then begin drop the target path if (all paths dropped) then begin test not possible exit ( ) end end else ( there is conflict between the implied values and aggressors) begin drop the aggressor objectives; if (all aggressor objectives dropped) then begin test not possible exit ( ) end end Multiple back trace ( ) Unassigned primary inputs are assigned Propagate ( );/*Propagate the delay in the victim along the target path*/ if (delay effect at PO) test is found; else begin no test possible exit( ) end end end end

Fig. 4.3 Pseudo-code for modified FAN-based test generation algorithm for crosstalk delay faults (Note Figure 4.3 reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation)

4.5 Procedure for Modified FAN-Based Test Generation

67

occurs, the objective is pushed to the secondary stack. If there is no conflict, the objective is moved to the primary stack. If it is not a fanout point, backtracing continues to generate the next objective. After current objectives are tried, objectives from the primary stack are taken and assigned most requested value and multiple backtrace is continued. The objectives in the secondary stack are tried after all the objectives in the primary stack are tried. All possible values are considered for the secondary stack objectives. If assignment is not possible, the aggressors which result in contradiction are removed. Test is not possible if all aggressors are removed. If assignment is possible, the objective is added to the current objective and multiple backtrace continues. In this algorithm, two stacks are used for test generation which has greater advantage over the single stack and it reduces the number of backtraces for generating a test. Since decision is made only at the fanout points rather than at primary inputs, backtraces are further reduced.

4.6 Experimental Results The test generation algorithm for crosstalk delay faults is tested on ISCAS’85 combinational circuits and several enhanced scan version of ISCAS’89 sequential circuits. Tables 4.4 and 4.5 give the characteristics of ISCAS’85 combinational circuits and the enhanced scan version of ISCAS’89 sequential circuits and ITC’99 benchmark circuits. The number of primary inputs (PI), number of primary outputs (PO), number of gates, number of paths, number of critical paths, number of victims, and total number of target faults corresponding to each circuit are given. The test generation algorithm using modified FAN is implemented in INTEL core I7 processor with 2.6 GHz and 4 GB RAM using C language in Linux environment. Results were compared with the results of modified PODEM-based ATPG, coded using C language. Comparison is done for fault coverage, average number of backtraces, CPU time, and total number of transitions for each circuit. Fault coverage  total number of faults detected/total number of target faults. Average number of backtraces  total number of backtraces/total number of paths. Number of transitions  transitions at the primary inputs + transitions at the gate outputs. A transition observability cost is computed for each longest path, and longest path with minimum observability cost is selected to propagate the crosstalk delay fault. First experimental results are observed without observability cost, and then, comparison results including observability cost are given. Table 4.6 gives the comparison between the percentage fault coverage for each circuit for FAN-based ATPG with PODEM-based ATPG. The bold number represents the maximum number of faults detected for each circuit. The average fault coverage increases by 10.4% for FAN-based ATPG when compared to PODEM-based ATPG.

68

4 An Automatic Test Generation Method …

Multiple backtrace ( ) begin repeat begin remove one entry from the current objective; if( objective follows a fan out point) then begin if( there is a contradiction with a previously assigned value) move the objective to a secondary stack else move the objective to a primary stack else begin Continue tracing Select an input of gate with value x assign( ) add to the current objective return multiple back trace end end end until current objectives ≠ null if (primary stack objective ≠null)then begin remove the highest level objective assign most requested value add to the current objective return multiple back trace() end if( secondary stack objective ≠ null) begin remove the highest level objective repeat begin assign value to the fan-out point Imply( ) if (success) begin add to the current objective return multiple back trace( ) end else assign next value end until all values assigned if(assignment not possible) begin Fig. 4.4 Pseudo-code for multiple backtrace of modified FAN-based test generation algorithm for crosstalk delay faults (Note Figure 4.4 reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation)

4.6 Experimental Results

69

drop the aggressor objectives if (all aggressor objectives dropped)then begin test not possible Exit( ) end end end end Fig. 4.4 (continued) Table 4.4 Characteristics of ISCAS’85 and enhanced scan version of ISCAS’89 benchmark circuits Circuit

No. of PIs

No. of POs

No. of gates

No. of paths

No. of critical paths

c17

5

2

6

11

6

c432

36

7

160

83,926

2199

c880

60

26

383

8642

c499

41

32

202

c1355

41

32

546

c1908

33

25

880

No. of victims 7

Total faults

42

103

9327

92

70

9279

9440

14

207

4,173,216

97,372

607

157,387

729,057

32

93

25,916 11,252

21,879

c3540

50

22

1669

28,676,671

95

150

c5315

178

123

2307

1,341,305

79

132

60,554

c7552

207

108

3512

726,493

7

154

138,680

s27

7

4

10

28

6

10

74

s208

19

10

96

145

2

18

743

s208.1

18

9

104

142

1

12

558

s298

17

20

119

231

1

10

537

s344

24

26

160

355

1

21

1190

s526

24

27

193

410

1

10

891

s386

13

13

159

207

10

49

4195

s510

25

13

211

369

1

13

1098

s420.1

34

17

218

474

1

14

1276

s820

23

24

289

492

11

43

7738

s953

16

23

395

1133

2

20

3036

s1196

32

32

529

3097

9

55

10,630

s1488

14

25

653

962

1

18

4305

s1238

32

32

508

3558

30

45

5822

s1423

91

79

657

44,726

8

65

15,493

s1494

14

25

647

976

1

18

4283

700

790

7951

1,345,319

565

s13207.1

188

241,743

Note Reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation

70

4 An Automatic Test Generation Method …

Table 4.5 Characteristics of ITC 99 benchmark circuits Circuit No. of No. of No. of No. of paths PIs POs gates

No. of critical paths

No. of victims

Total faults

b01_C

7

7

54

65

3

15

b02_C

5

5

32

26

1

7

421 103

b03_C

34

34

190

791

3

15

2957

b04_C

77

74

803

84,548

40

65

12,070

b06_C

71

150

65

70

6

15

456

b08_C b10_C

30 28

25 23

204 223

2809 703

49 2

43 21

2669 1338

b11_C

38

37

801

10,566

2

37

7845

b14_C

277

299

10,343

57,121,179

92

68

b20_C

522

512

20,716

289,792,088

193

307

b22_C

767

757

30,686

437,362,328

30

85

411,412 1,625,578 812,700

The number of test vectors for each benchmark circuit is also given. The number of test vectors that are generated is same for PODEM- and FAN-based ATPG. Table 4.7 gives the comparison between average numbers of backtraces for FANbased ATPG compared to PODEM-based ATPG. The bold number represents minimum number of backtraces obtained for each circuit. The algorithm achieved a high degree of reduction in average number of backtraces (29.70%) due to checking of contradictions at the fanout point instead of backtracing to primary inputs. Hence, the CPU execution time is greatly reduced. Table 4.7 also gives number of fanout points and the average aggressors activated per victim. As an example, for s208 circuit for a particular victim, the number of total aggressors is 99. Out of this 99, 94 aggressors are activated. Percentage of activated aggressors (94/99) * 100 is calculated. The same procedure is followed for the all the victims/activated aggressors of s208 circuit. Average of the percentage for all the victims/activated aggressors is taken and the results are presented. The results demonstrate that more number of aggressors are activated per victim. Hence, the algorithm handles single victim/multiple aggressors efficiently. Table 4.8 gives the comparison of number of transitions for PODEM- and FANbased ATPG. FAN gave less number of transitions for 16 of the 19 benchmark circuits. FAN reduces the number of transitions by 28.93% compared to PODEM. This is because compared to PODEM, backtracing in FAN results in more number of unassigned primary inputs with value X. These unassigned primary inputs are finally assigned static values S0 or S1. Because more number of primary inputs are assigned static values in FAN-based ATPG, the number of transitions is reduced. Thus, the efficient backtrace procedure in FAN reduces the number of transitions compared to PODEM-based ATPG, thus reducing the power dissipation in VLSI circuits. For c1355, c3540, c5315, and c7552, the number of target faults is limited to 10,000. The average fault coverage, percentage decrease in average number of back-

4.6 Experimental Results

71

Table 4.6 Comparison of fault coverage Circuit Fault coverage (%) c17 c432 c499 c880 c1908 *c1355 *c3540 *c5315 *c7552 s27 s208 s208.1 s298 s526 s386 s510 s420.1 s1196 s1238 Average

No. of test vectors

FAN

PODEM

92 80 71 80 15 33 59 57 68 83 68 10 85 86 62 65 22 62 87 64.53

90 79 46 30 7 27 43 39 43 58 42 43 59 84 77 47 12 52 86 54.13

13 3769 5328 1264 2379 2427 4933 5275 6110 32 67 29 115 116 212 91 55 942 543

*The number of target faults is limited to 10000

traces, average CPU time, and average number of transitions are taken without considering c1355, c5315, c7552, and c3540. Table 4.9 gives the comparison of fault coverage and number of transitions for PODEM- and FAN-based ATPG for ITC’99 benchmark circuits. FAN gave higher fault coverage for all the benchmark circuits. FAN gave less number of transitions for 8 of the 10 benchmark circuits. Figure 4.5 gives the comparison between the execution time of FAN and PODEMbased ATPG. For large circuits such as c880 and c499, CPU time is reduced by 60% for FAN-based ATPG. The switching activity is reduced further by introducing a transition observability cost factor during the propagation of fault to the primary output. The target paths for propagating the fault to the primary output are normally chosen as the longest paths from the victim site to the primary output. A transition observability cost is computed for each longest path which indicates the number of transitions required to propagate the fault to the primary output. The longest path with minimum observability cost is selected to propagate the crosstalk delay fault. Table 4.10 gives the fault coverage and number of transitions for each cir-

72

4 An Automatic Test Generation Method …

Table 4.7 Experimental results on benchmark circuits Circuit No. of Average Average number of name fanout aggresbacktraces points sors activated (%)

Decrease CPU time (s) in average no. of backtraces (%)

FAN

PODEM

FAN

PODEM

c17 c432 c499 c880 c1908 *c1355 *c3540

3 89 59 125 384 259 579

73 94 98 97 80 81 84

5.15 132.054 163.789 314.460 646.377 501.171 6058.5

8.461 216.518 233.418 436.56 842.28 712.45 8236.8

39.13 39.01 29.83 27.97 23.25 29.65 26.45

0.000 228.83 746.783 1016.33 3762.3 1865.8 8759.4

0.000 389.2 3040.1 3145.9 5786.5 3729.2 10,887.3

*c5315 *c7552

806 1300

91 86

7397.37 9865.12 25.01 10,872.99 13,763.21 20.99

7151.2 9867.03

9034.6 11,231.78

s27 s208 s208.1 s298 s526 s386 s510 s420.1 s1196 s1238 Average

4 32 28 34 54 26 73 58 155 165

94 95 80 88 93 85 91 73 94 98

9.593 89.029 89.55 76.104 132.353 102.88 156.615 175.67 508.99 424.97

0.017 0.967 0.450 2.683 8.81 10.3 9.00 6.1 1292.417 640.11 515.0

0.019 1.550 0.900 5.500 19.433 21.8 23.05 13.58 2862.4 710.15 1068.0

12.218 101.208 103.93 161.886 301.284 206.06 218.48 189.69 558.26 658.28

21.48 12.03 13.83 52.99 56.07 50.07 28.32 7.39 8.82 35.44 29.70

Note Reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation *The number of target faults is limited to 10000

cuit for FAN-based ATPG when transition observability cost is introduced. Table 4.11 gives the percentage decrease in number of transitions, test vectors, and CPU time for each circuit for FAN-based ATPG with a slight decrease in fault coverage, when compared to results of FAN-based ATPG without taking observability cost. The number of transitions decreases by 33.48% with a decrease in fault coverage by 6.42% when compared to the results taken without the observability cost. The CPU time is also reduced. The number of test vectors is reduced by 29.98%. Table 4.12 presents the comparison of the proposed FAN-based ATPG for crosstalk delay faults with the results of Chen et al. (2002), Sinha et al. (2008), Chun et al. (2009). The results are tabulated for combinational circuits. In Chen et al. (2002) and Sinha et al. (2008), the number of victim/aggressors pairs taken into con-

4.6 Experimental Results

73

Table 4.8 Comparison of number of transitions Circuit No. of transitions

Reduction in number of transitions over PODEM (%)

FAN

PODEM

c17 c432

94 199,585

117 345,413

19.66 42.21

c499

380,926

374,882

−1.58

c880

130,217

112,465

−13.63

c1908

430,634

458,133

6.00

*c1355

36,431

39,536

7.85

*c3540

49,788

52,327

4.85

*c5315

41,490

42,980

3.46

*c7552

83,489

85,790

2.68

s27 s208 s208.1 s298 s526

338 2131 930 6388 8036

285 3317 1837 8860 13,100

−15.68 35.75 49.37 27.90 38.65

s386

15,385

26,760

42.50

s510

4747

10,175

53.34

s420.1 s1196

3435 107,765

8036 222,839

57.25 51.63

s1238

69,164

116,570

40.66

Average

28.93

*The number of target faults is limited to 10,000 Note Reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation

sideration was 100. In Chun et al. (2009), the numbers of target faults were limited to 1000 and number of backtraces was limited to 10,000. In the proposed ATPG, all the target faults are taken into consideration for most of the benchmark circuits. The number of backtraces is also not limited. Comparatively, the proposed ATPG has a better fault coverage for most of the benchmarks. Table 4.13 represents the comparison of the proposed ATPG with the results of Li et al. (2006), Shen et al. (2005), Li et al. (2003) for sequential circuits. In Li et al. (2003), the waveform sensitization-based algorithm could not generate tests for the large circuits. Compared to previous works, the proposed test generation algorithm has produced comparable or greater fault coverage. For sequential circuits, the fault coverage increases by an average of 30% for the six circuits.

74

4 An Automatic Test Generation Method …

Table 4.9 Experimental results on ITC’99 benchmark circuits Circuit Fault coverage (%) No. of transitions FAN

PODEM

FAN

PODEM

b01_C

35

84

1675

2479

b02_C

88

79

133

180

b03_C

70

60

15,447

13,508

b04_C

62

53

112,885

145,847

b06_C

73

62

25,394

24,900

b08_C

63

54

86,527

111,014

b10_C

70

61

26,665

34,131

b11_C

70

60

128,340

165,815

*b14_C

64

52

4,369,929

4,514,389

*b20_C

54

42

18,806,453

19,331,202

*b22_C

53

41

12,932,226

12,475,579

*The number of target faults is limited to 10,000 12000

FAN PODEM

ExecuƟon Time(sec)

10000 8000 6000 4000 2000

s1238

s1196

c7552

c5315

c3540

c1355

c1908

c880

c499

c432

0

Benchmark Circuits Fig. 4.5 Comparison of execution time (Note Reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation)

4.7 Conclusion In this chapter, a modified version of FAN algorithm for testing crosstalk delay faults in combinational and enhanced scan version of sequential circuits is presented. The experimental results using modified FAN-based ATPG and modified

4.7 Conclusion

75

Table 4.10 Experimental results of FAN-based ATPG with observability cost Circuit Fault coverage No. of transitions No. of test CPU time (s) (%) vectors c17 c432

78 77

67 181,851

10 3407

0.00 206.267

c499

66

378,798

4964

665.517

c880

76

69,122

685

511.817

s27 s208 s208.1 s298 s386 s420.1 s510 s526 s1196

83 55 10 85 62 22 22 86 54

291 1162 647 3822 9015 2224 3066 4834 51,248

26 44 23 73 135 38 59 75 562

0.00 0.7 0.350 1.783 7.250 4.5 6.217 5.933 741.883

s1238

87

35,082

336

388.18

Table 4.11 Comparison of fault coverage and number of transitions for FAN-based ATPG with and without observability cost Circuit Decrease in fault Decrease in no. Decrease in no. Decrease in CPU coverage (%) of transitions (%) of test vectors time (%) (%) c17 c432 c499 c880 s27 s208 s208.1 s298 s386 s420.1 s510 s526 s1196 s1238 Average

14 3 5 4 0 13 0 0 0 0 43 0 8 0 6.42

28.72 8.88 0.56 46.91 13.9 45.47 30.43 40.16 41.4 35.25 35.49 39.84 52.44 49.27 33.48

23.07 9.6 6.83 45.8 18.75 34.32 20.68 36.52 36.32 30.9 35.16 35.34 40.33 38.12 29.98

0 9.86 10.88 49.64 100 27.61 22.22 33.54 29.61 26.22 30.92 32.65 42.59 39.35 32.50

76

4 An Automatic Test Generation Method …

Table 4.12 Comparison with previous works (ISCAS’85 combinational circuits) Circuit Chen et al. (2002) Sinha et al. Chun et al. Proposed ATPG (2008) (2009)

c432 c880 c1355 c1908 c5315 c7552

Fault coverage (%)

Fault coverage (%)

Fault coverage (%)

Fault coverage (%)

35 28 16 33 31 14

15 38 36 8 1 2

– 54.26 – 24.34 49 52

80 80 33 15 57 68

Table 4.13 Comparison with previous works (enhanced scan version of ISCAS’89 sequential circuits) Circuit Li et al. (2006) Shen et al. (2005) Li et al. (2003) Proposed ATPG

s208 s298 s386 s526 s420.1 s1196 s1238 s13207.1

Fault coverage (%)

Fault coverage (%)

Fault coverage (%)

Fault coverage (%)

31.50 42.66 34.43 66.30 27.19 31.32 – 87.14

55.48 – 51.89 55.24 – 1.03 3.83 25.13

– – – – – 8.41 3.11 –

68 85 62 86 22 62 87 64

Note Tables 4.12 and 4.13 reprinted from Article ID 745861, Jayanthy et al. (2012), with permission from M/s Hindavi Publishing Corporation

PODEM-based ATPG indicates that modified FAN-based ATPG increases the fault coverage with reduced number of transitions and thus reduces power dissipation during testing of VLSI circuits. During the propagation phase, an observability cost is introduced which further reduces the number of transitions. The modified version of FAN algorithm used for test generation significantly reduces the average number of backtraces compared to PODEM. Therefore, the CPU time of modified FAN-based ATPG reduces significantly compared to modified PODEM-based ATPG. Acknowledgements Section 4.3, Tables 4.4, 4.7, 4.8, 4.12, and 4.13 are reproduced from the reference Jayanthy et al. (2012) under the creative commons attribution license from M/s Hindavi Publishing Corporation. This is gratefully acknowledged.

References

77

References R. Aniket and Arunachalam, A Novel Algorithm for Testing Crosstalk Induced Delay Faults in VLSI Circuits, Proceedings of International Conference on VLSI Design, pp. 479–484 (2005) M.C. Bhuvaneswari, S. Jayanthy, Cross-talk delay fault test generation, in Application of Evolutionary Algorithms for Multi-objective Optimization in VLSI and Embedded Systems (2015). ISBN 978-81-322-1958-3 W.-Y. Chen, S.K. Gupta, M.A. Breuer, Analytical models for crosstalk excitation and propagation in VLSI circuits. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 21(10), 1117–1131 (2002) S. Chun, T. Kim, and S. Kang, ATPG-XP: Test Generation for Maximal Crosstalk-Induced Faults, IEEE Trans. Comput. Aided Des. Integr. Circ. Syst., 28 (9), 1401–1413 (September 2009) H. Fujiwara, T. Shimono, On the acceleration of test generation algorithms. IEEE Trans. Comput. C-32, 223–234 (1980) P. Goel, An implicit enumeration algorithm to generate tests for combinational logic circuits, in Proceedings of the FTCS-25, vol. 3 (1996), pp. 337–343 M.S. Hsiao, E.M. Rudnick, J.H. Patel, Alternating strategies for sequential circuit ATPG, in Proceedings of the European Design and Test Conference (1996), pp. 368–374 S. Jayanthy, M.C. Bhuvaneswari, K. Sujitha, Test generation for crosstalk-induced delay faults in VLSI circuits using modified FAN algorithm. VLSI Des. 2012(Article ID 745861), 10 (2012). https://doi.org/10.1155/2012/745861 S. Jayanthy, M.C. Bhuvaneswari, M. Prabhu, Simulation based ATPG for low power testing of crosstalk delay faults in asynchronous circuits. Int. J. Comput. Appl. Technol. 48(3), 241–252 (2013). ISSN 1741-5047 H. Li, Y. Zhang and X. Li, Delay test pattern generation considering crosstalk-induced effects, in Proc. Asian. Test. Symp. pp. 178–183, (2003) H. Li, P. Shen and X. Li, Robust test generation for precise crosstalk induced path delay faults, in Proc. VLSI Test Symp. pp. 300–305, (2006) E.M. Rudnick, G.S. Greenstein, A genetic algorithm framework for test generation. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 16(9), 1034–1044 (1997) E.M. Rudnick, J.G. Holm, D.G. Saab, J.H. Patel, Application of simple genetic algorithms to sequential circuit test generation, in Proceedings of the European Design and Test Conference (1994), pp. 40–45 D.G. Saab, Y.G. Saab, J.A. Abraham, CRIS: a test cultivation program for sequential VLSI circuits, in Proceedings of the International Conference Computer—Aided Design (1992), pp. 216–219 A.D. Sathe, M.L. Bushnell, Analog macromodeling of capacitive coupling faults in digital circuit interconnects, in Proceedings of the International Test Conference (2002), pp. 375–383 P. Shen, H. Li, Y.–J. Xu and X. Li, Non-Robust Test Generation for Precise Crosstalk-Induced Path Delay Faults, Proc. of Asian Test Symposium, pp. 120–125, (2005) A. Sinha, S.K. Gupta, M.A. Breuer, A multi-valued algebra for capacitance induced crosstalk delay faults, in Proceedings of the 17th Asian Test Symposium (2008) M. Srinivas, L.M. Patnaik, A simulation based test generation scheme using genetic algorithm, in Proceedings of International Conference on VLSI Design (1993), pp. 132–135 H. Takahashi, K.J. Keller, K.T. Le, K.K. Saluja, Y. Takamatsu, A method for reducing the target fault list of crosstalk faults in synchronous sequential circuits. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 24(2), 252–263 (2005)

Chapter 5

ATPG for Crosstalk Delay Faults using Single-Objective Genetic Algorithm

5.1 Introduction Test generation using deterministic algorithms is highly complex and timeconsuming. To obtain a particular output value for a component, backtracing is required to determine its input values. It is difficult to handle components other than simple gates (Rudnick and Greenstein 1997). In a simulation-based approach, processing occurs in the forward direction only. Hence, complex component types are handled more easily. Test can be generated for any type of circuit, and any type of fault can be simulated. In a simulation-based approach, a logic or fault simulator is used to select the best test to apply (Agrawal et al. 1989). Most of the existing simulation-based test generators for crosstalk-induced delay faults were random based, and hence, the test sets generated were typically much longer than those generated by deterministic test generators. These simulation-based test generators were by and large ad hoc with numerous heuristics. Even though the heuristics were very clever, there was no underlying well-defined algorithmic framework such as genetic algorithm (GA) or simulated annealing. Genetic algorithm is simulation based have been very effective for test generation of stuck-at faults in both combinational and sequential circuits. The use of GA for simulation-based test generation produces better fault coverage and lower execution times (Mazumder and Rudnick 1999). GA-based algorithms tend to generate more compact test sets when accurate fitness functions are used (Corno et al. 1996). In this chapter, GA is used for testing crosstalk delay faults. Tests are generated for most of the ISCAS’85 combinational circuits and enhanced scan version of ISCAS’89 sequential circuits. Results are obtained for four crossover operators, namely one-point, two-point, uniform, and weight-based crossover operators. The results demonstrate that GA-based test generation provides good results for most of the benchmark circuits.

© Springer Science+Business Media Singapore 2019 S. Jayanthy and M. C. Bhuvaneswari, Test Generation of Crosstalk Delay Faults in VLSI Circuits, https://doi.org/10.1007/978-981-13-2493-2_5

79

80

5 ATPG for Crosstalk Delay Faults …

5.2 Genetic Algorithm Genetic algorithm is search algorithm that mimics the process of natural selection and natural genetics as proposed by Darwin. They combine survival of the fittest among string structures. Genetic algorithm has been developed by Holland (1975) at the University of Michigan. The goal of their research has been robustness, the efficiency, and efficacy necessary for survival in many different environments; thereby, artificial systems can be made more robust and costly redesigns can be eliminated (Goldberg 2001). The simplicity, robustness, efficiency, and effectiveness of genetic algorithm make them a promising tool for complex applications. GA has been investigated as possible solution to large number of search and optimization problems (Davis 1991; Drechsler 1998; Srinivas and Patnaik 1994). Several of tasks in VLSI design and test involve optimization problems. Heuristic techniques which are used to obtain solutions increase design complexity. Therefore, GA is a good choice in VLSI design and test processes which are integrated into commercial electronic design automation (EDA) tools. The advantages of GA are as follows: • GA is superior to normal guided random method concerning with the test performance. • The improved level-oriented GA-based test generation method is more effective in finding the distance between the levels to which the fault signal can be propagated. • It can quickly scan a very large solution set through evolution. • The inductive nature of the GA means that it does not have to know any rules of the problem and it works by its own internal rules. Figure 5.1 shows the flowchart of GA. GA maintains a population pool of candidate solutions called strings or chromosomes. Each string is a collection of genes. Each string is associated with a fitness value (Jayanthy et al. 2013). The fitness function is usually user-defined and problem-specific. GA starts with an initial population, which consists of many individual solutions or strings that are randomly generated. Selection, crossover, and mutation are then used to generate an entirely new population from the existing population. Selection is one of the key operators on GA that ensures the survival of the fittest. Usually, members are selected for mating with a selection probability proportional to their fitness values. The two selection schemes commonly used are binary tournament selection and roulette wheel selection (Goldberg and Deb 1991). In binary tournament selection, two individuals are taken at random and the better individual is selected from the two. There are two types in binary tournament selection. They are with and without replacement. If they are again replaced into the population, it is tournament selection with replacement, and if they are not replaced into the population, it is tournament selection without replacement. The second scheme is the roulette wheel selection. In this selection, the search is more randomized but the fittest individuals have more probability to be selected. Tournament selection is the most popular selection method in genetic algorithm due to its efficiency and simple implementation (Razali and Geraghty 2011).

5.2 Genetic Algorithm

81

Fig. 5.1 Flowchart of GA

Start

Generate random initial population of test sequences

Evaluate each individual

Select individuals by applying a selection operator

With some probability perform crossover to produce offspring.

Mutate the offspring with a small probability

Replacement strategy

Criteria met?

End

Roulette wheel selection method provides highest pressure in initial generations when a few individuals have higher fitness than others do. Tournament selection provides more pressure in later generations when the fitness values of individuals are not significantly different (Rudnick and Greenstein 1997). In this work, tournament selection is used for selecting the chromosomes for next generation.

82

5 ATPG for Crosstalk Delay Faults …

Crossover combines the chromosomes of two individuals to obtain new fitter individuals with probability called as the crossover rate. There are a number of crossover operators (Goldberg 2001). Crossover operators used in this research work are explained in Sect. 5.3. Mutation involves the modification of the values of some genes of a solution with a given mutation rate. The last two operations are performed on the individuals selected from present population through selection operation. In the simple GA, the process of reproduction, crossover, and mutation is repeated until all entries in a new population are filled. When the required number of child chromosomes is produced, the new population and the existing population contend for membership in the generation’s membership pool. Selection of the chromosomes is governed by the replacement strategy, and numbers of replacement strategies are available in literature (Goldberg 2001). The old population is discarded. The sequence of selection, crossover, and mutation forms a one-generation cycle. GA progresses through generations until the objective is reached, for example, a fixed number of generations. The fitness of the overall population is expected to increase in successive generations (Goldberg 2001).

5.3 Test Generation Using GA Test pattern generation is a search process over a large vector space, and therefore, it is an ideal candidate for GA (Rudnick et al. 1994). The goal of GA in test generation is to find test vector which detects maximum faults.

5.3.1 Chromosome Encoding The chromosomes are made up of units called genes. Group of chromosomes form a population. Binary encoding scheme is employed. In crosstalk delay fault testing, a two-vector test pattern, , is required. Hence, the length of the test sequence is equal to twice the number of primary inputs.

1 0 1 1 1 1 0 0 0 0 1 1 V1

V2

5.3 Test Generation Using GA Fig. 5.2 One-point crossover

83

Parents

Children

0 0 0 0 0 0 0 0

p1

1 1 1 1 1 1 1 1

p2

0 0 0 0 1 1 1 1

c1

1 1 1 1 0 0 0 0

c2

5.3.2 Fitness Function The fitness function for test generation is the number of faults detected.

5.3.3 Crossover Operators Crossover is a GA operator that entails choosing two individuals to swap segments of their string, thereby producing new offspring that is combination of their parents. The one-point, two-point, uniform, and proposed weight-based crossovers are described in this section (Bhuvaneswari and Jayanthy 2015).

5.3.3.1

One-Point Crossover

A single crossover point is randomly selected on both parents. All bits beyond that point in either parent are swapped as shown in Fig. 5.2. The resulting strings are the children.

5.3.3.2

Two-Point Crossover

Two-point crossover has two points to be selected on the parent strings. All bits between the two points are swapped, rendering two children.

5.3.3.3

Uniform Crossover

In uniform crossover as shown in Fig. 5.3, the crossover operator decides with some probability, which parent will contribute each of the gene values in the offspring chromosomes (Rudnick and Greenstein 1997).

84

5 ATPG for Crosstalk Delay Faults …

Fig. 5.3 Uniform crossover

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

.1 .6 .3 .7 .8 .2 .4 .6 1

0

1

0

0

1

1

0

0

1

0

1

1

0

0

1

Table 5.1 Rules for WCO Bit weight of parent 1 Bit weight of parent 2

p2 Probability c1 c2

Operation

0 1 1

0 1 0

Same as uniform crossover Same as uniform crossover Assign bit of p2 to both children

0

1

Assign bit of p1 to both children

5.3.3.4

p1

Weight-Based Crossover (WCO)

In GA, crossover operators differ from each other primarily in the way they choose the gene from parents to form the offspring. In one-point, two-point, and uniform crossover operators, the selection of the gene is purely random. The WCO operator depends on the weights assigned to the genes for crossover operation. It is a combination of uniform crossover and weighted uniform crossover. If the number of generations is N, uniform crossover is performed for the first N/2 generations and for the next N/2 generations weights are assigned to the genes in the chromosome according to the similarity of the test patterns in the population and weighted uniform crossover is performed. The scheme for weighted computation is defined in (Bhuvaneswari and Sivanandam 2002). The rules for weighted crossover operator are defined in Table 5.1. Two parents p1 and p2 are selected to produce two child chromosomes c1 and c2. Each gene Gi,1 with weight W i,1 in parent p1 competes against the corresponding gene Gi,2 with weight W i,2 in parent p2. If the weights are equal, the bits are crossed with the probability as in uniform crossover. If the weights are different, both the child chromosomes are assigned the value of the lighter bit with weight 0. Weight Wk,c is assigned for each gene position k in chromosome c. Initially, weight zero is assigned to all Wk,c . After N/2 generations, the individuals in the new population are compared for similarity. If more than 75% of the chromosome test patterns in the population are identical in more than 75% of the bit position, then weight 1 is assigned to bits that are similar and weight 0 is assigned to the remaining bits.

5.3 Test Generation Using GA Table 5.2 Examples for weight computation

85 Population p1

Weight for p1

10111100 01111000 01110000 11110001

00110011 01110111 01110111 01110110

Population p2

Weight for p2

11111111 00011011 00110011 11010001

00000000 00000000 00000000 00000000

Table 5.2 shows weight computation of two populations p1 and p2, with 2 test vectors of length 8. In population p1, bits 1, 2,3,5,6, and 7 are similar bits, which account for 75% of the total bits in a test vector. Weight 1 is assigned to those that have the same value as the majority and weight 0 to the remaining unsimilar bits. In population p2, bits 1, 2, 3, and 5 are similar bits which account for only 50% of the total bits in a test vector. So zero weights are assigned to all bit positions

5.4 Crosstalk Delay Fault Simulator The objective of the fault simulator is to determine the number of faults detected by the test sequence, with a test vector sequence as inputs. The logic simulator uses event-driven technique (Ulrich 1969). Event-driven simulator is to detect events, i.e., changes in signal values, and simulate the gate in response to the event. If there is no change in signal values, then no gates will be simulated. In addition, nets are tested for changes only when necessary. It is necessary to test nets for changes, when a new input vector is read and instantaneously after a gate is simulated. When an event is detected, an event queue is created and stored for future processing. The events are processed one by one. In this research work, a circular event queue is used. The fault simulator uses three valued logics: 0, 1, and X. The fault simulator is capable of detecting single victim/multiple aggressor faults. The simulation algorithm is shown as a flowchart in Fig. 5.4. Initially, the simulator reads in a new test sequence. This is followed by fault-free circuit simulation, and faults are read from the fault list. All aggressors for a particular victim are read and concurrently checked for activation. Faults are activated when victim and aggressors have opposite transition. The fault is injected by delaying the victim by a time step equal to calculated delay value. Other events are scheduled as usual as for a faultfree circuit. The simulation is continued until the end of time frame. At any primary outputs of faulty circuit, if the delay effect is observed, then fault is detected and the victim and activated aggressors pairs are removed from the fault list. The other

86

5 ATPG for Crosstalk Delay Faults …

Start Read new test sequence No Simulate fault free circuit

End of test sequences?

Fault excitation

Fault injection and simulation

Yes

End

If faults are detected remove from fault list

Fig. 5.4 Flowchart of fault simulation-based ATPG

aggressors are considered for the next test pattern. The simulator reads the other target faults from the fault list, and fault simulation is done. The whole process is repeated for all the test vectors in the test set (Jayanthy and Bhuvaneswari 2011).

5.5 GA-Based Crosstalk Delay Test Generation Algorithm The objective of crosstalk delay fault test generation is generating a reduced test set, which contains smallest number of test vectors. This is fundamentally a process of exploring the test vector space. So GA can be used to optimize the process of exploring the test vector space. Every test vector/sequence can be treated as an individual or string, with the string length equal 2Q, where Q is the number of primary inputs in the circuit. Thus, the number of tests can be viewed as vector/sequence pairs as a population. Each individual is associated with a fitness, which measures the quality of this individual for detecting the faults. To assess the fitness of every test vector/sequence pair in a population in any generation of evolution, the crosstalk delay fault simulator is suitable. The individuals of the population which detect the fault are added to the test set. The pseudo-code for GA-based ATPG algorithm presented in this research work is shown in Fig. 5.5. The ATPG algorithm performs in two phases. In the first phase, the initial population of test vectors/sequences is obtained by pseudorandom process. The test vectors are evolved based on fitness function in the second phase of GAbased test generation. The fitness function used is:

5.5 GA-Based Crosstalk Delay Test Generation Algorithm Fig. 5.5 Pseudo-code of overall GA-based ATPG algorithm. Note Reprinted from Vol 9, Jayanthy and Bhuvaneswari (2009), with permission from ICGST-AIML

87

Overrall ATPG algorithm { TFL= {reduced set of target crosstalk delay faults} initial pop=phase I (TFL); if (FL =NULL) break; phase II (initial pop, TFL); }

Fitness = Number of faults detected. The crosstalk delay fault simulator is used to evaluate the fitness function.

5.5.1 Phase I: Pseudorandom Generation of Initial Test Sequence In phase I, the initial sequences consist of test vectors that are generated based on pseudorandom process. The generated sequences are fault simulated for the faults in the target fault list. The fault is removed from the fault list, if the sequence detects that fault, and the resultant sequence is added into the solution set. The last sequence generated in the corresponding cycle is added to the set, if no faults are detected by the sequence. This process is repeated for maximum number of iterations. The pseudo-code of phase I is shown in Fig. 5.6.

5.5.2 Phase II: GA-Based Test Generation In phase II, the initial population consists of sequences generated in phase I. New population is generated from the existing population by selecting two individuals (parents), and the individuals are crossed to create two entirely new individuals (child), and each child is mutated with a small mutation probability. The pseudocode for phase II is shown in Fig. 5.7. The selection operator is binary tournament selection with replacement. In this selection scheme, two individuals are taken at random, and the better individual is selected. The two new individuals are then placed in the new population, and the process continues until the generation is entirely filled. The previous population is discarded. The number of generations is represented as no_gen, and size of population is repre-

88 Fig. 5.6 Pseudo-code of pseudorandom generation of initial test sequence. Note Reprinted from Vol 9, Jayanthy and Bhuvaneswari (2009), with permission from ICGST-AIML

5 ATPG for Crosstalk Delay Faults …

Function Phase I initial pop(FL) for (n=0; n