place_partition.c File Reference

#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include "place_base.h"
#include "place_gordian.h"
#include "libhmetis.h"

Go to the source code of this file.

Data Structures
struct	FM_cell

Typedefs
typedef struct FM_cell	FM_cell

Functions
void	FM_updateGains (ConcreteNet *net, int partition, int inc, FM_cell target[], FM_cell *bin[], int count_1[], int count_2[])
void	initPartitioning ()
	Initializes data structures necessary for partitioning. More...
void	presortNets ()
	Sorts nets by corner positions. 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	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	partitionEqualArea (Partition *parent)
	Splits a partition into two halves of equal area. More...
void	partitionScanlineMincut (Partition *parent)
	Scans the cells within a partition from left to right and chooses the min-cut. More...
void	reallocPartition (Partition *p)
	Reallocates a partition and all of its children. More...
void	resizePartition (Partition *p)
	Recomputes the bounding boxes of the child partitions based on their relative areas. More...
void	incrementalSubpartition (Partition *p, ConcreteCell *newCells[], const int numNewCells)
	Adds new cells to an existing partition. Partition sizes/locations are unchanged. More...
void	incrementalPartition ()
	Adds new cells to an existing partition. Partition sizes/locations are unchanged. More...

Variables
ABC_NAMESPACE_IMPL_START Partition *	g_place_rootPartition = NULL
ConcreteNet **	allNetsR2 = NULL
ConcreteNet **	allNetsL2 = NULL
ConcreteNet **	allNetsB2 = NULL
ConcreteNet **	allNetsT2 = NULL

Typedef Documentation

typedef struct FM_cell FM_cell

Function Documentation

void FM_updateGains	(	ConcreteNet *	net,
		int	partition,
		int	inc,
		FM_cell	target[],
		FM_cell *	bin[],
		int	count_1[],
		int	count_2[]
	)

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 incrementalSubpartition	(	Partition *	p,
		ConcreteCell *	newCells[],
		const int	numNewCells
	)

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

The function recurses, adding new cells to appropriate subpartitions.

Definition at line 1052 of file place_partition.c.

                                                                                             {
  int c;
  ConcreteCell **newCells1 = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*numNewCells), 
    **newCells2 = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*numNewCells);
  int numNewCells1 = 0, numNewCells2 = 0;
  float cut_loc;

  assert(p);

  // add new cells to partition list
  p->m_members = (ConcreteCell**)realloc(p->m_members, 
       sizeof(ConcreteCell*)*(p->m_numMembers+numNewCells));
  memcpy(&(p->m_members[p->m_numMembers]), newCells, sizeof(ConcreteCell*)*numNewCells);
  p->m_numMembers += numNewCells;

  // if is a leaf partition, finished
  if (p->m_leaf) return;

  // split new cells into sub-partitions based on location
  if (p->m_vertical) {
    cut_loc = p->m_sub2->m_bounds.x;
    for(c=0; c<numNewCells; c++)
      if (newCells[c]->m_x < cut_loc)
        newCells1[numNewCells1++] = newCells[c];
      else
        newCells2[numNewCells2++] = newCells[c];
  } else {
    cut_loc = p->m_sub2->m_bounds.y;
    for(c=0; c<numNewCells; c++)
      if (newCells[c]->m_y < cut_loc)
        newCells1[numNewCells1++] = newCells[c];
      else
        newCells2[numNewCells2++] = newCells[c];    
  }

  if (numNewCells1 > 0) incrementalSubpartition(p->m_sub1, newCells1, numNewCells1);
  if (numNewCells2 > 0) incrementalSubpartition(p->m_sub2, newCells2, numNewCells2);

  free(newCells1);
  free(newCells2);
}

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 presortNets

(

)

Sorts nets by corner positions.

Allocates allNetsX2 structures.

Definition at line 105 of file place_partition.c.

                   {
  allNetsL2 = (ConcreteNet**)realloc(allNetsL2, sizeof(ConcreteNet*)*g_place_numNets);
  allNetsR2 = (ConcreteNet**)realloc(allNetsR2, sizeof(ConcreteNet*)*g_place_numNets);
  allNetsB2 = (ConcreteNet**)realloc(allNetsB2, sizeof(ConcreteNet*)*g_place_numNets);
  allNetsT2 = (ConcreteNet**)realloc(allNetsT2, sizeof(ConcreteNet*)*g_place_numNets);
  memcpy(allNetsL2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets);
  memcpy(allNetsR2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets);
  memcpy(allNetsB2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets);
  memcpy(allNetsT2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets);
  qsort(allNetsL2, g_place_numNets, sizeof(ConcreteNet*), netSortByL);
  qsort(allNetsR2, g_place_numNets, sizeof(ConcreteNet*), netSortByR);
  qsort(allNetsB2, g_place_numNets, sizeof(ConcreteNet*), netSortByB);
  qsort(allNetsT2, g_place_numNets, sizeof(ConcreteNet*), netSortByT);
}

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

Variable Documentation

ConcreteNet ** allNetsB2 = NULL

Definition at line 37 of file place_partition.c.

ConcreteNet ** allNetsL2 = NULL

Definition at line 36 of file place_partition.c.

ConcreteNet** allNetsR2 = NULL

Definition at line 35 of file place_partition.c.

ConcreteNet ** allNetsT2 = NULL

Definition at line 38 of file place_partition.c.

ABC_NAMESPACE_IMPL_START Partition* g_place_rootPartition = NULL

Definition at line 34 of file place_partition.c.