CCE Theses and Dissertations

Evolutionary Algorithms for VLSI Test Automation

Date of Award

2002

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Graduate School of Computer and Information Sciences

Advisor

Sumitra Mukherjee

Committee Member

Michael J. Laszlo

Committee Member

Junping Sun

Abstract

The generation of binary test patterns for VLSI devices belongs to the class of NP complete problems. As the complexity of VLSI circuits increases, the time to generate test vectors becomes computationally expensive. This dissertation focuses on an evolutionary algorithm (EA) approach for the generation of effective test vectors for single and multiple fault detection in VLSI circuits. EAs provide significant speedup while retaining good quality solutions through heuristic procedures. Although not guaranteed to find optimal solution, EAs are able to find very good solutions for a wide range of problems. Three basic steps are performed during the generation of the test vectors: selection, crossover, and mutation. In the selection step, a bias roulette-wheel and the steady state are used as the reproduction operators. The new candidate test vectors with the highest fitness function replace the old ones, once crossover and mutation occur. Using this scheme, population members steadily improve their fitness level with each generation. A new mutation operator is introduced that increases the Hamming distance among the candidate solutions for shrinkage faults in Programmable Logic Arrays (PLAs). The genetic operators (selection, crossover, and mutation) are applied to the CNF-satisfiability problem for the generation of test vectors for growth faults in PLAs. The CNF constraints satisfaction problem has several advantages over other approaches used for PLA testing. The method proposed eliminates the possibility of intersecting a redundant growth term with a valid candidate test vector. The genetic operator, unlike previous operators used in PLA test generation, does not use lookups or backtracking. That is, the CNF technique eliminates operations (such as backtracking and sharp (#) operation) that can become intractable with increasing PLA size. The proposed evolutionary algorithms based solution aims to address the shortcoming of the existing methods for VLSI testing. Deterministic procedures were used to allow the identification of untestable faults and to improve the fault coverage. This hybrid deterministic/genetic test generator helps improve fault effectiveness and reduce CPU time run. Experimental results have confirmed that the number of untestable faults identified contributed to test generation effectiveness .

This document is currently not available here.

Share Feedback

  Link to NovaCat

Share

COinS