Circuit Partitioning Using Particle Swarm Optimization for Pseudo-Exhaustive Testing

Pseudo-exhaustive testing reduces the size of test set and test application time compared to exhaustive testing, by partitioning the circuit into cones with lesser number of dependency and exercising each cone with all possible input patterns. This implies that the circuit with large number of inputs should be efficiently partitioned into cones having manageable number of inputs. Partitioning problem is NP-complete and effective heuristic solutions have been proposed in the past. In this paper, we present an approach based on Particle Swarm Optimization (PSO), for circuit partitioning. PSO is based on the iterative use of a set of particles that correspond to states in an optimization problem, moving each agent in a numerical space looking for the optimal position. Experiments on combinational benchmark circuits validate the effectiveness of our work. Our approach shows an improvement of 25% over another PSO based partitioning approach published in [15]. Over PIFAN [16] and I-PIFAN [14] our approach gave a maximum of 72% and 56% improvement, respectively.