Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Placement and Routing With Congestion Control: ECE556 Final Project Harish Krishnan

    Uploaded by

    veeru
    The document discusses placement and routing techniques as well as congestion control methods for VLSI design. It describes using simulated annealing for placement and rectilinear Steiner trees for routing. Congestion is modeled using a bin-based approach and quantified by the number of net crossings on global edges, with the goal of minimizing total congestion overflow.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Placement and Routing With Congestion Control: ECE556 Final Project Harish Krishnan

    Uploaded by

    veeru
    42 views9 pages
    The document discusses placement and routing techniques as well as congestion control methods for VLSI design. It describes using simulated annealing for placement and rectilinear Steiner trees for routing. Congestion is modeled using a bin-based approach and quantified by the number of net crossings on global edges, with the goal of minimizing total congestion overflow.

    Original Description:

    standed cell

    Original Title

    Standard Cell

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses placement and routing techniques as well as congestion control methods for VLSI design. It describes using simulated annealing for placement and rectilinear Steiner trees for routing. Congestion is modeled using a bin-based approach and quantified by the number of net crossings on global edges, with the goal of minimizing total congestion overflow.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    42 views9 pages

    Placement and Routing With Congestion Control: ECE556 Final Project Harish Krishnan

    Uploaded by

    veeru
    The document discusses placement and routing techniques as well as congestion control methods for VLSI design. It describes using simulated annealing for placement and rectilinear Steiner trees for routing. Congestion is modeled using a bin-based approach and quantified by the number of net crossings on global edges, with the goal of minimizing total congestion overflow.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 9

    Placement and Routing

    With Congestion Control


    ECE556 Final Project
    Harish Krishnan
    Placement and Routing
     Placement - Simulated Annealing.

     Routing- A Rectilinear Steiner Tree to


    connect the pins.

     Boththe above methods are extremely


    popular and widely implemented.
    Congestion Control
     What is the need for congestion control ?
    Prevent spilling of routes into channels. Excessive
    congestion results in local shortage of routing resource.

     TheProblem :- So how do we model


    congestion ?
    We need to find the parameters that affect congestion so
    as to arrive at an objective function to minimize.
    Congestion Control
     Our Model of Congestion – ‘Bin’ based approach

    Global Bins

    Cells

    Global Edges

    Congestion is quantified as number of crossings between routed nets and Global


    Bin edges
    Congestion Model
     For each global edge ‘e’ , de, the Routing Demand of
    ‘e’ is defined as the number of nets crossing ‘e’.
     The Routing Supply of edge ‘e’, se is a fixed value and
    a function of the edge length and technology
    parameters
     A global edge ‘e’ is congested if and only if the routing
    demand exceeds the routing supply (de > se)
     The overflow of edge ‘e’ in case it is congested is the
    difference between the demand and supply . We shall
    use the congestion overflow as the objective to
    minimize.
     The congestion overflow of the layout is defined as the
    summation of the overflow for all global edges.
    Wire length Minimization vs.
    Congestion Minimization
     Minimizing wire length is equivalent to minimizing
    average congestion. However wire length and
    congestion can be inconsistent in local regions.

    Congestion Minimized. Wire length minimized. However there is


    No overflow. overflow
    Post Processing Congestion
    Reduction Algorithms
     Flow – based cell centric algorithm :- Uses a
    flow based approach to move multiple cells
    simultaneously. Attempt to find better location for
    cells so as to minimize congestion. Can be
    modeled easily as a Transportation Problem
    where the source are the cells and the
    destinations are the global bins.
     Problem – Huge Memory Requirements.
     Program has a tendency to crash in case of
    large sample cases.
    Post Processing Algorithm
     Net – Centric Algorithm :- Tries to move net one by one so as to reduce
    congestion.
     Let us assume we have a placement for the given cells.

    1. Route all the nets.


    2. Compute weight for each net. The weight of each net is the number of
    overflowed global edges the net crosses.
    3. Sort the nets in descending order according to their weights.
    4. Move net so as to minimize the congestion overflow. Repeat Step 4
    until all the nets are analyzed.
    5. Update net weights.
    6. Repeat above steps until congestion overflow cannot be further minimized.
    ( We may also set a threshold if we find that the algorithm takes too long to
    complete).

     Thus the entire procedure is a ‘rip and reroute’ implementation.


    Credits
     Modeling and minimization of routing
    congestion.
    Maogang Wang and Majid Sarrafzadeh, North Western
    University
     On the Behavior of Congestion minimization
    during placement
    Wang, Sarrafzadeh, North Western University
     An efficient algorithm for VLSI global routing
    Shawki Areibi , Min Xie and Anthony Vannelli

    You might also like