Multi-chip module (MCM) substrates are designed for packing two or more semiconductor chips. On these substrates, there are open faults in the wiring, which are electrical disconnections. We must therefore test the substrates to detect open faults, and it is essential to establish an efficient method of testing them. One type of test method uses two probes. Two probes, each touching one edge (end) of an inter-chip wiring, are used to check for the presence of faults. Testing is complete when we have confirmed that no faults exist on the MCM substrate. The objective is to minimize the time to complete testing, that is, our aim is to design efficient routes for the two probes. In this paper, we propose a novel approach of formulating the routing problem as a shortest path problem with covering constraints (SPCC) and we also propose three algorithms for the SPCC. In computational experiments, we show that our formulation and algorithms outperform the existing method.
Multi-chip module (MCM) substrates are designed for packing two or more semiconductor chips [1] and [2] and many different chip dies are connected through a wired interconnect on these substrates. The end of a wired interconnect is called a pin, and a set of pins that are to be electrically connected is called a net (Fig. 1). MCM technology provides dense assembly capabilities and increased chip packaging at relatively low cost [3]. Because of the high-density assembly, MCM has several advantages in terms of power consumption, package volume, and so on [4]. However, high-density assembly causes faults on MCM substrates [5], [6], [7] and [8]. These faults are classified as open faults, short faults, near-open faults, and near-short faults (Fig. 2). An open fault is an electrical disconnection between two points (pins) that are to be connected. A short fault is an electrical connection between two different nets that are not to be connected. A near-open fault is nearly a wire break, but not an electrical disconnection; hence, this fault causes a high-resistance connection. A near-short fault is caused by insufficient spacing between nets (pins); thus, this fault may result in a short fault. In order to detect these faults, we measure the resistance or capacitance in a wire, and the measured value indicates which faults, if any, are present in the wire.Additionally, due to dense assemblies, each process of producing the MCM substrates takes much time. If one process is too time-consuming, the total time of completion of a MCM substrate is also so large. Hence, all processes need to be efficient. In particular, the checking of the above faults is too time-consuming and it is likely to be a bottleneck in the production of MCM substrates. An efficient method for checking faults therefore needs to be established [9] and it leads to a productivity improvement of MCM substrates. Electron-beam testing and probe testing have been proposed for fault detection. Electron-beam testing injects a charge into the nets and then scans them. The main advantage of this method is that it is adaptable to many substrate layouts without having to shift the hardware. In addition, electron-beam testing avoids a large number of mechanical contacts between the testing equipment and the substrate. This method may therefore be used on sensitive pins and fragile substrates. However, the vacuum-based electron-beam system has drawbacks with long testing times and high costs [10]. In contrast, in probe testing, the pins on the substrate are in direct contact with the testing equipment; the equipment is called a probe. This method is much faster and less expensive than electron-beam testing. This paper deals with probe testing, in which two probes simultaneously touch two pins, and wiring faults between the two pins are detected [11], [12], [13], [14], [15] and [16]. We use digital measurements to detect open and short faults, and analog measurements are used for detection of near-open and near-short faults. The analog measurements are usually much slower than the digital ones. Thus, in practice, only open and short fault are considered for probe testing. Furthermore, we can acquire sufficient information on capacitance to detect any short faults, even though we must test all the wires to detect open faults. We therefore usually have only to detect open faults [8].
We formulated the two-probe routing problem as a SPCC. We proposed a heuristic algorithm called the “Improved Greedy Heuristic”; this heuristic quickly finds a good solution. We also proposed the labeling algorithm for the SPCC; this algorithm find better solution than the “Improved Greedy Heuristic”, though more computation time is required. In addition, for larger-scale problem, we proposed a local search algorithm, where the subproblems are solved using our labeling algorithm. In computational experiments, even if it took the “Improved Greedy Heuristic” a little more time to find a feasible solution than the two-phase method, the objective functions of the “Improved Greedy Heuristic” were much smaller than those of the two-phase method. The results of the incumbent solution at 18,000 s showed that our labeling and local search algorithms outperformed the two-phase method for all instances. In particular, our local search algorithm outperformed other methods for large-scale instances.
