place_bin.c

/*===================================================================*/
//  
//     place_bin.c
//
//        Aaron P. Hurst, 2007
//              ahurst@eecs.berkeley.edu
//
/*===================================================================*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <assert.h>

//#define DEBUG

#include "place_base.h"

ABC_NAMESPACE_IMPL_START


// --------------------------------------------------------------------
// Global variables
//
// --------------------------------------------------------------------


// --------------------------------------------------------------------
// Function prototypes and local data structures
//
// --------------------------------------------------------------------

void spreadDensityX(int numBins, float maxMovement);
void spreadDensityY(int numBins, float maxMovement);


// --------------------------------------------------------------------
// globalFixDensity()
//
/// Doesn't deal well with fixed cells in the core area.
// --------------------------------------------------------------------
void globalFixDensity(int numBins, float maxMovement) {
  
  printf("QCLN-10 : \tbin-based density correction\n");
    
  spreadDensityX(numBins, maxMovement);
  // spreadDensityY(numBins, maxMovement);
}


// --------------------------------------------------------------------
// spreadDensityX()
//
// --------------------------------------------------------------------
void spreadDensityX(int numBins, float maxMovement) {

  int c, c2, c3, x, y;
  float totalArea = 0;
  int moveableCells = 0;
  float yBinArea = 0,  yCumArea = 0;
  int   yBinStart = 0, yBinCount = 0;
  int  xBinCount, xBinStart;
  float xBinArea, xCumArea;
  float lastOldEdge;
  float lastNewEdge;
  float curOldEdge, curNewEdge;
  float stretch, w;
  ConcreteCell *xCell, *yCell;
  ConcreteCell **binCells;
  ConcreteCell **allCells;

  binCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);
  allCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);

  for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
    ConcreteCell *cell =  g_place_concreteCells[c];
    if (!cell->m_fixed && !cell->m_parent->m_pad) {
      allCells[moveableCells++] = cell;
      totalArea += getCellArea(cell);
    }
  }
  
  // spread X
  qsort(allCells, (size_t)moveableCells, sizeof(ConcreteCell*), cellSortByY);

  y = 0;

  // for each y-bin...
  for(c=0; c<moveableCells; c++) {
    yCell = allCells[c];
    yBinArea += getCellArea(yCell);
    yCumArea += getCellArea(yCell);
    yBinCount++;

    // have we filled up a y-bin?
    if (yCumArea >= totalArea*(y+1)/numBins && yBinArea > 0) {
      memcpy(binCells, &(allCells[yBinStart]), sizeof(ConcreteCell*)*yBinCount);
      qsort(binCells, (size_t)yBinCount, sizeof(ConcreteCell*), cellSortByX);

#if defined(DEBUG)
      printf("y-bin %d count=%d area=%f\n",y,yBinCount, yBinArea);
#endif

      x = 0;
      xBinCount = 0, xBinStart =  0;
      xBinArea = 0, xCumArea = 0;
      lastOldEdge = g_place_coreBounds.x;
      lastNewEdge = g_place_coreBounds.x;

      // for each x-bin...
      for(c2=0; c2<yBinCount; c2++) {
        xCell = binCells[c2];
        xBinArea += getCellArea(xCell);
        xCumArea += getCellArea(xCell);
        xBinCount++;
        curOldEdge = xCell->m_x;
        
        printf("%.3f ", xCell->m_x);

        // have we filled up an x-bin?
        if (xCumArea >= yBinArea*(x+1)/numBins && xBinArea > 0) {
          curNewEdge = lastNewEdge + g_place_coreBounds.w*xBinArea/yBinArea;

          if (curNewEdge > g_place_coreBounds.x+g_place_coreBounds.w) 
            curNewEdge = g_place_coreBounds.x+g_place_coreBounds.w;
          if ((curNewEdge-curOldEdge)>maxMovement) curNewEdge = curOldEdge + maxMovement;
          if ((curOldEdge-curNewEdge)>maxMovement) curNewEdge = curOldEdge - maxMovement;

#if defined(DEBUG)
          printf("->\tx-bin %d count=%d area=%f (%f,%f)->(%f,%f)\n",x, xBinCount, xBinArea,
                 curOldEdge, lastOldEdge, curNewEdge, lastNewEdge);
#endif
          
          stretch = (curNewEdge-lastNewEdge)/(curOldEdge-lastOldEdge);
          
          // stretch!
          for(c3=xBinStart; c3<xBinStart+xBinCount; c3++) {
            if (curOldEdge == lastOldEdge)
              binCells[c3]->m_x = lastNewEdge+(c3-xBinStart)*(curNewEdge-lastNewEdge);
            else
              binCells[c3]->m_x = lastNewEdge+(binCells[c3]->m_x-lastOldEdge)*stretch;
            
              // force within core
            w = binCells[c3]->m_parent->m_width*0.5;
            if (binCells[c3]->m_x-w < g_place_coreBounds.x)
              binCells[c3]->m_x = g_place_coreBounds.x+w;
            if (binCells[c3]->m_x+w > g_place_coreBounds.x+g_place_coreBounds.w)
              binCells[c3]->m_x = g_place_coreBounds.x+g_place_coreBounds.w-w;
          }
          
          lastOldEdge = curOldEdge;
          lastNewEdge = curNewEdge;
          x++;
          xBinCount = 0;
          xBinArea = 0;
          xBinStart = c2+1;
        }
      }
      
      y++;
      yBinCount = 0;
      yBinArea = 0;
      yBinStart = c+1;
    }
  }

  free(binCells);
  free(allCells);
}


// --------------------------------------------------------------------
// spreadDensityY()
//
// --------------------------------------------------------------------
void spreadDensityY(int numBins, float maxMovement) {

  int c, c2, c3, x, y;
  float totalArea = 0;
  int moveableCells = 0;
  float xBinArea = 0,  xCumArea = 0;
  int   xBinStart = 0, xBinCount = 0;
  int   yBinCount, yBinStart;
  float yBinArea, yCumArea;
  float lastOldEdge;
  float lastNewEdge;
  float curOldEdge, curNewEdge;
  float stretch, h;
  ConcreteCell *xCell, *yCell;
  ConcreteCell **binCells;
  ConcreteCell **allCells;

  binCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);
  allCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);

  for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
    ConcreteCell *cell =  g_place_concreteCells[c];
    if (!cell->m_fixed && !cell->m_parent->m_pad) {
      allCells[moveableCells++] = cell;
      totalArea += getCellArea(cell);
    }
  }
  
  // spread Y
  qsort(allCells, moveableCells, sizeof(ConcreteCell*), cellSortByX);

  x = 0;

  // for each x-bin...
  for(c=0; c<moveableCells; c++) {
    xCell = allCells[c];
    xBinArea += getCellArea(xCell);
    xCumArea += getCellArea(xCell);
    xBinCount++;

    // have we filled up an x-bin?
    if (xCumArea >= totalArea*(x+1)/numBins && xBinArea > 0) {
      memcpy(binCells, &(allCells[xBinStart]), sizeof(ConcreteCell*)*xBinCount);
      qsort(binCells, (size_t)xBinCount, sizeof(ConcreteCell*), cellSortByY);

      // printf("x-bin %d count=%d area=%f\n",y,yBinCount, yBinArea);

      y = 0;
      yBinCount = 0, yBinStart =  0;
      yBinArea = 0, yCumArea = 0;
      lastOldEdge = g_place_coreBounds.y;
      lastNewEdge = g_place_coreBounds.y;
      
      // for each y-bin...
      for(c2=0; c2<xBinCount; c2++) {
        yCell = binCells[c2];
        yBinArea += getCellArea(yCell);
        yCumArea += getCellArea(yCell);
        yBinCount++;
        curOldEdge = yCell->m_y;
        
        // have we filled up an x-bin?
        if (yCumArea >= xBinArea*(y+1)/numBins && yBinArea > 0) {
          curNewEdge = lastNewEdge + g_place_coreBounds.h*yBinArea/xBinArea;

          if (curNewEdge > g_place_coreBounds.y+g_place_coreBounds.h) 
            curNewEdge = g_place_coreBounds.y+g_place_coreBounds.h;
          if ((curNewEdge-curOldEdge)>maxMovement) curNewEdge = curOldEdge + maxMovement;
          if ((curOldEdge-curNewEdge)>maxMovement) curNewEdge = curOldEdge - maxMovement;

          if (curOldEdge == lastOldEdge) continue; // hmmm
          stretch = (curNewEdge-lastNewEdge)/(curOldEdge-lastOldEdge);

          // stretch!
          for(c3=yBinStart; c3<yBinStart+yBinCount; c3++) {
            binCells[c3]->m_y = lastNewEdge+(binCells[c3]->m_y-lastOldEdge)*stretch;

            // force within core
            h = binCells[c3]->m_parent->m_height;
            if (binCells[c3]->m_y-h < g_place_coreBounds.y)
              binCells[c3]->m_y = g_place_coreBounds.y+h;
            if (binCells[c3]->m_y+h > g_place_coreBounds.y+g_place_coreBounds.h)
              binCells[c3]->m_y = g_place_coreBounds.y+g_place_coreBounds.h-h;
          }

          lastOldEdge = curOldEdge;
          lastNewEdge = curNewEdge;
          y++;
          yBinCount = 0;
          yBinArea = 0;
          yBinStart = c2+1;
        }
      }

      x++;
      xBinCount = 0;
      xBinArea = 0;
      xBinStart = c+1;
    }
  }

  free(binCells);
  free(allCells);
}
ABC_NAMESPACE_IMPL_END