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

Assignment 5

1. Normalized polish expression-based floorplanning

1-1. Convert the following normalized polish expression into the binary-tree form.

E = 1 2 V 3 4 5 6 H V 7 H 8 9 10 H V H V H


1-2. Use the following block dimensions to compute the width and the height of each sub-block (i.e., compute the width and the height of each internal node).

2. Sequence pair-based floorplanning

2-1. Draw an HCG and a VCG for the following sequence pair. Do not simplify the graphs.

Pos = (1 8 3 5 2 4 10 9 6 7), Neg = (10 8 6 2 4 5 3 1 7 9)


2-2. Simplify the HCG and VCG drawn above.


2-3. Compute the location of the bottom-left corner of each block and the width and the height of the floorplan. Use the block dimensions in Problem 1-2.

3. Sequence pair-based floorplanning with rotatable blocks

In the linear programming-based floorplanning, rotatable blocks are handled by adding binary variables.

In the sequence pair-based floorplanning, we can still handle rotatable blocks. For this, we introduce Type-4 move.

Type-4 move : Randomly choose a block and rotate it.


3-1. Apply Type-4 move to Block 5 in the above sequence pair and re-compute the width and height of the new floorplan. What are the width and the height of the floorplan? Explain whether you can reuse the HCG and the VCG drawn in Problem 2-1 or 2-2.

4. Incremental update for sequence pair-based floorplanning

4-1. Suppose you have n blocks and are given a sequence pair. We define Type-5 move as follows:

Type-5 move : Choose two blocks, B1 and B2, and move B1 to the front of B2 in the positive sequence.

For example, the following is a sequence pair given to us:

Pos = (1 2 3 4 5 6 7 8 9 10) , Neg = (5 3 8 10 4 9 2 6 1 7)

If we choose Block 4 (for B1) and Block 8 (for B2), we will obtain the following sequence pair after applying the Type-5 move:

Pos = (1 2 3 5 6 7 4 8 9 10) , Neg = (5 3 8 10 4 9 2 6 1 7)

In this example, how many pairs of blocks should you consider for incremental reconstruction of the HCG and VCG?


4-2. Suppose you have n blocks and are given a sequence pair (n >= 3). In general, what is the range of the number of the pairs of blocks you should consider for incremental reconstruction of the HCG and VCG after you apply the Type-5 move to two blocks in the positive sequence?