11/2/2018

GRID ROUTING

PROF. INDRANIL SENGUPTA

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Introduction
• In the VLSI design cycle, routing follows cell placement.
• Once routing is completed, precise paths are defined on the
layout surface, on which conductors carrying electrical signals
are run.
• Routing takes up almost 30% of the design time, and a large
percentage of layout area
area.
– One main objective is to minimize the area required for routing.

1
 11/2/2018

Types of Routing?
• Given a set of blocks placed on a layout surface and defined pin
l
locations:
i
– Given a set of obstacles and a set of pins to connect, determine a
solution to interconnect the pins on a single layer (GRID ROUTING).
– Determine the approximate regions through which each interconnection
net should pass (GLOBAL ROUTING).
– For each routing region, complete the interconnection by assigning
horizontal and vertical metal line segments on the layout surface
(DETAILED ROUTING).

The General Routing Problem

• Given:
– A sett off blocks
bl k with
ith pins
i on the
th boundaries.
b d i
– A set of signal nets.
– Locations of the blocks on the layout surface.
• Objective:
– Find suitable p
paths on the available layout
y space,
p on which wires are
run to connect the desired set of pins.
– Minimize some given objective function, subject to given constraints.

2
 11/2/2018

• Types of constraints:
– Minimum width of routing wires.
– Minimum separation between adjacent wires.
– Number of routing layers available.
– Timing constraints.

GRID ROUTING

3
 11/2/2018

Basic Concept
• The layout surface is assumed to be made up of a rectangular
array off grid
id cells.
ll
• Some of the grid cells act as obstacles.
– Blocks that are placed on the surface.
– Some nets that are already laid out.
• Obj
Objective
i iis to fi
find
d out a single‐layer
i l l path
h (sequence
( off grid
id
cells) for connecting two points belonging to the same net.

• Two broad classes of grid

routing
i algorithms:
l ih
1. Maze routing algorithms.
T
2. Line search algorithms.

4
 11/2/2018

Grid Routing Algorithms

1. Maze running algorithm
’ algorithm
– Lee’s
– Hadlock’s algorithm
2. Line search algorithm
– Mikami‐Tabuchi’s algorithm
– Hightower
Hightower’ss algorithm
3. Steiner tree algorithm

Maze Running Algorithms

• The entire routing surface is represented by a 2‐D array of grid cells.
– Allll pins, wires and
d edges
d off bounding
b d boxes
b that
h enclose
l the
h blocks
bl k
are aligned with respect to the grid lines.
– The segments on which wires run are also aligned.
– The size of grid cells is appropriately defined.
• Wires belonging to different nets can be routed through adjacent
cells
ll without
ih violating
i l i theh width
id h andd spacing
i rules.
l
• Maze routers connect a single pair of points at a time.
– By finding a sequence of adjacent cells from one point to the other.

10

5
 11/2/2018

Lee’s Algorithm
• The most common maze routing algorithm.
• Characteristics:
– If a path exists between a pair of points S and T, it is definitely found.
– It always finds the shortest path.
– Uses breadth‐first search.
• Time and space complexities are O(N2) for a grid of dimension
NN.

11

Phase 1 of Lee’s Algorithm

• Wave propagation phase
– Iterative process.
– During step i, non‐blocking grid cells at Manhattan distance of i from
grid cell S are all labeled with i.
– Labeling continues until the target grid cell T is marked in step L.
• L is the length of the shortest path.
– The process fails if:
• T is not reached and no new grid cells can be labeled during step i.
• T is not reached and i equals M, some upper bound on the path length.

12

6
 11/2/2018

Phase 2 of Lee’s Algorithm

• Retrace phase
– Systematically backtrack from the target cell T back towards the source cell SS.
– If T was reached during step i, then at least one grid cell adjacent to it will be
labeled i‐1, and so on.
– By tracing the numbered cells in descending order, we can reach S following the
shortest path.
• There is a choice of cells that can be made in general.
• In practice, the rule of thumb is not to change the direction of retrace unless
one has to do so.
• Minimizes number of bends.

13

Phase 3 of Lee’s Algorithm

• Label clearance
– All labeled cells except those corresponding to the path just found are
cleared.
– Cells along the path are marked as obstacles.
– Search complexity is as involved as the wave propagation step itself.

14

7
 11/2/2018

Initial
routingg T
problem

15

Phase 1
(i = 1) T

S 1

16

8
 11/2/2018

Phase 1
(i = 2) T

2 1 2

S 1 2

2 1 2

17

Phase 1
(i = 3) T

2 1 2 3

S 1 2

3 2 1 2 3

18

9
 11/2/2018

Phase 1
(i = 4) T
4

2 1 2 3

4 S 1 2

4 3 2 1 2 3

19

Phase 1
(i = 5) T 5

2 1 2 3

5 4 S 1 2

5 4 3 2 1 2 3

20

10
 11/2/2018

6
Phase 1
(i = 6) T 6 5

6 2 1 2 3

6 5 4 S 1 2

5 4 3 2 1 2 3

21

7 6
Phase 1
(i = 7) T 7 6 5

7 4

7 6 2 1 2 3

6 5 4 S 1 2

5 4 3 2 1 2 3

22

11
 11/2/2018

7 6
Phase 2
(RETRACE) T 7 6 5

7 4

7 6 2 1 2 3

6 5 4 S 1 2

5 4 3 2 1 2 3

23

Phase 3
(CLEAR) T
7

5 S
4 3 2 1

24

12
 11/2/2018

Phase 3
(MARK) T
7

5 S
4 3 2 1

25

7 6

T 7 6 5

7 4

7 6 2 1 2 3

6 5 4 S 1 2

5 4 3 2 1 2 3

26

13
 11/2/2018

• Memory Requirement
– Each cell needs to store a number between 1 and L, where
L is some bound on the maximum path length.
• For M x N grid, L can be at most M+N‐1.
– One bit combination to denote empty cell.
– One bit combination to denote obstacles.
log2(L+2) bits per cell

27

• Examples:
1. 2000 x 2000 grid
• B = logg2 4001 = 12
• Memory required = 2000 x 2000 x 12 bits = 6 Mbytes
2. 3000 x 3000 grid
• B = log2 6001 = 13
• Memory required = 3000 x 3000 x 13 bits = 14.6 Mbytes
3. 4000 x 4000 grid
• B = log2 8001 = 13
• Memory required = 4000 x 4000 x 13 bits = 26 Mbytes

28

14
 11/2/2018

• Improvements:
– Instead of using the sequence 1,2,3,4,5,….. for numbering the
cells the sequence 1,2,3,1,2,3,…
cells, 1 2 3 1 2 3 is used.
used
• For a cell, labels of predecessors and successors are
different. So tracing back is easy. 1.5 Mbytes for
log2(3+2) = 3 bits per cell. 2000 x 2000 grid

– Use the sequence 0,0,1,1,0,0,1,1,…..

• Predecessors and successors are again different.
1.0 Mbyte for
log2(2+2) = 2 bits per cell. 2000 x 2000 grid

29

Initial
routingg T
problem

30

15
 11/2/2018

Label
0 T

S 0

31

Label
00 T

0 0 0

S 0 0

0 0 0

32

16
 11/2/2018

Label
001 T

0 0 0 1

S 0 0

1 0 0 0 1

33

Label
0011 T
1

0 0 0 1

1 S 0 0

1 1 0 0 0 1

34

17
 11/2/2018

1 0
Label
0011001 T 1 0 0

1 1

1 0 0 0 0 1

0 0 1 S 0 0

0 1 1 0 0 0 1

35

1 0
Retrace
0011001 T 1 0 0

1 1

1 0 0 0 0 1

0 0 1 S 0 0

0 1 1 0 0 0 1

36

18
 11/2/2018

Reducing Running Time

• Starting point selection
– Choose the starting point as the one that is farthest from the center of the grid.
• Double fan‐out
– Propagate waves from both the source and the target cells.
– Labeling continues until the wavefronts touch.
• Framingg
– An artificial boundary is considered outside the terminal pairs to be connected.
– 10‐20% larger than the smallest bounding box.

37

Connecting Multi‐point Nets

• A multi‐pin net consists of three or more terminal points to be connected.
’ algorithm:
• Extension of Lee’s
– One of the terminals of the net is treated as source, and the rest as targets.
– A wave is propagated from the source until one of the targets is reached.
– All the cells in the determined path are next labeled as source cells, and the
remaining unconnected terminals as targets.
– Process continues.

38

19
 11/2/2018

T1

T2 S

39

T1

T2 S

40

20
 11/2/2018

T1

1 1

1 T2 1 S 1

1 1

41

T1
2 2

2 1 2 1 2

1 T2 1 S 1 2

1 1 2

42

21
 11/2/2018

T1
2

T2 S

43

Hadlock’s Algorithm
• Uses a new method for cell labeling called detour numbers.
– A goal directed search method.
– The detour number d(P) of a path P connecting two cells S and T
is defined as the number of grid cells directed away from its
target T.
– The length of the path P is given by
len(P) = MD (S,T) + 2 d(P)
where MD (S,T) is the Manhattan distance between S and T.

44

22
 11/2/2018

• The cell filling phase of Lee’s algorithm can be modified as

f ll
follows:
– Fill a cell with the detour number with respect to a specified target T
(not by its distance from source).
– Cells with smaller detour numbers are expanded with higher priority.
• Path retracingg is of course more complex,
p , and requires
q some
degree of searching.

45

46

23
 11/2/2018

S 0 0

47

1 1 T
1 1 1
1 1 1
1 1 1
1
1 S 0 0
1 1 1

48

24
 11/2/2018

2 2
1 1 T
2 1 1 1
2 1 1 1
2 1 1 1
2 1
2 1 S 0 0
2 1 1 1
2 2 2

49

3 3 3 3 3
3 2 2 3 3
1 1 3 T
3 2 1 1 1
3 2 1 1 1
3 2 1 1 1
3 2 1
3 2 1 S 0 0
3 2 1 1 1
3 2 2 2
3 3 3

50

25
 11/2/2018

3 3 3 3 3
3 2 2 3 3
1 1 3 T
3 2 1 1 1
3 2 1 1 1
3 2 1 1 1
3 2 1
3 2 1 S 0 0
3 2 1 1 1
3 2 2 2
3 3 3

51

• Advantages:
– Number of grid cells filled up is considerably less as
compared to Lee’s algorithm.
– Running time for an NxN grid ranges from O(N) to O(N2).
• Depends on the obstructions.
• Also
Al locations
l i off S and
d T.
T

52

26
 11/2/2018

Line Search Algorithm

• In maze running algorithms, the time and space complexities are too high.
• An
A alternative
lt ti approach h is
i called
ll d liline searching,
hi which
hi h overcomes this
thi
drawback.
• Basic idea:
– Assume no obstacles for the time being.
– A vertical line drawn through S and a horizontal line passing though T will
intersect
intersect.
• Manhattan path between S and T.
– In the presence of obstacles, several such lines need to be drawn.

53

• Line search algorithms do not guarantee finding the optimal

path.
h
– May need several backtrackings.
– Running time and memory requirements are significantly less.
– Routing area and paths are represented by a set of line segments.
• Not as a matrix as in Lee’s or Hadlock’s algorithm.

54

27
 11/2/2018

Mikami‐Tabuchi’s Algorithm
• Let S and T denote a pair of terminals to be connected.
• Step 0:
– Generate four lines (two horizontal and two vertical) passing through S and T.
– Extend these lines till they hit obstructions or the boundary of the layout.
– If a line generated from S intersects a line generated from T, then a
connecting path is found.
– If theyy do not intersect, theyy are identified as trial lines of level zero.
• Stored in temporary storage for further processing.

55

• Step i of Iteration: (i > 0)

– Pick up trial lines of level i‐1, one at a time.
• Along the trial line, all its grid points are traced.
• Starting from these grid points, new trial lines (of level i) are generated perpendicular
to the trial line of level i‐1.
– If a trial line of level i intersects a trial line (of any level) from the other terminal point, the
connecting path can be found.
• By backtracing from the intersection point to S and T.
• Otherwise, all trial lines of level i are added to temporary storage, and the procedure
repeated.
• The algorithm guarantees to find a path if it exists.

56

28
 11/2/2018

Illustration

T
S

57

Hightower’s Algorithm
• Similar to Mikami‐Tabuchi’s algorithm.
– Instead of generating all line segments perpendicular to a trial line, consider only
th
those lilines th
thatt can be
b extended
t d d beyond
b d the
th obstacle
b t l which
hi h blocked
bl k d ththe preceding
di
trial line.
• Steps of the algorithm:
– Pass a horizontal and a vertical line through source and target points (called first‐
level probes).
– If the source and the target lines meet, a path is found.
– Otherwise, pass a perpendicular line to the previous probe whenever it intersects
an obstacle.
• Concept of escape point and escape line.

58

29
 11/2/2018

Steiner Trees
• A tree interconnecting a set P={P1,…,Pn} of specified points in the rectilinear
plane and some arbitrary points is called a (rectilinear) Steiner tree of P.

• A Steiner tree with minimum total cost is called a Steiner minimal tree (SMT).
– The general SMT problem is NP‐hard.

59

Steiner Tree Based Algorithms

• Minimum length Steiner trees:
– Goall is to minimize the
h sum off the
h length
l h off the
h edges
d off the
h tree.
– Both exact and approximate versions exist.
• Weigted Steiner trees:
– Given a plane partitioned into a collection of weighted regions, an
edge with length L in a region with weight W has cost LW.
• Steiner trees with arbitrary orientations:
– Allows lines in non‐rectilinear directions like +45o and –45o.

60

30