language: en

Optimal Algorithms for Substrate Testing in Multi-Chip Modules

Andrew B. Kahng, Gabriel Robins and Elizabeth A. Walkup
Department of Computer Science, UCLA,
Los Angeles, CA 90024-1596
y Department of Computer Science,
University of Virginia, Charlottesville, VA, 22903-2442
z Department of Computer Science,
University of Washington, Seattle, WA 98195

Abstract Multi-chip module (MCM) packaging techniques present several new technical challenges, notably substrate testing. We formulate MCM substrate testing as a problem of connectivity verification in trees via k-probes, and present a linear-time algorithm which computes a minimum set of probes achieving complete open fault coverage. Since actual substrate testing also involves scheduling probe operations, we formulate efficient probe scheduling as a special type of metric traveling salesman optimization and give a provably-good heuristic. Empirical results using both random and industry benchmarks demonstrate reductions in testing costs of up to 21% over previous methods. We conclude with generalizations to alternate probe technologies and several open problems.

Key words: MCMs, testing, graph algorithms, fault detection, circuit probing, TSP.

1 Introduction