A fast four-via multilayer MCM router

An efficient multilayer general area router, named V4, for MCM and dense PCB designs is presented. The unique feature of the V4 router is that it uses no more than four vias to route every net and yet produces high quality routing solutions. A number of combinatorial optimization techniques are used in the router to produce high quality routing solutions in polynomial time. As a result, it is independent of net ordering, runs much faster, and has far less memory requirement compared to other multilayer general area routers. The router was tested on several examples, including two industrial MCM designs. Compared with the 3-D maze router, on average the V4 router uses 2% less wire length, 31% fewer vias, and runs 26 times faster. Compared with the SLICE router, on average the V4 router uses 4% less wire length and runs 4.6 times faster.>