Single-probe traversal optimization for testing of MCM substrate interconnections

In this paper, we investigate the problem of electrical testing of multichi p modules (MCM's) substrate interconnections prior to chip assembly. Recent ly, single-probe test techniques for MCM substrate interconnections have be en proposed that provide fault coverage comparable to double-probe test tec hniques. This work has two objectives. First, we assess the advantage of si ngle-probe test, techniques over double-probe techniques where overall test time is concerned. Second, we develop efficient heuristics to optimize the total distance traveled by a single test probe on an MCM substrate and: th ereby reduce the substrate testing time. We provide tight bounds on both si ngle-and double-probe testing times. For substrates with two to three termi nal pads in each of n nets, the expected travel time for a single probe is shorter by a factor of order n(1/4). Experiments on benchmark MCM netlists with real probe traversal speeds confirm that single-probe testing has an i ncreasing advantage over double-probe testing,. as the number of nets incre ases, For an MCM substrate of 800 nets, the projected test time is faster b y a factor of 2.5, A practical algorithm for finding efficient traversal :r outes is presented. It:is based on heuristic procedures of tour constructio n and local improvement for solving a variation of the traveling salesman p roblem. Experiments show that up to 40% reduction in probe traversal time c an be obtained with our algorithm.