Version abc71001

1 files changed, 1135 insertions, 0 deletions

diff --git a/src/phys/place/place_partition.c b/src/phys/place/place_partition.c
new file mode 100644
index 00000000..ea57cd1c
--- /dev/null
+++ b/src/phys/place/place_partition.c
@@ -0,0 +1,1135 @@
+/*===================================================================*/
+//  
+//     place_partition.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <math.h>
+#include <string.h>
+#include <stdio.h>
+#include <limits.h>
+#include <assert.h>
+//#include <sys/stat.h>
+//#include <unistd.h>
+
+#include "place_base.h"
+#include "place_gordian.h"
+
+#if !defined(NO_HMETIS)
+#include "libhmetis.h"
+#endif
+
+// --------------------------------------------------------------------
+// Global variables
+//
+// --------------------------------------------------------------------
+
+Partition *g_place_rootPartition = NULL;
+ConcreteNet **allNetsR2 = NULL, 
+  **allNetsL2 = NULL, 
+  **allNetsB2 = NULL, 
+  **allNetsT2 = NULL;
+
+
+// --------------------------------------------------------------------
+// Function prototypes and local data structures
+//
+// --------------------------------------------------------------------
+
+typedef struct FM_cell {
+    int loc;
+    int gain;
+    ConcreteCell *cell;
+    struct FM_cell *next, *prev;
+    bool locked;
+} FM_cell;
+
+void FM_updateGains(ConcreteNet *net, int partition, int inc, 
+                    FM_cell target [], FM_cell *bin [], 
+                    int count_1 [], int count_2 []);
+
+
+// --------------------------------------------------------------------
+// initPartitioning()
+//
+/// \brief Initializes data structures necessary for partitioning.
+//
+/// Creates a valid g_place_rootPartition.
+///
+// --------------------------------------------------------------------
+void initPartitioning() {
+  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;
+      }
+    }
+}
+
+
+// --------------------------------------------------------------------
+// presortNets()
+//
+/// \brief Sorts nets by corner positions.
+//
+/// Allocates allNetsX2 structures.
+///
+// --------------------------------------------------------------------
+void presortNets() {
+  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);
+}
+
+// --------------------------------------------------------------------
+// refinePartitions()
+//
+/// \brief Splits large leaf partitions.
+//
+// --------------------------------------------------------------------
+bool refinePartitions() {
+
+  return refinePartition(g_place_rootPartition);
+}
+
+
+// --------------------------------------------------------------------
+// reallocPartitions()
+//
+/// \brief Reallocates the partitions based on placement information.
+//
+// --------------------------------------------------------------------
+void reallocPartitions() {
+
+  reallocPartition(g_place_rootPartition);
+}
+
+
+// --------------------------------------------------------------------
+// refinePartition()
+//
+/// \brief Splits any large leaves within a partition.
+//
+// --------------------------------------------------------------------
+bool refinePartition(Partition *p) {
+  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;
+}
+
+
+// --------------------------------------------------------------------
+// repartitionHMetis()
+//
+/// \brief Repartitions the two subpartitions using the hMetis min-cut library.
+///
+/// The number of cut nets between the two partitions will be minimized.
+//
+// --------------------------------------------------------------------
+void repartitionHMetis(Partition *parent) {
+#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
+}
+
+
+// --------------------------------------------------------------------
+// repartitionFM()
+//
+/// \brief Fiduccia-Matheyses mincut partitioning algorithm.
+//
+/// UNIMPLEMENTED (well, un-C-ified)
+//
+// --------------------------------------------------------------------
+void repartitionFM(Partition *parent) {
+#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
+}
+
+// ----- FM_updateGains()
+//   moves a cell between bins
+#if 0
+void FM_updateGains(ConcreteNet *net, int partition, int inc, 
+                    FM_cell target [], FM_cell *bin [], 
+                    int count_1 [], int count_2 []) {
+
+    for(ConcretePinList::iterator it = net->getPins().begin(); !it; it++) {
+    FM_cell *current = &(target[(*it)->getCell()->getID()]);
+    assert(current->cell != 0);
+    
+    int old_gain = current->gain;
+    current->gain = 0;
+
+    // examine counts for the net on each pin
+    for(ConcretePinMap::iterator p_it = current->cell->getPins().begin(); !p_it; p_it++)
+        if ((*p_it)->isAttached()) {
+        int n_id = (*p_it)->getNet()->getID();
+        if (current->loc == 1 && count_1[n_id] == 1) current->gain++;
+        if (current->loc == 1 && count_2[n_id] == 0) current->gain--;
+        if (current->loc == 2 && count_1[n_id] == 0) current->gain--;
+        if (current->loc == 2 && count_2[n_id] == 1) current->gain++;
+        }
+
+    if (!current->locked) {
+        // remove cell from existing bin
+        int bin_num =  min(max(0, old_gain),FM_MAX_BIN);
+        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;
+        // add cell to correct bin
+        bin_num =  min(max(0, current->gain),FM_MAX_BIN);
+        current->prev = 0;
+        current->next = bin[bin_num];
+        if (bin[bin_num] != 0)
+        bin[bin_num]->prev = current;
+        bin[bin_num] = current;
+    }
+    }
+    
+}
+#endif
+
+
+// --------------------------------------------------------------------
+// partitionEqualArea()
+//
+/// \brief Splits a partition into two halves of equal area.
+//
+// --------------------------------------------------------------------
+void partitionEqualArea(Partition *parent) {
+  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;
+    }
+  
+}
+
+
+// --------------------------------------------------------------------
+// partitionScanlineMincut()
+//
+/// \brief Scans the cells within a partition from left to right and chooses the min-cut.
+//
+// --------------------------------------------------------------------
+void partitionScanlineMincut(Partition *parent) {
+#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
+}
+
+
+// --------------------------------------------------------------------
+// reallocPartition()
+//
+/// \brief Reallocates a partition and all of its children.
+//
+// --------------------------------------------------------------------
+void reallocPartition(Partition *p) {
+
+  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);
+}
+
+
+// --------------------------------------------------------------------
+// resizePartition()
+//
+/// \brief Recomputes the bounding boxes of the child partitions based on their relative areas.
+//
+// --------------------------------------------------------------------
+void resizePartition(Partition *p) {
+  // 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;
+  }
+}
+
+
+// --------------------------------------------------------------------
+// incrementalSubpartition()
+//
+/// \brief Adds new cells to an existing partition.  Partition sizes/locations are unchanged.
+///
+/// The function recurses, adding new cells to appropriate subpartitions.
+//
+// --------------------------------------------------------------------
+void incrementalSubpartition(Partition *p, ConcreteCell *newCells [], const int numNewCells) {
+  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);
+}
+
+
+// --------------------------------------------------------------------
+// incrementalPartition()
+//
+/// \brief Adds new cells to an existing partition.  Partition sizes/locations are unchanged.
+///
+/// The function recurses, adding new cells to appropriate subpartitions.
+//
+// --------------------------------------------------------------------
+void incrementalPartition() {
+  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);
+}