In this paper, we propose three new parallel genetic algorithms for simulation-based sequential circuit test generation. The three parallel algorithms are based upon a sequential algorithm that targets a group of faults simultaneously. The first algorithm is PGATEST1, which uses data decomposition to distribute the computation of the fitness of different members of a population among various processors. It produces the same result as the sequential algorithm. The second algorithm, PGATEST2, uses a parallel search strategy where each processor executes the sequential genetic algorithm with a different seed, and uses migration to share information between processors. This parallel algorithm has the potential of obtaining a better quality result than the serial algorithm. The third algorithm, PGATEST3, is a subpopulation based version of PGATEST2, where subpopulations are distributed across processors, and information is migrated from one processor to another.

All implementations were done using the MPI communication library and are therefore portable to many parallel platforms. Experimental results are reported on a wide range of sequential benchmark circuits on an IBM SP-2 multicomputer and a SUN Ultra Enterprise 3000 multiprocessor. All algorithms provide excellent performance in terms of speedup and quality on both shared-memory and distributed-memory parallel platforms.

Gzipped Postscript version of the paper