Formulation and heuristic algorithms for multi-chip module substrate testing

作     者：Murakami, Keisuke 

作者机构：Aoyama Gakuin Univ Dept Ind & Syst Engn Tokyo 150 Japan 

出 版 物：《COMPUTERS & ELECTRICAL ENGINEERING》 (计算机与电工)

年 卷 期：2013年第39卷第4期

页      面：1049-1060页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Grants-in-Aid for Scientific Research Funding Source: KAKEN 

主　　题：HEURISTIC algorithms MULTICHIP modules (Microelectronics) ROUTING protocols (Computer network protocols) DEBUGGING in computer science COMPUTER algorithms COMPUTATIONAL complexity CONSTRAINT satisfaction (Artificial intelligence) 

摘      要：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. (C) 2013 Elsevier Ltd. All rights reserved.