Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Routingzxc

    Uploaded by

    Chelsea Jagan
    xfvxcvxxvz

    Copyright:

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

    Routingzxc

    Uploaded by

    Chelsea Jagan
    15 views31 pages
    xfvxcvxxvz

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    xfvxcvxxvz

    Copyright:

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

    Routingzxc

    Uploaded by

    Chelsea Jagan
    xfvxcvxxvz

    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 31

    VLSI Routing

    Routing
    Problem
    Given a placement, and a fixed number of metal
    layers, find a valid pattern of horizontal and vertical
    wires that connect the terminals of the nets
    Levels of abstraction:
    o Global routing
    o Detailed routing
    Objectives
    Cost components:
    o Area (channel width)
    o Wire delays
    o Number of layers
    o Additional cost components: number of bends, vias
    Global vs. Detailed Routing
    Global routing
    Input: detailed placement, with exact
    terminal locations
    Determine channel (routing region)
    for each net
    Objective: minimize area (congestion),
    and timing (approximate)
    Detailed routing
    Input: channels and approximate
    routing from the global routing phase
    Determine the exact route and layers
    for each net
    Objective: valid routing, minimize area
    (congestion), meet timing constraints
    Additional objectives: min via, power Figs. [Sherwani]
    Routing Environment
    Chip architecture
    Full-custom
    Standard cell
    Gate Array
    Routing Environment
    Chip architecture
    Full-custom:
    o No constraint on routing regions

    Objective functions are the objective functions


    of general routing problem.

    Routability
    Area Minimization
    Total wire length minimization
    Maximum wire length minimization
    Routing Environment
    Chip architecture
    Standard cell: Feedthroughs

    o Variable channel height?


    o Feed-through cells connect Channel Failed net
    channels

    Channels do not have predetermined capacity


    Feedthroughs have predetermined capacty

    Area minimization
    Minimization to total wire length
    Minimization of maximum wire lenght
    Routing Environment
    Chip architecture
    Gate Array: Tracks
    o Fixed channel height
    o Limited switchbox connections
    o Prefabricated wire segments
    have different weights Failed connection

    Routability
    Minimize total wire length
    Minimize maximum wire length

    Figs. [Sherwani]
    Maze Routing (Lee Algorithm)
    Similar to breadth-first search 5
    Very simple algorithm 5 4 5
    Works on grid graph 4 3 t5 4 5
    Time complexity: grid size (NxN) 3 2 3 4 5
    Algorithm 2 1 s 1 2 3 4 5
    Propagate a wave from source 3 2 1 2 3 4 5
    until hit the sink
    (implemented using a queue)
    Trace back to find the path
    Guaranteed to find the optimal solution
    Usually multiple optimal solutions exist
    More than two terminals?
    For the third terminal, use the path between the first
    two as the source of the wave
    Multiple Terminal Nets
    D

    B 5
    4
    3 4
    3 4
    2 E
    2 3 4
    1

    A 1 3 4
    2
    Multiple Terminal Nets
    D

    B 5
    4
    3 4
    3 4
    2 E
    2 3 4
    1

    A 1 3 4
    2
    Multiple Terminal Nets
    D

    2 3 C
    2
    1 2
    1
    B 1

    1 2
    1 2
    E
    1 2

    A 1 2
    Multiple Terminal Nets
    2 D
    2
    1 1 2
    2
    1 C 1 2
    1 2
    1
    B 1 2

    1 2
    1 2
    E
    1 2

    A 1 2
    Finding More Desirable Paths
    Finding More Desirable Paths
    2 2 2 2 2 2 2 2 3
    2
    1 2 2 2 2 2 1
    1 3 3 3 3 2 2
    1 2 3 3 3 3 2 3
    3 2 3 3 3 3 3 3 3
    3 3 3 3 3 3 3 3
    3
    Finding More Desirable Paths
    2 2 2 2 2 2 2 2 3
    2
    1 2 2 2 2 2 1
    1 3 3 3 3 2 2
    1 2 3 3 3 3 2 3
    3 2 3 3 3 3 3 3 3
    3 3 3 3 3 3 3 3
    3
    Finding More Desirable Paths

    3 1 4
    5 2 2
    5 2 5
    5
    Finding More Desirable Paths

    6
    5 3 1 4
    8 5 2 2
    8 5 2 5
    8 5 8
    Finding More Desirable Paths
    13 11 9
    6
    11 9 7 5 3 1 4
    15 14 11 8 5 2 2
    16 14 11 8 5 2 5
    17 14 11 8 5 8
    Finding More Desirable Paths
    13 11 9
    6
    12 11 9 7 5 3 1 4
    15 14 11 8 5 2 2
    16 14 11 8 5 2 5
    17 14 11 8 5 8
    Finding More Desirable Paths
    13 11 9
    6
    12 11 9 7 5 3 1 4
    13 14 11 8 5 2 2
    16 14 11 8 5 2 5
    17 14 11 8 5 8
    Speed Improvement

    S T
    Hadlocks Algorithm

    2 2 2 2 2 2 2
    2 1 1 1 2 T
    2 1 1 1
    2 1
    2 S
    1 0
    2 1 1
    Soukups Algorithm

    S
    Line Search (Probe) Algorithm
    Mikami-Tabuchis Algorithm
    1 0 2 2
    1 2

    1
    1
    1

    0 1
    Line Search (Probe) Algorithm
    Hightowers Algorithm
    1 0 2 2
    1 2

    1
    1
    1

    0 1
    Multi Terminal Nets
    Minimize Wire length
    Steiner Tree
    Rectilinear Steiner Tree

    Steiner
    point

    MST Steiner tree

    You might also like