An efficient multilayer MCM router based on four-via routing

In this paper, we present an efficient multilayer general area router, named V4R, for MCM and dense PCB designs. One unique feature of the V4R router is that it uses no more than four interconnection vias to route every net and yet produces high quality routing solutions. Another unique feature of the V4R router is it combines global routing and detailed routing in one step and produces high quality detailed routing solutions directly from the given netlist and module placement. Several combinatorial optimization techniques, including efficient algorithms for computing a maximum weighted k-cofamily in a partially ordered set and a maximum weighted noncrossing matching in a bipartite graph, are used to solve the combined problem efficiently. As a result, the V4R router is independent of net ordering, runs much faster, and uses far less memory compared to other multilayer general area routers. We tested our router on several examples, including three industrial MCM designs from MCC. Compared with the 3-D maze router, on average the V4R router uses 44% fewer vias, 2% less wirelength, and runs 26 times faster. Compared with the SLICE router, on average the V4R router uses 9% fewer vias, 4% less wirelength, and runs 3.5 times faster. The V4R also uses fewer routing layers compared to the 3-D maze router and the SLICE router