m3D: A multidimensional dynamic configurable router

m3D is the third attempt to produce a dynamically configurable, multilayer router which not only can handle traditional two-level routing problems, but also multilayer routing and three-dimensional routing. The basic maze algorithm is extended so that all points connected to the net under consideration are used to propagate the cost wave. This results in the next shortest link between all the subnetwork components to be found, and a dynamically determined minimum spanning tree to be constructed for each network. Several levels of modifications are conducted on the preexisting routes, along with a rip-up and reroute strategy to handle the more dense problems. Test results indicate that m3D can complete problems as well as, or better than, many of the well-known routers, and that it has the capability of handling a wide range of routing problems. The router is part of an integrated automatic cell layout generation system