© KLMH

Chapter 5 – Global Routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing

Lienig
 Chapter 5 – Global Routing

© KLMH
5.1 Introduction
5.2 Terminology and Definitions
5.3 Optimization Goals
5.4 Representations of Routing Regions
5.5 The Global Routing Flow
5.6 Single-Net Routing
5.6.1 Rectilinear Routing
5.6.2 Global Routing in a Connectivity Graph
5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm
5.6.4 Finding Shortest Paths with A* Search
5.7 Full-Netlist Routing
5.7.1 Routing by Integer Linear Programming
5.7.2 Rip-Up and Reroute (RRR)
5.8 Modern Global Routing
5.8.1 Pattern Routing
5.8.2 Negotiated-Congestion Routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 2

Lienig
 5.1 Introduction

© KLMH
System Specification

Partitioning
Architectural Design
ENTITY test is
port a: in bit;
end ENTITY test;
Functional Design Chip Planning
and Logic Design

Circuit Design Placement

Physical Design
Clock Tree Synthesis

Physical Verification
DRC and Signoff
LVS Signal Routing
ERC
Fabrication

Timing Closure

© 2022 Springer Verlag

Packaging and Testing

Chip

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 3

Lienig
 5.1 Introduction

© KLMH
Given a placement, a netlist and technology information,
• determine the necessary wiring, e.g., net topologies and specific routing
segments, to connect these cells
• while respecting constraints, e.g., design rules and routing resource capacities,
and
• optimizing routing objectives, e.g., minimizing total wirelength and maximizing
timing slack.

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 4

Lienig
 5.1 Introduction

© KLMH
Terminology:
• Net: Set of two or more pins that have the same electric potential
• Netlist: Set of all nets.
• Congestion: Where the shortest routes of several nets are incompatible
because they traverse the same tracks.
• Fixed-die routing: Chip outline and routing resources are fixed.
• Variable-die routing: New routing tracks can be added as needed.

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 5

Lienig
 5.1 Introduction: General Routing Problem

© KLMH
Placement result
Netlist:
N1 = {C4, D6, B3}
N2 = {D4, B4, C1, A4}
3 4
N3 = {C2, D5} C
1
N4 = {B1, A1, C3} A 1 2
4

1 3
B 4 5 6
Technology Information 4
(Design Rules) D

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 6

Lienig
 5.1 Introduction: General Routing Problem

© KLMH
Netlist:
N1 = {C4, D6, B3}
N2 = {D4, B4, C1, A4}
3 4
N3 = {C2, D5} C
1
N4 = {B1, A1, C3} A 1 2
4
N1
1 3
B 4 5 6
Technology Information 4
(Design Rules) D

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 7

Lienig
 5.1 Introduction: General Routing Problem

© KLMH
Netlist:
N1 = {C4, D6, B3}
N2 = {D4, B4, C1, A4}
3 4
N3 = {C2, D5} C
1
N4 = {B1, A1, C3} A 1 2
4
N4 N2 N3 N1
1 3
B 4 5 6
Technology Information 4
(Design Rules) D

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 8

Lienig
 5.1 Introduction

© KLMH
Routing

Multi-Stage Routing
of Signal Nets

Global Detailed Timing-Driven Large Single- Geometric

Routing Routing Routing Net Routing Techniques
Coarse-grain Fine-grain Net topology Power (VDD) Non-Manhattan
assignment of assignment optimization and Ground and
routes to of routes to and resource (GND) clock routing
routing regions routing tracks allocation to routing (Chap. 7)
(Chap. 5) (Chap. 6) critical nets (Chap. 3)
(Chap. 8)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 9

Lienig
 5.1 Introduction

© KLMH
Global Routing

• Wire segments are tentatively assigned (embedded) within the chip layout
• Chip area is represented by a coarse routing grid
• Available routing resources are represented by edges with capacities
in a grid graph
⇒ Nets are assigned to these routing resources

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 10

Lienig
 5.1 Introduction

© KLMH
Global Routing Detailed Routing

N3 N3
N1 N1
N2 N2
N3 N3

N3 N3
N1 N1 N2 N1 N1 N2

Horizontal Vertical
Via
Segment Segment

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 11

Lienig
 5.1.2 Globalverdrahtung

© KLMH
Wire Tracks

Placement

Global Routing

Detailed Routing Congestion Map

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 12

Lienig
 5.2 Terminology and Definitions

© KLMH
• Routing Track: Horizontal wiring path
• Routing Column: Vertical wiring path
• Routing Region: Region that contains routing tracks or columns
• Uniform Routing Region: Evenly spaced horizontal/vertical grid
• Non-uniform Routing Region: Horizontal and vertical boundaries that are
aligned to external pin connections or macro-cell boundaries resulting in
routing regions that have differing sizes

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 13

Lienig
 5.2 Terminology and Definitions

© KLMH
Channel
Rectangular routing region with pins on two opposite sides

Standard cell layout (Two-layer routing)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 14

Lienig
 5.2 Terminology and Definitions

© KLMH
Channel
Rectangular routing region with pins on two opposite sides

Routing channel

Routing channel

Standard cell layout (Two-layer routing)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 15

Lienig
 5.2 Terminology and Definitions

© KLMH
Capacity
Number of available routing tracks or columns
Horizontal Routing Channel

B B C D B C B

h
dpitch

A C A B B C D

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 16

Lienig
 5.2 Terminology and Definitions

© KLMH
Capacity
Number of available routing tracks or columns
• For single-layer routing, the Horizontal Routing Channel
capacity is the height h of the
channel divided by the pitch dpitch
B B C D B C B

• For multilayer routing, the

capacity σ is the sum of the h
dpitch
capacities of all layers.
A C A B B C D
 h 
σ ( Layers ) = ∑
layer ∈Layers

d
 pitch (layer )



VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 17

Lienig
 5.2 Terminology and Definitions

© KLMH
Switchbox (Two-layer macro cell layout) Vertical
Channel
Intersection of horizontal and vertical channels

B C

3
Horizontal B B Horizontal
Channel Channel
A

C A B

Vertical
Channel

Horizontal channel is routed after vertical channel is routed

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 18

Lienig
 5.2 Terminology and Definitions

© KLMH
T-junction (Two-layer macro cell layout)

B C

C
B B Horizontal
Channel
A

C A B

Vertical
Channel

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 19

Lienig
 5.2 Terminology and Definitions

© KLMH
2D and 3D Switchboxes
Bottom pin connection
on 3D switchbox
Metal5
Metal4 3D switchbox

Top pin connection on cell

Pin on channel boundary

Horizontal
channel 2D switchbox
Metal3
Metal2
Metal1
Vertical channel

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 20

Lienig
 5.2 Terminology and Definitions

© KLMH
Gcells (Tiles) with macro cell layout

Metal1 Metal3

Metal2 Metal4 etc.

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 21

Lienig
 5.2 Terminology and Definitions

© KLMH
Gcells (Tiles) with standard cells

Metal1 Metal3
(Standard cells)

Metal2 Metal4 usw.

(Cell ports)
VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 22

Lienig
 5.2 Terminology and Definitions

© KLMH
Gcells (Tiles) with standard cells
(back-to-back)

Metal1 Metal3
(Back-to-back-
standard cells)
Metal2 Metal4 etc.
(Cell ports)
VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 23

Lienig
 5.3 Optimization Goals

© KLMH
• Global routing seeks to
− determine whether a given placement is routable, and
− determine a coarse routing for all nets within available routing regions

• Considers goals such as

− minimizing total wirelength, and
− reducing signal delays on critical nets

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 24

Lienig
 5.3 Optimization Goals

© KLMH
Full-custom design
Layout is dominated by macro cells and routing regions are non-uniform

D
B
C E V
D
A B 4
F H 5 H
1 5 C 2E
A 1 B D 4 H A 3
F
D F 3 V
B
C E C 2 E

© 2022 Springer Verlag

A
F

(1) Types of channels (2) Channel ordering

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 25

Lienig
 5.3 Optimization Goals

© KLMH
Standard-cell design
If number of metal layers is limited, feedthrough cells
must be used to route across multiple cell rows
Feedthrough
A cells

A
Variable-die,
standard cell design:
A Total height =
ΣCell row heights +
All channel heights

A A

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 26

Lienig
 5.3 Optimization Goals

© KLMH
Standard-cell design

Steiner tree solution with Steiner tree solution with

minimal wirelength fewest feedthrough cells

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 27

Lienig
 5.3 Optimization Goals

© KLMH
Gate-array design
Cell sizes and sizes of routing regions between cells are fixed

Available Key Tasks:

tracks
Determine routability

Unrouted Find a feasible solution

net

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 28

Lienig
 5.4 Representations of Routing Regions

© KLMH
5.1 Introduction
5.2 Terminology and Definitions
5.3 Optimization Goals
5.4 Representations of Routing Regions
5.5 The Global Routing Flow
5.6 Single-Net Routing
5.6.1 Rectilinear Routing
5.6.2 Global Routing in a Connectivity Graph
5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm
5.6.4 Finding Shortest Paths with A* Search
5.7 Full-Netlist Routing
5.7.1 Routing by Integer Linear Programming
5.7.2 Rip-Up and Reroute (RRR)
5.8 Modern Global Routing
5.8.1 Pattern Routing
5.8.2 Negotiated-Congestion Routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 29

Lienig
 5.4 Representations of Routing Regions

© KLMH
• Routing regions are represented using efficient data structures

• Routing context is captured using a graph, where

− nodes represent routing regions and
− edges represent adjoining regions

• Capacities are associated with both edges and nodes

to represent available routing resources

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 30

Lienig
 5.4 Representations of Routing Regions

© KLMH
Grid graph model

1 2 3 4 5 1 2 3 4 5
6 7 8 9 10 6 7 8 9 10
11 12 13 14 15 11 12 13 14 15
16 17 18 19 20 16 17 18 19 20

21 22 23 24 25 21 22 23 24 25

ggrid = (V,E), where the nodes v ∈ V represent the routing grid cells (gcells)
and the edges represent connections of grid cell pairs (vi,vj)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 31

Lienig
 5.4 Representations of Routing Regions

© KLMH
Channel connectivity graph

4 4

5
5

1 2 3 6 9 1 2 3 6 9

7 7

8 8

G = (V,E), where the nodes v ∈ V represent channels,

and the edges E represent adjacencies of the channels

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 32

Lienig
 5.4 Representations of Routing Regions

© KLMH
Switchbox connectivity graph

1 4 11 1 4 11

5 9 12 5 9 12

2 6 2 6

7 10 13 7 10 13

3 8 14 3 8 14

G = (V, E), where the nodes v ∈ V represent switchboxes

and an edge exists between two nodes if the corresponding switchboxes
are on opposite sides of the same channel

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 33

Lienig
 5.5 The Global Routing Flow – General Idea

© KLMH
1. Defining the routing regions (Region definition)
− Layout area is divided into routing regions

− Nets can also be routed over standard cells

− Regions, capacities and connections are represented by a graph

2. Mapping nets to the routing regions (Region assignment)

− Each net of the design is assigned to one or several
routing regions to connect all of its pins

− Routing capacity, timing and congestion affect mapping

3. Assigning crosspoints along the edges of the routing regions (Midway routing)
− Routes are assigned to fixed locations or crosspoints
along the edges of the routing regions

− Enables scaling of global and detailed routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 34

Lienig
 5.6 Single-Net Routing

© KLMH
5.1 Introduction
5.2 Terminology and Definitions
5.3 Optimization Goals
5.4 Representations of Routing Regions
5.5 The Global Routing Flow
5.6 Single-Net Routing
5.6.1 Rectilinear Routing
5.6.2 Global Routing in a Connectivity Graph
5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm
5.6.4 Finding Shortest Paths with A* Search
5.7 Full-Netlist Routing
5.7.1 Routing by Integer Linear Programming
5.7.2 Rip-Up and Reroute (RRR)
5.8 Modern Global Routing
5.8.1 Pattern Routing
5.8.2 Negotiated-Congestion Routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 35

Lienig
 5.6.1 Rectilinear Routing

© KLMH
B (2, 6) B (2, 6)

S (2, 4)
C (6, 4) C (6, 4)

A (2, 1) A (2, 1)

Rectilinear minimum Rectilinear Steiner

spanning tree (RMST) minimum tree (RSMT)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 36

Lienig
 5.6.1 Rectilinear Routing

© KLMH
• An RMST can be computed in O(p2) time, where p is the number of terminals
in the net using methods such as Prim’s Algorithm
• Prim’s Algorithm builds an MST by starting with a single terminal and greedily
adding least-cost edges to the partially-constructed tree
• Advanced computational-geometric techniques reduce the runtime to O(p log p)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 37

Lienig
 5.6.1 Rectilinear Routing

© KLMH
Characteristics of an RSMT
• An RSMT for a p-pin net has between 0 and p – 2 (inclusive) Steiner points
• The degree of any terminal pin is 1, 2, 3, or 4
The degree of a Steiner point is either 3 or 4
• A RSMT is always enclosed in the minimum bounding box (MBB) of the net
• The total edge length LRSMT of the RSMT is at least half the perimeter

• of the minimum bounding box of the net: LRSMT ≥ LMBB / 2

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 38

Lienig
 5.6.1 Rectilinear Routing

© KLMH
Transforming an initial RMST into a low-cost RSMT

p2 p2 p2 p2
p3 p3 p3 p3
S1 S

p1 p1 p1 p1

Construct L-shapes between points Final tree (RSMT)

with (most) overlap of net segments

© 2022 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 39

Lienig
 5.6.1 Rectilinear Routing

© KLMH
Hanan grid

• Adding Steiner points to an RMST can significantly reduce the wirelength

• Maurice Hanan proved that for finding Steiner points, it suffices to consider
only points located at the intersections of vertical and horizontal lines
that pass through terminal pins
• The Hanan grid consists of the lines x = xp, y = yp that pass through the
location (xp,yp) of each terminal pin p
• The Hanan grid contains at most (n2-n) candidate Steiner points
(n = number of pins), thereby greatly reducing the solution space
for finding an RSMT

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 40

Lienig
 5.6.1 Rectilinear Routing

© KLMH
Terminal pins Intersection lines Hanan points ( ) RSMT

© 2022 Springer Verlag

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 41

Lienig
 5.6.1 Rectilinear Routing

© KLMH
Definining routing regions Pin connections Pins assigned to grid cells

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 42

Lienig
 5.6.1 Rectilinear Routing

© KLMH
A A
A
A A A A
A A
A A

Pins assigned to grid cells Rectilinear Steiner Assigned routing regions

minimum tree (RSMT) and feedthrough cells

Sequential Steiner Tree Heuristic

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 43

Lienig
 5.6.1 Rectilinear Routing

© KLMH
A Sequential Steiner Tree Heuristic

1. Find the closest (in terms of rectilinear distance) pin pair,

construct their minimum bounding box (MBB)

2. Find the closest point pair (pMBB,pC) between any point pMBB on the MBB
and pC from the set of pins to consider

3. Construct the MBB of pMBB and pC

4. Add the L-shape that pMBB lies on to T (deleting the other L-shape).
If pMBB is a pin, then add any L-shape of the MBB to T.

5. Goto step 2 until the set of pins to consider is empty

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 44

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 45

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 46

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
pc
1 3

MBB

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 47

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1 3 1 3

2 2

1 2 4

pMBB

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 48

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1 3 1 3 1 3

2 2 2

1 2 4
3 4

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 49

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1 3 1 3 1 3

2 2 2

1 2 4
3 4

1 3

4 4

6 5

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 50

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1 3 1 3 1 3

2 2 2

1 2 4
3 4

1 3 1 3

5
2

4 4 4

6 5 6 5
7

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 51

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1 3 1 3 1 3

2 2 2

1 2 4
3 4

1 3 1 3 1 3

5
2 2

4 4 4
6 4

© 2022 Springer Verlag

6 5 6 5 6 5
7 7

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 52

Lienig
 5.6.1 Rectilinear Routing: Example Sequential Steiner Tree Heuristic

© KLMH
1 3 1 3 1 3

2 2 2

1 2 4
3 4

1 3 1 3 1 3

5
2 2

4 4 4
6 4

© 2022 Springer Verlag

6 5 6 5 6 5
7 7

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 53

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
4 4
Channel
connectivity
5
graph 5

1 2 3 6 9 1 2 3 6 9

7 7

8 8

Switchbox 1 4 11 1 4 11
connectivity
graph 5 9 12 5 9 12

2 6 2 6

7 10 13 7 10 13

3 8 14 3 8 14
VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 54

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
Channel
connectivity
graph

Switchbox
connectivity
graph

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 55

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
• Combines switchboxes and channels, handles non-rectangular block shapes
• Suitable for full-custom design and multi-chip modules

Overview:
1 2 3
4,2 4,2 4,2 4,2 3,1 4,2
A
1 2 3
B 4 1,2 1,5 1,2 1,2 7 1,2 0,4 0,1 1,2
4 5 6 7
5 6
A 8 4,2 4,2 9 4,2 4,2
8
B 9
2,2 2,7 2,2 2,2 2,7 2,2
10 11 12
10 11 12

© 2022 Springer Verlag

Routing regions Graph representation Graph-based path search

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 56

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
Defining the routing regions

Horizontal macro-cell edges Vertical macro-cell edges

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 57

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
Defining the connectivity graph

1 8 17 21 23

1 8 17 21 23 2 9 18
2 9 18 3 10
24 19 24
3 10 19 11 12
4
4 1112
13 14 15 20 22 25
5
5 13 1415 20 22 25
6 26 6 26
7 16 27
7 16 27

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 58

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
Horizontal capacity Vertical capacity
of routing region 1 of routing region 1

2 Tracks
1 1,2 8 17 21 23
1 Track

1 8 17 21 23 2 9 18
2 9 18 3 10
24 19 24
3 10 19 11 12
4
4 1112
13 14 15 20 22 25
5
5 13 1415 20 22 25
6 26 6 26
7 16 27
7 16 27

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 59

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
1 1,2 8 1,3 17 1,1 21 1,4 23 1,1

1 8 17 21 23 2 9 18
2,2 2,3 2,1
2 9 18 3 10
24 2,2 1,1 19 4,1 24 6,1
3 10 12
19 4 2,2 11 2,1 2,1
4 1112
13 14 15 20 22 25
5 3,1
5 13 1415 20 22 25 3,2 3,1 3,1 3,1 3,4 3,1

6 26 6 26 1,1
1,2
7 16 27
7 1,2 16 27
1,8 1,1

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 60

Lienig
 5.6.2 Global Routing in a Connectivity Graph

© KLMH
Algorithm Overview
1. Define routing regions
2. Define connectivity graph
3. Determine net ordering
4. Assign tracks for all pin connections in Netlist
5. Consider each net
a) Free corresponding tracks for net’s pins
b) Decompose net into two-pin subnets
c) Find shortest path for subnet connectivity graph
d) If no shortest path exists, do not route, otherwise, assign subnet to the nodes
of shortest path and update routing capacities
6. If there are unrouted nets, goto Step 5, otherwise END

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 61

Lienig
 l
1 2 3
A 4,2 4,2 4,2
w 1 2 3
B
Example
4 5 6 7 4 1,2 1,5 1,2 1,2 7

© KLMH
Global routing A
5 6
of the nets A-A and B-B 8
B 9 8 4,2 4,2 9

10 11 12
2,2 2,7 2,2

10 11 12

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 62

Lienig
 l
1 2 3
A 4,2 4,2 4,2
w 1 2 3
B
Example
4 5 6 7 4 1,2 1,5 1,2 1,2 7

© KLMH
Global routing A
5 6
of the nets A-A and B-B 8
B 9 8 4,2 4,2 9

10 11 12
2,2 2,7 2,2

10 11 12

1 2 3
A 4,2 3,1 4,2
B

4 1,2 0,4 0,1 1,2 7

A
5 6
B
8 4,2 4,2 9

2,2 2,7 2,2

10 11 12

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 63

Lienig
 l
1 2 3
A 4,2 4,2 4,2
w 1 2 3
B
Example
4 5 6 7 4 1,2 1,5 1,2 1,2 7

© KLMH
Global routing A
5 6
of the nets A-A and B-B 8
B 9 8 4,2 4,2 9

10 11 12
2,2 2,7 2,2

10 11 12

1 2 3
A 4,2 3,1 4,2
B

4 1,2 0,4 0,1 1,2 7

A
5 6
B
8 4,2 4,2 9

2,2 2,7 2,2

10 11 12

1 2 3
A 4,2 2,1 3,1

© 2022 Springer Verlag

B

4 1,2 0,4 0,1 1,1 7

A
5 6
B
8 3,1 4,1 9

10 1,1 1,7 1,1

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 64

Lienig
11 12
 l

A
w 1 2 3
B
Example
4 5 6 7

© KLMH
Global routing A
of the nets A-A and B-B 8
B 9

10 11 12

A
B

A
B

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 65

Lienig
 1 2 3
3,1 3,4 3,3
Example 1 2 3
B A

© KLMH
Determine 5 6 7
4 5 6 7 4 1,4 1,1 1,4 1,3
routability B
of a placement A
8 9 10
3,4 3,1 3,3

8 9 10

1 2 3
3,1 3,4 3,3
1 2 3
B A 5 6 7
4 0,3 0,1 0,4 0,2
4 5 6 7
B
A
8 9 10
3,4 3,1 2,2

8 9 10

1 2 3
3,1 3,4 3,3

?
1 2 3
5 6 7
B A
4 0,3 0,1 0,4 0,2
4 5 6 7
B
A
8 9 10 3,4 3,1 2,2

8 9 10

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 66

Lienig
 1 2 3
3,1 3,4 3,3
Example 1 2 3
B A

© KLMH
Determine 5 6 7
4 5 6 7 4 1,4 1,1 1,4 1,3
routability B
of a placement A
8 9 10
3,4 3,1 3,3

8 9 10

1 2 3
3,1 3,4 3,3
1 2 3
B A 5 6 7
4 0,3 0,1 0,4 0,2
4 5 6 7
B
A
8 9 10
3,4 3,1 2,2

8 9 10

1 2 3
2,0 2,3 3,3

1 2 3
5 6 7
B A
4 0,2 0,0 0,3 0,2
4 5 6 7
B
A
8 9 10 2,3 2,0 2,2

8 9 10

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 67

Lienig
 Example 1 2 3
B A

© KLMH
Determine
4 5 6 7
routability B
of a placement A
8 9 10

1 2 3
B A
4 5 6 7
B
A
8 9 10

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 68

Lienig
 5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm

© KLMH
• Finds a shortest path between two specific nodes in the routing graph

• Input
− graph G(V,E) with non-negative edge weights W,
− source (starting) node s, and
− target (ending) node t

• Maintains three groups of nodes

− Group 1 – contains the nodes that have not yet been visited
− Group 2 – contains the nodes that have been visited but for which the
shortest-path cost from the starting node has not yet been found
− Group 3 – contains the nodes that have been visited and for which the
shortest path cost from the starting node has been found

• Once t is in Group 3, the algorithm finds the shortest path by backtracing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 69

Lienig
 5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm

© KLMH
Example

s 1,4 8,8
1 4 7 Find the shortest path from source s
to target t where the path cost
∑w1 + ∑w2 is minimal
8,6 9,7 3,2

2,6 2,8
2 5 8 t

1,4 2,8 4,5

9,8 3,3
3 6 9

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 70

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
(1)
8,6 9,7 3,2

2,6 2,8
2 5 8 t

1,4 2,8 4,5

9,8 3,3
3 6 9

Current node: 1

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 71

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N [2] 8,6
[1]
8,6 9,7 3,2 W [4] 1,4

2,6 2,8
2 5 8 t W [4] 1,4

1,4 2,8 4,5 parent of node [node name] ∑w1(s,node),∑w2(s,node)

9,8 3,3
3 6 9

Current node: 1
Neighboring nodes: 2, 4
Minimum cost in group 2: node 4

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 72

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N [2] 8,6
[1]
8,6 9,7 3,2 W [4] 1,4

2,6 2,8 N [5] 10,11

2 5 8 t W [4] 1,4
W [7] 9,12

1,4 2,8 4,5

N [2] 8,6

9,8 3,3
3 6 9 parent of node [node name] ∑w1(s,node),∑w2(s,node)

Current node: 4
Neighboring nodes: 1, 5, 7
Minimum cost in group 2: node 2

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 73

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N [2] 8,6
[1]
8,6 9,7 3,2 W [4] 1,4

2,6 2,8 N [5] 10,11

2 5 8 t W [4] 1,4
W [7] 9,12

1,4 2,8 4,5 N [3] 9,10

N [2] 8,6
W [5] 10,12
9,8 3,3
3 6 9
N [3] 9,10

parent of node [node name] ∑w1(s,node),∑w2(s,node)

Current node: 2
Neighboring nodes: 1, 3, 5
Minimum cost in group 2: node 3

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 74

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N [2] 8,6
[1]
8,6 9,7 3,2 W [4] 1,4

2,6 2,8 N [5] 10,11

2 5 8 t W [4] 1,4
W [7] 9,12

1,4 2,8 4,5 N [3] 9,10

N [2] 8,6
W [5] 10,12
9,8 3,3
3 6 9
W [6] 18,18 N [3] 9,10

Current node: 3 N [5] 10,11

Neighboring nodes: 2, 6
Minimum cost in group 2: node 5 parent of node [node name] ∑w1(s,node),∑w2(s,node)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 75

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N [2] 8,6
[1]
8,6 9,7 3,2 W [4] 1,4

2,6 2,8 N [5] 10,11

2 5 8 t W [4] 1,4
W [7] 9,12

1,4 2,8 4,5 N [3] 9,10

N [2] 8,6
W [5] 10,12
9,8 3,3
3 6 9
W [6] 18,18 N [3] 9,10

N [6] 12,19
Current node: 5 N [5] 10,11
W [8] 12,19
Neighboring nodes: 2, 4, 6, 8
Minimum cost in group 2: node 7
W [7] 9,12

parent of node [node name] ∑w1(s,node),∑w2(s,node)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 76

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N (2) 8,6
(1)
8,6 9,7 3,2 W (4) 1,4

2,6 2,8 N (5) 10,11

2 5 8 t W (4) 1,4
W (7) 9,12

1,4 2,8 4,5 N (3) 9,10

N (2) 8,6
W (5) 10,12
9,8 3,3
3 6 9
W (6) 18,18 N (3) 9,10

N (6) 12,19
Current node: 7 N (5) 10,11
W (8) 12,19
Neighboring nodes: 4, 8
Minimum cost in group 2: node 8
N (8) 12,14 W (7) 9,12

N (8) 12,14

parent of node [node name] ∑w1(s,node),∑w2(s,node)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 77

Lienig
 1,4 8,8
s 1 4 7 Group 2 Group 3

© KLMH
N (2) 8,6
(1)
8,6 9,7 3,2 W (4) 1,4

2,6 2,8 N (5) 10,11

2 5 8 t W (4) 1,4
W (7) 9,12

1,4 2,8 4,5 N (3) 9,10

N (2) 8,6
W (5) 10,12
9,8 3,3
3 6 9
W (6) 18,18 N (3) 9,10

N (6) 12,19
Retrace from t to s N (5) 10,11
W (8) 12,19

N (8) 12,14 W (7) 9,12

N (8) 12,14

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 78

Lienig
 1,4 9,12
s 1 4 7

© KLMH
12,14

2 5 8 t

3 6 9

Optimal path 1-4-7-8 from s to t

with accumulated cost (12,14)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 79

Lienig
 5.6.4 Finding Shortest Paths with A* Search

© KLMH
• A* search operates similarly to Dijkstra’s algorithm, but extends the cost
function to include an estimated distance from the current node to the target
• Expands only the most promising nodes; its best-first search strategy
eliminates a large portion of the solution space

30 21 29 19 28
t 22 13 O 11 20 t 5 4 O
O 6 1 5 12 O 3 1 s Source
31 O 4 s 2 7 6 O 2 s
t Target
27 18 10 3 8 14
26 17 9 15 23 O Obstacle
25 16 24

Dijkstra‘s algorithm A* search

(exploring 31 nodes) (exploring 6 nodes)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 80

Lienig
 5.6.4 Finding Shortest Paths with A* Search

© KLMH
• Bidirectional A* search: nodes are expanded from both the source and
target until the two expansion regions intersect
• Number of nodes considered can be reduced

t 5 4 O t 3 6 O
O 3 1 4 O 5 1 s Source
O 2 s O 2 s
t Target

O Obstacle

Unidirectional A* search Bidirectional A* search

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 81

Lienig
 5.7 Full-Netlist Routing

© KLMH
5.1 Introduction
5.2 Terminology and Definitions
5.3 Optimization Goals
5.4 Representations of Routing Regions
5.5 The Global Routing Flow
5.6 Single-Net Routing
5.6.1 Rectilinear Routing
5.6.2 Global Routing in a Connectivity Graph
5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm
5.6.4 Finding Shortest Paths with A* Search
5.7 Full-Netlist Routing
5.7.1 Routing by Integer Linear Programming
5.7.2 Rip-Up and Reroute (RRR)
5.8 Modern Global Routing
5.8.1 Pattern Routing
5.8.2 Negotiated-Congestion Routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 82

Lienig
 5.7 Full-Netlist Routing

© KLMH
• Global routers must properly match nets with routing resources,
without oversubscribing resources in any part of the chip

• Signal nets are either routed

− simultaneously, e.g., by integer linear programming, or
− sequentially, e.g., one net at a time

• When certain nets cause resource contention or overflow for routing edges,
sequential routing requires multiple iterations: rip-up and reroute

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 83

Lienig
 5.7.1 Routing by Integer Linear Programming

© KLMH
• A linear program (LP) consists
− of a set of constraints and
− an optional objective function

• Objective function is maximized or minimized

• Both the constraints and the objective function must be linear

− Constraints form a system of linear equations and inequalities

• Integer linear program (ILP): linear program

where every variable can only assume integer values
− Typically takes much longer to solve
− In many cases, variables are only allowed values 0 and 1

• Several ways to formulate the global routing problem as an ILP,

one of which is presented next

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 84

Lienig
 5.7.1 Routing by Integer Linear Programming

© KLMH
• Three inputs
− W × H routing grid G,
− Routing edge capacities, and
− Netlist

• Two sets of variables

− k Boolean variables xnet1, xnet2, … , xnetk, each of which serves as an indicator
for one of k specific paths or route options, for each net net ∈ Netlist
− k real variables wnet1, wnet2, … , wnetk, each of which represents a net weight
for a specific route option for net ∈ Netlist

• Two types of constraints

− Each net must select a single route (mutual exclusion)
− Number of routes assigned to each edge (total usage) cannot exceed its capacity

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 85

Lienig
 5.7.1 Routing by Integer Linear Programming

© KLMH
• Inputs
− W,H: width W and height H of routing grid G
− G(i,j): grid cell at location (i,j) in routing grid G
− σ(G(i,j)~G(i + 1,j)): capacity of horizontal edge G(i,j) ~ G(i + 1,j)
− σ(G(i,j)~G(i,j + 1)): capacity of vertical edge G(i,j) ~ G(i,j + 1)
− Netlist: netlist
• Variables
− xnet1, ... , xnetk: k Boolean path variables for each net net ∈ Netlist
− wnet1, ... , wnetk: k net weights, one for each path of net net ∈ Netlist

• Maximize
∑w
net∈Netlist
net1 ⋅ xnet1 +  + wnetk ⋅ xnetk

• Subject to
− Variable ranges
− Net constraints
− Capacity constraints

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 86

Lienig
 5.7.1 Routing by Integer Linear Programming – Example

© KLMH
Global Routing Using Integer Linear Programming

• Given
− Nets A, B
− W = 5 × H = 4 routing grid G
− σ(e) = 1 for all e ∈ G
− L-shapes have weight 1.00 and Z-shapes have weight 0.99
− The lower-left corner is (0,0).

• Task
− Write the ILP to route the nets in the graph below

A
C
A B
C B

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 87

Lienig
 5.7.1 Routing by Integer Linear Programming – Example

© KLMH
• Solution
− For net A, the possible routes are two L-shapes (A1,A2) and two Z-shapes (A3,A4)

A A1 A A3 Net Constraints:
xA1 + xA2 + xA3 + xA4 ≤ 1
A4 Variable Constraints:
A2
0 ≤ xA1 ≤ 1, 0 ≤ xA2 ≤ 1,
A A 0 ≤ xA3 ≤ 1, 0 ≤ xA4 ≤ 1

− For net B, the possible routes are two L-shapes (B1,B2) and one Z-shape (B3)
Net Constraints:
xB1 + xB2 + xB3 ≤ 1
B2 Variable Constraints:
0 ≤ xB1 ≤ 1, 0 ≤ xB2 ≤ 1,
B1 B B3 B
0 ≤ xB3 ≤ 1
B B
− For net C, the possible routes are two L-shapes (C1,C2) and two Z-shapes (C3,C4)

C3 Net Constraints:
xC1 + xC2+ xC3 + xC4 ≤ 1
C2 C C Variable Constraints:
0 ≤ xC1 ≤ 1, 0 ≤ xC2 ≤ 1,
C1 C4
0 ≤ xC3 ≤ 1, 0 ≤ xC4 ≤ 1
C C
VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 88

Lienig
 5.7.1 Routing by Integer Linear Programming – Example

© KLMH
Horizontal Edge Capacity Constraints:
G(0,0) ~ G(1,0): xC1 + xC3 ≤ σ(G(0,0) ~ G(1,0)) = 1
G(1,0) ~ G(2,0): xC1 ≤ σ(G(1,0) ~ G(2,0)) = 1
G(2,0) ~ G(3,0): xB1 + xB3 ≤ σ(G(2,0) ~ G(3,0)) = 1
G(3,0) ~ G(4,0): xB1 ≤ σ(G(3,0) ~ G(4,0)) = 1
G(0,1) ~ G(1,1): xA2 + xC4 ≤ σ(G(0,1) ~ G(1,1)) = 1
G(1,1) ~ G(2,1): xA2 + xA3 + xC4 ≤ σ(G(1,1) ~ G(2,1)) = 1
G(2,1) ~ G(3,1): xB2 ≤ σ(G(2,1) ~ G(3,1)) = 1
G(3,1) ~ G(4,1): xB2 + xB3 ≤ σ(G(3,1) ~ G(4,1)) = 1
G(0,2) ~ G(1,2): xA4 + xC2 ≤ σ(G(0,2) ~ G(1,2)) = 1
G(1,2) ~ G(2,2): xA4 + xC2 + xC3 ≤ σ(G(1,2) ~ G(2,2)) = 1
G(0,3) ~ G(1,3): xA1 + xA3 ≤ σ(G(0,3) ~ G(1,3)) = 1
G(1,3) ~ G(2,3): xA1 ≤ σ(G(1,3) ~ G(2,3)) = 1

Vertical Edge Capacity Constraints:

G(0,0) ~ G(0,1): xC2 + xC4 ≤ σ(G(0,0) ~ G(0,1)) = 1
G(1,0) ~ G(1,1): xC3 ≤ σ(G(1,0) ~ G(1,1)) = 1
G(2,0) ~ G(2,1): xB2 + xC1 ≤ σ(G(2,0) ~ G(2,1)) = 1
G(3,0) ~ G(3,1): xB3 ≤ σ(G(3,0) ~ G(3,1)) = 1
G(4,0) ~ G(4,1): xB1 ≤ σ(G(4,0) ~ G(4,1)) = 1
G(0,1) ~ G(0,2): xA2 + xC2 ≤ σ(G(0,1) ~ G(0,2)) = 1
G(1,1) ~ G(1,2): xA3 + xC3 ≤ σ(G(1,1) ~ G(1,2)) = 1
G(2,1) ~ G(2,2): xA1 + xA4 + xC1 + xC4 ≤ σ(G(2,1) ~ G(2,2)) = 1
G(0,2) ~ G(0,3): xA2 + xA4 ≤ σ(G(0,2) ~ G(0,3)) = 1
G(1,2) ~ G(1,3): xA3 ≤ σ(G(1,2) ~ G(1,3)) = 1
G(2,2)
VLSI Physical Design: From~Graph
G(2,3): xA1 Closure
Partitioning to Timing ≤ σ(G(2,2) ~Chapter
G(2,3)) = 1 Routing
5: Global 89

Lienig
 5.7.2 Rip-Up and Reroute (RRR)

© KLMH
• Rip-up and reroute (RRR) framework: focuses on hard-to-route nets
• Idea: allow temporary violations, so that all nets are routed, but then iteratively
remove some nets (rip-up), and route them differently (reroute)

B A’
D’
Routing without A Routing with allowing
allowing violations B’ violations and RRR
D C
C’

B A’ B A’
D’ D’
A A
B’ B’
D C D C C’
C’

WL = 21 WL = 19
VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 90

Lienig
 5.8 Modern Global Routing

© KLMH
5.1 Introduction
5.2 Terminology and Definitions
5.3 Optimization Goals
5.4 Representations of Routing Regions
5.5 The Global Routing Flow
5.6 Single-Net Routing
5.6.1 Rectilinear Routing
5.6.2 Global Routing in a Connectivity Graph
5.6.3 Finding Shortest Paths with Dijkstra’s Algorithm
5.6.4 Finding Shortest Paths with A* Search
5.7 Full-Netlist Routing
5.7.1 Routing by Integer Linear Programming
5.7.2 Rip-Up and Reroute (RRR)
5.8 Modern Global Routing
5.8.1 Pattern Routing
5.8.2 Negotiated-Congestion Routing

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 91

Lienig
 5.8 Modern Global Routing

© KLMH
• General flow for modern global routers, where each router uses a unique set
of optimizations:

Global Routing Instance

Net Decomposition Initial Routing

no
Layer Assignment Violations?

(optional) yes

Final Improvements Rip-up and Reroute

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 92

Lienig
 5.8 Modern Global Routing

© KLMH
• Pattern Routing
− Searches through a small number of route patterns to improve runtime
− Topologies commonly used in pattern routing: L-shapes, Z-shapes, U-shapes

Up-Right Right-Up Up-Right- Right-Up- Detour-Up Detour- Detour- Detour-

L-Shape L-Shape Up Right Vertical Down Left Right
Z-Shape Z-Shape U-Shape Vertical Horizontal Horizontal
U-Shape U-Shape U-Shape

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 93

Lienig
 5.8 Modern Global Routing

© KLMH
• Negotiated-Congestion Routing
− Each edge e is assigned a cost value cost(e) that reflects the demand for edge e
− A segment from net net that is routed through e pays a cost of cost(e)
− Total cost of net is the sum of cost(e) values taken over all edges used by net:

cost (net ) = ∑ cost (e)

e∈net
− The edge cost cost(e) is increased according to the edge congestion φ(e), defined
as the total number of nets passing through e divided by the capacity of e:
η( e )
φ(e) =
σ (e)
− A higher cost(e) value discourages nets from using e and implicitly encourages
nets to seek out other, less used edges
⇒ Iterative routing approaches (Dijkstra’s algorithm, A* search, etc.) find routes
with minimum cost while respecting edge capacities

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 94

Lienig
 Summary of Chapter 5 – Types of Routing

© KLMH
Global Routing

• Input: netlist, placement, obstacles + (usually) routing grid

• Partitions the routing region (chip or block) into global routing cells (gcells)
• Considers the locations of cells within a region as identical
• Plans routes as sequences of gcells
• Minimizes total length of routes and, possibly, routed congestion
• May fail if routing resources are insufficient
− Variable-die can expand the routing area, so can't usually fail
− Fixed-die is more common today (cannot resize a block in a larger chip)
• Interpreting failures in global routing
− Failure with many violations => must restructure the netlist
and/or redo global placement
− Failure with few violations => detailed routing may be able to fix the problems

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 95

Lienig
 Summary of Chapter 5 – Types of Routing

© KLMH
Detailed Routing

• Input: netlist, placement, obstacles, global routes (on a routing grid),

routing tracks, design rules
• Seeks to implement each global route as a sequence of track segments
• Includes layer assignment (unless that is performed during global routing)
• Minimizes total length of routes, subject to design rules

Timing-Driven routing

• Minimizes circuit delay by optimizing timing-critical nets

• Usually needs to trade off route length and congestion against timing
• Both global and detailed routing can be timing-driven

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 96

Lienig
 Summary of Chapter 5 – Types of Routing

© KLMH
Large-Net Routing

• Nets with many pins can be so complex that routing a single net
warrants dedicated algorithms
• Steiner tree construction
− Minimum wirelength, extensions for obstacle-avoidance
− Nonuniform routing costs to model congestion
• Large signal nets are routed as part of global routing
and then split into smaller segments processed during detailed routing

Clock Tree Routing / Power Routing

• Performed before global routing to avoid competition for resources

occupied by signal nets

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 97

Lienig
 Summary of Chapter 5 – Routing Single Nets

© KLMH
• Usually ~50% of the nets are two-pin nets, ~25% have three pins,
~12.5% have four, etc.
− Two-pin nets can be routed as L-shapes or using maze search
(in a connectivity graph of the routing regions)
− Three-pin nets usually have 0 or 1 branching point
− Larger nets are more difficult to handle

• Pattern routing
− For each net, considers only a small number of shapes (L, Z, U, T, E)
− Very fast, but misses many opportunities
− Good for initial routing, sometimes is sufficient

• Routing pin-to-pin connections

− Breadth-first-search (when costs are uniform)
− Dijkstra's algorithm (non-uniform costs)
− A*-search (non-uniform costs and/or using additional distance information)

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 98

Lienig
 Summary of Chapter 5 – Routing Single Nets

© KLMH
• Minimum Spanning Trees and Steiner Minimal Trees in the rectilinear topology
(RMSTs and RSMTs)
− RMSTs can be constructed in near-linear time
− Constructing RSMTs is NP-hard, but feasible in practice
• Each edge of an RMST or RSMT can be considered a pin-to-pin connection
and routed accordingly
• Routing congestion introduces non-uniform costs, complicates the construction
of minimal trees (which is why A*-search still must be used)
• For nets with <10 pins, RSMTs can be found using look-up tables (FLUTE)
very quickly

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 99

Lienig
 Summary of Chapter 5 – Full Netlist Routing

© KLMH
• Routing by Integer Linear Programming (ILP)
− Capture the route of each net by 0-1 variables, form equations
constraining those variables
− The objective function can represent total route length
− Solve the equations while minimizing the objective function (ILP software)
− Usually a convenient but slow technique, may not scale to largest netlists
(can be extended by area partitioning)

• Rip-up and Re-route (RRR)

− Processes one net at a time, usually by A*-search and Steiner-tree heuristics
− Allows temporary overlaps between nets
− When every net is routed (with overlaps), it removes (rips up) those with overlaps
and routes them again with penalty for overlaps
− This process may not finish, but often does, else use a time-out

• Both ILP-based routing and RRR can be applied in global and detailed routing
− ILP-based routing is usually preferable for small, difficult-to-route regions
− RRR is much faster when routing is easy
VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 100

Lienig
 Summary of Chapter 5 – Modern Global Routing

© KLMH
• Initial routes are constructed quickly by pattern routing and the FLUTE package
for Steiner tree construction - very fast
• Several iterations based on modified pattern routing to avoid congestion
- also very fast
− Sometimes completes all routes without violations
− If violations remain, they are limited to a few congested spots
• The main part of the router is based on a variant of RRR
called Negotiated-Congestion Routing (NCR)
− Several proposed alternatives are not competitive
• NCR maintains "history" in terms of which regions attracted too many nets
• NCR increases routing cost according to the historical popularity of the regions
− The nets with alternative routes are forced to take those routes
− The nets that do not have good alternatives remain unchanged
− Speed of increase controls tradeoff between runtime and route quality

VLSI Physical Design: From Graph Partitioning to Timing Closure Chapter 5: Global Routing 101

Lienig