An investigation of circuit partitioning for parallel test generation

Explores the feasibility of using circuit partitioning approach to reduce the run-time complexity of test generation via parallel processing. Characterization of the major phases of test generation is used to show how the inherent parallelism existing in test generation can be exploited during forward implication and backward justification. Upper bounds on the concurrency available in specific are empirically determined by simulating the behavior of a ´perfect´ conflict-free test generation algorithm that operates without backtracking. Results presented for a number of benchmark circuits indicate that the average available parallelism is fairly low, limiting the potential speedup of a circuit partitioning approach to test generation.<>