PLAGA: A Highly Parallelizable Genetic Algorithm for Programmable Logic Arrays Test Pattern Generation

Abstract

An evolutionary algorithm (EA) approach is used in the development of a test vector generation application for single and multiple fault detection of shrinkage faults in Programmable Logic Arrays (PLA). Three basic steps are perfonned during the generation of the test vectors: crossover, mutation and selection. A new mutation operator is introduced that helps increase the Hamming distance among the candidate solutions. Once crossover and mutation have occurred, the new candidate test vectors with higher fitness function scores replace the old ones. With this scheme, population members steadily improve their fitness level with each new generation. The resulting process yields improved solutions to the problem of the PLA test vector generation for shrinkage faults. PLA testing and fault simulation computational time is prohibitive in uniprocessor machines, however PLAGA is well suited for poweifid parallel processing MIMD machines with vectorization capability.