Answer To: Programming Assignment 1 VLSI Floorplanner Design Flow of Integrated Circuits (IC) 1 2 3 4 5 1 2 3 4...
Arun Shankar answered on Feb 27 2021
#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; // Array 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->right==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->right,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 array. You should assume the expression array 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 corresponding polish expression
// to the given expression array. You should use the pointer "nth" to find out the index of the
// expression array and write the data accordingly. Notice that...