place_base.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Rect
struct	AbstractCell
struct	ConcreteCell
struct	ConcreteNet

Macros
#define	ABC__phys__place__place_base_h
#define	true   1
#define	false   0

Typedefs
typedef struct Rect	Rect
typedef struct AbstractCell	AbstractCell
typedef struct ConcreteCell	ConcreteCell
typedef struct ConcreteNet	ConcreteNet

Functions
void	addConcreteNet (ConcreteNet *net)
	Adds a net to the placement database.
void	addConcreteCell (ConcreteCell *cell)
void	delConcreteNet (ConcreteNet *net)
	Does not deallocate memory.
void	delConcreteCell (ConcreteCell *cell)
	Removes a cell from the placement database.
void	globalPreplace (float utilization)
	Place pad ring, leaving a core area to meet a desired utilization.
void	globalPlace ()
	Performs analytic placement using a GORDIAN-like algorithm.
void	globalIncremental ()
	Performs analytic placement using a GORDIAN-like algorithm.
void	globalFixDensity (int numBins, float maxMovement)
	Doesn't deal well with fixed cells in the core area.
float	fastEstimate (ConcreteCell *cell, int numNets, ConcreteNet *nets[])
float	fastTopoPlace (int numCells, ConcreteCell *cells[], int numNets, ConcreteNet *nets[])
Rect	getNetBBox (const ConcreteNet *net)
	Returns the bounding box of a net.
float	getNetWirelength (const ConcreteNet *net)
	Returns the half-perimeter wirelength of a net.
float	getTotalWirelength ()
	Returns the total HPWL of all nets.
float	getCellArea (const ConcreteCell *cell)
void	writeBookshelf (const char *filename)
int	netSortByL (const void *a, const void *b)
	Sorts nets by position of one of its corners.
int	netSortByR (const void *a, const void *b)
int	netSortByB (const void *a, const void *b)
int	netSortByT (const void *a, const void *b)
int	netSortByID (const void *a, const void *b)
int	cellSortByX (const void *a, const void *b)
	Sorts cells by either position coordinate.
int	cellSortByY (const void *a, const void *b)
int	cellSortByID (const void *a, const void *b)

Variables
int	g_place_numCells
int	g_place_numNets
float	g_place_rowHeight
Rect	g_place_coreBounds
Rect	g_place_padBounds
ConcreteCell **	g_place_concreteCells
ConcreteNet **	g_place_concreteNets

Macro Definition Documentation

ABC__phys__place__place_base_h

#define ABC__phys__place__place_base_h

Definition at line 11 of file place_base.h.

false

#define false   0

Definition at line 29 of file place_base.h.

true

#define true   1

Definition at line 28 of file place_base.h.

Typedef Documentation

AbstractCell

typedef struct AbstractCell AbstractCell

ConcreteCell

typedef struct ConcreteCell ConcreteCell

ConcreteNet

typedef struct ConcreteNet ConcreteNet

Rect

typedef struct Rect Rect

Function Documentation

addConcreteCell()

void addConcreteCell

(

ConcreteCell *

cell

)

The cell object must already be allocated and the ID must be set appropriately.

Definition at line 155 of file place_base.c.

                                           {
  assert(cell);
  assert(cell->m_id >= 0);
  if (cell->m_id >= g_place_concreteCellsSize) {
    g_place_concreteCellsSize = (cell->m_id > g_place_concreteCellsSize ? 
                                 cell->m_id : g_place_concreteCellsSize);
    g_place_concreteCellsSize *= 1.5;
    g_place_concreteCellsSize += 20;
    g_place_concreteCells = (ConcreteCell**)realloc(g_place_concreteCells, 
          sizeof(ConcreteCell*)*g_place_concreteCellsSize);
    assert(g_place_concreteCells);
  }
  if (cell->m_id >= g_place_numCells) {
    memset(&(g_place_concreteCells[g_place_numCells]), 0,
          sizeof(ConcreteCell*)*(cell->m_id+1-g_place_numCells));
    g_place_numCells = cell->m_id+1;
  }
  g_place_concreteCells[cell->m_id] = cell;
}

Here is the call graph for this function:

Here is the caller graph for this function:

addConcreteNet()

void addConcreteNet

(

ConcreteNet *

net

)

Adds a net to the placement database.

The net object must already be allocated and the ID must be set appropriately.

Definition at line 114 of file place_base.c.

                                        {
  assert(net);
  assert(net->m_id >= 0);
  if (net->m_id >= g_place_concreteNetsSize) {
    g_place_concreteNetsSize = (net->m_id > g_place_concreteNetsSize ? 
                               net->m_id : g_place_concreteNetsSize);
    g_place_concreteNetsSize *= 1.5;
    g_place_concreteNetsSize += 20;
    g_place_concreteNets = (ConcreteNet**)realloc(g_place_concreteNets, 
             sizeof(ConcreteNet*)*g_place_concreteNetsSize);
    assert(g_place_concreteNets);
  }
  if (net->m_id >= g_place_numNets) {
    memset(&(g_place_concreteNets[g_place_numNets]), 0,
            sizeof(ConcreteNet*)*(net->m_id+1-g_place_numNets));
    g_place_numNets = net->m_id+1;
    assert(g_place_numNets <= g_place_concreteNetsSize);
  }
  g_place_concreteNets[net->m_id] = net;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cellSortByID()

int cellSortByID	(	const void *	a,
		const void *	b )

Definition at line 338 of file place_base.c.

                                               {
  const ConcreteCell *pa = *(const ConcreteCell **)a;
  const ConcreteCell *pb = *(const ConcreteCell **)b;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  if (pa->m_id < pb->m_id) return -1;
  if (pa->m_id > pb->m_id) return 1;
  return 0;
}

Here is the caller graph for this function:

cellSortByX()

int cellSortByX	(	const void *	a,
		const void *	b )

Sorts cells by either position coordinate.

These are for use with qsort().

Can tolerate pointers to NULL objects.

Definition at line 314 of file place_base.c.

                                              {
  const ConcreteCell *pa = *(const ConcreteCell **)a;
  const ConcreteCell *pb = *(const ConcreteCell **)b;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  if (pa->m_x < pb->m_x) return -1;
  if (pa->m_x > pb->m_x) return 1;
  return 0;
}

Here is the caller graph for this function:

cellSortByY()

int cellSortByY	(	const void *	a,
		const void *	b )

Definition at line 326 of file place_base.c.

                                              {
  const ConcreteCell *pa = *(const ConcreteCell **)a;
  const ConcreteCell *pb = *(const ConcreteCell **)b;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  if (pa->m_y < pb->m_y) return -1;
  if (pa->m_y > pb->m_y) return 1;
  return 0;
}

Here is the caller graph for this function:

delConcreteCell()

void delConcreteCell

(

ConcreteCell *

cell

)

Removes a cell from the placement database.

Does not deallocate memory.

Important: does not modify nets that may point to this cell. If these are connections are not removed, segmentation faults and other nasty errors will occur.

Definition at line 216 of file place_base.c.

                                           {
  assert(cell);
  g_place_concreteCells[cell->m_id] = 0;
  while(!g_place_concreteCells[g_place_numCells-1]) g_place_numCells--;
 
  if (g_place_rootPartition) delCellFromPartition(cell, g_place_rootPartition);
}

Here is the call graph for this function:

delConcreteNet()

void delConcreteNet

(

ConcreteNet *

net

)

Does not deallocate memory.

Definition at line 141 of file place_base.c.

                                        {
  assert(net);
  g_place_concreteNets[net->m_id] = 0;
  while(!g_place_concreteNets[g_place_numNets-1]) g_place_numNets--;
}

fastEstimate()

float fastEstimate	(	ConcreteCell *	cell,
		int	numNets,
		ConcreteNet *	nets[] )

Definition at line 92 of file place_inc.c.

                                                     {
  float len = 0;
  int n;
  Rect box;
 
  assert(cell);
 
  for(n=0; n<numNets; n++) {
    box = getNetBBox(nets[n]);
    if (cell->m_x < box.x) len += (box.x - cell->m_x);
    if (cell->m_x > box.x+box.w) len += (cell->m_x-box.x-box.w);
    if (cell->m_y < box.y) len += (box.x - cell->m_y);
    if (cell->m_y > box.y+box.h) len += (cell->m_y-box.y-box.h);
  }
  
  return len;
}

Here is the call graph for this function:

fastTopoPlace()

float fastTopoPlace	(	int	numCells,
		ConcreteCell *	cells[],
		int	numNets,
		ConcreteNet *	nets[] )

getCellArea()

float getCellArea

(

const ConcreteCell *

cell

)

Definition at line 99 of file place_base.c.

                                            {
  assert(cell);
  return cell->m_parent->m_width*cell->m_parent->m_height;
}

Here is the caller graph for this function:

getNetBBox()

Rect getNetBBox

(

const ConcreteNet *

net

)

Returns the bounding box of a net.

Definition at line 45 of file place_base.c.

                                          {
  int t;
  Rect r;
 
  assert(net);
 
  r.x = r.y = INT_MAX;
  r.w = r.h = -INT_MAX;
  for(t=0; t<net->m_numTerms; t++) {
    r.x = net->m_terms[t]->m_x < r.x ? net->m_terms[t]->m_x : r.x;
    r.y = net->m_terms[t]->m_y < r.y ? net->m_terms[t]->m_y : r.y;
    r.w = net->m_terms[t]->m_x > r.w ? net->m_terms[t]->m_x : r.w;
    r.h = net->m_terms[t]->m_y > r.h ? net->m_terms[t]->m_y : r.h;
  }
  r.w -= r.x; r.h -= r.y;
  return r;
}

Here is the caller graph for this function:

getNetWirelength()

float getNetWirelength

(

const ConcreteNet *

net

)

Returns the half-perimeter wirelength of a net.

Definition at line 70 of file place_base.c.

                                               {
  Rect r;
 
  assert(net);
 
  r = getNetBBox(net);
  return r.w+r.h;
}

Here is the call graph for this function:

Here is the caller graph for this function:

getTotalWirelength()

float getTotalWirelength

(

)

Returns the total HPWL of all nets.

Definition at line 86 of file place_base.c.

                           {
  float r = 0;
  int n;
  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n])
    r += getNetWirelength(g_place_concreteNets[n]);
  return r;
}

Here is the call graph for this function:

Here is the caller graph for this function:

globalFixDensity()

void globalFixDensity	(	int	numBins,
		float	maxMovement )

Doesn't deal well with fixed cells in the core area.

Definition at line 43 of file place_bin.c.

                                                      {
  
  printf("QCLN-10 : \tbin-based density correction\n");
    
  spreadDensityX(numBins, maxMovement);
  // spreadDensityY(numBins, maxMovement);
}

Here is the call graph for this function:

Here is the caller graph for this function:

globalIncremental()

void globalIncremental

(

)

Performs analytic placement using a GORDIAN-like algorithm.

Requires a valid set of partitions.

Definition at line 94 of file place_gordian.c.

                           {
  if (!g_place_rootPartition) {
    printf("WARNING: Can not perform incremental placement\n");
    globalPlace();
    return;
  }
 
  printf("PLAC-10 : Incremental global placement\n");
 
  incrementalPartition();
 
  printf("QMAN-00 : \tconstructing initial quadratic problem...\n");
  constructQuadraticProblem();
 
  solveQuadraticProblem(!IGNORE_COG);
  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
  
  // clean up
  sanitizePlacement();
  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
  globalFixDensity(25, g_place_rowHeight*5);
  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
}

Here is the call graph for this function:

Here is the caller graph for this function:

globalPlace()

void globalPlace

(

)

Performs analytic placement using a GORDIAN-like algorithm.

Updates the positions of all non-fixed non-pad cells.

Definition at line 39 of file place_gordian.c.

                   {
  bool completionFlag = false;
  int iteration = 0;  
 
  printf("PLAC-10 : Global placement (wirelength-driven Gordian)\n");
 
  initPartitioning();
 
  // build matrices representing interconnections
  printf("QMAN-00 : \tconstructing initial quadratic problem...\n");
  constructQuadraticProblem();
 
  // iterate placement until termination condition is met
  while(!completionFlag) {
    printf("QMAN-01 : \titeration %d numPartitions = %d\n",iteration,g_place_numPartitions);
    
    // do the global optimization in each direction
    printf("QMAN-01 : \t\tglobal optimization\n");
    solveQuadraticProblem(!IGNORE_COG);
      
    // -------- PARTITIONING BASED CELL SPREADING ------
 
    // bisection
    printf("QMAN-01 : \t\tpartition refinement\n");
    if (REALLOCATE_PARTITIONS) reallocPartitions();
    completionFlag |= refinePartitions();
      
    printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
      
    iteration++;
  }
  
  // final global optimization
  printf("QMAN-02 : \t\tfinal pass\n");
  if (FINAL_REALLOCATE_PARTITIONS) reallocPartitions();
  solveQuadraticProblem(!IGNORE_COG);
  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
 
  // clean up
  sanitizePlacement();
  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
  globalFixDensity(25, g_place_rowHeight*5);
  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
}

Here is the call graph for this function:

Here is the caller graph for this function:

globalPreplace()

void globalPreplace

(

float

utilization

)

Place pad ring, leaving a core area to meet a desired utilization.

Sets the position of pads that aren't already fixed.

Computes g_place_coreBounds and g_place_padBounds. Determines g_place_rowHeight.

Definition at line 31 of file place_pads.c.

                                       {
  int i, c, h, numRows;
  float coreArea = 0, totalArea = 0;
  int padCount = 0;
  float area;
  ConcreteCell **padCells = NULL;
  AbstractCell *padType = NULL;
  ConcreteCell *cell;
  float nextPos;
  int remainingPads, northPads, southPads, eastPads, westPads;
 
  printf("PLAC-00 : Placing IO pads\n");;
 
  // identify the pads and compute the total core area
  g_place_coreBounds.x = g_place_coreBounds.y = 0;
  g_place_coreBounds.w = g_place_coreBounds.h = -INT_MAX;
 
  for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
    cell = g_place_concreteCells[c];
    area = getCellArea(cell);
    if (cell->m_parent->m_pad) {
      padType = cell->m_parent;
    } else {
      coreArea += area;
      g_place_rowHeight = cell->m_parent->m_height;
    }
 
    if (cell->m_fixed) {
      g_place_coreBounds.x = g_place_coreBounds.x < cell->m_x ? g_place_coreBounds.x : cell->m_x;
      g_place_coreBounds.y = g_place_coreBounds.y < cell->m_y ? g_place_coreBounds.y : cell->m_y;
      g_place_coreBounds.w = g_place_coreBounds.w > cell->m_x ? g_place_coreBounds.w : cell->m_x;
      g_place_coreBounds.h = g_place_coreBounds.h > cell->m_y ? g_place_coreBounds.h : cell->m_y;
    } else if (cell->m_parent->m_pad) {
      padCells = realloc(padCells, sizeof(ConcreteCell **)*(padCount+1));
      padCells[padCount++] = cell;
    }
    totalArea += area;
  }
  if (!padType) {
    printf("ERROR: No pad cells\n");
    exit(1);
  }
  g_place_padBounds.w -= g_place_padBounds.x;
  g_place_padBounds.h -= g_place_padBounds.y;
 
  coreArea /= utilization;
 
  // create the design boundaries
  numRows = sqrt(coreArea)/g_place_rowHeight+1;
  h = numRows * g_place_rowHeight;
  g_place_coreBounds.h = g_place_coreBounds.h > h ? g_place_coreBounds.h : h;
  g_place_coreBounds.w = g_place_coreBounds.w > coreArea/g_place_coreBounds.h ? 
    g_place_coreBounds.w : coreArea/g_place_coreBounds.h;
  // increase the dimensions by the width of the padring
  g_place_padBounds = g_place_coreBounds;
  if (padCount) {
    printf("PLAC-05 : \tpreplacing %d pad cells\n", padCount);
    g_place_padBounds.x -= padType->m_width;
    g_place_padBounds.y -= padType->m_height;
    g_place_padBounds.w = g_place_coreBounds.w+2*padType->m_width;
    g_place_padBounds.h = g_place_coreBounds.h+2*padType->m_height;
  }
 
  printf("PLAC-05 : \tplaceable rows  : %d\n", numRows);
  printf("PLAC-05 : \tcore dimensions : %.0fx%.0f\n",
         g_place_coreBounds.w, g_place_coreBounds.h);
  printf("PLAC-05 : \tchip dimensions : %.0fx%.0f\n",
         g_place_padBounds.w, g_place_padBounds.h);
  
  remainingPads = padCount;
  c = 0;
 
  // north pads
  northPads = remainingPads/4; remainingPads -= northPads;
  nextPos = 0;
  for(i=0; i<northPads; i++) {
    cell = padCells[c++];
    cell->m_x = g_place_padBounds.x+cell->m_parent->m_width*0.5 + nextPos;
    cell->m_y = g_place_padBounds.y+cell->m_parent->m_height*0.5;
    nextPos += (g_place_padBounds.w-padType->m_width) / northPads;
  }
  
  // south pads
  southPads = remainingPads/3; remainingPads -= southPads;
  nextPos = 0;
  for(i=0; i<southPads; i++) {
    cell = padCells[c++];
    cell->m_x = g_place_padBounds.w+g_place_padBounds.x-cell->m_parent->m_width*0.5 - nextPos;
    cell->m_y = g_place_padBounds.h+g_place_padBounds.y-cell->m_parent->m_height*0.5;
    nextPos += (g_place_padBounds.w-2*padType->m_width) / southPads;
  }
 
  // east pads
  eastPads = remainingPads/2; remainingPads -= eastPads;
  nextPos = 0;
  for(i=0; i<eastPads; i++) {
    cell = padCells[c++];
    cell->m_x = g_place_padBounds.w+g_place_padBounds.x-cell->m_parent->m_width*0.5;
    cell->m_y = g_place_padBounds.y+cell->m_parent->m_height*0.5 + nextPos;
    nextPos += (g_place_padBounds.h-padType->m_height) / eastPads;
  }
 
  // west pads
  westPads = remainingPads;
  nextPos = 0;
  for(i=0; i<westPads; i++) {
    cell = padCells[c++];
    cell->m_x = g_place_padBounds.x+cell->m_parent->m_width*0.5;
    cell->m_y = g_place_padBounds.h+g_place_padBounds.y-cell->m_parent->m_height*0.5 - nextPos;
    nextPos += (g_place_padBounds.h-padType->m_height) / westPads;
  }
 
}

Here is the call graph for this function:

Here is the caller graph for this function:

netSortByB()

int netSortByB	(	const void *	a,
		const void *	b )

Definition at line 263 of file place_base.c.

                                             {
  const ConcreteNet *pa = *(const ConcreteNet **)a;
  const ConcreteNet *pb = *(const ConcreteNet **)b;
  Rect ba, bb;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  ba = getNetBBox(pa), bb = getNetBBox(pb);
  if (ba.y + ba.h < bb.y + bb.h) return -1;
  if (ba.y + ba.h > bb.y + bb.h) return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

netSortByID()

int netSortByID	(	const void *	a,
		const void *	b )

Definition at line 291 of file place_base.c.

                                              {
  const ConcreteNet *pa = *(const ConcreteNet **)a;
  const ConcreteNet *pb = *(const ConcreteNet **)b;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  if (pa->m_id < pb->m_id) return -1;
  if (pa->m_id > pb->m_id) return 1;
  return 0;
}

netSortByL()

int netSortByL	(	const void *	a,
		const void *	b )

Sorts nets by position of one of its corners.

These are for use with qsort().

Can tolerate pointers to NULL objects.

Definition at line 235 of file place_base.c.

                                             {
  const ConcreteNet *pa = *(const ConcreteNet **)a;
  const ConcreteNet *pb = *(const ConcreteNet **)b;
  Rect ba, bb;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  ba = getNetBBox(pa), bb = getNetBBox(pb);
  if (ba.x < bb.x) return -1;
  if (ba.x > bb.x) return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

netSortByR()

int netSortByR	(	const void *	a,
		const void *	b )

Definition at line 249 of file place_base.c.

                                             {
  const ConcreteNet *pa = *(const ConcreteNet **)a;
  const ConcreteNet *pb = *(const ConcreteNet **)b;
  Rect ba, bb;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  ba = getNetBBox(pa), bb = getNetBBox(pb);
  if (ba.x + ba.w < bb.x + bb.w) return -1;
  if (ba.x + ba.w > bb.x + bb.w) return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

netSortByT()

int netSortByT	(	const void *	a,
		const void *	b )

Definition at line 277 of file place_base.c.

                                             {
  const ConcreteNet *pa = *(const ConcreteNet **)a;
  const ConcreteNet *pb = *(const ConcreteNet **)b;
  Rect ba, bb;
 
  if (!pa && !pb) return 0;
  else if (!pa) return -1;
  else if (!pb) return 1;
  ba = getNetBBox(pa), bb = getNetBBox(pb);
  if (ba.y < bb.y) return -1;
  if (ba.y > bb.y) return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

writeBookshelf()

void writeBookshelf

(

const char *

filename

)

Definition at line 94 of file place_io.c.

                                          {
  writeBookshelfNodes("out.nodes");
  writeBookshelfPl("out.pl");
}

Here is the call graph for this function:

Variable Documentation

g_place_concreteCells

ConcreteCell** g_place_concreteCells

extern

Definition at line 33 of file place_base.c.

g_place_concreteNets

ConcreteNet** g_place_concreteNets

extern

Definition at line 35 of file place_base.c.

g_place_coreBounds

Rect g_place_coreBounds

extern

Definition at line 30 of file place_base.c.

g_place_numCells

int g_place_numCells

extern

Definition at line 26 of file place_base.c.

g_place_numNets

int g_place_numNets

extern

Definition at line 27 of file place_base.c.

g_place_padBounds

Rect g_place_padBounds

extern

Definition at line 31 of file place_base.c.

g_place_rowHeight

float g_place_rowHeight

extern

Definition at line 28 of file place_base.c.