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 middl e which split the over-the-cell (OTC) routing region into top and bottom pa rts. Nets are routed in both the channel (if needed) and OTC by using a cha nnel router, Our router uses a combined constraint graph and tile expansion algorithm. We report the first maze router to take advantage of a graph ba sed 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;thi ng that is not determined a priori is the height or number of tracks needed . Our router achieves channelless solutions for the Primary1 circuit by rou ting over the cell in three layers, It also generates equal or better resul ts compared to the best of the previous channel routers for all the example s we have tried. In fact, Sockeye is the first router to achieve density so lutions for the r1, r3, and r4 examples for two layers and for the r3 examp le for three layers.