init.c

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

/* initial placement: constructive algorithm */
#include "struct.h"

/* local variables */

/* local prototypes */
/*
void buildOts(int);
void removeDupOts();
void insert(int, struct OT *, int, int);
void Ideterministic(int);
*/

void init() {
  int i,j,k;
  int h=sqrt(cell_count);
  int w=cell_count/h;
  int left=cell_count-h*w;
  int index=0;

  Hot=otCreate(HOR);
  Hot->code=(int *)calloc(cell_count*2, sizeof(int));
  Hot->perm=(int *)calloc(cell_count, sizeof(int));
  Hot->orient=(int *)calloc(cell_count, sizeof(int));
  Hot->x=(int *)calloc(cell_count, sizeof(int));
  Hot->y=(int *)calloc(cell_count, sizeof(int));

  ots=(struct OT **)calloc(Ksize, sizeof(struct OT*));

  
Hot->n=cell_count;
for (i=0; i<h; i++)
{
   if (i<left) k=w+1;
   else k=w;
   for (j=0; j<k; j++)
   {
     Hot->code[index]=0;
     index++;
   }
   for (j=0; j<k; j++)
   {
     Hot->code[index]=1;
     index++;
   }
}

for (i=0; i<cell_count; i++)
{
  Hot->perm[i]=rtable[i];
  Hot->orient[i]=0;
  if (ver[i].type[0]=='L')
  ver[i].type[2]='R';
}
   



}

int perturb(int b, float pCost)
{
int i,j,  bestindex, bestorient, bestinsert ;
float bestcost;

place(Hot);
compute_cost(Hot);
for (i=0; i<Ksize;i++)
  ots[i]=otCopy(Hot);

changeOT(ots[1]);
for (j=0; j<Ksize; j++)
{
for (i=0; i<ots[j]->n; i++)
printf("%d ", ots[j]->perm[i]);
printf(" ots 1 perm \n");
for (i=0; i<ots[j]->n; i++)
printf("%d ", ots[j]->orient[i]);
printf("  orient \n");
for (i=0; i<ots[j]->n*2; i++)
printf("%d ", ots[j]->code[i]);
printf(" code \n");
}

bestcost=MAXfloat;
for (i=0; i<Ksize; i++)
{
delOt( ots[i], b);
printf("after delete one ot->n %d \n", ots[i]->n);
//while(place(ots[i]));

for (j=0; j<ots[i]->n; j++)
printf("%d ", ots[i]->perm[j]);
printf(" perm \n");

for (j=0; j<ots[i]->n; j++)
printf("%d ", ots[i]->orient[j]);
printf("  orient \n");
for (j=0; j<ots[i]->n*2; j++)
printf("%d ", ots[i]->code[j]);
printf(" code \n");


replaceOts(b,-1, ots[i]);
if (bestcost >Kcost)
{
  bestcost=Kcost;
  bestindex=i;
  bestinsert=Kinsert;
  bestorient=Korient;
}
}

printf("best cost %f, cost %f \n", bestcost, cost);
if (cost > bestcost)
{rebuild(b, bestindex, bestinsert, bestorient);
return 1;}

  return 0;
}

void Ideterministic(int n, float pCost)
{
int i, j, iter=0;
  for (i=j=0; j<n; j++) {
  int m=(i+j)%n;
  if (!m) iter++;
  if (perturb(m, pCost)) i=m, j=-1;
  }
}


void buildOts(int b) {
  int i;
  int j;
  float bestcost=MAXfloat;
  int bestinsert, bestindex, bestorient;

place(Hot);
 for (i=0; i<Ksize; i++)
  ots[i]=otCopy(Hot);

printf(" ---------------------in build \n");
changeOT(ots[1]);
for (j=0; j<Ksize; j++)
{
for (i=0; i<ots[j]->n; i++)
printf("%d ", ots[j]->perm[i]);
printf(" ots 1 perm \n");
for (i=0; i<ots[j]->n; i++)
printf("%d ", ots[j]->orient[i]);
printf("  orient \n");
for (i=0; i<ots[j]->n*2; i++)
printf("%d ", ots[j]->code[i]);
printf(" code \n");
}


for (i=0; i<Ksize; i++)
{
 replaceOts(rtable[b],-1,ots[i]);
 if (bestcost>Kcost)
 {
   bestcost=Kcost;
   bestinsert=Kinsert;
   bestorient=Korient;
   bestindex=i;
  }
}
 
 rebuild(rtable[b], bestindex, bestinsert, bestorient);
 freeOts();
 
}

void rebuild ( int delet, int bestindex, int bestinsert, int bestorient)
{
 int j, k,i;
 int ii;

//printf(" in the rebuild, bestindex %d, %d, %d\n", bestindex, bestinsert, bestorient);
 struct OT *p;
p=ots[bestindex];

 Hot->n=p->n+1;
//printf(" Hot ->n %d ots ->n %d\n", Hot->n, p->n);
 for (j=k=0;  j<=bestinsert; j++) 
     {Hot->code[j]=p->code[j];
     if(p->code[j]==0) 
      { Hot->perm[k]=p->perm[k];
        Hot->orient[k]=p->orient[k];
       k++;}
     }
//printf(" ok here 1 \n");
    ii=2*p->n-j;
   for (i=0; i<ii ; i++)
 Hot->code[2*p->n+1-i]=p->code[2*p->n-1-i];
     Hot->code[j]=0;
     Hot->code[j+1]=1;
     ii=p->n-k;
//printf(" ok here 2 \n");
for (i=0; i<ii; i++) 
     { Hot->orient[p->n-i]=p->orient[p->n-i-1];
       Hot->perm[p->n-i]=p->perm[p->n-i-1];}
     Hot->perm[k]=delet;
     Hot->orient[k]=bestorient;
     Hot->dir=p->dir;




}





void freeOts() {
 int i;
  for (i=0;i<Ksize;i++) {
    struct OT *p=ots[i];
    if (p->n) {
      if (p->code) free(p->code);
      if (p->perm) free(p->perm);
      if (p->orient) free(p->orient);
      if (p->x) free(p->x);
      if (p->y) free(p->y);
    }
  }

}

void insert(int ind, struct OT *ot, int cp, int or) {
  int i, j;
  struct OT *p=ots[ind];
  p->n=ot->n+1;
  p->dir=ot->dir;
  p->code=(int *)calloc(sizeof(int),p->n*2);
  p->perm=(int *)calloc(sizeof(int),p->n);
  p->orient=(int *)calloc(sizeof(int),p->n);
  p->x=(int *)calloc(sizeof(int),p->n);
  p->y=(int *)calloc(sizeof(int),p->n);
  for (i=j=0;i<cp;i++) if (!(p->code[i]=ot->code[i])) j++;
  p->code[i]=0;
  p->code[i+1]=1;
  for (i=cp+2;i<2*p->n;i++) p->code[i]=ot->code[i-2];
  for (i=0;i<j;i++) p->perm[i]=ot->perm[i], p->orient[i]=ot->orient[i];
  p->perm[i]=rtable[ot->n]; p->orient[i]=or;
  for (i=j+1;i<p->n;i++) p->perm[i]=ot->perm[i-1], p->orient[i]=ot->orient[i-1];
}

void debugOT(char *s, struct OT *ot) {
  int i,maxx=0,maxy=0;
  int area;
  printf(s);
  printf(": size=%d dir=%d wh:[",ot->n,ot->dir);
  for (i=0;i<ot->n;i++) {
    int x,y,w,h;
    if (ot->orient[i]%2) w=ver[ot->perm[i]].h, h=ver[ot->perm[i]].w;
    else w=ver[ot->perm[i]].w, h=ver[ot->perm[i]].h;
    x=ot->x[i]+w; y=ot->y[i]+h;
    if (x>maxx) maxx=x;
    if (y>maxy) maxy=y;
    printf("(%d,%d)",w,h);
  }
  printf("] perm:[");
  for (i=0;i<ot->n;i++) printf("%d ",ot->perm[i]); printf("] orient:[");
  for (i=0;i<ot->n;i++) printf("%d ",ot->orient[i]); printf("] xy:[");
  for (i=0;i<ot->n;i++) printf("(%d,%d)",ot->x[i],ot->y[i]); printf("] code:[");
  for (i=0;i<ot->n*2;i++) printf("%d ",ot->code[i]); printf("] chip=%d\n",maxx*maxy);
  area=maxx*maxy;
  if (maxx>maxy) area+=(int)pow((double)maxx,CO1); else area+=(int)pow((double)maxy,CO1);
}




void IInsertB(int verb, struct OT *ot, int index)
{
int x, y, w, h,maxx, maxy, miny, i,k , newarea;
float newcost;
struct V *b=&ver[verb];
struct NodeList *p;
struct NodeList *qq;

    x=fcurrent->x+fcurrent->w;
//printf(" x is %d \n", x);
for (i=0; i<2; i++)
{
if (i==0) 
  {w=b->w;
   h=b->h;}
else 
   {w=b->h;
    h=b->w;}
maxx=x+w;

maxy=0;
p=fcurrent;
while (p->x+p->w <= x)
         p=p->next;

  while (p!=NULL && p->x <maxx)
 { int cury=p->block->y+p->h;
    if (maxy < cury) maxy=cury;
   p=p->next;}
  y=maxy;
  maxy=maxy+h;


     qq=HeadCeil;
     while(qq && qq->x+qq->w <=x)
       qq=qq->next;
     miny=xybound;
//printf(" miny %d, maxx, %d, HeadCeily %d ,%d\n", miny, maxx, qq->y, HeadCeil->y);
    while (qq && qq->x<maxx)
     {
      int cury=qq->block->y;
//printf(" cury %d \n", cury);
       if (cury<miny) miny=cury;
         qq=qq->next;
      }
//printf(" wide %d maxy %d Gap %d, miny %d \n", Width, maxy, Gap, miny);
   newarea=miny-maxy;
//printf(" Gap %d \n", newarea);
   if (Gap<newarea) newarea=Gap;
   if (Width>maxx) maxx=Width;

//printf(" new Gap %d, maxx %d \n", newarea, maxx);
   newarea=(xybound-newarea)*maxx;
//printf(" Gap %d newarea %d \n", Gap, newarea);
   newcost=newarea;
    if (Kcost>newcost)
      {
      Kcost=newcost;
      Kinsert=index;
       Korient=i;
      }
}
}
      
      
void replaceOts(int a, int c, struct OT *ot)
{
int i;
int tindex=0;

Kcost=MAXfloat;

pushCeil(ot);

createVfloor();
HeadFloor=Inivfloor();
HeadFloor->parent=&froot;
HeadFloor->prev=&froot;
froot.next=HeadFloor;
fcurrent=&froot;


tindex=0;
if (c==-1)
IInsertB(a, ot, -1);
else
InsertIIB(a, c, ot, -1);
for (i=0; i< 2*ot->n; i++)
{
  if (ot->code[i]==0)
  {
 peelCeil(tindex, ot);
 placeCell(ot,tindex);
 if (c==-1)
 IInsertB(a, ot,i);
  else
  InsertIIB(a, c, ot, i);
  tindex++;
  }
  else
{ fcurrent=fcurrent->parent;
  if (c==-1)
  IInsertB(a, ot,i);
  else
  InsertIIB(a, c, ot, i);
 }
}

//printf(" Kinsert %d Kcost %f \n", Kinsert, Kcost);
free(HeadCeil);

}


struct OT *otCreate(int dir) {
  struct OT *p;
  p=(struct OT *)calloc(sizeof(struct OT),1);
  p->n=0;
  p->dir=dir;
  p->code=p->perm=p->orient=NULL;
  p->x=p->y=NULL;
  return p;
}

void LLinsert(struct OT *ot, int a, int b)
{
int i, j, k;
int count;

for (i=0; i<ot->n && ot->perm[i]!=a; i++);
for (j=k=1; j<ot->n*2 && k<i+1; j++) if (ot->code[j]==0) k++;
if (i==0) k=1;
else k=j;
count=1;
for (j=k; j<ot->n*2 && count>0; j++)
 if (ot->code[j]==0) {count++; i++;}
 else count--;
  for (k=2*ot->n+1; k>j+1;k--) ot->code[k]=ot->code[k-2];
  ot->code[j]=0;
  ot->code[j+1]=1;
  i++;
  for (k=ot->n; k>i;k--) ot->perm[k]=ot->perm[k-1];
  ot->perm[i]=b;
 ot->n=ot->n+1;
}