On the Acceleration of Test Generation Algorithms

TLDR

Accelerating test generation requires reducing backtracks and shortening the time between them. The paper proposes several acceleration techniques and introduces the FAN algorithm for test generation. The authors implement an automatic test generation system that integrates the FAN algorithm with concurrent fault simulation. The FAN algorithm outperforms PODEM, and the integrated system generates tests quickly and effectively on circuits up to 3000 gates.

Abstract

In order to accelerate an algorithm for test generation, it is necessary to reduce the number of backtracks in the algorithm and to shorten the process time between backtracks. In this paper, we consider several techniques to accelerate test generation and present a new test generation algorithm called FAN (fan-out-oriented test generation algorithm). It is shown that the FAN algorithm is faster and more efficient than the PODEM algorithm reported by Goel. We also present an automatic test generation system composed of the FAN algorithm and the concurrent fault simulation. Experimental results on large combinational circuits of up to 3000 gates demonstrate that the system performs test generation very fast and effectively.