Gate - A Genetic Algorithm for Compacting Randomly Generated Test Sets

Report
Authors:Aylor, J, Department of Computer ScienceUniversity of Virginia Cohoon, J, Department of Computer ScienceUniversity of Virginia Feldhousen, E, Department of Computer ScienceUniversity of Virginia Johnson, B, Department of Computer ScienceUniversity of Virginia
Abstract:

A new technique. named GATE. is presented for the generation of compact test sets. GATE combines a previously proven method for random test pattern generation with the adaptive searching capabilities of genetic algorithms to produce very high quality test sets. A series of experiments demonstrated that our technique performed consistently better than the traditional method with respect to both fault coverage and test set size. 1‘ This research was supported in part by the Virginia Center for Innovative Technology through grant 530971 and by the Defense Advanced Projects Research Agency (DARPA) through contract NO0Ol4 - 89-J 1699. :1: This author's current address is Cardiology Business Unit. Hewlett - Packard Company, 1700 S. Baker Street. McMinnvi1le, OR 97128. 1 . INTRODUCTION The generation of test vectors for combinational VLSI circuits continues to be an important research area. The current situation, which has significant costs associated with test generation and application. is due largely both to the NP-completeness of deterministic test pattern generation [FUJI82, ii3AR75] and to the incompleteness of random techniques. As a result, great ellort has been spent developing efficient test generation techniques that use a variety of methods to produce compact test sets with high fault coverage. These methods range from the deterministic ones that attempt to generate at least one test for each single stucl«: - at fault in a circuit, to random and pseudo-random test generation that are used in conjunction with built-in self test, and to exhaustive methods that apply all possible input combinations [CART85, FUJI83. GOEL81, MCcL81, ROTH66}. While all these methods are appropriate under the proper circumstances, they can be further improved. For example, deterministic algorithmic methods attempt to generate at least one test for each single stuck-at fault in a circuit. And while they are complete in the sense that given enough time. they will determine a test for all detectable faults in a circuit {FUJI85]. the required computation time for the fastest algorithm grows exponentially with circuit size [BRAH87]. Similar concerns can be expressed about other methods. The work presented here uses genetic algorithms to offer an improved test generation technique. where a genetic algorithm [GoLD89, HoLL75] is an optimization method that resembles the mechanics of natural evolution that seems particularly well-suited to VLSI problems [COHo9l}. Specifically, this research focuses on new ways of creating compact test sets from test sets that were generated with random techniques. Methods that improve the coverage of such test sets and approaches to minimizing the computational cost of this new technique are also presented. This is achieved in part by extending and exploiting the successful SOFE method of random .2- pattern generation and fault simulation developed by Carter. Dennis, Iyengar. and
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Aylor, J, J Cohoon, E Feldhousen, and B Johnson. "Gate - A Genetic Algorithm for Compacting Randomly Generated Test Sets." University of Virginia Dept. of Computer Science Tech Report (1990).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1990