On selecting programmable space compactors for built-in self-text using genetic algorithms

With the increasing complexity of modern VLSI circuits, achieving high quality built-in self-test requires monitoring an increasingly large number of internal nodes. Due to the limitations in observing large numbers of nodes, it has become increasingly necessary to compact the output from a large number of lines to a small number of lines in a process known as space compaction. In the past, space compaction has usually been performed by circuit-independent compactors, such as the popular parity function. Recently, a class of circuit-specific space compactors, known as programmable space compactors (PSCs), has been proposed. A PSC is a highly effective space compactor tailored for a specific circuit under test (CUT) subjected to a specific set of test stimuli. Circuit-specific information such as the fault-free and expected faulty behaviour of a circuit can be used to choose compactors which have better fault coverage and/or lower area costs than the parity function. The drawback of PSCs is the difficulty involved in finding optimal PSCs for a circuit. The space of possible PSC functions is extremely large and grows exponentially with the number of lines to be compacted. Although searching for optimal PSC functions is a difficult problem, it is not impossible. This thesis presents a method for searching for combinational PSCs based upon genetic algorithms (GAs), a randomized search technique. Randomized search techniques, such as simulated annealing and genetic algorithms, have become increasingly popular in recent years as methods for solving search and optimization problems beyond the capabilities of classical techniques. This thesis develops a procedure for using circuit-specific information in the application of (GAs) to the search for optimal PSCs for a given CUT and a given set of test stimuli. A measure of the effectiveness, or fitness, of PSCs is developed as a means for guiding the genetic search. The factors used to assess the effectiveness of a PSC are its 11 fault coverage (estimated by its probability of aliasing) and area (measured in terms of gate equivalents). The nature of GAs allows for searches to be completed in a fixed amount of CPU time. The availability of greater computing resources in the future will enable larger scale searches and improve small-scale searches. The results of genetic searches (limited to approximately 30 minutes of CPU time on a Sun Sparc 10 workstation) for PSCs, with a compaction ratio of 4 : 1, for the ISCAS ‘85 benchmark circuits are presented here. These results show that searches based upon genetic algorithms can find PSCs with better fault coverage at a lower cost than the parity function while using limited computing resources. In some cases, cost savings of up to 80% were realized while simultaneously achieving improved fault coverage over similar space compactors based upon the parity function.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat