Abstract
performance systems. .4 large portion of system delay, as well as power consumption and electrical noise, can be attributed to the interconnect. To adldress these challenges, much work has been done on topology optimization, wire sizing, driver sizing, and repeater insertion/sizing. While these techniques have received considerable attention, the benefit can be limited in practical design applications. In modern circuits, most nets have only a few pins, allowing very little improvement through topology optimiza~tion. Wire sizing, driver sizing, and repeater insertion increase power consumption and total circuit area, and must therefore be used sparingly. In this paper we explore a new routing paradigm which strikes at the root of the interconnect problern by reducing wire lengths directly. We present a non-Manhattan Steiner tree heuristic, obtaining wire length reductions of much as 17% on average, when compared to rectilinear topologies. Additionally, we present a graph-based interconnect optimization algorithm, called the GRATS-tree algorithm, which allows performance optimization beyond what can be obtained through wire length reduction alone. The GRATStree algorithm produces for a timing-critical net, a number of possible interconnect structures that provide trade-offs among signal delay, routing area, and routing congestion. Previously, non-Manhattan structures have been restricted to channel routing or small hand-designed applications; we present a new global router which allows large scale non-Manhattan design. Although we consider circuit placements performed under rectilinear objectives, our global router can reduce maximum congestion levels by as much as 20%. To our knowledge, this is the first work to consider extensive use of non- Manhattan structures under modern design constraints. While many challenges remain, our experiments indicate considerable promise for this approach.
Date of this Version
April 1999