EE 582 (Physical Design Automation of VLSI Circuits and Systems)

Assignment 2

In this assignment, you will analyze the Kernighan-Lin partitioning algorithm in two aspects.

Download the following file into your working directory.

• wget http://eecs.wsu.edu/~daehyun/teaching/2014_EE582/assignments/a02.tar.gz

Unzip it.

• tar xvfz a02.tar.gz

You will see the following directories.

• hgr: benchmark files

• kl1: KL algorithm (slow version)

• kl2: KL algorithm (fast version)

You can compile each source code by just entering the directory and running "make".

Once you have an executable (its name is KL by default), you can run it as follows.

• ./KL ../hgr/fract.hgr (or other benchmark files)

It will print out some debugging messages and show the final results as follows:

• Final result: cutsize: 4144 -> 582 (-3562)

Re-compile the source code after commenting out the gain/sum debugging message lines so that you are not bugged by the long messages.

1. Comparison of the quality of the slow/fast versions

The fast version has trade-offs between the runtime and the solution quality.

The goal in this assignment is to compare the quality of the slow and the fast versions.

For that, you are supposed to run kl1 and kl2 with the same seed value for srand() and compare the final cutsize.

At line 15 in kl.cpp in kl1 and kl2, you will see the following line:

• srand (time(NULL));

If you compile the current source, you will always get different initial solutions. However, our goal in this assignment is to compare the quality of the slow and the fast versions. Therefore, we want to start from the same initial partitioning result to be fair for both kl1 and kl2.

Change the source code as follows:

• srand (1097);

Notice that 1097 is just a number I decided to use. If you use the same seed value for kl1 and kl2, you will always get the same initial partitioning result for kl1 and kl2.

Run kl1 and kl2 with 100 different seed numbers. (For fract.hgr and p1.hgr)

Draw a graph comparing kl1 and kl2 (for each benchmark). The x-axis and the y-axis of the graph should be the initial cutsize and the difference of the final cutsizes of kl1 and kl2, respectively. (You will plot 100 dots in the graph.)

What to submit

• The 100 seed numbers used for fract.hgr and p1.hgr.

• A comparison graph for each benchmark (fract.hgr and p1.hgr).

• Discussion on the comparion of the quality of the slow/fast versions. (Focus on the quality itself. You don't need to mention anything about the runtime.)

2. Is the quality of a final solution dependent on the quality of its initial solution?

The goal in this assignment is to analyze the relationship between the quality of the initial and the final solutions.

For that, you are supposed to run kl2 with several seed values for srand() and analyze the relationship.

Run kl2 with 100 different seed numbers for p2.hgr, structP.hgr, and biomedP.hgr.

Draw a graph comparing the quality (cutsize) of the initial and the final solutions (for each benchmark). The x-axis and the y-axis of the graph should be the initial cutsize and the final cutsize, respectively. (You will plot 100 dots in the graph.)

What to submit

• The 100 seed numbers used for p2.hgr, structP.hgr, and biomedP.hgr.

• The solution quality graph for each benchmark.

• Discussion on the dependency of the quality of the final solutions on the quality of the initial solutions.ions.