Main PageDAC'02Front MatterTable of ContentsSession IndexAuthor IndexCongestion-driven Codesign of Power and SignalNetworks∗Haihua Su†Jiang Hu†Sachin S. Sapatnekar∗Sani R. Nassif††IBM Corp.11501 Burnet Rd.Austin, TX 78758{haihua,jianghu,nassif}@us.ibm.com∗ECE Dept, Univ. of Minnesota200 Union St. SEMinneapolis, MN [email protected] present a global wire design methodology that simul-taneously considers the performance needs for both signallines and power grids under congestion considerations. Aniterative procedure is employed in which the global routingis performed according to a congestion map that includesthe resource utilization of the power grid, followed by a stepin which the power grid is adjusted to relax the congestionin crowded regions. This adjustment is in the form of wireremoval in noncritical regions, followed by a wire sizing stepthat overcomes the effects of wire removal. Experimentalresults show that the overall routability can be significantlyimproved while the power grid noise is maintained withinthe voltage droop constraint.Categories and Subject DescriptorsB.8.2 [Performance and Reliability]: Performance Anal-ysis and Design AidsGeneral TermsAlgorithmsKeywordswire congestion, codesign, signal routing, power grid noise1. INTRODUCTIONThe role of interconnect has become increasingly criticalin nanometer design and the need to meet stringent perfor-mance constraints has resulted in strong contention for scantrouting resources. A major consumer of these resources isthe power distribution network, which contains dense grids.On the other hand, global wires also compete for the same∗This work was supported in part by the NSF under awardCCR-0098117 and by the SRC under contract 99-TJ-714.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for pro£t or commercial advantage and that copiesbear this notice and the full citation on the £rst page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior speci£cpermission and/or a fee.DAC 2002, June 10-14, 2002, New Orleans, Louisiana, USA.Copyright 2002 ACM 1-58113-461-4/02/0006 ...$5.00.routing resources, as they often require shortest-path routesto meet their own performance requirements. Traditionally,these two have been designed independently, with the rout-ing needs for a regular power grid being determined first,after which the remaining resources are calculated to pro-vide routing resource budgets for the signal nets.As the number and criticality of global signal wires be-comes more dominant, such a methodology becomes unsus-tainable as the initial budgets may often be entirely unrea-sonable. Therefore, in nanometer design, there is a strongneed for a unified approach to the design of signal wires andpower grids, with an integrated approach to routing resourcemanagement.While it is convenient to build a regular power grid witha constant pitch (defined as the distance between adjacentwires in the grid), some degrees of freedom exist and it isdesirable that they be exploited. For instance, in regionswhere the demand for routing resources from signal netsis high, a sparser power grid may be used as long as theperformance constraints on the supply and ground lines canbe met; likewise, signal nets are well advised to avoid the hotspots of the chip if possible, since these may need a locallydense power grid.SignalPower Wire RemovalPowerGrid or CellsMacrosNetlistGlobalRouterCongestion Map+ Power Grid SizingFigure 1: Congestion-driven power grid design andglobal routing.The idea of managing wire congestion in signal routinghas long been a significant objective in global routing. Vari-ous congestion-driven techniques include sequential routing(e.g., [6]), rip-up-and-reroute (e.g., [20]), and multicommod-ity flow based methods (e.g., [16]) have been proposed. Mostof these techniques aim at solving the problem solely at therouting stage, assuming that the total routing resources arefixed. Recent publications [1, 11] have presented techniquesfor simultaneous global routing and resource allocation un-der performance constraints.Power grid optimization techniques have also been studiedin [17, 19, 21]. All of these aim at minimizing total powerwire area subject to the voltage droop and/or electromi-gration constraints, formulating the problem as a nonlinearprogram. The work in [12] presents a technique for shieldinsertion in a predesigned power grid to control inductiveeffects.To the best of our knowledge, no published work performsa concurrent optimization of the power grid along with signalwires under routing congestion constraints, and this is thesubject of the work presented in this paper. Our proposedcongestion-driven flow is illustrated in Fig. 1. The dashedrectangle corresponds to a more conventional global rout-ing flow. In essence, our approach presents a new flow thatadds a feedback loop that permits the readjustment of thesignal routing budgets by altering the power grid appropri-ately. Our approach incorporates a tight coupling betweenpower grid adjustments and the routing of signal wires toexploit the altered congestions that result from these adjust-ments, and aims to solve problems with severe congestionconstraints where conventional techniques are inadequate.2. POWER GRID-AWARE SIGNAL ROUT-INGAs in global routing, we tessellate the entire chip into anarray of grid cells, as shown in Fig. 2(a), and use the wiringinformation across the boundaries between neighboring gridcells to estimate the signal wire congestion distributions.We denote the width, in µm, of a boundary b between twoneighboring grid cells as W (b). This width represents thelimited resources that must be shared on each layer by thesupply lines and the signal lines that traverse the boundary,as shown in Fig. 2(b). In other words, the number of wirescrossing b is inherently limited by the width W (b), and W (b)may partly or wholly be occupied by the crossing wires.We represent the total width occupied by power grid wireson boundary b as P (b). If a power grid wire pihas atrack width of w(pi), which includes its wire width andthe required spacing from an adjacent wire, and there area set of such wires, p1, p2, ...pm, that cross b, then P (b) =Pmi=1w(pi) represents the space that is unavailable for sig-nal wires to cross the boundary. Therefore, we subtract