CS6135 -  VLSI Physical Design Automation Homework 5 - Global Routing  - Solved

1. Introduction
Routing is a crucial step in IC design. The placement stage determines the location of each cell of an IC design. Then in the routing stage, we need to connect all the placed cells with wires properly. The routing problem can be divided into two steps: global routing and detailed routing. During global routing, nets are connected on a coarse‐grain grid graph with capacity constraints. Then detailed routing follows the solution obtained in global routing to find the exact routing solution. The quality of global routing affects timing, power and density in the chip area, and thus global routing is a very important stage in the design cycle.

In this homework, you are asked to implement an existing algorithm or develop your own algorithm to solve the global routing problem with a set of 2-pin nets.

 

2. Problem Description
(1)       Input:  

l   The layout is partitioned into rectangular grids called global bins, as known as G-cells, as shown is Figure (a), and each pin is assumed to lie at the center of the gird that contains the pin.

In the grid graph G shown in Figure (b), each vertex 𝑣𝑣 ∈ 𝑉𝑉 represents a global bin, and each edge 𝑒𝑒 ∈ 𝐸𝐸 corresponds to a boundary between two adjacent global bins.

l   Vertical and horizontal capacities of grids’ boundaries.

l   A set of nets, 𝑁𝑁 = {𝑛𝑛1, 𝑛𝑛2, … , 𝑛𝑛𝑘𝑘}, to be routed over a grid graph 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸). Each net 𝑛𝑛𝑖𝑖, 1 ≤ 𝑖𝑖 ≤ 𝑘𝑘, has a set of pins to be connected. 

 

(2)       Output: 

The critical points’ coordinates of each net after global routing is done. Notice that “critical points” means the starting point, ending point and turning points.

 

(3)       Objective: 

The routing problem for a net 𝑛𝑛𝑖𝑖 is to find an additional subset of vertices,

𝑠𝑠𝑖𝑖 ⊆ 𝑉𝑉, and a subset of edges, 𝐸𝐸𝑖𝑖 ⊆ 𝐸𝐸, to form a Steiner tree 𝑇𝑇𝑖𝑖 = (𝑉𝑉𝑖𝑖, 𝐸𝐸𝑖𝑖), where 𝑉𝑉𝑖𝑖 = 𝑛𝑛𝑖𝑖 ∪ 𝑠𝑠𝑖𝑖. The supply 𝑠𝑠(𝑒𝑒) of an edge 𝑒𝑒 represents the number of available routing tracks passing through it. The number of wires that utilize an edge 𝑒𝑒  is called the demand 𝑑𝑑(𝑒𝑒)  on the edge. In other hand, the demand 𝑑𝑑(𝑒𝑒) represents how many nets that pass through 𝑒𝑒. The overflow on an edge 𝑒𝑒 is defined to be the difference between its demand and supply as shown below:

                                                                     𝑑𝑑(𝑒𝑒) −0𝑠𝑠, otherwise(𝑒𝑒), if 𝑑𝑑(𝑒𝑒) > 𝑠𝑠(𝑒𝑒)  (1) 

𝑜𝑜𝑣𝑣𝑒𝑒𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜(𝑒𝑒) = 

The major optimization objective of global routing is to minimize the total overflow on all edges as shown in (2), and the second objective is to minimize the total wirelength on all edges as shown in (3).

                                                                     min   𝑜𝑜𝑣𝑣𝑒𝑒𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜(𝑒𝑒)                                (2) 

∀𝑒𝑒∈𝐸𝐸

                                                                              min    𝑜𝑜𝑒𝑒𝑛𝑛𝑙𝑙𝑙𝑙ℎ(𝑒𝑒)                                      (3) 

∀𝑛𝑛𝑖𝑖∈𝑁𝑁 ∀𝑒𝑒∈𝐸𝐸𝑖𝑖

This homework asks you to write a global router that can route multiple nets. To simplify the global routing problem, we have some simplifications as follows:

(a)       Consider only two layers (vertical and horizontal).

(b)       Consider only grid-based coordinates. The lower left corner of the global routing region in each layer is (0, 0). The width and height of grids are ignored because all x- and y-coordinates are grid-based.

As the result, 𝑜𝑜𝑒𝑒𝑛𝑛𝑙𝑙𝑙𝑙ℎ(𝑒𝑒) will always be 1.

(c)       Consider only 2-pin nets.

(d)       Consider only fixed wire width and spacing. All wire width and spacing are equal to 1.

 

 

 

3. Input Format
There is only an input file of each testcase. Here is an example:

grid 3 3

// grid # of horizontal grids # of vertical grids vertical capacity 2

// vertical capacity vertical capacity horizontal capacity 2

// horizontal capacity horizontal capacity num net 3

// num net # of nets net0 0 2

// net-name net-id # of pins 

0                    1 

// pin x-grid coordinate pin y-grid coordinate

1                    1 net1 1 2   0 2   1 1 net2 2 2   2 2

  1 0
 

4. Output Format
Here is an example:

net0 0

// net-name net-id

(0, 1, 1)-(1, 1, 1)

// (pin x-grid coordinate, pin y-grid coordinate, 1)

!

net1 1

(0, 2, 1)-(1, 2, 1) (1, 2, 1)-(1, 1, 1) !

net2 2

(2, 2, 1)-(2, 0, 1)

(2, 0, 1)-(1, 0, 1) !
Example: 

 

(0,2) 
net1 
 
 

 
 

(2,2) 
 

 
 
(1,2) 
 

(0,1) 
net0 
 
 

 
 

(2,1) 
 

 
 
(1,1) 
 

(0,0) 
 

 
 

(1,0) 
net2 
 
 

 
 
(2,0) 
 

5. Language/Platform
(1)       Language: C/C++

(2)       Platform: Unix/Linux