Vlsi Physical Design Automation: Lecture 18. Global Routing (ii)

EE382V Fall 2006

VLSI Physical Design Automation Lecture 18. Global Routing (II) Prof. David Pan [email protected] Office: ACES 5.434 Minsik Cho [email protected] 10/22/08

1

Global Routing Approaches •

Sequential Approach (Rip-up and Re-route) – – – –

Maze Routing Line probing Shortest Path Based Algorithms Steiner Tree Based Algorithms

• Concurrent Approach – Integer Programming

2

Sequential Approach Algorithm: 1. Graph modeling of the routing regions 2. For each net k: We can use different 2.1 Find a route r for net k on the graph. methods to do this. 2.2 For each edge e in r: 2.2.1 capacity(e) = capacity(e) - 1 2.2.2 if capacity(e) < 0 then cost(e) = α × cost(e)

3

Maze Routing for Multi-Terminal Nets

4

Maze Routing on Weighted Graph

5

Example of Weighted Graph

6

Mikami & Tabuchi’s Algorithm

7

Line Probing • Keep two lists of line segments, slist and tlist, for the source and the target respectively. • If a line segment from slist intersects with one from tlist, a route is found; else, new line segments are generated from the escape points.

S

slist

T

Intersection

tlist

8

Line Probing • We can use all the grid vertices on the line segments as escape points: 1 0 1 1 1 0 1 1 1 1

Escape point

S T

1 0 1 1

Iteration number

1 0 1 • Always find a path but may not be optimal.

9

Hightower’s Algorithm

10

Line Probing • We can pick just one escape point from each line segment. 0 1

0

S T

Iteration number 0 Escape point

1 1 0

• May fail to find a path even if one exists. 11

12

Comparison of Algorithms

13

BFS based Maze Routing (A*) • Need to search whole space? – Guide the search to the goal explicitly

• A* search is faster if you need “good path”, not “perfect path” – Use priority queue – C(n) = F(n)+H(n) • F(n) is a computed cost from source to current location. • H(n) is a predicted cost from current location to target. • If H(n)=0, it becomes maze routing!

– Optimal (shortest path) when H(n) <= H’(n) (no overestimation) • H’(n) is the exact cost • H(n)=0 never overestimates! 14

Maze vs A* routing (I)

15

Maze vs A* routing (II)

16

Shortest Path Based Algorithms • For 2-terminal nets only. • Use Dijkstra’s algorithm to find the shortest path between the source s and the sink t of a net. • Different from Maze Routing: – The graph need not be a rectangular grid. – The edges need not be of unit length.

17

Dijkstra’s Shortest Path Algorithm • Label of vertices = Shortest distance from S. • Let P be the set of permanently labeled vertices. • Initially, – P = Empty Set. – Label of S = 0, Label of all other vertices = infinity.

• While (T is not in P) do – Pick the vertex v with the min. label among all vertices not in P. – Add v to P. – Update the label for all neighbours of v.

18

Dijkstra’s Algorithm: Example Min. Label Vertex B 1 T T 8 14 10

8

8

8

P (Permanently Labeled) B 1 T B 1 10 10 10

B 1 T 8 9 10 2 3 94 6 0 7 S 5 5 2 7 C A

B 1 T 8 9 10 2 3 94 6 0 7 S 5 5 2 7 C A

B 1 T 8 13 10 2 3 94 6 0 7 S 5 5 2 7 C A 19

A

C

8

2 3 94 6 0 7 S 5 5 2 7

8

2 3 94 6 0 7 S 5 5 2

8

2 3 94 6 0 7 S 5 2

A

C

A

C

Steiner Tree Based Algorithms • For multi-terminal nets. • Find Steiner tree instead of shortest path. • Construct a Steiner tree from the minimum spanning trees (MST)

20

Net Ordering • In sequential approach, we need some net ordering. • A bad net ordering will increase the total wire length, and may even prevent com-pletion of routing for some circuits which are indeed routable.

A

B B A

B first (Good order)

A

B B

A

A first (Bad order)

21

Criteria for Net Ordering • Criticality of net - critical nets first. • Estimated wire length - short nets first since they are less flexible. • Consider bounding rectangles (BR):

A

B B

A B is in A’s BR

Which one should be routed first and why? (Note that this rule of thumb is not always applicable.) 22

Net Ordering (cont’d)

23

Rip-Up and Re-route • It is impossible to get the optimal net ordering. • If some nets are failed to be routed, the rip-up and reroute technique can be applied: Cannot route C

So rip-up B and route C first.

Finally route B.

A

A

A

A

A

A

B

B

B

B

B

B

C

C

C

C

C

C 24

Concurrent Approach • • •

Consider all the nets simultaneously. Formulate as an integer program. Given: Nets

Set of possible routing trees

net 1

T11, T12, ...... , T1k1

: : net n

: : Tn1, Tn2, ... , Tnkn

Lij = Total wire length of Tij Ce = Capacity of edge e • Determine variable xij s.t. xij = 1 if Tij is used xij = 0 otherwise. 25

Integer Program Formulation ki

n

Min.

∑∑ L × x ij

i =1

s.t.

ij

j =1

∑ ∑

ki

x = 1 for all i = 1 ,  , n ij j =1

i , j s.t. e∈Tij

xij ≤ Ce

for all edge e

xij = 0 or 1 ∀i, j

26

Concurrent Approach: Example 2

1

1

3 3 1 2 2

Solution 2

1

1

3 3 1 2 2

1,2

b

1,3

Possible trees:

d

net 1: 2

3

3

1,2

net 2: 2

3

3

Ca= Cb= Cc= Cd= 2

net 3: 2

2

a 2,3

c

Min. 2 x11 + 3 x12 + 3 x13 + 2 x21 + 3 x22 + 3 x23 + 2 x31 + 2 x32  x11 + x12 + x13 = 1;  x + x + x = 1; What are the constraints  21 22 23 s.t.  for edge capacity? x + x = 1 ;  31 32  xij = 0 or 1 ∀i, j; x12 + x13 + x21 + x23 + x31 < Ca 27

Integer Programming Approach • • • •

Standard techniques to solve IP. No net ordering. Give global optimum. Can be extremely slow, especially for large problems. To make it faster, a fewer choices of routing trees for each net can be used. May make the problem infeasible or give a bad solution. • Determining a good set of choices of routing trees is a hard problem by itself.

28

Hierarchical Approach to Speed Up Integer Programming Formulation For Global Routing M. Burstein and R. Pelavin, “Hierarchical Wire Routing”, IEEE TCAD, vol. CAD-2, pages 223-234, Oct. 1983.

10/22/08

29

Hierarchical Approach • Large Integer Programs are difficult to solve. • Hierarchical Approach reduces global routing to routing problems on a 2x2 grid. • Decompose recursively in a top-down fashion. • Those 2x2 routing problems can be solved optimally by integer programming formulation.

30

Hierachical Approach: Example • Solving a 2xn routing problem hierarchically. Level 1

Level 2

Level 3

Solution: 31

Types of 2x2 Routing Problems Type 1

Type 7

Type 2

Type 8

Type 3

Type 9

Type 4

Type 10

Type 5

Type 11

Type 6 32

Objective Function of 2x2 Routing Possible Routing Trees: T11, T12, T21, T22,....., T11,1,..., T11,4 # of nets of each type: n1, ..., n11 Determine xij: # of type-i nets using Tij for routing. yi: # of type-i nets that fails to route. yi + ∑ j xij = ni

i = 1,  ,11

Want to minimize ∑i =1 yi . 11

33

Constraints of 2x2 Routing Cb

Bab Ca Bda

a

b d Cd

c

Constraints on Edge Capacity: Bbc Cc Bcd

∑i, j s.t. a∈T ∑i, j s.t. b∈T ∑i, j s.t. c∈T ∑i, j s.t. d∈T

ij

ij

ij ij

xij ≤ Ca xij ≤ Cb xij ≤ Cc xij ≤ Cd

Constraints on # of Bends in a Region:

∑i, j s.t. T ∑i, j s.t. T ∑i, j s.t. T ∑i, j s.t. T

ij

has a bend in region ab

xij ≤ Bab

ij

has a bend in region bc

xij ≤ Bbc

ij

has a bend in region cd

xij ≤ Bcd

ij

has a bend in region da

xij ≤ Bda 34

Pop Quiz •

If you two nets, one with 2 pins, the other with 4 pins with a zero capacity edge

C=1

C=0

– What is going to be the result?

yi + ∑ j xij = ni

i = 1,  ,11

Want to minimize ∑i =1 yi .

Type 1

11

Type 11

35

ILP Formulation of 2x2 Routing Min. ∑i =1 yi s.t. yi + ∑ j xij = ni i = 1,  ,11 xij ≥ 0, yi ≥ 0 ∀i, j 11

∑i, j s.t. a∈T ∑i, j s.t. b∈T ∑i, j s.t. c∈T ∑i, j s.t. d∈T

ij

ij

ij ij

• •

xij ≤ Ca xij ≤ Cb xij ≤ Cc xij ≤ Cd

∑i, j s.t. T ∑i, j s.t. T ∑i, j s.t. T ∑i, j s.t. T

ij

has a bend in region ab

xij ≤ Bab

ij

has a bend in region bc

xij ≤ Bbc

ij

has a bend in region cd

xij ≤ Bcd

ij

has a bend in region da

xij ≤ Bda

Only 39 variables (28 xij and 11 yi) and 19 constraints (plus 38 non-negative constrains). Problems of this size are usually not too difficult to solve. 36