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

Assignment 3

In this assignment, you will analyze the Fiduccia-Mattheyses partitioning algorithm in two aspects.

Download the following file into your working directory.

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

Unzip it.

• tar xvfz a03.tar.gz

You will see the following directories.

• hgr: benchmark files

• fm: FM algorithm

Compile the source code by running "make".

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

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

1. 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 fm with several seed values for srand() and analyze the relationship.

Run fm with 1000 different seed numbers for p2.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 1000 dots in the graph.)

What to submit

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

2. Impact of the balance factor on the cutsize

In the source code, search for "min_balance". This variable is used for balance check.

All the cells have the same area (= unit area = 1).

Run fm for biomedP.hgr with a fixed seed number and seven different balance factors (0.45, 0.4, 0.3, 0.2, 0.1, 0.01, 0.001).

Show the cutsize for each balance factor.

Can you find out why the trend happens?

What to submit

• Cutsize vs. balance factor (just a table)

• Discussion on the trend