Distributed Automatic Test Pattern Generation with a Parallel FAN Algorithm

摘要

The generation of test patterns for digital circuits is known as a NP hard problem [2]. Due to the backtracking mechanism in the sequential algorithms for test pattern generation it is difficult to speed up the process. In this paper we present a parallel formulation of the FAN algorithm [3,6] implemented on a heterogeneous cluster of workstations. Two different methods are used to take into account easy- and hard-to-detect faults. We'll show the strategies for our parallel implementations as well as implementation details. Linear speedups are shown with the results in section 4. Furthermore we introduce a new method for test vector compaction using a genetic algorithm. This results in smaller test sets compared to traditional methods. The reader should be familiar with notations of the FAN algorithm.