Optimal Routing in Rectilinear Channels

Programs for integrated circuit layout typically have two phases: placement and routing. The router should produce as efficient a layout as possible, but of course the quality of the routing depends heavily on the quality of the placement. On the other hand, the placement procedure would like to know how good a routing it can expect without actually routing the wires. This paper presents fast algorithms for optimal routing and for accurately estimating the area cost of such routings without actually laying them out.The most common types of junctions occurring in layouts are T-shaped or X-shaped; this paper presents efficient algorithms to measure and produce the optimal rectilinear, two-layer routing in channels formed around such junctions. The ability to do this is based on the new notion of pairwise ordering which is used to propagate routing constraints from one part of a channel to the rest, and alleviates a fundamental problem plaguing traditional channel routers, in addition we present a greedy algorithm for optimal routing in rectangles with a new type of terminal ordering which comes up frequently in practice but has not been studied before.