zip

CS6135 Homework 2-Two-way Min-cut Partitioning Solved

35.00 $

Category:

Description

5/5 - (1 vote)

 

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 min- cut partitioning. Note that any form of plagiarism is strictly prohibited. If you have any problem, please contact TA.

2. ProblemDescription

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

  1. (1)  Input:

     A netlist for a circuit (.nets)

     The size of each cell (.cells)

  2. (2)  Output:

1. Introduction and Goal

 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 |𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐴𝐴) − 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐵𝐵)| < 𝑛𝑛 , where

10 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝐴𝐴) 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. (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. (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.

    1

Example:

.cells .nets

c21 NETn1{c2c3c4} c32 NETn2{c3c7}
c41 NETn3{c3c5c7} c72 NETn4{c1c3c5c7} c51 NETn5{c2c4c8} c11 NETn6{c4c6}

c82 NETn7{c2c6c8}

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

2

Example:

cut_size 1 A4
c1
c3

c5 c7 B4 c2 c4 c6 c8

5. Language/Platform

  1. (1)  Language: C/C++
  2. (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. (1)  Your name and student ID
  2. (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. (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

    and find out how much time you spent on I/O and how much time you spent

$ 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 𝐼𝐼𝐼𝐼 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑛𝑛

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?

3

  1. 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?

  2. How did you find the maximum partial sum and restore the result?
  3. 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?

  4. What else did you do to enhance your solution quality or to speed up your program?
  5. What have you learned from this homework? What problem(s) have you encountered in this homework?
  6. If you implement parallelization, please describe the implementation details and provide some experimental results

7. RequiredItems

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

(1) src/containsallyoursourcecode,yourMakefileandREADME.
 README must contain how to compile and execute your program. An

example of README is like the following figure:

4

(2) output/containsallyouroutputsoftestcasesfortheTAtoverify. (3) bin/containsyourexecutablefile.
(4) CS6135_HW2_{STUDENT_ID}_report.pdfcontainsyourreport.

The file structure would be like the following figure:

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

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

For example:

    $ tar -zcvf CS6135_HW2_109062501.tar.gz HW2/

8. Grading

  •   80%: The solution quality (final cut size) and the runtime of each testcase, hidden testcases included. Note that this part will be executed with single thread version.
  •   20%: The completeness of your report
  •   5% (bonus): Parallelization.

    5

P.S. Using C++11

The C++11 standard is implemented in GCC 4.8.1 and beyond, yet the default version of gcc in our CAD servers (ic21~ic29) is 4.1.2.
You need to source /tools/linux/gnu/setup_toolkit.csh to link gcc to gcc 4.8.5.

However, it’s too much work and too forgettable that you need to source it every time when you log in on a server.
Instead, you can create a shell resource file called .tcshrc in the root folder and put the source command in it. Just enter the following command once, re-log in, and then it won’t never bother you anymore.

$ echo “source /tools/linux/gnu/setup_toolkit.csh” >> ~/.tcshrc

P.S. hMETIS

If you have time, you can learn how to run hMETIS and compare your results with those generated by hMETIS. (http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview)

Notes:
 The executable file name must be named as hw2.
 Please use the following command format to run your program.

    $ hw2 *.nets *.cells *.out

E.g.: $ hw2 p2-1.nets p2-1.cells p2-1.out
 Program must be terminated within 10 minutes for each testcase.
 Grading is based on final cut size (primary) and runtime (secondary).

6

  • HW2-kwukij.zip

Related products