From 607c253cd2712bacce21ca9b98a848f331ea03a9 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 16 Feb 2007 08:01:00 -0800 Subject: Version abc70216 --- src/phys/place/place_bin.c | 263 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 263 insertions(+) create mode 100644 src/phys/place/place_bin.c (limited to 'src/phys/place/place_bin.c') diff --git a/src/phys/place/place_bin.c b/src/phys/place/place_bin.c new file mode 100644 index 00000000..567ff0fe --- /dev/null +++ b/src/phys/place/place_bin.c @@ -0,0 +1,263 @@ +/*===================================================================*/ +// +// place_bin.c +// +// Aaron P. Hurst, 2007 +// ahurst@eecs.berkeley.edu +// +/*===================================================================*/ + +#include +#include +#include +#include +#include + +#include "place_base.h" + +// -------------------------------------------------------------------- +// 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; cm_fixed && !cell->m_parent->m_pad) { + allCells[moveableCells++] = cell; + totalArea += getCellArea(cell); + } + } + + // spread X + qsort(allCells, moveableCells, sizeof(ConcreteCell*), cellSortByY); + + y = 0; + + // for each y-bin... + for(c=0; c= totalArea*(y+1)/numBins && yBinArea > 0) { + memcpy(binCells, &(allCells[yBinStart]), sizeof(ConcreteCell*)*yBinCount); + qsort(binCells, yBinCount, sizeof(ConcreteCell*), cellSortByX); + + // printf("y-bin %d count=%d area=%f\n",y,yBinCount, yBinArea); + + 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; c2m_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; + + stretch = (curNewEdge-lastNewEdge)/(curOldEdge-lastOldEdge); + + + // stretch! + for(c3=xBinStart; c3m_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; cm_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= totalArea*(x+1)/numBins && xBinArea > 0) { + memcpy(binCells, &(allCells[xBinStart]), sizeof(ConcreteCell*)*xBinCount); + qsort(binCells, 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; c2m_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; + + stretch = (curNewEdge-lastNewEdge)/(curOldEdge-lastOldEdge); + + // stretch! + for(c3=yBinStart; c3m_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); +} -- cgit v1.2.3