View Full Document


Unformatted text preview:

Congestion driven Codesign of Power and Signal Networks Haihua Su Jiang Hu IBM Corp 11501 Burnet Rd Austin TX 78758 Sachin S Sapatnekar Sani R Nassif ECE Dept Univ of Minnesota 200 Union St SE Minneapolis MN 55455 haihua jianghu nassif us ibm com ABSTRACT We present a global wire design methodology that simultaneously considers the performance needs for both signal lines and power grids under congestion considerations An iterative procedure is employed in which the global routing is performed according to a congestion map that includes the resource utilization of the power grid followed by a step in which the power grid is adjusted to relax the congestion in crowded regions This adjustment is in the form of wire removal in noncritical regions followed by a wire sizing step that overcomes the effects of wire removal Experimental results show that the overall routability can be significantly improved while the power grid noise is maintained within the voltage droop constraint Categories and Subject Descriptors B 8 2 Performance and Reliability Performance Analysis and Design Aids General Terms Algorithms sachin ece umn edu routing resources as they often require shortest path routes to meet their own performance requirements Traditionally these two have been designed independently with the routing needs for a regular power grid being determined first after which the remaining resources are calculated to provide routing resource budgets for the signal nets As the number and criticality of global signal wires becomes more dominant such a methodology becomes unsustainable as the initial budgets may often be entirely unreasonable Therefore in nanometer design there is a strong need for a unified approach to the design of signal wires and power grids with an integrated approach to routing resource management While it is convenient to build a regular power grid with a constant pitch defined as the distance between adjacent wires in the grid some degrees of freedom exist and it is desirable that they be exploited For instance in regions where the demand for routing resources from signal nets is high a sparser power grid may be used as long as the performance constraints on the supply and ground lines can be met likewise signal nets are well advised to avoid the hot spots of the chip if possible since these may need a locally dense power grid Keywords wire congestion codesign signal routing power grid noise Power Grid Macros or Cells Signal Netlist 1 INTRODUCTION The role of interconnect has become increasingly critical in nanometer design and the need to meet stringent performance constraints has resulted in strong contention for scant routing resources A major consumer of these resources is the 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 award CCR 0098117 and by the SRC under contract 99 TJ 714 Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that copies bear this notice and the full citation on the rst page To copy otherwise to republish to post on servers or to redistribute to lists requires prior speci c permission 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 Power Wire Removal Power Grid Sizing Global Router Congestion Map Figure 1 Congestion driven power grid design and global routing The idea of managing wire congestion in signal routing has long been a significant objective in global routing Various 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 Most of these techniques aim at solving the problem solely at the routing stage assuming that the total routing resources are fixed Recent publications 1 11 have presented techniques for simultaneous global routing and resource allocation under performance constraints Power grid optimization techniques have also been studied in 17 19 21 All of these aim at minimizing total power wire area subject to the voltage droop and or electromigration constraints formulating the problem as a nonlinear program The work in 12 presents a technique for shield insertion in a predesigned power grid to control inductive effects To the best of our knowledge no published work performs a concurrent optimization of the power grid along with signal wires under routing congestion constraints and this is the subject of the work presented in this paper Our proposed congestion driven flow is illustrated in Fig 1 The dashed rectangle corresponds to a more conventional global routing flow In essence our approach presents a new flow that adds a feedback loop that permits the readjustment of the signal routing budgets by altering the power grid appropriately Our approach incorporates a tight coupling between power grid adjustments and the routing of signal wires to exploit the altered congestions that result from these adjustments and aims to solve problems with severe congestion constraints where conventional techniques are inadequate 2 POWER GRID AWARE SIGNAL ROUTING As in global routing we tessellate the entire chip into an array of grid cells as shown in Fig 2 a and use the wiring information across the boundaries between neighboring grid cells to estimate the signal wire congestion distributions We denote the width in m of a boundary b between two neighboring grid cells as W b This width represents the limited resources that must be shared on each layer by the supply lines and the signal lines that traverse the boundary as shown in Fig 2 b In other words the number of wires crossing 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 wires on boundary b as P b If a power grid wire pi has a track width of w pi which includes its wire width and the required spacing from an adjacent wire and there are a of such wires p1 p2 pm that cross b then P b Pset m i 1 w pi represents the space that is unavailable for signal wires to cross the boundary Therefore we subtract this quantity from the boundary width to obtain the space available for signal wires as W b P b Typically a uniform track width w is applied to all the signal wires

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...

Join to view SuDAC02 and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SuDAC02 and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?