<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Tahoma
}
--></style>
</head>
<body class='hmmessage'><div dir='ltr'>
<font class="Apple-style-span" face="Tahoma" size="2"><br></font><div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <vector></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <string></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <fstream></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <iostream.h></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <map></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <cstdio></font></div><div><font class="Apple-style-span" face="Tahom
a" size="2">#include <cstring></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <climits></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <sys/time.h></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <sys/resource.h></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <vector></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <cassert></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <stack></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <algorithm></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include <cmath></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">#include "mpi.h"</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><
div><font class="Apple-style-span" face="Tahoma" size="2">//--------------------------fplan.h--------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">using namespace std;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">struct Pin{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int net;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int x,y; // relative position</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int ax,ay; // absolute position</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pin(int x_=-1,int y_=-1){ x=x_,y=y_; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};</font></di
v><div><font class="Apple-style-span" face="Tahoma" size="2">typedef vector<Pin> Pins;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">typedef Pin* Pin_p;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">typedef vector<Pin_p> Net;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">typedef vector<Net > Nets;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">enum Module_Type { MT_Hard, MT_Soft, MT_Reclinear, MT_Buffer };</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">struct Module{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> char name[20];</font></div><div><font class="Apple-style-spa
n" face="Tahoma" size="2"> int width,height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int x,y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int area;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pins pins;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Module_Type type;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">typedef vector<Module> Modules;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">struct Module_Info{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool rotate, flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int x,y;</font></div><div><font class="Apple-style-sp
an" face="Tahoma" size="2"> int rx,ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">typedef vector<Module_Info> Modules_Info;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">class FPlan{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> public:</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int rank;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int Size;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> FPlan(const Modules& modules,const Modules_Info& modules_info)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> 
; {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int rank = MPI::COMM_WORLD.Get_rank();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int Size = MPI::COMM_WORLD.Get_size();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int sendModule_Info(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int receiveModule_Info(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int sendModule(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int receiveModule(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> FPlan(float calpha);</font></div><div><font class="Apple-style-span" face="T
ahoma" size="2"> void read(char*);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void init()<span class="Apple-tab-span" style="white-space:pre"> </span>=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void perturb()<span class="Apple-tab-span" style="white-space:pre"> </span>=0; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void keep_sol()<span class="Apple-tab-span" style="white-space:pre"> </span>=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void keep_best()<span class="Apple-tab-span" style="white-space:pre"> </span>=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void recover()<span class="Apple-tab
-span" style="white-space:pre"> </span>=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void recover_best() =0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual double getCost(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int size() { return modules_N; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double getTotalArea() { return TotalArea; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double getArea() { return Area; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int getWireLength(){ return WireLength;}</font></div><div><font class="Apple-style-
span" face="Tahoma" size="2"> double getWidth() { return Width; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double getHeight() { return Height; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float getDeadSpace();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // information</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void list_information();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void show_modules(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void normalize_cost(int);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div>
<div><font class="Apple-style-span" face="Tahoma" size="2"> protected:</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double calcWireLength();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void scaleIOPad(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double Area;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double Width,Height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int WireLength;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double TotalArea;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><
font class="Apple-style-span" face="Tahoma" size="2"> int modules_N; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Modules modules;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Module root_module;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Modules_Info modules_info; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Nets network;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double norm_area, norm_wire;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float cost_alpha;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> vector<vector<int> > connection;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div>
<font class="Apple-style-span" face="Tahoma" size="2"> private:</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void read_dimension(Module&);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void read_IO_list(Module&,bool parent);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void read_network();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void create_network(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> map<string,int> net_table;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> string filename; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};</font></div><div><font class="Apple-style-span" face="Tahoma" size="
2">int FPlan::sendModule_Info(int proc, int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[6] = {1,1,1,1,1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[6];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[6];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype FPlan_Module_Info;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font c
lass="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].rotate, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].flip, &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].x, &displs[2] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].y, &displs[3] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].rx, &displs[4] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].ry,
&displs[5] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[2] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[3] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[4] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[5] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font cl
ass="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 5; i >= 0; i --) //substracting the base address from the subsequent displacements</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 6, blockcounts, displs, types, &FPlan_Module_Info );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &FPlan_Module_Info );</font></div><div><font class="Apple-style-span" face=
"Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Send(&modules_info, modules_N, FPlan_Module_Info , proc, tag, MPI_COMM_WORLD);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// A function for defining a structure for MPI to collect the node/state object through out the processes</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int FPlan::receiveModule_Info(int proc,
int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[6] = {1,1,1,1,1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[6];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[6];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2
"> MPI_Datatype FPlan_Module_Info;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Status status;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].rotate, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].flip, &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].x, &displs[2] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].y, &displs[3] );</font></div><div><font class="Apple-style-spa
n" face="Tahoma" size="2"> MPI_Address( &modules_info[0].rx, &displs[4] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules_info[0].ry, &displs[5] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[2] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[3] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> type
s[4] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[5] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 5; i >= 0; i --) //substracting the base address from the subsequent displacements</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 6, blockcounts, displs, types, &FPlan_Module_Info );</font></div><div><font class="Apple-style-span" face="Tahoma" s
ize="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &FPlan_Module_Info );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Recv(&modules_info,modules_N, FPlan_Module_Info , proc, tag, MPI_COMM_WORLD, &status);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Ap
ple-style-span" face="Tahoma" size="2">int FPlan::sendModule(int proc, int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[8] = {1,20,1,1,1,1,1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[8];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[8];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype FPlan_Module;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2
"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].id, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].name[20], &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].width, &displs[2] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].height, &displs[3] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].x, &displs[4] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modul
es[0].y, &displs[5] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].area, &displs[6] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].type, &displs[7] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_CHAR;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[2] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[3] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[4] = MP
I_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[5] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[6] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[7] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 7; i >= 0; i --) //substracting the base address from the subsequent displacements</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &nbs
p; MPI_Type_struct( 8, blockcounts, displs, types, &FPlan_Module );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &FPlan_Module );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Send(&modules,modules_N, FPlan_Module, proc, tag, MPI_COMM_WORLD);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><di
v><font class="Apple-style-span" face="Tahoma" size="2"> /*struct Module{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int id; //id of the module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> char name[20]; //name of the module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int width,height; //height and width of the module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int x,y; //coordinate of the module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int area; //total area of the module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pins pins; //array of pins contained in a module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2
"> Module_Type type; //type of the module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};*/</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// A function for defining a structure for MPI to collect the node/state object through out the processes</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int FPlan::receiveModule(int proc, int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[8] = {1,20,1,1,1,1,1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[8];//number of the types used in the mpi struct</font></
div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[8];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype FPlan_Module;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Status status;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].id, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].name[20], &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> M
PI_Address( &modules[0].width, &displs[2] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].height, &displs[3] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].x, &displs[4] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].y, &displs[5] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].area, &displs[6] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &modules[0].type, &displs[7] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] =
MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_CHAR;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[2] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[3] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[4] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[5] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[6] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[7] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 7; i >= 0; i
--) //substracting the base address from the subsequent displacements</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 8, blockcounts, displs, types, &FPlan_Module );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &FPlan_Module );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style
-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Recv(&modules, modules_N, FPlan_Module, proc, tag, MPI_COMM_WORLD, &status);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void error(char *msg,char *msg2="");</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">bool rand_bool();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float rand_01();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double seconds(
);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">extern float init_avg;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">extern float avg_ratio;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">extern float lamda;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double SA_Floorplan(FPlan &fp, int k, int local=0, float term_T=0.1);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double Random_Floorplan(FPlan &fp,int times);</font></div><div><font class="Apple-style
-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//--------------------------------fplan.cpp---------------------------------//</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Project: B*-trees floorplanning</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Advisor: Yao-Wen Chang <ywchang@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Authors: Jer-Ming Hsu <barz@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// <span class="Apple-tab-span" style="white-space:pre"> </span> Hsun-Cheng Lee <gis88526@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Sponsor: Arcadia Inc.</font></div><div><font class="Apple-style-span" face="Tahoma" siz
e="2">// Date: 7/19/2000 ~</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">char line[100],t1[40],t2[40];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">ifstream fs;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">FPlan::FPlan(float calpha=1){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int rank = MPI::COMM_WORLD.Get_rank();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &
nbsp; int Size = MPI::COMM_WORLD.Get_size();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_area= 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_wire= 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cost_alpha=calpha;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::packing(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(cost_alpha!=1)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> calcWireLength();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size
="2">void FPlan::clear(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Area = 0; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> WireLength = 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double FPlan::getCost(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(cost_alpha==1)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return cost_alpha*(Area/norm_area);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else if(cost_alpha < 1e-4)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return (WireLength/norm_wire);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
else</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return cost_alpha*(Area/norm_area)+(1-cost_alpha)*(WireLength/norm_wire);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float FPlan::getDeadSpace(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 100*(Area-TotalArea)/float(Area);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::normalize_cost(int t){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_area=norm_wire=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><
font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < t; i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> perturb();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_area += Area;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_wire += WireLength;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_area /= t;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> norm_wire /= t;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf("normalize area=%.0f, wire=%.0f\n", norm_area, norm_wire)
;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Read</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">char* tail(char *str){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> str[strlen(str)-1]=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return str;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font><
/div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::read(char *file){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> filename = file; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs.open(file);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(fs==NULL)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> error("unable to open file: %s",file);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool final=false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Module dummy_mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; !fs.eof(); i++){</font></div><div><font class="Appl
e-style-span" face="Tahoma" size="2"> // modules</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules.push_back(dummy_mod);<span class="Apple-tab-span" style="white-space:pre"> </span>// new module</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Module &mod = modules.back();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.id = i;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.pins.clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> t1 >> t2;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> tail(t2);<span class="Apple-tab-span" style="white-space:pre"> </span>// remove ";"</font></div><div><font class="Apple-style-span" face="Tahom
a" size="2"> strcpy(mod.name,t2);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> t1 >> t2;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(!strcmp(t2,"PARENT;"))</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>final= true;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // dimension</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> read_dimension(mod); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> read_IO_list(mod,final);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></f
ont></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // network</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(final){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> read_network();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> break;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> root_module = modules.back();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules.pop_back();<span class="Apple-tab-span" style="white-space:pre"> </span>// exclude the parent module</font></div><div><font class="Apple-style-span" face=
"Tahoma" size="2"> modules_N = modules.size(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules_info.resize(modules_N);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules.resize(modules_N);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> create_network();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> TotalArea = 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules_N; i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> TotalArea += modules[i].area;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="
2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::read_dimension(Module &mod){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> t1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int min_x=INT_MAX,min_y=INT_MAX,max_x=INT_MIN,max_y=INT_MIN;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int tx,ty;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < 4;i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> tx >> ty; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> min_x=min(min_x,tx); max_x=max(max_x,tx);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> 
; min_y=min(min_y,ty); max_y=max(max_y,ty);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.x = min_x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.y = min_y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.width = max_x - min_x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.height = max_y - min_y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.area = mod.width * mod.height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> t1 >> t2;</font></div><div><font class="Apple-style-span" face="Tah
oma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::read_IO_list(Module &mod,bool parent=false){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // IO list</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(!fs.eof()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pin p;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs.getline(line,100);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(strlen(line)==0) continue;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> sscanf(line,"%s %*s %d %d",t1,&p.x,&p.y);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><
div><font class="Apple-style-span" face="Tahoma" size="2"> if(!strcmp(t1,"ENDIOLIST;"))</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>break;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(parent){ // IO pad is network</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // make unique net id</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> net_table.insert(make_pair(string(t1),net_table.size()));</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p.net = net_table[t1];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span"
face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p.mod = mod.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p.x -= mod.x; p.y -= mod.y;<span class="Apple-tab-span" style="white-space:pre"> </span>// shift to origin</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod.pins.push_back(p);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs.getline(line,100);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::read_network(){</font></div><di
v><font class="Apple-style-span" face="Tahoma" size="2"> while(!fs.eof()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool end=false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> t1 >> t2;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(!strcmp(t1,"ENDNETWORK;"))</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> break;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // determine which module interconnection by name</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int m_id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(m_id
=0; m_id < modules.size(); m_id++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(!strcmp(modules[m_id].name,t2))</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> break;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(m_id== modules.size())</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>error("can't find suitable module name!");</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(!fs.eof()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fs >> t1;</font></div><div><font class=
"Apple-style-span" face="Tahoma" size="2"> if(t1[strlen(t1)-1]==';'){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> tail(t1);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> end=true;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // make unique net id</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> net_table.insert(make_pair(string(t1),net_table.size()));</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[m_id].pins[n++].net = net_table[t1];</font></div><div><font
class="Apple-style-span" face="Tahoma" size="2"> if(end) break;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Wire Length Estimate</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::create_n
etwork(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> network.resize(net_table.size());</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules_N; i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int j=0; j < modules[i].pins.size(); j++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pin &p = modules[i].pins[j];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> network[p.net].push_back(&p);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span"
face="Tahoma" size="2"> for(int j=0; j < root_module.pins.size(); j++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pin &p = root_module.pins[j];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> network[p.net].push_back(&p);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> connection.resize(modules_N+1);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules_N+1; i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> connection[i].resize(modules_N+1);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fill(connection[i].begin(), connection[i].end(), 0);</font></div><div><font class
="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < network.size(); i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int j=0; j < network[i].size()-1; j++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p= network[i][j]->mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int k=j+1 ; k < network[i].size(); k++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int q= network[i][k]->mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> connection[p][q]++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
connection[q][p]++; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::scaleIOPad(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float px = Width/float(root_module.width);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float py = Height/float(root_module.height);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-st
yle-span" face="Tahoma" size="2"> for(int i=0; i < root_module.pins.size(); i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pin &p = root_module.pins[i];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p.ax = int(px * p.x);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p.ay = int(py * p.y);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double FPlan::calcWireLength()</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></d
iv><div><font class="Apple-style-span" face="Tahoma" size="2"> scaleIOPad();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> WireLength=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // compute absolute position</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules_N; i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int mx= modules_info[i].x, my= modules_info[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool rotate= modules_info[i].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int w= modules[i].width;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int j=0; j < modules[i].pins.size(); j++){</font></div><d
iv><font class="Apple-style-span" face="Tahoma" size="2"> Pin &p = modules[i].pins[j];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(!rotate){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p.ax= p.x+mx, p.ay= p.y+my;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else{ // Y' = W - X, X' = Y</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>p.ax= p.y+mx, p.ay= (w-p.x)+my;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div
><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < network.size(); i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int max_x= INT_MIN, max_y= INT_MIN;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int min_x= INT_MAX, min_y= INT_MAX;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(network[i].size() > 0);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int j=0; j < network[i].size(); j++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &
nbsp; {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Pin &p = *network[i][j];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> max_x= max(max_x, p.ax), max_y= max(max_y, p.ay);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> min_x= min(min_x, p.ax), min_y= min(min_y, p.ay);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// printf("%d %d %d %d\n",max_x,min_x,max_y,min_y);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> WireLength += (max_x-min_x)+(max_y-min_y);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return WireLength;</font></div><div><font class="Apple-style-span"
face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Modules Information</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">string query_map(map<string,int> M,int value){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(map<string,int>::iterator p=M.begin(); p != M.end(); p++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p->second == value)</font></div><div><font class="A
pple-style-span" face="Tahoma" size="2"> return p->first;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return "";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::show_modules()</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules.size();i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Module: " << modules[i].name << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << " Width = " << modules[i].width<<
endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << " Height= " << modules[i].height << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << " Area = " << modules[i].area << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// cout << modules[i].pins.size() << " Pins:\n";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// for(int j=0; j < modules[i].pins.size(); j++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// cout << query_map(net_table,modules[i].pins[j].net) << " ";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// cout << modules[i].pins[j].x << " " << modules[i].pins[j].y << endl;</font></div><div><font cla
ss="Apple-style-span" face="Tahoma" size="2">// }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void FPlan::list_information(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> string info = filename + ".info"; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> ofstream of(info.c_str());</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> of << modules_N << " " << Width << " " << Height << endl;</font></div><div><font class="Ap
ple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules_N; i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> of << modules_info[i].x << " " << modules_info[i].rx << " ";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> of << modules_info[i].y << " " << modules_info[i].ry << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> of << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> calcWireLength(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int x,y,rx,ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < network.
size(); i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(network[i].size()>0);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> x = network[i][0]->ax;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> y = network[i][0]->ay;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int j=1; j < network[i].size(); j++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> rx = network[i][j]->ax;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> ry = network[i][j]->ay;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> of << x << " " << y << " " << rx << " " <<
ry << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> x = rx, y = ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Num of Module = " << modules_N << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Height = " << Height*1e-3 << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Width = " << Width*1e-3 << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Area &nb
sp; = " << Area*1e-6 << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Wire Length = " << calcWireLength()*1e-3 << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Total Area = " << TotalArea*1e-6 << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf( "Dead Space = %.2f\n", getDeadSpace());</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Auxilliary Functions</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//-----
----------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void error(char *msg,char *msg2){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(msg,msg2);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> throw 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">bool rand_bool(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return bool(rand()%2);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-sp
an" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float rand_01(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return float(rand()%10000)/10000;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double seconds(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> rusage time;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> getrusage(RUSAGE_SELF,&time);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return (double)(1.0*time.ru_utime.tv_sec+0.000001*time.ru_utime.tv_usec);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//
--------------------------------------sa.h----------------------------------//</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float init_avg = 0.00001;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int hill_climb_stage = 7;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float avg_ratio=150;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float lamda=1.3;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double mean(vector<double> &chain){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double sum=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < chain.size();i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> sum+= chain[i];</font></div><div><font class
="Apple-style-span" face="Tahoma" size="2"> return sum/chain.size();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double std_var(vector<double> &chain){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double m = mean(chain);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double sum=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double var;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int N= chain.size();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < N;i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &nb
sp; sum += (chain[i]-m)*(chain[i]-m);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> var = sqrt(sum/(N-1));</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(" m=%.4f ,v=%.4f\n",m,var);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return var;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">/* Simulated Annealing B*Tree Floorplan</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> k: factor of the number of permutation in one temperature</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &nb
sp;local: local search iterations</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> termT: terminating temperature</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">*/</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//----------------------sa.cpp--------------------------------//</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double SA_Floorplan(FPlan &fp, int k, int local, float term_T)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int MT,uphill,reject;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double pre_cost,best,cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float d_cost,reject_rate;</font></div><div><font class="Appl
e-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int N = k * fp.size();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float P=0.9;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float T,actual_T=1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double avg=init_avg;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float conv_rate = 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double time=seconds(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double estimate_avg = 0.08 / avg_ratio;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "Estimate Average Delta Cost = " << estimate_avg <
;< endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(local==0)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> avg = estimate_avg;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> T = avg / log(P); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // get inital solution</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.keep_sol(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.keep_best();</font></div><div><font class="Apple-style-span" face="T
ahoma" size="2"> pre_cost = best = fp.getCost();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int good_num=0,bad_num=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double total_cost=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int count=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> ofstream of("/tmp/btree_debug");</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> do{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> count++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> total_cost = 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MT=u
phill=reject=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf("Iteration %d, T= %.2f\n", count, actual_T);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> vector<double> chain; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(; uphill < N && MT < 2*N; MT++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.perturb();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cost = fp.getCost(); </font></div><div><font class="Apple-style-span" face="Tahoma" size
="2"> d_cost = cost - pre_cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float p = exp(d_cost/T);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> chain.push_back(cost);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(d_cost <=0 || rand_01() < p ){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.keep_sol();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> pre_cost = cost;</font></div><div><font class="Apple-style-span" face="Ta
homa" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(d_cost > 0){ </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> uphill++, bad_num++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> of << d_cost << ": " << p << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else if(d_cost < 0) good_num++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // keep best solution</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(cost < best){</font></div><div><font class="App
le-style-span" face="Tahoma" size="2"> fp.keep_best();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> best = cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(" ==> Cost= %f, Area= %.6f, ", best, fp.getArea()*1e-6);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf("Wire= %.3f\n", fp.getWireLength()*1e-3); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(fp.getArea() >= fp.getTotalArea());</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> time = seconds(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font><
/div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> reject++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.recover();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// cout << T << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double sv = std_var(chain);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float r_t = exp(lamda*T/sv);</font></div><div><font class="Apple
-style-span" face="Tahoma" size="2"> T = r_t*T;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // After apply local-search, start to use normal SA</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(count == local){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> T = estimate_avg/ log(P);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> T *= pow(0.9,local);<span class="Apple-tab-span" style="white-space:pre"> </span>// smothing the annealing schedule</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> actual_T = exp(estimate_avg/T);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</fo
nt></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(count > local){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> actual_T = exp(estimate_avg/T);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> conv_rate = 0.95;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> reject_rate = float(reject)/MT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(" T= %.2f, r= %.2f, reject= %.2f\n\n", actual_T, r_t, reject_rate);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }while(reject_rate < conv_rate && actual_T >
; term_T);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(reject_rate >= conv_rate)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "\n Convergent!\n";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else if(actual_T <= term_T)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "\n Cooling Enough!\n";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf("\n good = %d, bad=%d\n\n", good_num, bad_num);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.recover_best();</font></div><div><font class="Apple-style-span" face=
"Tahoma" size="2"> fp.packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return time; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">double Random_Floorplan(FPlan &fp,int times){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int N =times,t=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double total_cost=0,pre_cost,cost,best;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> pre_cost = best = fp.getCost();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><di
v><font class="Apple-style-span" face="Tahoma" size="2"> do{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < N;i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.perturb();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cost = fp.getCost();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(cost-pre_cost > 0){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> t++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> total_cost += cost-pre_cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> pre_cost
= cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(cost < best){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.keep_best();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> best = cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "==> Cost=" << best << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }<span class="Apple-tab-span" style="white-space:pre"> </span></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }while(total_cost==0);</font></div><div><fon
t class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.recover_best();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.packing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> total_cost /= t;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return total_cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//------------------------------------Btree------------------------------------//</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Project: B*-trees floorplanning</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Advisor: Yao-Wen Chang <ywchang@cis.nctu.edu.tw></font></di
v><div><font class="Apple-style-span" face="Tahoma" size="2">// Authors: Jer-Ming Hsu <barz@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// <span class="Apple-tab-span" style="white-space:pre"> </span> Hsun-Cheng Lee <gis88526@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Sponsor: Arcadia Inc.</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Date: 7/19/2000 ~</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">const int NIL = -1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">typedef bool DIR;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">const bool LEFT=0, RIGHT=1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-st
yle-span" face="Tahoma" size="2">struct Node{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int id,parent,left,right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int rotate,flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int isleaf(){ return (left==NIL && right==NIL); }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">struct Contour{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int front,back;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">class B_Tree : public FPlan{</font></div><div><font cl
ass="Apple-style-span" face="Tahoma" size="2"> public:</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int sendcontour(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int receivecontour(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int sendNode(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int receiveNode(int proc, int tag);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> B_Tree(const B_Tree& obj,int i):FPlan(obj.modules,obj.modules_info)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].id=obj.nodes[i].id;</font></div><div
><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].parent=obj.nodes[i].parent;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].left=obj.nodes[i].left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].right=obj.nodes[i].right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].flip=obj.nodes[i].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> contour[i].front=obj.contour[i].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[i].back=obj.contour[i].back;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &
nbsp; <span class="Apple-tab-span" style="white-space:pre"> </span>modules[i].id=obj.modules[i].id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].name[20]=obj.modules[i].name[20];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].width=obj.modules[i].width;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].height=obj.modules[i].height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].x=obj.modules[i].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].y=obj.modules[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].area=obj.modules[i].area;</font></div><div><font class
="Apple-style-span" face="Tahoma" size="2"> modules[i].pins=obj.modules[i].pins;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules[i].type=obj.modules[i].type;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>modules_info[i].rotate=obj.modules_info[i].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules_info[i].flip=obj.modules_info[i].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules_info[i].x=obj.modules_info[i].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules_info[i].y=obj.modules_info[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
modules_info[i].rx=obj.modules_info[i].rx;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> modules_info[i].ry=obj.modules_info[i].ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> B_Tree(float calpha=1) :FPlan(calpha)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void init();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void packing();</font></div><div><fo
nt class="Apple-style-span" face="Tahoma" size="2"> virtual void perturb();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void keep_sol();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void keep_best(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void recover();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> virtual void recover_best();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // debuging</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void testing();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
protected:</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void show_tree(); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int place_module(int mod,int abut,bool is_left=true);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool legal();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // Auxilary function</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void wire_nodes(int parent,int child,DIR edge);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int child(int node,DIR d
);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool legal_tree(int p,int n,int &num);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void add_changed_nodes(int n);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // SA permutating operation</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void swap_node(Node &n1, Node &n2);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void insert_node(Node &parent,Node &node);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void delete_node(Node &node);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"
> bool delete_node2(Node &node,DIR pull);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void insert_node2(Node &parent,Node &node,</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> DIR edge,DIR push,bool fold=false);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int contour_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> vector<Contour> contour;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> vector<Node> nodes; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><di
v><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> private: </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> struct Solution{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> vector<Node> nodes;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double cost;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Solution() { cost = 1; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void clear() { cost = 1, nodes.clear(); }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> };</font></div><div><font class="Apple-sty
le-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void get_solution(Solution &sol);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void recover(Solution &sol);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> void recover_partial();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Solution best_sol, last_sol;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // for partial recover</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> vector<Node> changed_nodes;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int changed_root; </font></div><div><font class="Apple-style-span" face="Tahoma
" size="2">};</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int B_Tree::sendcontour(int proc, int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[2] = {1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[2];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[2];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype B_Tree_
contour;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &contour[0].front, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &contour[0].back, &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_INT;</font></div><div><
font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 1; i >= 0; i --) //substracting the base address from the subsequent displacements</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 2, blockcounts, displs, types, &B_Tree_contour );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit(
&B_Tree_contour );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Send(&contour, modules_N, B_Tree_contour, proc, tag, MPI_COMM_WORLD);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int B_Tree::receivecontour(int proc, int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font c
lass="Apple-style-span" face="Tahoma" size="2"> int blockcounts[2] = {1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[2];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[2];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype B_Tree_contour;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Status status;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma
" size="2"> MPI_Address( &contour[0].front, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &contour[0].back, &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 1; i >= 0; i --) //substracting the base address from the subsequent displacements</f
ont></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 2, blockcounts, displs, types, &B_Tree_contour );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &B_Tree_contour );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Recv(&contour, modules
_N, B_Tree_contour, proc, tag, MPI_COMM_WORLD, &status);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">/*struct Node</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int id,parent,left,right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int rotate,flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int isleaf(){ return (left==NIL && right==NIL); }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">};*/</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-styl
e-span" face="Tahoma" size="2">// A function for defining a structure for MPI to distribute the node/state object through out the processes</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int B_Tree::sendNode(int proc, int tag) {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[6] = {1,1,1,1,1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[6];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[6];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Ta
homa" size="2"> MPI_Datatype B_Tree_node;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and displs with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].id, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].parent, &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].left, &displs[2] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].right, &displs[3] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address
( &nodes[0].rotate, &displs[4] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].flip, &displs[5] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecutive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[2] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[3] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[4] = MPI_INT ;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[5] = MPI_INT ;</font></div>
<div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 5; i >= 0; i --) //substracting the base address from the subsequent displacements</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 6, blockcounts, displs, types, &B_Tree_node );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &B_Tree_node );</font></div><div><font class="Apple-style-span" face
="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // send the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Send(&nodes[0],modules_N, B_Tree_node, proc, tag, MPI_COMM_WORLD);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// A function for defining a structure for MPI to collect the node/state object through out the processes</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int B_Tree::receiveNode(int proc, int tag) {</font
></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int blockcounts[6] = {1,1,1,1,1,1};//count of the blocks of the subsequent type</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype types[6];//number of the types used in the mpi struct</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Aint displs[6];//record of the displacement from the beginning of a particular type block</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Datatype B_Tree_node;// name of the mpi structure object</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Status status;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize types and disp
ls with addresses of items</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].id, &displs[0] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].parent, &displs[1] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].left, &displs[2] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].right, &displs[3] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].rotate, &displs[4] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Address( &nodes[0].flip, &displs[5] );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //consecu
tive types in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[0] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[1] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[2] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[3] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[4] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> types[5] = MPI_INT;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for (int i = 5; i >= 0; i --) //substracting the base address from the subsequent displacements</font></div><div><font class="Ap
ple-style-span" face="Tahoma" size="2"> displs [i] -= displs [0];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //MPI_Type_struct( no, blockcounts, displs, types,mpi_structure);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_struct( 6, blockcounts, displs, types, &B_Tree_node );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //use the structure in mpi</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Type_commit( &B_Tree_node );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // recieve the mpi structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">&
nbsp; MPI_Recv(&nodes[0],modules_N, B_Tree_node, proc, tag, MPI_COMM_WORLD, &status);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//--------------------------btree.cpp-------------------------------------//</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Project: B*-trees floorplanning</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Advisor: Yao-Wen Chang <ywchang@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Authors: Jer-Ming Hsu <barz@cis.nctu.edu.tw></font></div><div><font class="Appl
e-style-span" face="Tahoma" size="2">// <span class="Apple-tab-span" style="white-space:pre"> </span> Hsun-Cheng Lee <gis88526@cis.nctu.edu.tw></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Sponsor: Arcadia Inc.</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Date: 7/19/2000 ~</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float rotate_rate = 0.3;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">float sw
ap_rate = 0.5;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Initialization</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::clear(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initial contour value</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour_root = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> FPlan::clear();</font></div><div><font class="Apple-styl
e-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::init(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize contour structure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour.resize(modules_N);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // initialize b*tree by complete binary tree</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes.resize(modules_N);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes_root=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=
0; i < modules_N; i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].id = i;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].parent = (i+1)/2-1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].left = (2*i+1 < modules_N ? 2*i+1 : NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[i].right = (2*i+2 < modules_N ? 2*i+2 : NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[0].parent = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> best_sol.clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> last_sol.clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cle
ar();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> normalize_cost(10);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">} </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Testing, Debuging tools</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">bool B_Tree::legal(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int num=0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2
"> return legal_tree(NIL,nodes_root,num);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">bool B_Tree::legal_tree(int p,int n,int &num){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> num++;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[n].parent!=p) return false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[n].left != NIL)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(legal_tree(n,nodes[n].left,num) != true) return false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[n].right != NIL)</font></div><div><font class="Apple-style-sp
an" face="Tahoma" size="2"> if(legal_tree(n,nodes[n].right,num) != true) return false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p==NIL) // root</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return (num==modules_N);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return true;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::testing(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p,n;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Solution E;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><
font class="Apple-style-span" face="Tahoma" size="2"> do{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> n = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(n==nodes_root)<span class="Apple-tab-span" style="white-space:pre"> </span>// n is not root</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> n = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(n==p||nodes[n].parent==p||nodes[p].parent==n)<span class="Apple-tab-span" style="white-space:pre"> </span>// n != p & n.parent != p</font></div><div><font class="Appl
e-style-span" face="Tahoma" size="2"> p = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &node = nodes[n];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &parent = nodes[p];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> get_solution(E);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap_node(parent,node);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }while(legal());</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "p=" << p << ", n=" << n << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size
="2"> recover(E);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> show_tree();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "\n p=" << p << ", n=" << n << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap_node(nodes[p],nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> show_tree();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::show_tree(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << "root: " << nodes_root << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < modules_N; i++){</font></div><div><f
ont class="Apple-style-span" face="Tahoma" size="2"> cout << nodes[i].id << ": ";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << nodes[i].left << " ";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << nodes[i].parent << " ";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cout << nodes[i].right << endl;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Placement modules</font></div><div><fo
nt class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::packing(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> stack<int> S;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p = nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> place_module(p,NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &n = nodes[p];</font></div><div><font class="Apple-style-span" face=
"Tahoma" size="2"> if(n.right != NIL) S.push(n.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n.left != NIL) S.push(n.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // inorder traverse</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(!S.empty()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = S.top();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> S.pop();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &n = nodes[p];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(n.parent != NIL);</font></div>
<div><font class="Apple-style-span" face="Tahoma" size="2"> bool is_left = (nodes[n.parent].left == n.id);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> place_module(p,n.parent,is_left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n.right != NIL) S.push(n.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n.left != NIL) S.push(n.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // compute Width, Height</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double max_x=-1,max_y=-1;</font></div><div><font cl
ass="Apple-style-span" face="Tahoma" size="2"> for(int p= contour_root; p != NIL; p=contour[p].front){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> max_x = max(max_x,double(modules_info[p].rx)); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> max_y = max(max_y,double(modules_info[p].ry));</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Width = max_x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Height = max_y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Area = Height*Width;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
FPlan::packing(); <span class="Apple-tab-span" style="white-space:pre"> </span>// for wirelength </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// is_left: default is true</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int B_Tree::place_module(int mod,int abut,bool is_left){ //this routine can be parallelized</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> B_Tree obj;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.init();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(Size>1)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(rank==0)</font></div><div><font class="Appl
e-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>for(int i=0; i<modules_N; i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].id=nodes[i].id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].parent=nodes[i].parent;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].left=nodes[i].left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].right=nodes[i].right;</font></div><div><font class="Apple-style-span" face="Tahoma" siz
e="2"> obj.nodes[i].flip=nodes[i].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> obj.contour[i].front=contour[i].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.contour[i].back=contour[i].back;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>obj.modules[i].id=modules[i].id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].name[20]=modules[i].name[20];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].width=modules[i].width;</font></div><div><font class=
"Apple-style-span" face="Tahoma" size="2"> obj.modules[i].height=modules[i].height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].x=modules[i].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].y=modules[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].area=modules[i].area;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].pins=modules[i].pins;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].type=modules[i].type;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>obj.modules_info[i].
rotate=modules_info[i].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].flip=modules_info[i].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].x=modules_info[i].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].y=modules_info[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj. modules_info[i].rx=modules_info[i].rx;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].ry=modules_info[i].ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.contour_root=contour_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &
nbsp; obj.nodes_root=nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>for(int i=1; i<Size; i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.sendNode(i,0);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.sendcontour(i, 20);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.sendModule_Info(i, 30);</font></div><div><fon
t class="Apple-style-span" face="Tahoma" size="2"> obj.sendModule(i, 40);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=1; i<Size; i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
<span class="Apple-tab-span" style="white-space:pre"> </span>obj.receiveNode(i, 0);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.receivecontour(i, 20);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> obj.receiveModule_Info(i, 30);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span>obj.receiveModule(i,40);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int j=((i-1)*(modules_N/Size));j<((i)*(modules_N/Size));j++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:p
re"> </span>{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> B_Tree(obj,j);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">if(rank!=0)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div
><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.receiveNode(0, 0);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span>obj.receivecontour(0, 20);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>obj.receiveModule_Info(0, 30);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.receiveModule(0,40);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> /* Modules modules;
//dynamic array which store modules</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> Module root_module; //for storing root node</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> Modules_Info modules_info; */</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span>for(int i=((rank-1)*(modules_N/Size));i<((rank)*(modules_N/Size));i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-spa
n" face="Tahoma" size="2"> B_Tree(obj,i);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Module_Info &mod_mf = modules_info[mod];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.rotate = nodes[mod].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.flip = nodes[mod].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int w = modules[mod].width;</font></div><div><font class="App
le-style-span" face="Tahoma" size="2"> int h = modules[mod].height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[mod].rotate)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap(w,h);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(abut==NIL){<span class="Apple-tab-span" style="white-space:pre"> </span>// root node</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour_root = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.x = mod_mf.y = 0;</font></div><div><font class=
"Apple-style-span" face="Tahoma" size="2"> mod_mf.rx = w, mod_mf.ry = h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p; // trace contour from p</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(is_left){<span class="Apple-tab-span" style="white-space:pre"> </span>// left</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int abut_width = (nodes[abut].rotate ? modules[abut].height :</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
modules[abut].width);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.x = modules_info[abut].x + abut_width;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.rx = mod_mf.x + w;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = contour[abut].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[abut].front = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = abut;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p==NIL){ // no obstacle in X axis</font></div><div><font class="Apple-
style-span" face="Tahoma" size="2"> mod_mf.y = 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.ry = h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{<span class="Apple-tab-span" style="white-space:pre"> </span>// upper</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.x = modules_info[abut].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.rx = mod_mf.x + w;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = abut;</font></div><div><font clas
s="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n=contour[abut].back;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n==NIL)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> { // i.e, mod_mf.x==0</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour_root = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[n].front = mod;</font></div><div><font clas
s="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = n;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int min_y = INT_MIN;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int bx,by;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(p!=NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(; p!=NIL ; p=contour[p].front)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bx = mod
ules_info[p].rx;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> by = modules_info[p].ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> min_y = max(min_y, by);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(bx >= mod_mf.rx){ <span class="Apple-tab-span" style="white-space:pre"> </span>// update contour</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.y = min_y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.ry = mod_mf.y + h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(bx > mod_mf.rx){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = p;</font></div><div><font
class="Apple-style-span" face="Tahoma" size="2"> contour[p].back = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{ <span class="Apple-tab-span" style="white-space:pre"> </span>// bx==mod_mf.rx</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n= contour[p].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = n;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n!=NIL)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[n].back = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> break;</font></div><div><font class="Ap
ple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p==NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.y = (min_y==INT_MIN? 0 : min_y);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.ry = mod_mf.y + h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">////////////////////////////////////////////////////////////////////////////////</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-spa
n" style="white-space:pre"> </span> <span class="Apple-tab-span" style="white-space:pre"> </span>for(int i=((rank-1)*(modules_N/Size));i<((rank)*(modules_N/Size));i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>obj.nodes[i].id=nodes[i].id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].parent=nodes[i].parent;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].left=nodes[i].left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].right=nodes[i].right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.nodes[i].flip=nodes[i].flip
;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> obj.contour[i].front=contour[i].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.contour[i].back=contour[i].back;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>obj.modules[i].id=modules[i].id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].name[20]=modules[i].name[20];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].width=modules[i].width;</font></div
><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].height=modules[i].height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].x=modules[i].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].y=modules[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].area=modules[i].area;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].pins=modules[i].pins;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules[i].type=modules[i].type;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span>ob
j.modules_info[i].rotate=modules_info[i].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].flip=modules_info[i].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].x=modules_info[i].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].y=modules_info[i].y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj. modules_info[i].rx=modules_info[i].rx;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.modules_info[i].ry=modules_info[i].ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.contour_root=contour_root;</font></div><div><font class="Apple-style-span" face="Tahoma"
size="2"> obj.nodes_root=nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">////////////////////////////////////////////////////////////////////////////////</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> <span class="Apple-tab-span" style="white-space:pre"> </span> obj.sendNode(0, 0);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.sendcontour(0, 20);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> obj.sendModule_Info(0, 30);</font></div><div><font class="Apple-style-span" face="Tah
oma" size="2"> obj.sendModule(0, 40);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Module_Info &mod_mf = modules_info[mod];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.rotate = nodes[mod].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.flip = nodes[mod].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int w = modules[mod].width;</font></div><div><font class="Apple-style-span" face="Tah
oma" size="2"> int h = modules[mod].height;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[mod].rotate)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap(w,h);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(abut==NIL){<span class="Apple-tab-span" style="white-space:pre"> </span>// root node</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour_root = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.x = mod_mf.y = 0;</font></div><div><font class="Apple-style-span" face=
"Tahoma" size="2"> mod_mf.rx = w, mod_mf.ry = h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p; // trace contour from p</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(is_left){<span class="Apple-tab-span" style="white-space:pre"> </span>// left</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int abut_width = (nodes[abut].rotate ? modules[abut].height :</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &n
bsp; modules[abut].width);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.x = modules_info[abut].x + abut_width;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.rx = mod_mf.x + w;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = contour[abut].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[abut].front = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = abut;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p==NIL){ // no obstacle in X axis</font></div><div><font class="Apple-style-span" face="Tahoma
" size="2"> mod_mf.y = 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.ry = h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{<span class="Apple-tab-span" style="white-space:pre"> </span>// upper</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.x = modules_info[abut].x;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.rx = mod_mf.x + w;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = abut;</font></div><div><font class="Apple-style-span" fac
e="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n=contour[abut].back;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n==NIL){ // i.e, mod_mf.x==0</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour_root = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[n].front = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].back = n;</font>
</div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int min_y = INT_MIN;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int bx,by;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(p!=NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(; p!=NIL ; p=contour[p].front)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> {</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bx = modules_info[p].rx;</font></div><div><font class="Apple-style-span" face="Tahoma" size="
2"> by = modules_info[p].ry;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> min_y = max(min_y, by);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(bx >= mod_mf.rx){ <span class="Apple-tab-span" style="white-space:pre"> </span>// update contour</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.y = min_y;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.ry = mod_mf.y + h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(bx > mod_mf.rx){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = p;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &
nbsp; contour[p].back = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{ <span class="Apple-tab-span" style="white-space:pre"> </span>// bx==mod_mf.rx</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n= contour[p].front;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = n;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n!=NIL)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[n].back = mod;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> break; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">&nbs
p; }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p==NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.y = (min_y==INT_MIN? 0 : min_y);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> mod_mf.ry = mod_mf.y + h;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> contour[mod].front = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" fac
e="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Manipulate B*Tree auxilary procedure</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::wire_nodes(int parent,int child,DIR edge){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(parent!=NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> (edge==LEFT? nodes[parent].left: nodes[parent].right) = child;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(child!=NIL) nodes[child]
.parent = nodes[parent].id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int B_Tree::child(int node,DIR d){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(node!=NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return (d==LEFT? nodes[node].left:nodes[node].right); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Simulated Annea
ling Temporal Solution</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::get_solution(Solution &sol){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> sol.nodes_root = nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> sol.nodes = nodes;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> sol.cost = getCost();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::keep_sol(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">&nbs
p; get_solution(last_sol);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::keep_best(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> get_solution(best_sol);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::recover(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> recover(last_sol);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> // recover_partial();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font c
lass="Apple-style-span" face="Tahoma" size="2">void B_Tree::recover_best(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> recover(best_sol);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::recover(Solution &sol){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes_root = sol.nodes_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes = sol.nodes;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::recover_partial(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(changed_root != NI
L)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes_root = changed_root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < changed_nodes.size(); i++){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &n = changed_nodes[i];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n.id] = n;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::add_changed_nodes(int n){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n==NIL) return;</font></d
iv><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> for(int i=0; i < changed_nodes.size(); i++)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(changed_nodes[i].id == n)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>return;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> changed_nodes.push_back(nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// Simulated Annealing Permutation Operations</font></
div><div><font class="Apple-style-span" face="Tahoma" size="2">//---------------------------------------------------------------------------</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::perturb(){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p,n;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> n = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_nodes.clear();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_root = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahom
a" size="2"> if(rotate_rate > rand_01()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_nodes.push_back(nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n].rotate = !nodes[n].rotate;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(rand_bool()) nodes[n].flip = !nodes[n].flip;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else{ <span class="Apple-tab-span" style="white-space:pre"> </span></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(swap_rate >rand_01()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> do{</font></div><div><font class="Apple-style-span" fa
ce="Tahoma" size="2"> p = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }while(n==p||nodes[n].parent==p||nodes[p].parent==n);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_nodes.push_back(nodes[p]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_nodes.push_back(nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap_node(nodes[p],nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">&
nbsp; do{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> p = rand()%modules_N;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }while(n==p);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_nodes.push_back(nodes[p]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_nodes.push_back(nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> delete_node(nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> insert_node(nodes[p],nodes[n]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</f
ont></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::swap_node(Node &n1, Node &n2){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n1.left!=NIL){ </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(n1.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n1.left].parent = n2.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n1.right!=NIL){</font></div><div><font class="Apple-style-span
" face="Tahoma" size="2"> //add_changed_nodes(n1.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n1.right].parent = n2.id; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n2.left!=NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(n2.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n2.left].parent = n1.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n2.right!=NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(n2.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> node
s[n2.right].parent = n1.id; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n1.parent != NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(n1.parent);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[n1.parent].left==n1.id)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n1.parent].left = n2.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n1.parent].right = n2.id; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div>
<font class="Apple-style-span" face="Tahoma" size="2"> changed_root = n1.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes_root = n2.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(n2.parent != NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(n2.parent);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(nodes[n2.parent].left==n2.id)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[n2.parent].left = n1.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
nodes[n2.parent].right = n1.id; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_root = n2.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes_root = n1.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap(n1.left,n2.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap(n1.right,n2.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> swap(n1.parent,n2.parent);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><
font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::insert_node(Node &parent, Node &node){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> node.parent = parent.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool edge = rand_bool();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(edge){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(parent.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> node.left = parent.left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> node.right = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(parent.left!=NIL)</font></div><div><font class="Apple-style-span" face="Tahoma"
size="2"> nodes[parent.left].parent = node.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> parent.left = node.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(parent.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> node.left = NIL;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> node.right = parent.right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(parent.right!=NIL)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[parent.right].parent = node.id;<
/font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> parent.right = node.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::delete_node(Node &node){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int child = NIL;<span class="Apple-tab-span" style="white-space:pre"> </span>// pull which child</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int subchild = NIL; // child's subtree</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int subparent= NIL; </font></div><div><font class="A
pple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(!node.isleaf()){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> bool left= rand_bool();<span class="Apple-tab-span" style="white-space:pre"> </span>// choose a child to pull up</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(node.left ==NIL) left=false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(node.right==NIL) left=true;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(node.left);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(node.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font cla
ss="Apple-style-span" face="Tahoma" size="2"> if(left){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> child = node.left;<span class="Apple-tab-span" style="white-space:pre"> </span>// child will never be NIL</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(node.right!=NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> subchild = nodes[child].right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> subparent = node.right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[node.right].parent = child; </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[child].right = node.right;<span class="Apple-tab-span" style="white-space:pre"> </span>// abut with node
's another child</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> child = node.right;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(node.left!=NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> subchild = nodes[child].left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> subparent = node.left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>nodes[node.left].parent = child;</font></div><div><font class="Apple-style-span" face="
Tahoma" size="2"> nodes[child].left = node.left;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(subchild);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[child].parent = node.parent;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(node.parent == NIL){<span class="Apple-tab-span" style="white-space:pre"> </span>// root</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">// changed_root = nodes_root;</font></div><div><font class="Apple-style-span" face="
Tahoma" size="2"> nodes_root = child;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{<span class="Apple-tab-span" style="white-space:pre"> </span>// let parent connect to child</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //add_changed_nodes(node.parent);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(node.id == nodes[node.parent].left)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[node.parent].left = child;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> nodes[node.parent].right = child;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div>
<div><font class="Apple-style-span" face="Tahoma" size="2"> // place subtree</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(subchild != NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &sc = nodes[subchild];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(subparent != NIL);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(1){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Node &p = nodes[subparent];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p.left==NIL || p.right==NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">  
; //add_changed_nodes(p.id);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>sc.parent = p.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(p.left==NIL) p.left = sc.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> else p.right = sc.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> break;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><span class="Apple-tab-span" style="white-space:pre"> </span>subparent = (rand_bool() ? p.left : p.right);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">
}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">bool B_Tree::delete_node2(Node &node,DIR pull){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> DIR npull = !pull;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p = node.parent;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n= node.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int c= child(n,pull
);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int cn=child(n,npull);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> assert(n!= nodes_root); // not root;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> DIR p2c = (nodes[p].left==n ? LEFT:RIGHT);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(c==NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(p,cn,p2c);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return (cn!=NIL); // folding</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div><
font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(p,c,p2c);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(c!=NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int k=child(c,npull);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(c,cn ,npull);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> cn= k;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> n= c;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> c= child(c,pull);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2
"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(cn != NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(n,cn,pull);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return true;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return false;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">/*</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Insert node into parent's left or right subtree according by "edge".</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> Push node into parent's subtree in
"push" direction.</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if "fold" is true, then fold the leaf.</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> (for the boundary condition of "delete" operation)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> delete <==> insert are permutating operations that can be recoved.</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">*/</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">void B_Tree::insert_node2(Node &parent,Node &node,</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> &nbs
p; DIR edge,DIR push,bool fold){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> DIR npush = !push;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int p= parent.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int n= node.id;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int c= child(p,edge);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(p,n,edge);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(n,c,push);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> while(c!=NIL){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">&nb
sp; wire_nodes(n,child(c,npush) ,npush);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> n= c;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> c= child(c,push);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(n,NIL,npush);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(fold){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(nodes[n].parent,NIL,push);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> wire_nodes(nodes[n].parent,n,npush); </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2
">}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2">int main(int argc,char **argv)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">char processor_name[ MPI_MAX_PROCESSOR_NAME ];</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int namelen;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI::Init(argc, argv);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int rank = MPI::COMM_WORLD.Get_rank();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int size = MPI::COMM_WORLD.Get_size();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI_Get_processor_name( processor_name, &
;namelen );</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> char filename[80],outfile[80]="";</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int times=400, local=7;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float init_temp=0.9, term_temp=0.1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float alpha=1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argc<=1){</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf("Usage: btree <filename> [times=%d] [hill_climb_stage=%d]\n",</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> ti
mes, local);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(" [avg_ratio=%.1f] [cost_ratio=%f]\n",avg_ratio,alpha);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(" [lamda=%.2f] [term-temp=%.2f]\n",lamda,term_temp);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf(" [output]\n");</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 0;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }else{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> int argi=1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) strcpy(filename, argv[argi++]);</font></div><div><font class="Apple-sty
le-span" face="Tahoma" size="2"> if(argi < argc) times=atoi(argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) local=atoi(argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) avg_ratio=atof(argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) alpha=atof(argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) lamda=atof(argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) term_temp=atof(argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(argi < argc) strcpy(outfile, argv[argi++]);</font></div><div><font class="Apple-style-span" face="Tahoma" s
ize="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> try{</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double time = seconds();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> B_Tree fp(alpha);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.read(filename);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //fp.show_modules();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.init();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> double last_time = SA_Floorplan(fp, times, local, term_temp);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> //
Random_Floorplan(fp,times);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fp.list_information();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> { // log performance and quality</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> if(strlen(outfile)==0)</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> strcpy(outfile,strcat(filename,".res"));</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> last_time = last_time - time;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> printf("CPU time = %.2f\n",seconds()-time);</font></div><
div><font class="Apple-style-span" face="Tahoma" size="2"> printf("Last CPU time = %.2f\n",last_time);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> FILE *fs= fopen(outfile,"a+");</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> </font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fprintf(fs,"CPU= %.2f, Cost= %.6f, Area= %.0f, Wire= %.0f, Dead=%.4f ",</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> last_time, float(fp.getCost()), float(fp.getArea()),</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> float(fp.getWireLength()), float(fp.getDeadSpace()));</font></div><d
iv><font class="Apple-style-span" face="Tahoma" size="2"> fprintf(fs," :%d %d %.0f \n", times, local, avg_ratio);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> fclose(fs);</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"><br></font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> }catch(...){}</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> MPI::Finalize();</font></div><div><font class="Apple-style-span" face="Tahoma" size="2"> return 1;</font></div><div><font class="Apple-style-span" face="Tahoma" size="2">}</font></div></div> </div></body>
</html>