A ROBUST OVER-THE-CELL CHANNEL ROUTER

Abstract

In this paper, we present an efficient algorithm for over-the-cell routing in the standard cell layout design technology. 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. Our 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. While with the three-layer model, there are two disjoint routing layers over the cells for intercell connections. In our approach, we decompose the problem 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, our algorithm removes a net or a subnet which intersects the column with highest column density and route it over the cells according to some prioritized criteria. In comparison with the previous researches, our approach achieved the best effectiveness and has used the least CPU-time. On the average, the execution speed of our router is 163 and 4163 times faster than that of [8] and [9], respectively. Besides, our algorithm can produce results comparable to those produced by the WISER algorithm [10].