[SOLVED] CS6135 Homework 5-Global Routing

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:

 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.

•   Vertical and horizontal capacities of grids’ boundaries.
•   A set of nets, 𝑁𝑁 = {𝑛𝑛 , 𝑛𝑛 , … , 𝑛𝑛 }, to be routed over a grid graph 𝐺𝐺 =

12𝑘𝑘
(𝑉𝑉,𝐸𝐸). Each net 𝑛𝑛𝑖𝑖,1 ≤ 𝑖𝑖 ≤ 𝑘𝑘, has a set of pins to be connected.

1

(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.

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

(3) Objective:

𝑠𝑠𝑖𝑖 ⊆ 𝑉𝑉, 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:

𝑑𝑑(𝑒𝑒) − 𝑠𝑠(𝑒𝑒), if 𝑑𝑑(𝑒𝑒) > 𝑠𝑠(𝑒𝑒) 𝑜𝑜𝑣𝑣𝑒𝑒𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜(𝑒𝑒) = � 0, otherwise (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 � � � 𝑜𝑜𝑒𝑒𝑛𝑛𝑙𝑙𝑙𝑙h(𝑒𝑒)� ∀𝑛𝑛𝑖𝑖∈𝑁𝑁 ∀𝑒𝑒∈𝐸𝐸𝑖𝑖

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:

1. (a)  Consider only two layers (vertical and horizontal).
2. (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, 𝑜𝑜𝑒𝑒𝑛𝑛𝑙𝑙𝑙𝑙h(𝑒𝑒) 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.

2

(3)

3. Input Format

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

4. Output Format

Here is an example:

3

4. (4)  The details of your implementation. You have to use flow chart(s) to help elaborate your algorithm, and please follow the symbols usually used in flow charts. (If you are not familiar with the symbols, please refer to this reference: https://www.programiz.com/article/flowchart-programming)If your method is similar to some previous works/papers, please cite thepapers and reveal the difference(s).
5. (5)  What tricks did you do to speed up your program or to enhance your solutionquality? Also plot the effects of those different settings like the ones shown below.
6. (6)  What have you learned from this homework? What problem(s) have you encountered in this homework?

7. Required Items

Please compress HW5/ (using tar) into one with the name CS6135_HW5_${StudentID}.tar.gz before uploading it to iLMS.

1. (1)  src/containsallyoursourcecode,yourMakefileandREADME.
    README must contain how to compile and execute your program. Anexample is like the one shown in HW2.
2. (2)  output/containsallyouroutputsoftestcasesfortheTAtoverify.
3. (3)  bin/containsyourexecutablefile.
4. (4)  CS6135_HW5_${StudentID}_report.pdfcontainsyourreport.

You can use the following command to compress your directory on a workstation:

    $ tar -zcvf CS6135_HW5_{StudentID}.tar.gz <directory>

For example:

    $ tar -zcvf CS6135_HW5_109062501.tar.gz HW5/

8. Grading

 80%: The solution quality (total overflow and total wirelength) and the runtime of each testcase; hidden testcases included.

 20%: The completeness of your report.
 5% Bonus: Parallelization. Please specify your system specification.

5

 5% Bonus: For each testcase, you could draw the congestion map like the following example. The congestion map and the legend are needed.

Notes:

•   Make sure the following commands can be executed. Go into directory “src/”, enter “make” to compile your program and generate the executable file, called “hw5”, which will be in directory “bin/”.  Go into directory “src/”, enter “make clean” to delete your executablefile.
•   Please use the following command format to run your program.

      $ ./hw5 *.modified.txt *.result
  

  E.g.:

      $ ./hw5 ../testcase/ibm01.modified.txt ../output/ibm01.result
  

•   Use arguments to read the file path. Do not write file path in your code.
•   Program must be terminated within 10 minutes for each testcase.
•   Grading is based on total overflow (primary), total wirelength (secondary) andruntime (tertiary).
•   We will test your program by shell script. Please make sure your program can beexecuted by HW5_grading.sh.

6