Parallel Simulated Annealing Based Test Generation in Distributed Computing Paradigms

Seema Bawa
Department of Computer Science & Engineering, TIET, Patiala, India.
E-mail: sbawa@mail.tiet.ac.in
Gopal K. Sharma
Information Technology Group, ABV-IIITM, Gwalior, India.
E-mail:gksharma@iiitm.ac.in

Abstract

Test generation for VLSI circuits is known to be a NP-complete problem and a significant amount of research has been done in past to solve the test generation problem. However, it remains to be a challenging problem due to increased complexity of VLSI circuits and the availability of raw computational power with very high-speed networks of easily affordable powerful workstations. As a result, the tools and techniques proposed earlier may become obsolete for solving computationally intensive problem like test generation. It is found that there are two kinds of approaches to solve the test generation problem: conventional and unconventional. The conventional approaches are mainly targeted for serial machines and when it comes to parallelization, they try to parallelize some portion of the best known serial algorithm(s), which is not the best option always. Therefore, the test generation problem has been reformulated in such a way that parallel and/or distributed algorithms can be devised to solve the problem in parallel and/or distributed computing paradigms. Therefore, the unconventional approaches have been considered for the design and development of parallel and/or distributed algorithms for test generation. These unconventional approaches for test generation are based on either Boolean satisfiability or Optimization techniques. In this paper, optimization based approach is focused in order to devise parallel and distributed methods to solve the VLSI test generation problem.

In the optimization based approach, the test generation problem is reformulated as an energy minimization problem, energy function is minimized to zero in order to find a test pattern for a given fault in the circuit. Hence, the problem is basically the minimization of the energy function which is of the form of pseudo-Boolean quadratic function. The problem reformulation has been detailed in the paper.

Keeping in view of the efficiency and easy parallelization, simulated annealing based approach is found the appropriate choice to be exploited for energy minimization and therefore proposed for optimization based test generation in the paper. The energy function derived for the ATG constraint network for a given fault under consideration in the circuit has been analyzed and function is found multimodal in nature. Simulated annealing efficiently and effectively minimizes such type of functions as the possibility of getting trapped into local minima is very less. However, the selection of the simulated annealing parameters like initial temperature, annealing schedule, temperature length is a complex task especially in parallel and distributed computing environment because the individual processor must be allowed to search the disjoint search space. An efficient parallel simulated annealing based test generation approach is proposed in this paper. The proposed approach handles all the critical issues including the selection of the simulated annealing parameters and effectively minimizes the energy function so derived for test generation.

Finally, the simulated annealing based test generation approach has been successfully implemented in a distributed computing environment using PVM and MPI. The experimental results obtained in PVM and MPI environments have been analyzed using various plots. These results demonstrate the efficiency and effectiveness of the proposed algorithm in both PVM and MPI environments. The algorithm has also been tested and test patterns were generated for some of the practical example circuits. The test generation results for these example circuits have also been depicted using different plots. The results reported in the paper are found quite encouraging and demonstrate effectiveness of the proposed algorithm in both the cases. However, there is a clear evidence that the computation time in MPI case is much less as compared to PVM and therefore, distributed computing paradigm using MPI is preferable.