A gridless multilayer router for standard cell circuits using CTM cells

We present a gridless multilayer router suitable for standard cell circuits using central terminal model (CTM) cells. A CTM cell has pins in the middle which split the over-the-cell (OTC) routing region into top and bottom parts. Nets are routed in both the channel (if needed) and OTC by using a channel router. Our router uses a combined constraint graph and tile expansion algorithm. We report the first maze router to take advantage of a graph based algorithm to solve the net ordering problem. Unlike a laggard pure maze router, it has the time efficiency of a fast graph based algorithm and the better results of a maze routing algorithm. This is also the first report of the use of a tile expansion maze router for the variable height routing problem. By variable height routing we mean that a single execution of the routing algorithm will result in a completely routed solution. The only thing that is not determined a priori is the height or number of tracks needed. Our router achieves channelless solutions for the Primary1 circuit by routing over the cell in three layers. It also generates equal or better results compared to the best of the previous channel routers for all the examples we have tried. In fact, Sockeye is the first router to achieve density solutions for the r1, r3, and r4 examples for two layers and for the r3 example for three layers.