[mpich-discuss] help required

[Pavan Balaji]

What do you need help with?

  -- Pavan

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

-- 
Pavan Balaji
http://www.mcs.anl.gov/~balaji