Ant-algorithm-annealing-algorithm-based optimization approach for MCM interconnect test

A novel optimization approach based on ant algorithm (AA) and simulated annealing algorithm (SA) is presented for the Multi-chip Module (MCM) interconnect test generation problem in this paper. In order to apply ant algorithm into the interconnect test, the pheromone updating rule and state transition rule is designed by combing the characteristics of MCM interconnect test generation. By using the method, the ideal searching direction of global optimal solution could be found as soon as possible, while the shortcomings of high initial temperature required and slow convergence speed of simulated annealing algorithm were also overcame. AA generates the initial candidate test vectors in this approach. In order to get the best test vector with the high fault coverage, SA is employed to evolve the candidates generated by AA. The international standard MCM benchmark circuit was used to verify the approach. Comparing with not only the evolutionary algorithms, but also the deterministic algorithms, simulation results indicate that this optimization approach can achieve high fault coverage, compact test set and short execution time.