A Local Search Algorithm for Large-Scale MCM Substrate Testing

DOI Web Site BIBCODE 13 References Open Access
  • MURAKAMI Keisuke
    Department of Industrial and Systems Engineering, Aoyama Gakuin University

Description

A multi-chip module substrate is designed for packing two or more semiconductor chips. On a substrate, there may exist two types of faults; one in a wiring and the other at an intersection of two wires, called via, and the faults must be detected. The testing is performed by a pair of probes, which touch the two ends of an inter-chip wiring. The completion time of the whole testing is the time when it has been confirmed that no fault exists on the substrate. A two-probe routing problem is considered to design efficient routes of the two probes for minimizing the completion time of the whole testing. In this paper, the two-probe routing problem is formulated as a constrained shortest path problem, and a heuristic algorithm by local search techniques is proposed. Computational experiments demonstrate that the proposed heuristic algorithm outperforms a known two-phase heuristic.

Journal

References(13)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top