A portable message passing distributed library for optimizing combinatorial problems with application to circuits testing. (c2007)

Abstract

Various heuristic algorithms have been used to tackle combinatorial problems such as genetic algorithms and simulated annealing. Recently, MPI has recently emerged as a standard for parallel programmIng on cluster-based machines. However, there is a difficulty in proposing an MPI Java port. This Thesis proposes a portable and distributed library for solving combinatorial optimization problems USIng Java. The library facilitates the use of genetic algorithms and simulated annealing and uses an MPI style message passIng mechanism in order to create parallel processes that can communicate across the network USIng Java RMI. The library is optimized for communication and speed and Improves the programmers efficiency through a visual interface. We verify our approach by formulating a new solution for the test generation problem in VLSI circuits based on parallel fault simulation. The problem is formulated and solved using GA and SA and solved using the proposed Library. The IS CAS benchmarks are attempted and favorable results are reported.