CS6135 -  VLSI Physical Design Automation Homework 2 - Solved

Two-way Min-cut Partitioning 

 

1. Introduction and Goal
Let 𝐶𝐶 be a set of cells and 𝑁𝑁 be a set of nets. Each net connects a subset of cells. The two-way min-cut partitioning problem is to partition the cell set into two groups 𝐴𝐴 and 𝐵𝐵. The cost of a two-way partitioning is measured by the cut size, which is the number of nets having cells in both groups. In this homework assignment, you are asked to implement FM ALGORITHM to solve the problem of two-way mincut partitioning. Note that any form of plagiarism is strictly prohibited. If you have any problem, please contact TA.

 

2. Problem
The two-way min-cut partitioning problem is defined as follows:

(1)       Input: 

ü   A netlist for a circuit (.nets) ü            The size of each cell (.cells)

(2)       Output: 

ü   The final cut size and a partition result (.out)

(3)       Objective: 

Partition the circuit in two sub-circuits 𝐴𝐴 and 𝐵𝐵, such that the cut size is minimized under the constraint of |𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐴𝐴)− 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐵𝐵)| <  10𝑛𝑛 , where

𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐴𝐴) is the sum of all cell sizes in 𝐴𝐴, 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐵𝐵) is the sum of all cell sizes in 𝐵𝐵, and 𝑛𝑛 is the sum of all cell sizes in the circuit.

 

3. Input File
(1)       The .cells file: 

This input file specifies a list of cells. Each cell statement starts with its cell name (unordered) and size (a positive integer).

(2)       The .nets file: 

This input file specifies a list of nets. Each net statement starts with the keyword “NET” and the name of the net. The cells that are connected by the net are listed between a pair of braces following the net name.

Example: 

.cells  .nets 

 c2 1   NET n1 { c2 c3 c4 } c3 2   NET n2 { c3 c7 } c4 1   NET n3 { c3 c5 c7 } c7 2   NET n4 { c1 c3 c5 c7 } c5 1   NET n5 { c2 c4 c8 } c1 1   NET n6 { c4 c6 } c8 2   NET n7 { c2 c6 c8 } c6 2 

P.S. We will give a testcase generator coded by ruby. It’s applicable to ruby v1.9.3 and beyond. 

 

4. Output File
The .out file: 

Report the cells in each group and the cut size. Please strictly follow the output format or your result will be treated as illegal. You can run the “verifier” to check whether your result is legal or not. Output Format: 

  cut_size # 

A    #cell_in_groupA     cell_ID 

              … 

B    #cell_in_groupB     cell_ID 

              … 

Example:              cut_size 1 

    A 4    c1     c3     c5     c7     B 4 

   c2     c4     c6     c8 

 

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

(2)       Platform: Unix/Linux

 

6. Report
Your report should contain the following content, and you can add more as you wish.

The more the better.

(1)       Your name and student ID

(2)       How to compile and execute your program, and give an execution example. If you implement parallelization, please let me know how to execute it with single thread.

(3)       The final cut size and the runtime of each testcase

P.S. You could use the command time to measure runtime.

e.g., $ /usr/bin/time -p ./main 

$ echo "alias time '/usr/bin/time -p'" >> ~/.tcshrc 

Re-log in then $ time ./main is equal to $ /usr/bin/time -p ./main 

(4)       Runtime = 𝑇𝑇𝐼𝐼𝐼𝐼 + 𝑇𝑇𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑛𝑛. For each case, please analyze your runtime and find out how much time you spent on I/O and how much time you spent on the computation (FM Algorithm).

(5)       The details of your implementation containing explanations of the following questions:

I.            Where is the difference between your algorithm and FM Algorithm described in class? Are they exactly the same?

 

II.         Did you implement the bucket list data structure?

ü   If so, is it exactly the same as that described in the slide? How many are they?

ü   If not, why? You had a better data structure? Or, is bucket list

useless?

III.      How did you find the maximum partial sum and restore the result?

IV.      Please compare your results with the top 5 students’ results from last year and show your advantage either in runtime or in solution quality. Are your results better than them?

ü   If so, please express your advantages to beat them.

ü   If not, it’s fine. If your program is too slow, then what do you reckon the bottleneck of your program is? If your solution quality is inferior, what do you think that you could do to improve the result in the future?

V.        What else did you do to enhance your solution quality or to speed up your program?

VI.      What have you learned from this homework? What problem(s) have you encountered in this homework?

VII.   If you implement parallelization, please describe the implementation details and provide some experimental results