VLSI Physical Design by Unknown

Author:Unknown
Language: eng
Format: epub, pdf

5.6

Single-Net Routing

151

Example: Determining Routability

Given: (1) Nets A and B, (2) the layout area with routing regions and obstacles (left), and (3) the corresponding connectivity graph (right).

Task: Determine the routability of A and B.

1

2

3

1

2

3

3,1

3,4

3,3

B

A

4

5

6

7

4

5

6

7

1,4

1,1

1,4

1,3

B

8

9

A

10

8

9

10

3,4

3,1

3,3

Solution:

Net A is first routed through nodes (regions) 4–5–6–7–10, which is the shortest path. After this assignment, the horizontal capacities of nodes 4–5–6–7 are

exhausted, i.e., each horizontal capacity ¼ 0.

1

2

3

3,1

3,4

3,3

B

A

4

5

6

7

0,3

0,1

0,4

0,2

B

A

8

9

10

3,4

3,1

2,2

The shortest path for net B was previously through nodes 4–5–6, but this path would now make these nodes’ horizontal capacities negative. A longer (but

feasible) path exists through nodes 4–8–9–5–1–2–6. Thus, this particular

placement is considered routable.

1

2

3

2,0

2,3

3,3

B

A

4

5

6

7

0,2

0,0

0,3

0,2

B

A

8

9

10

2,3

2,0

2,2

152

5

Global Routing

5.6.3

Finding Shortest Paths with Dijkstra’s Algorithm

Dijkstra’s algorithm [6] finds shortest paths from a specified source node to all other nodes in a graph with nonnegative edge weights. This shortest path is based on various path costs, such as edge weights, between two specific nodes in the routing graph—i.e., from a source to a particular target. The algorithm terminates when the minimum path cost to a target node is found. As the routing space is represented as a (graph) grid, this type of path search is often referred to as maze routing.

Dijkstra’s algorithm uses a data structure for storing and querying partial

solutions sorted by path costs from the start. With this, it belongs to the class of best-search algorithms which explore a graph by expanding the most promising node chosen according to a specified cost calculation.

Dijkstra’s algorithm takes as input (1) a graph G(V,E) with nonnegative edge weights W, (2) a source (starting) node s, and (3) a target (ending) node t. The algorithm maintains three groups of nodes—(1) unvisited, (2) considered, and (3) known. 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.

Dijkstra’s Algorithm

Input: weighted graph G(V,E) with edge weights W, source node s, target

node t

Output: shortest path path from s to t

1

group1 = V

// initialize groups 1, 2 and 3

2

group2 = group3 = path = Ø

3

foreach (node node 2 group1)

4

parent[node] = UNKNOWN

// parent of node is unknown, initial

5

cost[s][node] = 1

// cost from s to any node is maximum

6

cost[s][s] = 0

// except the s-s cost, which is 0

7

curr_node = s

// s is the starting node

8

MOVE(s,group1,group3)

// move s from Group 1 to Group 3

9

while (curr_node != t)

// while not at target node t

10

foreach (neighboring node node of curr_node)

11

if (node 2 group3)

// shortest path is already known

12

continue

13

trial_cost = cost[s][curr_node] + W[curr_node][node]

14

if (node 2 group1)

// node has not been visited

15

MOVE(node,group1,group2)

// mark as visited

16

cost[s][node] = trial_cost

// set cost from s to node

17

parent[node] = curr_node

// set parent of node

(continued)

5.6

Single-Net Routing

153

18

else if (trial_cost < cost[s][node]) // node has been visited and

// new cost from s to node is lower

19

cost[s][node] = trial_cost

// update cost from s to node and

20

parent[node] = curr_node

// parent of node

21

curr_node = BEST(group2)

// find lowest-cost node in Group 2

22

MOVE(curr_node,group2,group3)

// and

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.