Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

Programming Assignment 1 VLSI Floorplanner Design Flow of Integrated Circuits (IC) 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 V H H V Floorplan Model – Slicing Floorplan H: Horizontal cut V:...

1 answer below »
Programming Assignment 1
VLSI Floorplanne
Design Flow of Integrated Circuits (IC)
1
2 3
4
5
1
2 3
4
5
1
2 3
4
5
1
2 3
4
5
1
2 3
4
5
V H
H
V
Floorplan Model – Slicing Floorplan
H: Horizontal cut
V: Vertical cut
A non-slicing floorplan.
1
2
3
4
5 ?
Floorplan Model – Non-slicing Floorplan
Slicing Tree Representation of Slicing Floorplan
․Properties
¾A binary tree (complete)
¾Modules on leave nodes & Cutlines on internal nodes
¾1D expression by postfix traversal
Postfix expression: 12H345HHV
1
2 H
1 2 3 4
V
3 4
(a) Postfix expression: 12H (b) Postfix expression: 34V
H 1
2
W12
W12= max(W1 , W2)
H12= H1 + H2
W34 = W3 + W4
H34 = max(H3 , H4)
H 3
4
W34
Packing from a Postfix Expression
․Binary operato
¾H: maximum on width and summation on height
¾V: maximum on height and summation on width
1
2 H
1 23 4
V
3 4
V
H 1
23
4
W1234
W1234 = W12 + W34
H1234 = max(H12 , H34)
(c) Postfix expression: 12H34VV
․Binary operato
¾H: maximum on width and summation on height
¾V: maximum on height and summation on width
Packing Two Sub-floorplans Recursively (I)
1
2
3 4
H 1
23
4
W1234
H
1 2
V
3 4
H
(d) Postfix expression: 12H34VH
W1234 = max(W12 + W34)
H1234 = H12 + H34
Packing Two Sub-floorplans Recursively (II)
․Binary operato
¾H: maximum on width and summation on height
¾V: maximum on height and summation on width
Floorplan Optimization
․Area minimization is the top priority!
․Simulated Annealing (SA)
¾Randomly modify the slicing tree and select the one with the
minimum floorplan area
¾We have provided you this optimization engine
1. Generate an initial slicing tree T
2. Calculate the area of the slicing tree T
3. Generate a random neighboring solution by changing the tree
4. Calculate the cost of the new neighboring solution
5. Compare them:
if new_area < old_area, then move to the new solution
else accept the new solution with a user-defined probability
6. Repeat steps 3-5 above until an acceptable solution is found
TODO Task 1: Generating an Initial Slicing Tree
․init_slicing_tree
¾Initialize a left-skewed slicing tree
V
2
1
V
Node
address
left right parent module cutline
0x10 0x20 0x30 NULL NULL V
0x20 0x40 0x50 0x10 NULL V
0x30 NULL NULL 0x10 1 UNDEFINED_CUTLINE
0x40 0x60 0x70 0x20 NULL V
0x50 NULL NULL 0x20 2 UNDEFINED_CUTLINE
V
4 3
0x10
0x20 0x30
0x500x40
0x60 0x70
typedef struct NODE {
module_t* module;
cutline_t cutline;
struct NODE* parent;
struct NODE* left;
struct NODE* right;
}node_t;
(a) circuit1.txt
(b) circuit4.txt
Initial Floorplan
H
1 2
V
3 4
V
0x30
0x60 0x700x40 0x50
0x20
0x10
nth XXXXXXXXXX
Expression
unit
1 2 H 3 4 V V
Node
address
0x40 0x50 0x20 0x60 0x70 0x30 0x10
Postfix traversal algorithm
1. Traverse the left subtree by recursively calling the Postfix function.
2. Traverse the right subtree by recursively calling the Postfix function.
3. Process the data part of root element (or cu
ent element).
TODO Task 2: Postfix Traversal Algorithm
․get_expression
¾Perform the postfix traversal
¾Get the postfix expression of the slicing tree
H
1 2
V
3 4
V
Operation: recut
H
1 2
V
3 4
H
TODO Task 3: Tree Modifier – rotate and recut
․rotate
¾Swap the height and the width of a module from a leave node
․recut
¾Change the cutline of an internal node
TODO Task 3: Tree Modifier – swap_module
․swap_module
¾Swap two modules from two leave nodes
¾Simply swap the pointer value
¾Do not modify the node links
H
1 2
V
3 4
V
H
1 4
V
3 2
V
Operation: swap_module
TODO Task 4: Tree Modifier – swap_topology
․swap_topology
¾Swap two subtrees rooted at two given node pointers
¾Modify the node links appropriately
H
1 2
V
3 4
V
H
1
V
V
3 4
2
Operation: swap_topology
Example of swap_topology
H
1 2
V
3 4
V
0x30
0x60 0x700x40 0x50
0x20
0x10 swap_topology
(0x40, 0x30) H 1
2V
3 4
V
0x30
0x60 0x70
0x40
0x50
0x20
0x10
Node
address
left right parent module cutline
0x10 0x20 0x40 NULL NULL V
0x20 0x30 0x50 0x10 NULL H
0x30 0x60 0x70 0x20 NULL V
0x40 NULL NULL 0x10 1 UNDEFINED_CUTLINE
0x60 NULL NULL 0x30 3 UNDEFINED_CUTLINE
H
1 2
V
3 4
V
H
1 2
V
3 4
H
H
1 4
V
3 2
HH
1
H
V
3
4
2
ecut
swap_module
swap_topology
Example of a Sequence of Tree Modifiers
TODO Items
1. log in the CADE server: lab2-20.eng.utah.edu
• CADE server has all required files installed already
• You may use NoMachine or SSH
• If you want to work on your own “Linux” machine, install cairo li
ary
following instructions at: https:
www.cairographics.org/download
2. Clone the class githu
• git clone https:
github.com/tsung-wei-huang/ece5960
3. Enter the folder ece5960/hw/hw1
4. Hit “make” to compile all sources
5. An executable “floorplan” will be present in the folde
6. Usage: ./floorplan circuits/circuit1.txt circuit1.png
• Replace the number “1” with others to run different circuits
7. A default scoring output will be printed in the console
• Maximum score is 90
• 10 points are saved for documentation
8. Finish all TODO sections in floorplan.c; this is the only file you need to
work on
9. Email me your floorplan.c together with your uid and name by 3:30 PM
2/27 (before class)
https:
www.cairographics.org/download
https:
github.com/tsung-wei-huang/ece5960
~$ git clone https:
github.com/tsung-wei-huang/ece5960.git
~$ cd ece5960/hw/hw1
~$ make
~$ ./floorplan circuits/circuit1.txt circuit.png
Demo
********************************** HW1 **********************************
Initial slicing tree: Root=0xa7d0d0, num_nodes=7, num_modules=4
Initial expression: 32V1V0V
Initial area: XXXXXXXXXX
Perform optimization...
Module 0 is placed at (0, 0) with height=280 and width=296
Module 1 is placed at (523, 296) with height=188 and width=333
Module 2 is placed at (0, 296) with height=192 and width=523
Module 3 is placed at (296, 0) with height=296 and width=549
Packing area = XXXXXXXXXXhas overlapped? 0 (1:yes, 0:no))
Draw floorplan to circuit1.png
********************************** END ***********************************
****************************** VERIFICATION ******************************
Circuit: 4 golden_modules, slicing tree size = 4 leaves and 3 internals
(1) Function 'init_slicing_tree': co
ect! +25
(2) Function 'is_leave' : co
ect! +5
(3) Function 'is_internal' : co
ect! +5
(4) Function 'is_in_subtree' : co
ect! +10
(5) Procedure 'rotate' : co
ect! +5
(6) Procedure 'recut' : co
ect! +5
(7) Procedure 'swap_module' : co
ect! +5
(8) Procedure 'swap_topology' : co
ect! +10
(9) Procedure 'get_expression' : co
ect! +20
Your final score for this MP : 90
**************************** END VERIFICATION ****************************
hw1-5t5cozqc-ghiijoju.pdf main-ocfpprp2-b3c24fmd.cpp floorplanc-qp1eon1a-nz5mabgl.cpp floorplanh-5r4iqhe3-g2wbgrbl.cpp
Answered Same Day Feb 26, 2021

Solution

Arun Shankar answered on Feb 27 2021
144 Votes
#include "floorplan.h"
*This program will try to use tree to organize shapes in sush a way as the rectangles are organized in a bigger reactangle
This is very important to circuits designs and organizing things on silicon The trees will be sliced.*
Global variables. The global variables will be effectice after the input has been parsed
by calling the procedure read_module.
int num_modules;
# of input modules.
module_t* modules;
A
ay for modules.
Procedure: floorplan
The major procedure of the floorplan. The procedure concists of the following major steps:
- initialize the slicing tree.
- print the information of the slicing tree.
- perform the optimization process.
void floorplan(const char file[], const char outfile[]) {

printf("\n********************************** HW1 ***********************************\n");

Read the modules from the given input file.
read_modules(file);

Initialize the slicing tree.
node_t* root = init_slicing_tree(NULL, 0);
int num_nodes = (num_modules
1) - 1;
printf("Initial slicing tree: Root=%p, num_nodes=%d, num_modules=%d\n", root, num_nodes, num_modules);

Obtain the expression of the initial slicing tree.
expression_unit_t* expression = (expression_unit_t*)calloc(num_nodes, sizeof(expression_unit_t));
get_expression(root, num_nodes, expression);
printf("Initial expression: ");
pnt_expression(expression, num_nodes);
double area = packing(expression, num_nodes);
printf("Initial area: %.5e\n", area);
draw_modules("init.png");
free(expression);

Perform the optimization process.
printf("Perform optimization...\n");
area = optimize(root, num_nodes);
pnt_modules();
printf("Packing area = %.5e (has overlapped? %d (1:yes, 0:no))\n", area, is_overlapped());

Output your floorplan.
printf("Draw floorplan to %s\n", outfile);
draw_modules(outfile);

printf("********************************** END ***********************************\n");
}
FUNCTIONS/PROCEDURES YOU HAVE TO FINISH.
Function: is_leaf_node
Return 1 if the given slicing tree node is a leaf node, and 0 otherwise.
int is_leaf_node(node_t* ptr)
{

TODO: (remember to modify the return value appropriately) - DONE
if((ptr->left==nullptr) && (ptr-
ight==nullptr))
return 1;
return 0;
}
Function: is_internal_node
Return 1 if the given slicing tree node is an internal node, and 0 otherwise.
int is_internal_node(node_t* ptr)
{

TODO: (remember to modify the return value appropriately) - DONE
if(is_leaf_node(ptr)==1)
return 0;
return 1;
}
Function: is_in_subtree
Return 1 if the given subtree rooted at node 'b' resides in the subtree rooted at node 'a'.
int is_in_subtree(node_t* a, node_t* b)
{

TODO: (remember to modify the return value appropriately) - DONE
if((b->module == a->module)&&(b->cutline==a->cutline))
return 1;

if(is_in_subtree(a->left,b))
return 1;
return is_in_subtree(a-
ight,b);
}
Procedure: rotate
Rotate a module from a given leaf node of the slicing tree by 90 degree. That is, the height
and the width of the modules are swapped.
void rotate(node_t* ptr)
{

TODO: DONE Rotate the module, swapping the width and height.
module_t* m = ptr->module;
if(m=nullptr)
return;
int temp = m->w;
m->w = m->h;
m->h = temp;
}
Procedure: recut
Change the cutline of a module in a given internal node of the slicing tree.
If the original cutline is a vertical cutline, the resulting cutline should be changed to
horizontal and vice versa.
void recut(node_t* ptr)
{
if(!is_internal_node(ptr)) return;
assert(ptr->module == NULL && ptr->cutline != UNDEFINED_CUTLINE);

TODO: - DONE
if(ptr->cutline==V)
ptr->cutline = H;
else if(ptr->cutline==H)
ptr->cutline = V;
return;
}
Procedure: swap_module
Swap the two modules between two given leaf nodes in the slicing tree.
void swap_module(node_t* a, node_t* b)
{
if(!is_leaf_node(a) || !is_leaf_node(b)) return;
assert(a->module != NULL && a->cutline == UNDEFINED_CUTLINE);
assert(b->module != NULL && b->cutline == UNDEFINED_CUTLINE);
if undefined cutline, then the modules are numbers

TODO: - DONE
module_t* temp = a->module;
a->module = b->module;
b->module = temp;
}
Procedure: swap_topology
Swap the topology of two subtrees rooted at two given nodes of the slicing tree.
The procedure applies "is_in_subtree" first to tell if any of the subtree belongs
to a part of the other.
void swap_topology(node_t* a, node_t* b)
{
if(a == NULL || b == NULL) return;
if(a->parent == NULL || b->parent == NULL) return;
if(is_in_subtree(a, b) || is_in_subtree(b, a)) return;
assert(a->parent != NULL && b->parent != NULL);


TODO: - DONE
node_t* ap = a->parent;
node_t* bp = b->parent;
a->parent = bp;
b->parent = ap;
}
Procedure: get_expression
Perform the post-order traversal on the given slicing tree and stores the polish expression
into the given expression a
ay. You should assume the expression a
ay is pre-allocated with
size N. In other words, you don't have to perform dynamic memory allocation. In fact, there
is no need for you to add any code here, but it would be better if you can understand the
details of this procedure especially the last two lines where the procedure postfix_traversal
is called internally to obtain the expression.
void get_expression(node_t* root, int N, expression_unit_t* expression) {
int i;

Clear the expression.
for(i=0; i expression[i].module = NULL;
expression[i].cutline = UNDEFINED_CUTLINE;
}

Obtain the expression using the postfix traversal.
int nth = 0;
postfix_traversal(root, &nth, expression);
}
Procedure: postfix_traversal
Perform the postfix traversal on the slicing tree and store the co
esponding polish expression
to the given expression a
ay. You should use the pointer "nth" to find out the index of the
expression a
ay and write the data accordingly. Notice that...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Attach File