## Description

Please work on EWS machine for this MP.

Physical design is an important step in the design automation flow of VLSI systems. It refers to all synthesis steps that

convert a circuit representation (in terms of gates and transistors) into a geometric representation (see Figure 1).

Floorplanning is one major step in physical design. It assembles partitioned circuit modules into a rectangular chip to

optimize a predefined cost metric such as area; it is particularly crucial because the resulting floorplan affects all the

subsequent steps in physical design, such as cell placement, wire routing, and so on. In this MP, you are asked to implement

a floorplanner that layouts a set of rectangular modules and optimizes the packing area.

Figure 1: Physical design flow of VLSI systems.

Floorplan Model

The floorplan model we consider for this MP is slicing. A slicing floorplan can be obtained by repetitively cutting the floorplan

horizontally or vertically, whereas a non-slicing floorplan cannot. Figure 2 shows an example of a slicing floorplan. The

floorplan here is a slicing floorplan since each module can be sliced out through a sequence of vertical cut or horizontal cut.

In this example, the 1st vertical cut slices out the module 5, and the 2nd horizontal cut slices out the module 4. Subsequently,

the 3rd horizontal cut slices out the module 1 and the final vertical cut slices out the module 2 and module 3. On the other

hand, we cannot apply this cutting process to slice out any modules from the floorplan.

Figure 2: A slicing floorplan example.

Slicing Tree Floorplan Representation

On the basis of the property of a slicing floorplan, a tree data structure can be used to represent a slicing floorplan. A slicing

tree is a binary tree with modules at leaves and cutlines at internal nodes (non-leaf nodes). There are two cutline

types, H and V. The cutline H divides the floorplan horizontally and the cutline V divides the floorplan vertically. An example is

shown in Figure 3. The tree root, V, represents the vertical cutline that divides the floorplan into the left sub-floorplan packed

by modules 1 and 2 and the right sub-floorplan packed by modules 3, 4, and 5. The left child of the root is an internal node

with horizontal cutline, which horizontally divides the left sub-floorplan into the bottom sub-floorplan (module 1) and the top

sub-floorplan (module 2). Similarly, the right child of the root represents a horizontal cut that divides the sub-floorplan into the

bottom (module 3) and the top (modules 4 and 5) sub-floorplans, after which the top sub-floorplan is further divided into the

bottom (module 4) and the top (module 5) sub-floorplans.

Figure 3: An example of a slicing floorplan and its slicing tree representation. The corresponding postfix expression

is 12H345HHV.

The slicing tree representation is advantageous in its 1D postfix expression E = {e1, e2, e3, e4, …, e2n-1} where n is the

number of modules and ei

is an expression unit which belongs to {1, 2, 3, 4, …, n, V, H}. Here, each number denotes a

module index and H (V) represents a horizontal (vertical) cutline. The postfix expression is a postfix order of the tree nodes

and it be obtained via a postfix traversal on the slicing tree. For example, the postfix expression of the slicing tree in Figure 3

is E = {12H345HHV}. With this elegant property, design automation tools can work on the 1D postfix expression instead of

the explicit 2D layout so as to ease the optimization process. The transformation of a postfix expression E to its

corresponding floorplan can be achieved via a bottom-up approach that recursively combines the sub-floorplans on the basis

of E. The two cutlines are viewed as two binary operators. If a and b are two modules or two sub-floorplans, the

expression abH implies to place a below b, and abV implies to place a to the left of b. The resulting rectangle area can be

determined during the packing process, as illustrated in Figure 4. So by manipulating the slicing trees, we can generate

multiple floorplan representations. This technique is very useful for optimization where the chip size should be as small as

possible.

Figure 4: Transformation of a 1D postfix expression into the corresponding 2D floorplan. The resulting rectangle area can be

determined in a recursive manner.

Coding Blocks

In this MP, we have defined a set of structs and you should follow them to design your floorplanner. Definitions for these

structs can be found in floorplan.h. You can define your own structs here if necessary for your implementation (not

recommended though). The cutline_t is an enum identifier and it defines the type of a cutline, whose value could be either

vertical (V) or horizontal (H), or undefined (UNDEFINED_CUTLINE). The module_t is a struct identifier for a module, which

contains 1) an integer variable idx denoting the unique index of the module, 2) two integer variabls llx and lly denoting the

lower-left x and y coordinates of the module, and 3) two integer variables w and h denoting the width and height of the

module. The expression_unit_t defines the unit of the postfix expression, which could be either a module pointer or a cutline

value. The node_t is a struct identifier that defines the node in the slicing tree. A node is either an internal node, where a

cutline type must be explicitly specified or a leaf node where the value of module pointer must be assigned. Each node is

associated with three node pointers, parent, left, and right. The topology of the slicing tree can be implicitly inferred by these

node-to-node pointers. The pointer parent points to the parent of the node. Every node has only one parent and the parent of

the tree root is assigned by NULL. Due to the binary property of a slicing tree, a node has two children, which are connected

by the pointer left and the pointer right, respectively. A node with NULL values on both left and right pointers is a leaf node.

An example is shown in Figure 7. For instance, the node 0x40 (memory address) is a leaf node and the node 0x10 is the tree

root. The nodes 0x20 and 0x30 are internal nodes.

typedef enum CUTLINE {

V = 0,

H = 1,

UNDEFINED_CUTLINE

} cutline_t;

typedef struct MODULE {

int idx;

int llx, lly;

int w, h;

} module_t;

typedef struct EXPRESSION_UNIT {

module_t* module;

cutline_t cutline;

} expression_unit_t;

typedef struct NODE {

module_t* module;

cutline_t cutline;

struct NODE* parent;

struct NODE* left;

struct NODE* right;

} node_t;

Figure 5: A slicing tree example with a table showing the corresponding data field of nodes.

In addition, we will have two global variables, num_modules and modules, defined in floorplan.cpp. As we will parse the

circuit for you (the procedure for circuit parsing is read_module), the global variable num_modules records the total number

of modules and the global variable modules is a pointer to the module array parsed from the given circuit input.

The first task you have to finish after the parsing is to create an initial slicing tree by the function init_slicing_tree. For

simplicity, we ask you to generate a slicing tree that results in a horizontally-aligned floorplan. In other words, all the modules

are aligned together and placed along a horizontal line. In this case, the resulting slicing tree is left-skewed, growing down to

the left. The right child of each node is always a leaf node attached by a module pointer. An example of a left-skewed slicing

tree with 4 modules is shown in Figure 6. You need to implement the function init_slicing_tree recursively. The

function init_slicing_tree takes a node pointer to the parent of the current recursion and an integer variable indicating the

index on the module array. At each recursion step, first generate an internal node with vertical cutline and a right child node

attached by a module pointer (as the property of a left-skewed slicing tree). Then create a left child node and step to the next

recursion parented by the current internal node. Establish the tree links appropriately (left, right, parent pointers). The

recursion ceases when no more modules can be attached, and should ultimately return a pointer to the tree root. We will

verify your initialization by its postfix expression, which should appear like “n, n-1, V, n-2, V, n-3, V… 2, V, 1, V”.

Figure 6: A left-skewed slicing tree for a horizontally aligned floorplan. The right child of any internal node is a leaf node.

Based on the above primitives, the rest job of this MP is to implement a set of functions and procedures for a slicing-tree

floorplanner. The first set consists of three fundamental tree queries, is_leaf_node, is_internal_node, and is_in_subtree.

The second set consists of two procedures, get_expression and postfix_traversal, which are essential for encoding the 2D

floorplan to a 1D postfix expression. The final set is the tree modifiers for the perturbation of slicing

trees, rotate, recut, swap_module, and swap_topology.

int num_modules;

module_t* modules;

node_t* init_slicing_tree(node_t* par, int nth);

The function is_leaf_node takes a node pointer and should return 1 if the node pointer points to a leaf node in the slicing

tree, or 0 otherwise. The function is_internal_node takes a node pointer and should return 1 if the node pointer points to an

internal node in the slicing tree, or return 0 otherwise. The function is_in_subtree takes two node pointers to

nodes a and b in the slicing tree, and should return 1 if the subtree rooted at the node b belongs to a part of the subtree

rooted at the node a. Notice that a subtree rooted at the node k is defined as the set of all downstream nodes of the

node k (inclusive). For example, the subtree rooted at the node 0x30 (memory address) in Figure 7 consists of three nodes,

0x30, 0x60, and 0x70. Further, any subtrees rooted at one of these three nodes (i.e., 0x30, 0x60, 0x70) belong to a part of

the subtree rooted at the node 0x30. On the other hand, the subtree rooted at the node 0x20 is exclusive of the subtree

rooted at the node 0x30.

The procedure get_expression traverses the slicing tree in a postfix order and encodes it into a postfix expression. The

postfix expression should be stored in the given array pointed by expression. In order to obtain the postfix expression of the

slicing tree, you have to finish the recursive procedure postfix_traversal, which is an internal call of the

procedure get_expression. The procedure postfix_traversal takes three input arguments, a node pointer pointing to a

subtree from which the current recursive call takes place, an integer pointer indicating the position where the postfix

expression needs to fill, and a pointer to the expression array. The algorithm of postfix traversal on a tree is given by Figure

7. The postfix traversal is performed in a recursive manner. A node is processed as long as both its two children nodes are

handled. Using the postfix traversal algorithm, the derived postfix expression of the slicing tree in this example should

be 12H34VV, where the course of the postfix traversal is shown in the table.

Figure 7: An example of postfix (postorder) traversal on a slicing tree. The derived postfix expression is 12H34VV.

The procedure rotate takes a pointer to an arbitrary node in the slicing tree and rotates the corresponding module (if any) by

90 degree. In other words, the width and the height of the module should be swapped. Similarly the procedure recut changes

the cutline from either horizontal direction to vertical direction or vertical direction to horizontal direction. On the other hand,

the procedure swap_module takes two node pointers and swaps the corresponding module pointers. Finally, the

procedure swap_topology swaps the two subtrees rooted at two given node pointers. For the first three

procedures, rotate, recut, and swap_module, simply change the data field of each node and do not modify the topology of

the tree. For the procedure swap_topology, you have to manipulate the link between tree nodes in order to change the tree

topology (i.e., left, right, parent pointers in the node struct should be redirected appropriately). An example of the

operation swap_topology is demonstrated in Figure 8.

int is_leaf_node(node_t* ptr);

int is_internal_node(node_t* ptr);

int is_in_subtree(node_t* a, node_t* b);

void get_expression(node_t* root, int N, expression_unit_t* expression);

void postfix_traversal(node_t* ptr, int* nth, expression_unit_t* expression);

Figure 8: An example of the operation swap_topology on two nodes 0x40 (memory address) and 0x30. The data field on

corresponding nodes should be modified accordingly.

The coding sections you have to finish have been marked by “TODO” in floorplan.c.

Benchmark Description

A circuit benchmark example (circuit1.txt) is shown in the following block. The first line is always a positive number N (>2)

indicating the total number of modules. After that, N lines are followed with each line consisting of 1) an integer number

indicating the unique index of a module, and 2) the width and height of this module. All data field are integers (i.e., no floating

points). Although we have provided a parser for you and you don’t have to worry about the I/O, reading the format will help

you understand the problem. More details about the parsing process can be referred to the procedure read_module.

Building and Testing

In this MP, we provide you a makefile to help automatically build and manage your project. Under the directory of your source

codes, type the command “make floorplanner” to compile and build your source code into an executable binary. You will find

a binary named “floorplanner” in the same folder, if no error messages occur. Similarly, the command “make clean” will

remove all compiled files and temporary objects.

You can start testing your code after you successfully compile and build the source codes. Simply type “make circuit_name”,

where circuit_name is replaced with circuit1, circuit2, circuit3, circuit4, and circuit5. You will find results on the screen. By

default, the library has been installed on EWS machine and you should be able to compile your MP without error.

void rotate(node_t* ptr);

void recut(node_t* ptr);

void swap_module(node_t* a, node_t* b);

void swap_topology(node_t* a, node_t* b);

4

0 280 296

1 333 188

2 523 192

3 549 296

~> make floorplanner

~> make circuit1

Presentation Slide

The presentation slide for this MP can be found here: presentation.pptx or presentation.pdf Please carefully read the

presentation before you start.

Grading Rubric

Functionality (90%)

1. is_leaf_node function: 5%

2. is_internal_node: 5%

3. is_in_subtree: 10%

4. rotate: 5%

5. recut: 5%

6. swap_module: 5%

7. swap_topology: 10%

8. get_expression: 20%

9. init_slicing_tree: 25%

Style and comments (10%)

If your code doesn’t compile, you will receive zero.

****************************** VERIFICATION ******************************

Circuit: 4 golden_modules, slicing tree size = 4 leaves and 3 internals

(1) Function ‘init_slicing_tree’: correct! +25

(2) Function ‘is_leaf’ : correct! +5

(3) Function ‘is_internal’ : correct! +5

(4) Function ‘is_in_subtree’ : correct! +10

(5) Procedure ‘rotate’ : correct! +5

(6) Procedure ‘recut’ : correct! +5

(7) Procedure ‘swap_module’ : correct! +5

(8) Procedure ‘swap_topology’ : correct! +10

(9) Procedure ‘get_expression’ : correct! +20

Your final score for this MP : 90

**************************** END VERIFICATION ****************************

No labels