A robust over-the-cell channel router

An efficient algorithm for over-the-cell routing in the standard cell layout design technology is presented. Two variations are discussed: one aims to minimize the channel density with fewest tracks over the cells while the other aims to minimize the final channel width. The algorithm can fit both the two-layer and three-layer routing models. With the two-layer model, there is a single routing layer over the cells for intercell connections. With the three-layer model, there are two disjoint routing layers over the cells for intercell connections. In this approach, the problem is decomposed into two phases: (1) over-the-cell routing and (2) conventional channel routing. The over-the-cell routing phase, which is executed iteratively, consists of two steps, routing over the cells and choosing net segments within the channel. For each iteration in the over-the-cell routing phase, the algorithm removes a net or a subnet which intersects the column with the highest column density and routes it over the cells according to some prioritized criteria. In comparison with the previous researches, this approach achieved the best effectiveness and has used the least CPU-time