Mighty: a rip-up and reroute detailed router

Abstract

For the macro-cell design style and for routing problems where the routing regions are irregular, two dimensional routers are often necessary. In this paper a new routing technique that can be applied for general two-layer detailed routing problems including switch boxes, channels and partially routed areas, is presented. The routing regions that can be handled are very general: the boundaries can be described by any rectilinear chains and the pins can be on the boundaries of the region or inside it, the obstructions can be of any shape and size. The technique is based on an algorithm that routes incrementally and intelligently the nets in the routing region and allows modifications and rip-up of nets that may impede the complete routing of other nets. The modification steps (also called weak modification) push some segments of nets already routed to make room for a blocked net. The rip-up and re-route steps (called strong modification), remove segments of nets already routed to make room for a blocked connection and is invoked only if weak modification fails. The algorithm is rigorously proven to complete in finite time and its complexity is analyzed. Many test cases have been run and on all the examples known in the literature the router has performed as well or better than existing algorithms. In particular, the Burstein's difficult switch box example has been routed using one less column than the original data. In addition, the router has routed difficult channels such as Deutsch's in density and has performed better than or as well as YACR-II in all the channels available to us. REFERENCES