place_gordian.h File Reference

#include "place_base.h"
#include "place_qpsolver.h"

Go to the source code of this file.

Data Structures
struct	Partition

Macros
#define	ABC__phys__place__place_gordian_h
#define	CLIQUE_PENALTY   1.0
#define	IGNORE_NETSIZE   20
#define	LARGEST_FINAL_SIZE   20
#define	PARTITION_AREA_ONLY   true
#define	REALLOCATE_PARTITIONS   false
#define	FINAL_REALLOCATE_PARTITIONS   false
#define	IGNORE_COG   false
#define	MAX_PARTITION_NONSYMMETRY   0.30
#define	REPARTITION_LEVEL_DEPTH   4
#define	REPARTITION_TARGET_FRACTION   0.15
#define	REPARTITION_FM   false
#define	REPARTITION_HMETIS   true
#define	FM_MAX_BIN   10
#define	FM_MAX_PASSES   10

Typedefs
typedef struct Partition	Partition

Functions
void	initPartitioning ()
	Initializes data structures necessary for partitioning. More...
void	incrementalPartition ()
	Adds new cells to an existing partition. Partition sizes/locations are unchanged. More...
bool	refinePartitions ()
	Splits large leaf partitions. More...
void	reallocPartitions ()
	Reallocates the partitions based on placement information. More...
bool	refinePartition (Partition *p)
	Splits any large leaves within a partition. More...
void	resizePartition (Partition *p)
	Recomputes the bounding boxes of the child partitions based on their relative areas. More...
void	reallocPartition (Partition *p)
	Reallocates a partition and all of its children. More...
void	repartitionHMetis (Partition *parent)
	Repartitions the two subpartitions using the hMetis min-cut library. More...
void	repartitionFM (Partition *parent)
	Fiduccia-Matheyses mincut partitioning algorithm. More...
void	partitionScanlineMincut (Partition *parent)
	Scans the cells within a partition from left to right and chooses the min-cut. More...
void	partitionEqualArea (Partition *parent)
	Splits a partition into two halves of equal area. More...
void	sanitizePlacement ()
	Moves any cells that are outside of the core bounds to the nearest location within. More...
void	constructQuadraticProblem ()
	Constructs the matrices necessary to do analytical placement. More...
void	solveQuadraticProblem (bool useCOG)
	Calls quadratic solver. More...

Variables
int	g_place_numPartitions
qps_problem_t *	g_place_qpProb
Partition *	g_place_rootPartition

Macro Definition Documentation

#define ABC__phys__place__place_gordian_h

Definition at line 11 of file place_gordian.h.

#define CLIQUE_PENALTY   1.0

Definition at line 21 of file place_gordian.h.

#define FINAL_REALLOCATE_PARTITIONS   false

Definition at line 28 of file place_gordian.h.

#define FM_MAX_BIN   10

Definition at line 39 of file place_gordian.h.

#define FM_MAX_PASSES   10

Definition at line 40 of file place_gordian.h.

#define IGNORE_COG   false

Definition at line 29 of file place_gordian.h.

#define IGNORE_NETSIZE   20

Definition at line 22 of file place_gordian.h.

#define LARGEST_FINAL_SIZE   20

Definition at line 25 of file place_gordian.h.

#define MAX_PARTITION_NONSYMMETRY   0.30

Definition at line 30 of file place_gordian.h.

#define PARTITION_AREA_ONLY   true

Definition at line 26 of file place_gordian.h.

#define REALLOCATE_PARTITIONS   false

Definition at line 27 of file place_gordian.h.

#define REPARTITION_FM   false

Definition at line 35 of file place_gordian.h.

#define REPARTITION_HMETIS   true

Definition at line 36 of file place_gordian.h.

#define REPARTITION_LEVEL_DEPTH   4

Definition at line 33 of file place_gordian.h.

#define REPARTITION_TARGET_FRACTION   0.15

Definition at line 34 of file place_gordian.h.

Typedef Documentation

typedef struct Partition Partition

Function Documentation

void constructQuadraticProblem

(

)

Constructs the matrices necessary to do analytical placement.

Definition at line 53 of file place_genqp.c.

                                 {
  int maxConnections = 1;
  int ignoreNum = 0;
  int n,t,c,c2,p;
  ConcreteCell  *cell;
  ConcreteNet   *net;
  int           *cell_numTerms = calloc(g_place_numCells, sizeof(int));
  ConcreteNet ***cell_terms = calloc(g_place_numCells, sizeof(ConcreteNet**));
  bool incremental = false;
  int nextIndex = 1;
  int *seen = calloc(g_place_numCells, sizeof(int));
  float weight;
  int last_index;

  // create problem object
  if (!g_place_qpProb) {
    g_place_qpProb = malloc(sizeof(qps_problem_t));
    g_place_qpProb->area = NULL;
    g_place_qpProb->x = NULL;
    g_place_qpProb->y = NULL;
    g_place_qpProb->fixed = NULL;
    g_place_qpProb->connect = NULL;
    g_place_qpProb->edge_weight = NULL;
  }

  // count the maximum possible number of non-sparse entries
  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) {
    ConcreteNet *net = g_place_concreteNets[n];
    if (net->m_numTerms > IGNORE_NETSIZE) {
      ignoreNum++;
    }
    else {
      maxConnections += net->m_numTerms*(net->m_numTerms-1);
      for(t=0; t<net->m_numTerms; t++) {
        c = net->m_terms[t]->m_id;
        p = ++cell_numTerms[c];
        cell_terms[c] = (ConcreteNet**)realloc(cell_terms[c], p*sizeof(ConcreteNet*));
        cell_terms[c][p-1] = net;
      }
    }
  }
  if(ignoreNum) {
    printf("QMAN-10 : \t\t%d large nets ignored\n", ignoreNum);
  }

  // initialize the data structures
  g_place_qpProb->num_cells = g_place_numCells;
  maxConnections += g_place_numCells + 1;

  g_place_qpProb->area        = realloc(g_place_qpProb->area,
                                       sizeof(float)*g_place_numCells);// "area" matrix
  g_place_qpProb->edge_weight = realloc(g_place_qpProb->edge_weight,
                                       sizeof(float)*maxConnections);  // "weight" matrix
  g_place_qpProb->connect     = realloc(g_place_qpProb->connect,
                                       sizeof(int)*maxConnections);    // "connectivity" matrix
  g_place_qpProb->fixed       = realloc(g_place_qpProb->fixed,
                                       sizeof(int)*g_place_numCells);  // "fixed" matrix

  // initialize or keep preexisting locations
  if (g_place_qpProb->x != NULL && g_place_qpProb->y != NULL) {
    printf("QMAN-10 :\tperforming incremental placement\n");
    incremental = true;
  }
  g_place_qpProb->x = (float*)realloc(g_place_qpProb->x, sizeof(float)*g_place_numCells);
  g_place_qpProb->y = (float*)realloc(g_place_qpProb->y, sizeof(float)*g_place_numCells);

  // form a row for each cell
  // build data
  for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) {
    cell = g_place_concreteCells[c];
    
    // fill in the characteristics for this cell
    g_place_qpProb->area[c] = getCellArea(cell);
    if (cell->m_fixed || cell->m_parent->m_pad) {
      g_place_qpProb->x[c] = cell->m_x;
      g_place_qpProb->y[c] = cell->m_y;
      g_place_qpProb->fixed[c] = 1;
    } else {
      if (!incremental) {
        g_place_qpProb->x[c] = g_place_coreBounds.x+g_place_coreBounds.w*0.5;
        g_place_qpProb->y[c] = g_place_coreBounds.y+g_place_coreBounds.h*0.5;
      }
      g_place_qpProb->fixed[c] = 0;
    }

    // update connectivity matrices
    last_index = nextIndex;
    for(n=0; n<cell_numTerms[c]; n++) {
      net = cell_terms[c][n];
      weight = net->m_weight / splitPenalty(net->m_numTerms);
      for(t=0; t<net->m_numTerms; t++) {
        c2 = net->m_terms[t]->m_id;
        if (c2 == c) continue;
        if (seen[c2] < last_index) {
          // not seen
          g_place_qpProb->connect[nextIndex-1] = c2;
          g_place_qpProb->edge_weight[nextIndex-1] = weight;
          seen[c2] = nextIndex;
          nextIndex++;
        } else {
          // seen
          g_place_qpProb->edge_weight[seen[c2]-1] += weight;
        }
      }
    }
    g_place_qpProb->connect[nextIndex-1] = -1;
    g_place_qpProb->edge_weight[nextIndex-1] = -1.0;    
    nextIndex++;
  } else {
    // fill in dummy values for connectivity matrices
    g_place_qpProb->connect[nextIndex-1] = -1;
    g_place_qpProb->edge_weight[nextIndex-1] = -1.0;    
    nextIndex++;    
  }

  free(cell_numTerms);
  free(cell_terms);
  free(seen);
}

void incrementalPartition

(

)

Adds new cells to an existing partition. Partition sizes/locations are unchanged.

The function recurses, adding new cells to appropriate subpartitions.

Definition at line 1103 of file place_partition.c.

                            {
  int c = 0, c2 = 0;
  int numNewCells = 0;
  ConcreteCell **allCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells),
    **newCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);

  assert(g_place_rootPartition);

  // update cell list of root partition
  memcpy(allCells, g_place_concreteCells, sizeof(ConcreteCell*)*g_place_numCells);
  qsort(allCells, g_place_numCells, sizeof(ConcreteCell*), cellSortByID);
  qsort(g_place_rootPartition->m_members, g_place_rootPartition->m_numMembers,
        sizeof(ConcreteCell*), cellSortByID);

  // scan sorted lists and collect cells not in partitions
  while(!allCells[c++]);
  while(!g_place_rootPartition->m_members[c2++]);

  for(; c<g_place_numCells; c++, c2++) {
    while(c2 < g_place_rootPartition->m_numMembers &&
          allCells[c]->m_id > g_place_rootPartition->m_members[c2]->m_id) c2++;
    while(c < g_place_numCells && 
          (c2 >= g_place_rootPartition->m_numMembers ||
           allCells[c]->m_id < g_place_rootPartition->m_members[c2]->m_id)) {
      // a new cell!
      newCells[numNewCells++] = allCells[c];
      c++;
    }
  }
  
  printf("QPRT-50 : \tincremental partitioning with %d new cells\n", numNewCells);
  if (numNewCells>0) incrementalSubpartition(g_place_rootPartition, newCells, numNewCells);

  free(allCells);
  free(newCells);
}

void initPartitioning

(

)

Initializes data structures necessary for partitioning.

Creates a valid g_place_rootPartition.

Definition at line 67 of file place_partition.c.

                        {
  int i;
  float area;

  // create root partition
  g_place_numPartitions = 1;
  if (g_place_rootPartition) free(g_place_rootPartition);
  g_place_rootPartition = malloc(sizeof(Partition));
  g_place_rootPartition->m_level = 0;
  g_place_rootPartition->m_area = 0;
  g_place_rootPartition->m_bounds = g_place_coreBounds;
  g_place_rootPartition->m_vertical = false;
  g_place_rootPartition->m_done = false;
  g_place_rootPartition->m_leaf = true;
      
  // add all of the cells to this partition
  g_place_rootPartition->m_members = malloc(sizeof(ConcreteCell*)*g_place_numCells);
  g_place_rootPartition->m_numMembers = 0;
  for (i=0; i<g_place_numCells; i++) 
    if (g_place_concreteCells[i]) {
      if (!g_place_concreteCells[i]->m_fixed) {
        area = getCellArea(g_place_concreteCells[i]);
        g_place_rootPartition->m_members[g_place_rootPartition->m_numMembers++] =
          g_place_concreteCells[i];
        g_place_rootPartition->m_area += area;
      }
    }
}

void partitionEqualArea

(

Partition *

parent

)

Splits a partition into two halves of equal area.

Definition at line 834 of file place_partition.c.

                                           {
  float halfArea, area;
  int i=0;
  
  // which way to sort?
  if (parent->m_vertical)
    // sort by X position
    qsort(parent->m_members, parent->m_numMembers, sizeof(ConcreteCell*), cellSortByX);
  else
    // sort by Y position
    qsort(parent->m_members, parent->m_numMembers, sizeof(ConcreteCell*), cellSortByY);

  // split the list
  halfArea = parent->m_area*0.5;
  parent->m_sub1->m_area = 0.0;
  parent->m_sub1->m_numMembers = 0;
  parent->m_sub1->m_members = (ConcreteCell**)realloc(parent->m_sub1->m_members, 
                                  sizeof(ConcreteCell*)*parent->m_numMembers);
  parent->m_sub2->m_area = 0.0;
  parent->m_sub2->m_numMembers = 0;
  parent->m_sub2->m_members = (ConcreteCell**)realloc(parent->m_sub2->m_members, 
                                  sizeof(ConcreteCell*)*parent->m_numMembers);

  for(; parent->m_sub1->m_area < halfArea; i++) 
    if (parent->m_members[i]) {
      area = getCellArea(parent->m_members[i]);
      parent->m_sub1->m_members[parent->m_sub1->m_numMembers++] = parent->m_members[i];
      parent->m_sub1->m_area += area;
  }
  for(; i<parent->m_numMembers; i++) 
    if (parent->m_members[i]) {
      area = getCellArea(parent->m_members[i]);
      parent->m_sub2->m_members[parent->m_sub2->m_numMembers++] = parent->m_members[i];
      parent->m_sub2->m_area += area;
    }
  
}

void partitionScanlineMincut

(

Partition *

parent

)

Scans the cells within a partition from left to right and chooses the min-cut.

Definition at line 879 of file place_partition.c.

                                                {
#if 0
  int current_cuts = 0;
  int minimum_cuts = INT_MAX;
  ConcreteCell *minimum_location = NULL;
  double currentArea = 0, halfArea = parent->m_area * 0.5;
  double areaFlexibility = parent->m_area * MAX_PARTITION_NONSYMMETRY;
  double newLine, oldLine = -DBL_MAX;

  for(ConcreteNetList::iterator n_it = m_design->nets.begin(); !n_it; n_it++)
    (*n_it)->m_mark = 0;
  for(h::list<ConcreteCell *>::iterator i = parent->m_members.begin();
      !i.isDone(); i++) {
    assert(*i);
    for(ConcretePinMap::iterator j = (*i)->getPins().begin();
    !j.isDone(); j++) {
      assert(*j);
      if((*j)->isAttached()) {
    (*j)->getNet()->m_mark = 1;
      }
    }
  }

  if (parent->vertical) {
    parent->m_members.sort(sortByX);
    int all1 = 0, all2 = 0;
    h::list<ConcreteCell *>::iterator local = parent->m_members.begin();
    for(; !local.isDone(); local++) {
      currentArea += (*local)->getArea();
      if (currentArea < halfArea-areaFlexibility)
    continue;
      if (currentArea > halfArea+areaFlexibility)
    break;
      newLine = (*local)->temp_x;
      while(all1 < g_place_numNets && allNetsL2[all1]->getBoundingBox().left() <= newLine) {
    if(allNetsL2[all1]->m_mark) {
      current_cuts++;
    }
    all1++;
      }
      while(all2 < g_place_numNets && allNetsR2[all2]->getBoundingBox().right() <= newLine) {
    if(allNetsR2[all2]->m_mark) {
      current_cuts--;
    }
    all2++;
      }
      if (current_cuts < minimum_cuts) {
    minimum_cuts = current_cuts;
    minimum_location = *local;
      }
      oldLine = newLine;
    }
  }
  else {
    parent->m_members.sort(sortByY);
    int all1 = 0, all2 = 0;
    h::list<ConcreteCell *>::iterator local = parent->m_members.begin();
    for(; !local.isDone(); local++) {
      currentArea += (*local)->getArea();
      if (currentArea < halfArea-areaFlexibility)
    continue;
      if (currentArea > halfArea+areaFlexibility)
    break;
      newLine = (*local)->temp_y;
      while(all1 < g_place_numNets && allNetsB2[all1]->getBoundingBox().top() <= newLine) {
    if(allNetsB2[all1]->m_mark) {
      current_cuts++;
    }
    all1++;
      }
      while(all2 < g_place_numNets && allNetsT2[all2]->getBoundingBox().bottom() <= newLine) {
    if(allNetsT2[all2]->m_mark) {
      current_cuts--;
    }
    all2++;
      }
      if (current_cuts < minimum_cuts) {
    minimum_cuts = current_cuts;
    minimum_location = *local;
      }
      oldLine = newLine;
    }
  }
  if (minimum_location == NULL) {
    return partitionEqualArea(parent);
  }
  h::list<ConcreteCell *>::iterator it = parent->m_members.begin();
  parent->m_sub1->m_members.clear();
  parent->m_sub1->m_area = 0;
  for(; *it != minimum_location; it++) {
    parent->m_sub1->m_members.push_front(*it);
    parent->m_sub1->m_area += (*it)->getArea();
  }
  parent->m_sub2->m_members.clear();
  parent->m_sub2->m_area = 0;
  for(; !it; it++) {
    parent->m_sub2->m_members.push_front(*it);
    parent->m_sub2->m_area += (*it)->getArea();
  }
#endif
}

void reallocPartition

(

Partition *

p

)

Reallocates a partition and all of its children.

Definition at line 988 of file place_partition.c.

                                    {

  if (p->m_leaf) {
    return;
  }

  // --- INITIAL PARTITION

  if (PARTITION_AREA_ONLY)
    partitionEqualArea(p);
  else 
    partitionScanlineMincut(p);

  resizePartition(p);

  // --- PARTITION IMPROVEMENT
  if (p->m_level < REPARTITION_LEVEL_DEPTH) {
    if (REPARTITION_HMETIS)
      repartitionHMetis(p);
    
    resizePartition(p);
  }

  reallocPartition(p->m_sub1);
  reallocPartition(p->m_sub2);
}

void reallocPartitions

(

)

Reallocates the partitions based on placement information.

Definition at line 138 of file place_partition.c.

                         {

  reallocPartition(g_place_rootPartition);
}

bool refinePartition

(

Partition *

p

)

Splits any large leaves within a partition.

Definition at line 150 of file place_partition.c.

                                   {
  bool degenerate = false;
  int nonzeroCount = 0;
  int i;

  assert(p);

  // is this partition completed?
  if (p->m_done) return true;

  // is this partition a non-leaf node?
  if (!p->m_leaf) {
    p->m_done = refinePartition(p->m_sub1);
    p->m_done &= refinePartition(p->m_sub2);
    return p->m_done;
  }
  
  // leaf...
  // create two new subpartitions
  g_place_numPartitions++;
  p->m_sub1 = malloc(sizeof(Partition));
  p->m_sub1->m_level = p->m_level+1;
  p->m_sub1->m_leaf = true;
  p->m_sub1->m_done = false;
  p->m_sub1->m_area = 0;
  p->m_sub1->m_vertical = !p->m_vertical;
  p->m_sub1->m_numMembers = 0;
  p->m_sub1->m_members = NULL;
  p->m_sub2 = malloc(sizeof(Partition));
  p->m_sub2->m_level = p->m_level+1;
  p->m_sub2->m_leaf = true;
  p->m_sub2->m_done = false;
  p->m_sub2->m_area = 0;
  p->m_sub2->m_vertical = !p->m_vertical;
  p->m_sub2->m_numMembers = 0;
  p->m_sub2->m_members = NULL;
  p->m_leaf = false;

  // --- INITIAL PARTITION

  if (PARTITION_AREA_ONLY)
    partitionEqualArea(p);
  else 
    partitionScanlineMincut(p);

  resizePartition(p);

  // --- PARTITION IMPROVEMENT

  if (p->m_level < REPARTITION_LEVEL_DEPTH) {
    if (REPARTITION_FM)
      repartitionFM(p);
    else if (REPARTITION_HMETIS)
      repartitionHMetis(p);
  }
    
  resizePartition(p);
  
  // fix imbalances due to zero-area cells
  for(i=0; i<p->m_sub1->m_numMembers; i++)
    if (p->m_sub1->m_members[i]) 
      if (getCellArea(p->m_sub1->m_members[i]) > 0) {
        nonzeroCount++;
      }
  
  // is this leaf now done?
  if (nonzeroCount <= LARGEST_FINAL_SIZE)
      p->m_sub1->m_done = true;
  if (nonzeroCount == 0)
      degenerate = true;

  nonzeroCount = 0;
  for(i=0; i<p->m_sub2->m_numMembers; i++)
    if (p->m_sub2->m_members[i])
      if (getCellArea(p->m_sub2->m_members[i]) > 0) {
        nonzeroCount++;
      }

  // is this leaf now done?
  if (nonzeroCount <= LARGEST_FINAL_SIZE)
      p->m_sub2->m_done = true;
  if (nonzeroCount == 0)
      degenerate = true;

  // have we found a degenerate partitioning?
  if (degenerate) {
    printf("QPART-35 : WARNING: degenerate partition generated\n");
    partitionEqualArea(p);
    resizePartition(p);
    p->m_sub1->m_done = true;
    p->m_sub2->m_done = true;
  }
  
  // is this parent now finished?
  if (p->m_sub1->m_done && p->m_sub2->m_done) p->m_done = true;
  
  return p->m_done;
}

bool refinePartitions

(

)

Splits large leaf partitions.

Definition at line 126 of file place_partition.c.

                        {

  return refinePartition(g_place_rootPartition);
}

void repartitionFM

(

Partition *

parent

)

Fiduccia-Matheyses mincut partitioning algorithm.

UNIMPLEMENTED (well, un-C-ified)

Definition at line 435 of file place_partition.c.

                                      {
#if 0
    assert(!parent->leaf && parent->m_sub1->leaf && parent->m_sub2->leaf);

    // count of each net's number of cells in each bipartition
    int count_1[m_design->nets.length()];
    memset(count_1, 0, sizeof(int)*m_design->nets.length());
    int count_2[m_design->nets.length()];
    memset(count_2, 0, sizeof(int)*m_design->nets.length());

    FM_cell target[m_design->cells.length()];
    memset(target, 0, sizeof(FM_cell)*m_design->cells.length());
    FM_cell *bin[FM_MAX_BIN+1];
    FM_cell *locked = 0;
    memset(bin, 0, sizeof(FM_cell *)*(FM_MAX_BIN+1));

    int max_gain = 0;
    int before_cuts = 0, current_cuts = 0;
    double initial_cut;
    int targets = 0;
    long cell_id;
    double halfArea = parent->m_area / 2.0;
    double areaFlexibility = parent->m_area * MAX_PARTITION_NONSYMMETRY;
    ConcreteNet *net;

    // INITIALIZATION
    //   select cells to partition

    if (parent->vertical) {
    // vertical

    initial_cut = parent->m_sub2->m_bounds.x;

    // initialize all cells
    for(h::list<ConcreteCell *>::iterator it = rootPartition->m_members.begin(); !it; it++) {
        cell_id = (*it)->getID();
        if ((*it)->temp_x < initial_cut)
        target[cell_id].loc = -1;
        else
        target[cell_id].loc = -2;
        target[cell_id].cell = *it;
        target[cell_id].gain = 0;
    }

    // initialize cells in partition 1
    for(h::list<ConcreteCell *>::iterator it = parent->m_sub1->m_members.begin(); !it; it++) {
        cell_id = (*it)->getID();
        // pay attention to cells that are close to the cut
        if (abs((*it)->temp_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) {
        targets++;
        target[cell_id].loc = 1;
        }
    }

    // initialize cells in partition 2
    for(h::list<ConcreteCell *>::iterator it = parent->m_sub2->m_members.begin(); !it; it++) {
        cell_id = (*it)->getID();
        // pay attention to cells that are close to the cut
        if (abs((*it)->temp_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) {
        targets++;
        target[cell_id].loc = 2;
        }       
    }

    // count the number of cells on each side of the partition for every net 
    for(h::hash_map<ConcreteNet *>::iterator n_it = m_design->nets.begin(); !n_it; n_it++) {
        for(ConcretePinList::iterator p_it = (net = *n_it)->getPins().begin(); !p_it; p_it++)
        if (abs(target[(*p_it)->getCell()->getID()].loc) == 1)
            count_1[net->getID()]++;
        else if (abs(target[(*p_it)->getCell()->getID()].loc) == 2)
            count_2[net->getID()]++;
        else if ((*p_it)->getCell()->temp_x < initial_cut) 
            count_1[net->getID()]++;
        else
            count_2[net->getID()]++;
        if (count_1[net->getID()] > 0 && count_2[net->getID()] > 0) before_cuts++;
    }
    
    } else {
    // horizontal

    initial_cut = parent->m_sub2->m_bounds.y;

    // initialize all cells
    for(h::list<ConcreteCell *>::iterator it = rootPartition->m_members.begin(); !it; it++) {
        cell_id = (*it)->getID();
        if ((*it)->temp_y < initial_cut)
        target[cell_id].loc = -1;
        else
        target[cell_id].loc = -2;
        target[cell_id].cell = *it;
        target[cell_id].gain = 0;
    }

    // initialize cells in partition 1
    for(h::list<ConcreteCell *>::iterator it = parent->m_sub1->m_members.begin(); !it; it++) {
        cell_id = (*it)->getID();
        // pay attention to cells that are close to the cut
        if (abs((*it)->temp_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) {
        targets++;
        target[cell_id].loc = 1;
        }
    }

    // initialize cells in partition 2
    for(h::list<ConcreteCell *>::iterator it = parent->m_sub2->m_members.begin(); !it; it++) {
        cell_id = (*it)->getID();
        // pay attention to cells that are close to the cut
        if (abs((*it)->temp_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) {
        targets++;
        target[cell_id].loc = 2;
        }       
    }

    // count the number of cells on each side of the partition for every net 
    for(h::hash_map<ConcreteNet *>::iterator n_it = m_design->nets.begin(); !n_it; n_it++) {
        for(ConcretePinList::iterator p_it = (net = *n_it)->getPins().begin(); !p_it; p_it++)
        if (abs(target[(*p_it)->getCell()->getID()].loc) == 1)
            count_1[net->getID()]++;
        else if (abs(target[(*p_it)->getCell()->getID()].loc) == 2)
            count_2[net->getID()]++;
        else if ((*p_it)->getCell()->temp_y < initial_cut) 
            count_1[net->getID()]++;
        else
            count_2[net->getID()]++;
        if (count_1[net->getID()] > 0 && count_2[net->getID()] > 0) before_cuts++;
    }
    }

    // INITIAL GAIN CALCULATION
    for(long id=0; id < m_design->cells.length(); id++)
    if (target[id].loc > 0) {
        assert(target[id].cell != 0);
        assert(target[id].gain == 0);

        // examine counts for the net on each pin
        for(ConcretePinMap::iterator p_it = target[id].cell->getPins().begin(); !p_it; p_it++)
        if ((*p_it)->isAttached()) {
            int n_id = (*p_it)->getNet()->getID();
            if (target[id].loc == 1 && count_1[n_id] == 1) target[id].gain++;
            if (target[id].loc == 1 && count_2[n_id] == 0) target[id].gain--;
            if (target[id].loc == 2 && count_1[n_id] == 0) target[id].gain--;
            if (target[id].loc == 2 && count_2[n_id] == 1) target[id].gain++;
        }

        assert(target[id].cell->getPins().length() >= abs(target[id].gain));

        // add it to a bin
        int bin_num = min(max(0, target[id].gain),FM_MAX_BIN);
        max_gain = max(max_gain, bin_num);

        assert(bin_num >= 0 && bin_num <= FM_MAX_BIN);
        target[id].next = bin[bin_num];
        target[id].prev = 0;
        if (bin[bin_num] != 0)
        bin[bin_num]->prev = &target[id];
        bin[bin_num] = &target[id];
    }

    // OUTER F-M LOOP
    current_cuts = before_cuts;
    int num_moves = 1;
    int pass = 0;
    while(num_moves > 0 && pass < FM_MAX_PASSES) {
    pass++;
    num_moves = 0;  

    // check_list(bin, locked, targets); // DEBUG

    // move all locked cells back
    int moved_back = 0;
    while(locked != 0) {
        FM_cell *current = locked;
        current->locked = false;

        int bin_num = min(max(0, current->gain),FM_MAX_BIN);       
        max_gain = max(max_gain, bin_num);

        locked = current->next;
        if (locked != 0)
        locked->prev = 0;

        if (bin[bin_num] != 0)
        bin[bin_num]->prev = current;
        current->next = bin[bin_num];
        bin[bin_num] = current;

        moved_back++;
    }
    // cout << "\tmoved back: " << moved_back << endl;
    // check_list(bin, locked, targets); // DEBUG   
    
    max_gain = FM_MAX_BIN;
    while(bin[max_gain] == 0 && max_gain > 0) max_gain--;

    // INNER F-M LOOP (single pass)
    while(1) {

        int bin_num = FM_MAX_BIN;
        FM_cell *current = bin[bin_num];

        // look for next cell to move
        while (bin_num > 0 && (current == 0 || 
        (current->loc==1 && current->cell->getArea()+parent->m_sub2->m_area > halfArea+areaFlexibility) ||
        (current->loc==2 && current->cell->getArea()+parent->m_sub1->m_area > halfArea+areaFlexibility))) {

        if (current == 0) current = bin[--bin_num]; else current = current->next;       
        }
        if (bin_num == 0)
        break;

        num_moves++;
        current->locked = true;
        // cout << "moving cell " << current->cell->getID() << " gain=" << current->gain << " pins= " << current->cell->getPins().length() << " from " << current->loc;

        // change partition marking and areas
        if (current->loc == 1) {
        current->loc = 2;
        parent->m_sub1->m_area -= current->cell->getArea();
        parent->m_sub2->m_area += current->cell->getArea();

        // update partition counts on all nets attached to this cell
        for(ConcretePinMap::iterator p_it = current->cell->getPins().begin(); 
            !p_it; p_it++) {
            
            if (!(*p_it)->isAttached()) // ignore unattached pins
            continue;
            net = (*p_it)->getNet();
            
            count_1[net->getID()]--;
            count_2[net->getID()]++;

            // cout << "\tnet " << net->getID() << " was " << count_1[net->getID()]+1 << "/" << count_2[net->getID()]-1 << " now " << count_1[net->getID()] << "/" << count_2[net->getID()] << endl;

            // if net becomes critical, update gains on attached cells and resort bins
            if (count_1[net->getID()] == 0) { current_cuts--; FM_updateGains(net, 2, -1, target, bin, count_1, count_2); }
            if (count_2[net->getID()] == 1) { current_cuts++; FM_updateGains(net, 1, -1, target, bin, count_1, count_2); }
            
            // check_list(bin, locked, targets); // DEBUG
        }

        } else {
        current->loc = 1;
        parent->m_sub2->m_area -= current->cell->getArea();
        parent->m_sub1->m_area += current->cell->getArea();

        // update gains on all nets attached to this cell
        for(ConcretePinMap::iterator p_it = current->cell->getPins().begin(); 
            !p_it; p_it++) {
            
            if (!(*p_it)->isAttached()) // ignore unattached pins
            continue;
            net = (*p_it)->getNet();
            count_2[net->getID()]--;
            count_1[net->getID()]++;

            // cout << "\tnet " << net->getID() << " was " << count_1[net->getID()]-1 << "/" << count_2[net->getID()]+1 << " now " << count_1[net->getID()] << "/" << count_2[net->getID()] << endl;

            if (count_2[net->getID()] == 0) { current_cuts--; FM_updateGains(net, 2, -1, target, bin, count_1, count_2); }
            if (count_1[net->getID()] == 1) { current_cuts++; FM_updateGains(net, 1, -1, target, bin, count_1, count_2); }
        
            // check_list(bin, locked, targets); // DEBUG
        }
        }

        //cout << " cuts=" << current_cuts << endl;

        // move current to locked

/*
        cout << "b=" << bin[bin_num] << " ";
        cout << current->prev << "-> ";
        if (current->prev == 0)
        cout << "X";
        else cout << current->prev->next;
        cout  << "=" << current << "=";
        if (current->next == 0)
        cout << "X";
        else
        cout << current->next->prev;
        cout << " ->" << current->next << endl;
*/

        if (bin[bin_num] == current)
        bin[bin_num] = current->next;
        if (current->prev != 0)
        current->prev->next = current->next;
        if (current->next != 0)
        current->next->prev = current->prev;

/*
        cout << "b=" << bin[bin_num] << " ";
        cout << current->prev << "-> ";
        if (current->prev == 0)
        cout << "X";
        else cout << current->prev->next;
        cout  << "=" << current << "=";
        if (current->next == 0)
        cout << "X";
        else
        cout << current->next->prev;
        cout << " ->" << current->next << endl;
*/

        current->prev = 0;
        current->next = locked;
        if (locked != 0)
        locked->prev = current;
        locked = current;
        
        // check_list(bin, locked, targets); // DEBUG   

        // update max_gain
        max_gain = FM_MAX_BIN;
        while(bin[max_gain] == 0 && max_gain > 0) max_gain--;
    }

    // cout << "\tcurrent cuts= " << current_cuts << " moves= " << num_moves << endl;
    }

    // reassign members to subpartitions
    cout << "FIDM-20 : \tbalance before " << parent->m_sub1->m_members.length() << "/"
       << parent->m_sub2->m_members.length() << " ";
    parent->m_sub1->m_members.clear();
    parent->m_sub1->m_area = 0;
    parent->m_sub2->m_members.clear();
    parent->m_sub2->m_area = 0;
    for(h::list<ConcreteCell *>::iterator it = parent->m_members.begin(); !it; it++) {
    if (target[(*it)->getID()].loc == 1 || target[(*it)->getID()].loc == -1) {
        parent->m_sub1->m_members.push_back(*it);
        parent->m_sub1->m_area += (*it)->getArea();
    }
    else {
        parent->m_sub2->m_members.push_back(*it);
        parent->m_sub2->m_area += (*it)->getArea();
    }
    }
    cout << " after " << parent->m_sub1->m_members.length() << "/"
       << parent->m_sub2->m_members.length() << endl;


    cout << "FIDM-21 : \tloc: " << initial_cut <<  " targetting: " << targets*100/parent->m_members.length() << "%" << endl;
    cout << "FIDM-22 : \tstarting cuts= " << before_cuts << " final cuts= " << current_cuts << endl;
#endif
}

void repartitionHMetis

(

Partition *

parent

)

Repartitions the two subpartitions using the hMetis min-cut library.

The number of cut nets between the two partitions will be minimized.

Definition at line 258 of file place_partition.c.

                                          {
#if defined(NO_HMETIS)
  printf("QPAR_02 : \t\tERROR: hMetis not available.  Ignoring.\n");
#else

  int n,c,t, i;
  float area;
  int *edgeConnections = NULL;
  int *partitionAssignment = (int *)calloc(g_place_numCells, sizeof(int));
  int *vertexWeights = (int *)calloc(g_place_numCells, sizeof(int));
  int *edgeDegree = (int *)malloc(sizeof(int)*(g_place_numNets+1));
  int numConnections = 0;
  int numEdges = 0;
  float initial_cut;
  int targets = 0;
  ConcreteCell *cell = NULL;
  int options[9];
  int afterCuts = 0;

  assert(parent);
  assert(parent->m_sub1);
  assert(parent->m_sub2);

  printf("QPAR-02 : \t\trepartitioning with hMetis\n");

  // count edges
  edgeDegree[0] = 0;
  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n])
    if (g_place_concreteNets[n]->m_numTerms > 1) {
      numConnections += g_place_concreteNets[n]->m_numTerms;
      edgeDegree[++numEdges] = numConnections;
    }
  
  if (parent->m_vertical) {
    // vertical
    initial_cut = parent->m_sub2->m_bounds.x;
    
    // initialize all cells
    for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
      if (g_place_concreteCells[c]->m_x < initial_cut)
        partitionAssignment[c] = 0;
      else
        partitionAssignment[c] = 1;
    }
  
    // initialize cells in partition 1
    for(t=0; t<parent->m_sub1->m_numMembers; t++) if (parent->m_sub1->m_members[t]) {
      cell = parent->m_sub1->m_members[t];
      vertexWeights[cell->m_id] = getCellArea(cell);
      // pay attention to cells that are close to the cut
      if (abs(cell->m_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) {
        targets++;
        partitionAssignment[cell->m_id] = -1;
      }
    }
    
    // initialize cells in partition 2
    for(t=0; t<parent->m_sub2->m_numMembers; t++) if (parent->m_sub2->m_members[t]) {
      cell = parent->m_sub2->m_members[t];
      vertexWeights[cell->m_id] = getCellArea(cell);
      // pay attention to cells that are close to the cut
      if (abs(cell->m_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) {
        targets++;
        partitionAssignment[cell->m_id] = -1;
      }     
    }
    
  } else {
    // horizontal
    initial_cut = parent->m_sub2->m_bounds.y;
    
    // initialize all cells
    for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
      if (g_place_concreteCells[c]->m_y < initial_cut)
        partitionAssignment[c] = 0;
      else
        partitionAssignment[c] = 1;
    }
    
    // initialize cells in partition 1
    for(t=0; t<parent->m_sub1->m_numMembers; t++) if (parent->m_sub1->m_members[t]) {
      cell = parent->m_sub1->m_members[t];
      vertexWeights[cell->m_id] = getCellArea(cell);
      // pay attention to cells that are close to the cut
      if (abs(cell->m_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) {
        targets++;
        partitionAssignment[cell->m_id] = -1;
      }
    }
    
    // initialize cells in partition 2
    for(t=0; t<parent->m_sub2->m_numMembers; t++) if (parent->m_sub2->m_members[t]) {
      cell = parent->m_sub2->m_members[t];
      vertexWeights[cell->m_id] = getCellArea(cell);
      // pay attention to cells that are close to the cut
      if (abs(cell->m_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) {
        targets++;
        partitionAssignment[cell->m_id] = -1;
      }     
    }
  }

  options[0] = 1;  // any non-default values?
  options[1] = 3; // num bisections
  options[2] = 1;  // grouping scheme
  options[3] = 1;  // refinement scheme
  options[4] = 1;  // cycle refinement scheme
  options[5] = 0;  // reconstruction scheme
  options[6] = 0;  // fixed assignments?
  options[7] = 12261980; // random seed
  options[8] = 0;  // debugging level

  edgeConnections = (int *)malloc(sizeof(int)*numConnections);

  i = 0;
  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) {
    if (g_place_concreteNets[n]->m_numTerms > 1)
      for(t=0; t<g_place_concreteNets[n]->m_numTerms; t++)
        edgeConnections[i++] = g_place_concreteNets[n]->m_terms[t]->m_id;
  }

  HMETIS_PartRecursive(g_place_numCells, numEdges, vertexWeights,
               edgeDegree, edgeConnections, NULL,
               2, (int)(100*MAX_PARTITION_NONSYMMETRY),
               options, partitionAssignment, &afterCuts);
    
  /*
  printf("HMET-20 : \t\t\tbalance before %d / %d ... ", parent->m_sub1->m_numMembers,
         parent->m_sub2->m_numMembers);
  */

  // reassign members to subpartitions
  parent->m_sub1->m_numMembers = 0;
  parent->m_sub1->m_area = 0;
  parent->m_sub2->m_numMembers = 0;
  parent->m_sub2->m_area = 0;
  parent->m_sub1->m_members = (ConcreteCell**)realloc(parent->m_sub1->m_members, 
       sizeof(ConcreteCell*)*parent->m_numMembers); 
  parent->m_sub2->m_members = (ConcreteCell**)realloc(parent->m_sub2->m_members, 
       sizeof(ConcreteCell*)*parent->m_numMembers); 
 
  for(t=0; t<parent->m_numMembers; t++) if (parent->m_members[t]) {
    cell = parent->m_members[t];
    area = getCellArea(cell);
    if (partitionAssignment[cell->m_id] == 0) {
      parent->m_sub1->m_members[parent->m_sub1->m_numMembers++] = cell;
      parent->m_sub1->m_area += area;
    }
    else {
      parent->m_sub2->m_members[parent->m_sub2->m_numMembers++] = cell;
      parent->m_sub2->m_area += area;
    }
  }
  /*
  printf("after %d / %d\n", parent->m_sub1->m_numMembers,
         parent->m_sub2->m_numMembers);
  */

  // cout << "HMET-21 : \t\t\tloc: " << initial_cut <<  " targetting: " << targets*100/parent->m_members.length() << "%" << endl;
  // cout << "HMET-22 : \t\t\tstarting cuts= " << beforeCuts << " final cuts= " << afterCuts << endl;

  free(edgeConnections);
  free(vertexWeights);
  free(edgeDegree);
  free(partitionAssignment);
#endif
}

void resizePartition

(

Partition *

p

)

Recomputes the bounding boxes of the child partitions based on their relative areas.

Definition at line 1022 of file place_partition.c.

                                   {
  // compute the new bounding box
  p->m_sub1->m_bounds.x = p->m_bounds.x;
  p->m_sub1->m_bounds.y = p->m_bounds.y;
  if (p->m_vertical) {
    p->m_sub1->m_bounds.w = p->m_bounds.w*(p->m_sub1->m_area/p->m_area);
    p->m_sub1->m_bounds.h = p->m_bounds.h;
    p->m_sub2->m_bounds.x = p->m_bounds.x + p->m_sub1->m_bounds.w;
    p->m_sub2->m_bounds.w = p->m_bounds.w*(p->m_sub2->m_area/p->m_area);
    p->m_sub2->m_bounds.y = p->m_bounds.y;
    p->m_sub2->m_bounds.h = p->m_bounds.h;
  } else {
    p->m_sub1->m_bounds.h = p->m_bounds.h*(p->m_sub1->m_area/p->m_area);
    p->m_sub1->m_bounds.w = p->m_bounds.w;
    p->m_sub2->m_bounds.y = p->m_bounds.y + p->m_sub1->m_bounds.h;
    p->m_sub2->m_bounds.h = p->m_bounds.h*(p->m_sub2->m_area/p->m_area);
    p->m_sub2->m_bounds.x = p->m_bounds.x;
    p->m_sub2->m_bounds.w = p->m_bounds.w;
  }
}

void sanitizePlacement

(

)

Moves any cells that are outside of the core bounds to the nearest location within.

Definition at line 125 of file place_gordian.c.

                         { 
  int c;
  float order_width = g_place_rowHeight;
  float x, y, edge, w, h;
  
  printf("QCLN-10 : \tsanitizing placement\n");

  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) {
      continue;
    }
    // the new locations of the cells will be distributed within
    // a small margin inside the border so that ordering is preserved
    order_width = g_place_rowHeight;

    x = cell->m_x, y = cell->m_y,
      w = cell->m_parent->m_width, h = cell->m_parent->m_height;

    if ((edge=x-w*0.5) < g_place_coreBounds.x) {
      x = g_place_coreBounds.x+w*0.5 +
        order_width/(1.0+g_place_coreBounds.x-edge);
    }
    else if ((edge=x+w*0.5) > g_place_coreBounds.x+g_place_coreBounds.w) {
      x = g_place_coreBounds.x+g_place_coreBounds.w-w*0.5 -
        order_width/(1.0+edge-g_place_coreBounds.x-g_place_coreBounds.w);
    }
    if ((edge=y-h*0.5) < g_place_coreBounds.y) {
      y = g_place_coreBounds.y+h*0.5 +
        order_width/(1.0+g_place_coreBounds.y-edge);
    }
    else if ((edge=y+h*0.5) > g_place_coreBounds.y+g_place_coreBounds.h) {
      y = g_place_coreBounds.y+g_place_coreBounds.h-h*0.5 -
        order_width/(1.0+edge-g_place_coreBounds.x-g_place_coreBounds.w);
    }
    cell->m_x = x;
    cell->m_y = y;
  }
}

void solveQuadraticProblem

(

bool

useCOG

)

Calls quadratic solver.

Definition at line 275 of file place_genqp.c.

                                        {
  int c;

  reverseCOG *COG_rev = malloc(sizeof(reverseCOG)*g_place_numPartitions);

  g_place_qpProb->cog_list = malloc(sizeof(int)*(g_place_numPartitions+g_place_numCells));
  g_place_qpProb->cog_x = malloc(sizeof(float)*g_place_numPartitions);
  g_place_qpProb->cog_y = malloc(sizeof(float)*g_place_numPartitions);

  // memset(g_place_qpProb->x, 0, sizeof(float)*g_place_numCells);
  // memset(g_place_qpProb->y, 0, sizeof(float)*g_place_numCells);

  qps_init(g_place_qpProb);

  if (useCOG)
      g_place_qpProb->cog_num = generateCoGConstraints(COG_rev);
  else
      g_place_qpProb->cog_num = 0;

  g_place_qpProb->loop_num = 0;

  qps_solve(g_place_qpProb);

  qps_clean(g_place_qpProb);

  // set the positions
  for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) {
    g_place_concreteCells[c]->m_x = g_place_qpProb->x[c];
    g_place_concreteCells[c]->m_y = g_place_qpProb->y[c];
  }
  
  // clean up
  free(g_place_qpProb->cog_list);
  free(g_place_qpProb->cog_x);
  free(g_place_qpProb->cog_y);

  free(COG_rev);
}

Variable Documentation

int g_place_numPartitions

Definition at line 28 of file place_gordian.c.

qps_problem_t* g_place_qpProb

Definition at line 28 of file place_genqp.c.

Partition* g_place_rootPartition

Definition at line 34 of file place_partition.c.