main.c

用C实现的基于O-tree的ic设计布图布线工具源代码,有相关文档

/* building block placement */
#define GLOBAL 1

#include "struct.h"
#include <time.h>

extern int wirelen,  real_area;
extern float bestcost ;
extern float newp;



/* global */
float bestcost, localbest;
struct snode *Lfloor, *Lceil;
int *X, *Y;
int bestarea, bestwire;


/* local prototypes */
//extern "C" long random();
extern long random();
void deterministic();
void detCompactOts(int);
void Insert(struct OT *ot1, struct OT *ot2, int b, int cp, int or);
void random_perm(struct OT *);
void create_rtbl();
int clockrotate(int b, float pCost);
int jia();
void AdjustOT(struct OT *ot);

int main(int argc, char **argv) {
  int i;
  double time1, time2;
  int It;

  printf("Otree Floorplanner version 1.3 (");
 // printf(TIMESTAMP);
  printf(")\n");
  if (argc<2) {
    printf("Error: No input file!\n");
    exit(0);
  }
  read(argv[1]);

if (argc<3) {
   printf("Error: No cost function coefficient \n");
   exit(0);
   }

newp=atof(argv[2]);



if (argc<4) {
    printf("Error: No iteration number!\n");
    exit(0);
  }
It=atoi(argv[3]);


//  initialize_window();
//  draw_panel();
  clock();
  time1=clock()/(double)(CLOCKS_PER_SEC);
  rtable=(int *)calloc(cell_count,sizeof(int));
  X=(int *)calloc(cell_count, sizeof(int));
  Y=(int *)calloc(cell_count, sizeof(int));
  for (i=0; i<cell_count; i++) rtable[i]=i;
bestcost=MAXfloat;
froot.x=froot.y=froot.w=froot.h=0;
Ksize=1;
Vot=otCreate(HOR);
bestOT=otCreate(HOR);


init();
place(Hot);
compute_area(Hot);
compute_wirelen(Hot);
normArea=real_area;
normWL=wirelen;

for (i=0; i<It; i++)
{
deterministic();
//debugOTX("final", Hot);

  create_rtbl();
  init();
}

printf(" Final Otree \n");

for (i=0; i<2*cell_count; i++)
printf("%d ", bestOT->code[i]);
printf("   code \n");
for (i=0; i<cell_count; i++)
printf("%d ", bestOT->perm[i]);
printf("     perm \n");

printf(" area is %d , wirelength  is %d \n",bestarea, bestwire);

printf(" The x-coordinate ----------------- \n");

for (i=0; i<cell_count; i++)
printf("%d ", X[i]);

printf( "\n The y-coordinate ------------------ \n");
for (i=0; i<cell_count; i++)
printf("%d ", Y[i]);



time2=clock()/(double)(CLOCKS_PER_SEC);


printf(" \n The time is %f \n", time2-time1);


  return 0;
}


void deterministic() {
int i;
int  j, iter=0;
int m;
struct NodeList *nPtr, *nPtr2;

localbest=MAXfloat;
for (i=0; i<LL_count; i++)
{
 delOt(Hot, LL[i].b);
 LLinsert(Hot, LL[i].a, LL[i].b);
}
  for (i=j=0; j<cell_count; j++) {
  m=(i+j)%cell_count;
  if (!m) iter++;
  if (clockrotate(m, pCost)) i=m, j=-1;
  }

otDismiss(Hot);
Hot=otCopy(Vot);
for (j=0;j<cell_count; j++)
clockrotate(j,0);
// /*
printf(" ---------------   ----------\n");
for (i=0; i<cell_count*2; i++)
printf("%d ", Vot->code[i] );
printf("    code \n");
for (i=0; i<cell_count; i++)
printf("%d ", Vot->perm[i] );
printf("    perm \n");
for (i=0; i<cell_count; i++)
printf("%d ", Vot->orient[i] );
printf("    orient \n");
//place(Vot);
//printf(" the final cost is %f \n", cost);
// freeOts();
for (i=0; i<cell_count; i++)
printf("%d ", X[i]);
printf("  X \n");
for (i=0; i<cell_count; i++)
printf("%d ", Y[i]);
printf("  Y \n");

/* free the node list 
nPtr = froot.next;
while ( nPtr != NULL )
{
    nPtr2 = nPtr->next;
    free(nPtr);
    nPtr = nPtr2;
}

 free the node list 
nPtr = HeadCeil;
while ( nPtr != NULL )
{
    nPtr2 = nPtr->next;
    free(nPtr);
    nPtr = nPtr2;
}

 free the node list 
nPtr = HeadFloor;
while ( nPtr != NULL )
{
    nPtr2 = nPtr->next;
    free(nPtr);
    nPtr = nPtr2;
}
*/

// */
}



int clockrotate(int a, float pCost)
{
int i,k, bestindex, bestinsert, bestorient, c=-1;
int cindex=0;
float oldcost;

place(Hot);
while(otCompact(Hot));
if (Hot->dir) otCompact(Hot);
compute_cost(Hot);
oldcost=cost;


 ots[0]=otCopy(Hot);

 delOt( ots[0], a);


 if (ver[a].type[0]=='L')
   {
    for (i=0; i<LL_count; i++)
     {
      if (a==LL[i].a) 
        c=LL[i].b; 
      else if (a==LL[i].b)
      c=LL[i].a;
      }
    delOt(ots[0],c);
   }
for (k=0; k<Ksize; k++)
{

  replaceOts(a,c, ots[k]);

if (c>-1) 
{a=Ainsert; 
c=Cinsert;}
rebuild(a, k, Kinsert, Korient);
  if (c>-1)
LLinsert( Hot, a, c);

 
changeOT(ots[k]);
Csibling(ots[k]);
if (k<Ksize-1)
ots[k+1]=otCopy(ots[k]);
otDismiss(ots[k]);
ots[k]=otCopy(Hot);
while (otCompact(ots[k]));
if (ots[k]->dir) otCompact(ots[k]);
place(ots[k]);
compute_cost(ots[k]);
Kcost=cost;



if(localbest >Kcost)
{localbest=Kcost;
 otDismiss(Vot);
 Vot=otCopy(ots[k]);
cindex=1;
}


AdjustOT(ots[k]);
place(ots[k]);
compute_cost(ots[k]);
Kcost=cost;


if (bestcost>Kcost)
{bestcost=Kcost;
bestarea=real_area;
bestwire=wirelen;
otDismiss(bestOT);
bestOT= otCopy(ots[k]);
place(ots[k]);
for (i=0; i<cell_count; i++)
{
 X[i]=ver[i].x;
Y[i]=ver[i].y;
}

cindex=1;
}

otDismiss(Hot);
Hot=otCopy(Vot);


}



freeOts();
return cindex;
}





void Insert(struct OT *ot1, struct OT *ot2, int index, int cp, int or) {
  int i, j;
  
  for (i=j=0;i<cp;i++) if (!(ot1->code[i]=ot2->code[i])) j++;
  ot1->code[i]=0;
  ot1->code[i+1]=1;
  for (i=cp+2;i<2*ot1->n;i++) ot1->code[i]=ot2->code[i-2];
  for (i=0;i<j;i++) ot1->perm[i]=ot2->perm[i], ot1->orient[i]=ot2->orient[i];
  ot1->perm[i]=index; ot1->orient[i]=or;
  for (i=j+1;i<ot1->n;i++) 
   {ot1->perm[i]=ot2->perm[i-1]; 
    ot1->orient[i]=ot2->orient[i-1];}
}






void random_perm(struct OT *ot) {
  int i,j;
  for (i=0;i<ot->n;i++) {
    j=rand()%ot->n;
    if (i!=j) {
      int t;
      t=ot->perm[j];
      ot->perm[j]=ot->perm[i];
      ot->perm[i]=t;
    }
  }
  while (place(ot)) ;
  if (ot->dir==VER) place(ot);
}

void create_rtbl() {
  int i;
  for (i=0; i<cell_count-1; i++) {
    int j=rand()%(cell_count-i);
    if (j) {
      int t=rtable[i];
      rtable[i]=rtable[i+j];
      rtable[i+j]=t;
    }
  }
}

void InsertIIB(int a, int c, struct OT *ot, int index)
{
int w1, h1, w2, h2,maxx1, maxx2, maxy1, maxy2, miny1,miny2, i,j , newarea;
int x1, x2, y1, y2;
float newcost;
struct V *b1, *b2;
struct NodeList *p = NULL;
struct snode *temp;
struct NodeList *qq;
int Gap1, Gap2;

for (i=0; i<2; i++)
{
  if (i==0) 
  {b1=&ver[a]; 
   b2=&ver[c];}
  else 
   {b1=&ver[c]; 
    b2=&ver[a];}
  w1=b1->w;
  h1=b1->h;
  w2=b2->w;
  h2=b2->h;
  for (j=0; j<2; j++)
   {
     if (j==0) 
        x1=x2=fcurrent->x+fcurrent->w;
     else
       {  if (w1>w2)
           {x1=fcurrent->x+fcurrent->w;
            x2=x1+w1-w2;}
          else 
            {x2=fcurrent->x+fcurrent->w;
             x1=x2+w2-w1;}
        }

     maxx1=x1+w1;
     maxy1=0;
     Lceil=NULL;
     Lfloor=NULL;
     p=fcurrent;
     while (p->x+p->w <= x1)
         p=p->next;
  while (p!=NULL && p->x <maxx1)
 { int cury=p->block->y+p->h;

     if (p->block->type[0]=='L')
     {
      temp=(struct snode *)malloc(sizeof(struct snode));
         temp->value=p->block->L;
         temp->next=Lceil;
         Lceil=temp;
     }

    if (maxy1 < cury) maxy1=cury;
   p=p->next;}
  y1=maxy1;

   if (w1>w2)
    {
      y2=y1+h1;
      if (j==0) 
        {maxx1=x2+w2; 
         maxx2=x1+w1;
         maxy1=y2+h2; 
         maxy2=y1+h1;}
      else 
         {maxx1=x2; 
          maxx2=x1+w1;
          maxy1=y1+h1; 
          maxy2=y2+h2;}
     qq=HeadCeil;
     while(qq && qq->x+qq->w <=x1)
       qq=qq->next;
     miny1=xybound;
     miny2=xybound;
    while (qq && qq->x<maxx1)
     {
      int cury=qq->block->y;

       if (qq->block->type[0]=='L')
         {
          temp=(struct snode *)malloc(sizeof(struct snode));
            temp->value=qq->block->L;
            temp->next=Lfloor;
            Lfloor=temp;
          }

       if (cury<miny1) miny1=cury;
       if (qq->x+qq->w >maxx1) miny2=cury;
         qq=qq->next;
      }
     while (qq && qq->x <maxx2)
      {
       int cury=qq->block->y;
        if (qq->block->type[0]=='L')
         {
            temp=(struct snode *)malloc(sizeof(struct snode));
            temp->value=qq->block->L;
            temp->next=Lfloor;
            Lfloor=temp;
          }

         if (cury<miny2) miny2=cury;
         qq=qq->next;
      }
    Gap1=miny1-maxy1;
    Gap2=miny2-maxy2;
   if (Gap1 <Gap2) newarea=Gap1;
    else newarea=Gap2;
    maxx1=x1+w1;
   if (Width>x1+w1) maxx1=Width;
}

else {

  maxx2=x2+w2;  // yao add on 6.23.05

    p=fcurrent;
   while (p->x+p->w <= x2)
         p=p->next;
    maxy2=y1+h1;
  while (p!=NULL && p->x <maxx2)
 { int cury=p->block->y+p->h;
    if (p->block->type[0]=='L')
     {
      temp=(struct snode *)malloc(sizeof(struct snode));
         temp->value=p->block->L;
         temp->next=Lceil;
         Lceil=temp;
     }
    if (maxy2 < cury) maxy2=cury;
   p=p->next;}

  y2=maxy2;
  maxy2=y2+h2;
  maxx2=x2+w2;
  qq=HeadCeil;
  while (qq && qq->x+qq->w <=x2)
       qq=qq->next;
     miny2=xybound;
    while (qq && qq->x<maxx2)
     {
      int cury=qq->block->y;
       if (qq->block->type[0]=='L')
         {
          temp=(struct snode *)malloc(sizeof(struct snode));
            temp->value=qq->block->L;
            temp->next=Lfloor;
            Lfloor=temp;
          }

       if (cury<miny2) miny2=cury;
         qq=qq->next;
      }
   newarea=miny2-maxy2;
   maxx1=x2+w2;
   if (Width >x2+w2) maxx1=Width;
  }

if (Gap<newarea) newarea=Gap;
   newarea=(xybound-newarea)*maxx1;

   newcost=newarea;
if (jia()) newcost=MAXfloat;
    if (Kcost>newcost)
      {
      Kcost=newcost;
      Kinsert=index;
       Korient=i;
      b1->x=x1;
      b2->x=x2;
      b1->y=y1;
      b2->y=y2;
      if (i==0) 
        {Ainsert=a; 
         Cinsert=c;
         }
      else 
         {Ainsert=c; 
          Cinsert=a;
          }
         if (j==0) ver[a].type[1]=ver[c].type[1]='L';
         else ver[a].type[1]=ver[c].type[1]='R';
      }
freelist(Lfloor);
freelist(Lceil);
}
}
}

int jia()
{
struct snode *p;
struct snode *q;
p=Lfloor; 
while (p)
{
  q=Lceil;
  while(q)
  {
    if (p->value==q->value) return 1;
    q=q->next;
  }
 p=p->next;
}
return 0;
}


int Fsibling(struct OT *ot, int a, int b)
{
int i, j, k, aindex=a, bindex=b;
 for (i=0; i<ot->n && ot->perm[i]!=a && ot->perm[i]!=b; i++);
  if (ot->perm[i]==b) 
    { aindex=b;
      bindex=a;}
for (j=k=1; j<ot->n*2 && k<i+1; j++) if (ot->code[j]==0) k++;

  if (ot->code[j]==1 )
    {
      if(ot->perm[i+1]==bindex) return 0;
      else return 1;
    }
  else
    {
     int kindex=1;
     while(kindex >0)
      {
        if (ot->code[j]==1) kindex--;
        else 
            {kindex++; 
             k++;}
         j++;
      }
    
     if (k+1>cell_count) return 1;

     if (ot->perm[k]==bindex) return 0;
     else return 1;
   }
     
}



void AdjustOT(struct OT *ot)
{
  int i;
  for (i=0; i<LL_count; i++)
 {
  if(Fsibling(ot, LL[i].a,LL[i].b))
   {
     delOt(ot, LL[i].b);
     LLinsert(ot, LL[i].a,LL[i].b);
   }
 }
}