Genetic-algorithm- annealing-algorithm-based scheme for MCM interconnect test

A novel optimization scheme based on genetic algorithm (GA) and simulated annealing algorithm (SA) is presented for the Multi-chip Module (MCM) interconnect test generation problem in this paper. The pheromone updating rule and state transition rule of ACA is designed for automatic test generation by combing the characteristics of MCM interconnect test. GA generates the initial candidate test vectors by utilizing genetic operator. In order to get the best test vector with the high fault coverage, SA is employed to evolve the candidates generated by GA. By using this scheme, the ideal searching direction of global optimal solution could be found as soon as possible and the convergence speed of GA was also improved, while the shortcomings of high initial temperature required and slow convergence speed of SA were also overcame. 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 scheme can achieve high fault coverage, compact test set and short execution time.