place_base.h File Reference

Go to the source code of this file.

Data Structures
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. More...
void	addConcreteCell (ConcreteCell *cell)
void	delConcreteNet (ConcreteNet *net)
	Does not deallocate memory. More...
void	delConcreteCell (ConcreteCell *cell)
	Removes a cell from the placement database. More...
void	globalPreplace (float utilization)
	Place pad ring, leaving a core area to meet a desired utilization. More...
void	globalPlace ()
	Performs analytic placement using a GORDIAN-like algorithm. More...
void	globalIncremental ()
	Performs analytic placement using a GORDIAN-like algorithm. More...
void	globalFixDensity (int numBins, float maxMovement)
	Doesn't deal well with fixed cells in the core area. More...
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. More...
float	getNetWirelength (const ConcreteNet *net)
	Returns the half-perimeter wirelength of a net. More...
float	getTotalWirelength ()
	Returns the total HPWL of all nets. More...
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. More...
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. More...
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

#define ABC__phys__place__place_base_h

Definition at line 11 of file place_base.h.

#define false   0

Definition at line 29 of file place_base.h.

#define true   1

Definition at line 28 of file place_base.h.

Typedef Documentation

typedef struct AbstractCell AbstractCell

typedef struct ConcreteCell ConcreteCell

typedef struct ConcreteNet ConcreteNet

typedef struct Rect Rect

Function Documentation

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;
}

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;
}

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;
}

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;
}

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;
}

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);
}

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--;
}

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;
}

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

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;
}

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;
}

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;
}

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;
}

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);
}

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());
}

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());
}

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;
  }

}

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;
}

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;
}

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;
}

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;
}

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;
}

void writeBookshelf

(

const char *

filename

)

Definition at line 94 of file place_io.c.

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

Variable Documentation

ConcreteCell** g_place_concreteCells

Definition at line 33 of file place_base.c.

ConcreteNet** g_place_concreteNets

Definition at line 35 of file place_base.c.

Rect g_place_coreBounds

Definition at line 30 of file place_base.c.

int g_place_numCells

Definition at line 26 of file place_base.c.

int g_place_numNets

Definition at line 27 of file place_base.c.

Rect g_place_padBounds

Definition at line 31 of file place_base.c.

float g_place_rowHeight

Definition at line 28 of file place_base.c.