A graph partitioning heuristic for the parallel pseudo-exhaustive logical test of VLSI combinational circuits

The logical test of integrated VLSI circuits is one of the main phases of their design and fabrication. The pseudo-exahustive approach for the logical test of integrated circuits consists in partitioning the original circuits to be tested into non-overlapping subcricuits with a small, bounded number of subcircuits, which are then exhaustively tested in parallel. In this work, the authors present an approximate algorithm for the problem of partitioning integrated combinational circuits, based on the tabu search metaheuristic. The proposed algorithm presents several original features, such as: the use of a reduced neighborhood, obtained from moves involving only a subset of boundary nodes; complex moves which entail several resulting moves, although the variations in the cost function are easily computable; a bi-criteria cost function combining the number of subcircuits and the number of cuts, which simultaneously adds a diversification strategy to the search; and the use of a bin-packing heuristic as a post-optimization step. The behavior of the proposed algorithm was evaluated through its application to a set of benchmark circuits. The computational results have been compared with those obtained by the other algorithms in the literature, with significant improvements. The average reduction rates have been of the order of 30% in the number of subcircuits in the partition, and of the order of 40% in the number of cuts.