MCM Interconnect Test Scheme Based on Ant Colony Algorithm and Particle Swarm Optimization Algorithm

A novel scheme based on ant colony algorithm (ACA) and particle swarm optimization (PSO) algorithm is proposed for Multi-chip Module (MCM) interconnect test generation in this paper. By combing the characteristics of MCM interconnect test, the velocity updating equation and position updating equation of PSO is designed for automatic test generation. PSO generates the initial candidate test vectors. Employing the pheromone-updating rule and state transition rule, ACA evolves these initial candidates. The international standard MCM benchmark circuit provided by the MCNC group was used to verify the approach. Simulation results show that the approach can achieve high fault coverage and compact test set, comparing with the evolutionary algorithms and the deterministic algorithms.

I. INTRODUCTION

The development of digital integrated circuit has put forward urgent demands for test technology. The high reliability of MCM is due to that bare integrated circuit chips are welded and interconnected under high density and small dimension condition [1]. But it is also hard to resolve the problem of MCM interconnect test. Various deterministic interconnecting algorithms have been studied during recent years. We describe the performance of some representative algorithms as follows. For Counting Sequence Algorithm (CSA) [2], vectors are optimal for detecting all shorts in a circuit of N nets, while Modified Counting Sequence Algorithm (MCSA) needs [3] vectors for testing all faults. In order to make the fault coverage rate equal to 100%, True/Compliment Algorithm (T/CA) generate [4] test vectors; Walking One's Algorithm (WOA) is a very common test approach for interconnect testing, whose test set length is N [4].