A hierarchical MCM routing using four-via routing

Recently, multichip modules (MCM) promise to be widely applied due to the advantage of multichip packaging. But, the routing problem for MCM is more difficult than those for VLSI or PCB because of the high packing density and high performance in MCM design. The problem is formulated as a general-area multilayer routing problem, and several algorithms have been proposed. Among these algorithms, a router of four-via routing proposed by Khoo and Cong (see IEEE Trans. CAD, vol.14, no.10, p.1277-90, 1995), named V4R, is the most efficient. V4R routes each net using no more than four interconnection vias, and it can make a better routing result than other MCM routers. However, there are some unresolved issues; for example, nets are routed in order of their terminal positions, so that more routing layers may be required even for short-length nets, or some routing layers are more congested because as many nets as possible are routed on the routing layers under consideration. In this paper, we present a hierarchical routing approach combined with V4R, aiming to improve the above-mentioned issues but also to preserve the characteristics of four-via routing and efficiency of V4R. In our proposed method, first, a routing area is divided into subareas hierarchically and then V4R is repeatedly applied in each subarea in the bottom-up way. Experimental results show that our approach is fairly good in the total routing-length compared with V4R itself