Version abc80130_2

19 files changed, 4753 insertions, 0 deletions

diff --git a/src/phys/place/Makefile b/src/phys/place/Makefile
new file mode 100644
index 00000000..1f700105
--- /dev/null
+++ b/src/phys/place/Makefile
@@ -0,0 +1,30 @@
+TARGETS = place_test BookshelfView.class
+
+CFLAGS = -g -pedantic -Wall
+
+STATIC_LIBS = libhmetis.a
+DYNAMIC_LIBS = -lm
+
+OBJECTS = place_test.o place_qpsolver.o place_base.o place_pads.o place_genqp.o place_gordian.o \
+	place_partition.o place_legalize.o place_bin.o
+
+
+# For hMetis free code, uncomment the following lines
+#
+# CFLAGS = -g -pedantic -Wall -DNO_HMETIS
+# STATIC_LIBS =
+
+
+all: $(TARGETS)
+
+%.o: %.c *.h
+	gcc $(CFLAGS) -c -o $@ $<
+
+place_test: $(OBJECTS)
+	gcc *.o $(STATIC_LIBS) $(DYNAMIC_LIBS) -o place_test
+
+BookshelfView.class: BookshelfView.java
+	javac BookshelfView.java
+
+clean:
+	rm -rf *.o place_test *.class *~
diff --git a/src/phys/place/README b/src/phys/place/README
new file mode 100644
index 00000000..d4f8ac8f
--- /dev/null
+++ b/src/phys/place/README
@@ -0,0 +1,50 @@
+/*===================================================================*/
+//  
+// GORDIAN-like placement package
+//
+//              Aaron P. Hurst (ahurst@eecs.berkeley.edu)
+//              Addl code from Philip Chong (pchong@cadence.com)
+//              hMetis partitioner (www.cs.umn.edu/~metis)
+//
+/*===================================================================*/
+
+1. Requirements
+
+An i386 Linux system (though others will certainly work with some tweaks).
+A standard ANSI C development platform.  
+
+The following are optional, but useful:
+
+- hMetis partitioner.  This can be obtained from (www.cs.umn.edu/~metis)
+    Place (links to) the files "libhmetis.a" and "libhtmetis.h" in this directory.
+    Otherwise, #define NO_HMETIS in the file "place_gordian.h"
+- Java SDK, if compiling BookshelfView is desired.
+- Perl, if additional script utilities are desired.
+
+2. Descriptions of contents:
+
+place_base.h contains the basic data structures and "external" API.
+place_gordian.h contains the "internal" API and configuration options.
+
+There are also several utilities:
+
+i) place_test 
+
+Reads a netlist description in GSRC Bookshelf format, performs global placement,
+and rewrites the placement file.  An example usage:
+
+./place_test ac97_emap.nodes ac97_emap.nets ac97_emap.pl
+
+ii) BookshelfView
+
+A simple Java GUI to view the resulting placements.  It has been tested with
+Java 5 and 6.  Usage:
+
+java BookshelfView ac97_emap.nodes ac97_emap.pl
+
+iii) hpwl
+
+A perl script to print the half-perimeter wirelength of a placement.  Usage:
+
+./hpwl ac97_emap.nets ac97_emal.pl
+
diff --git a/src/phys/place/hpwl b/src/phys/place/hpwl
new file mode 100644
index 00000000..f69a1d05
--- /dev/null
+++ b/src/phys/place/hpwl
@@ -0,0 +1,57 @@
+#! /usr/bin/perl
+
+$netsfile = shift;
+$plfile = shift;
+
+# ------------------------------ read placement
+
+open FILE, $plfile;
+while (<FILE>) {
+  chop;
+  if (/(\w+)\s+([\-\d\.]+)\s+([\-\d\.]+)\s+\:/) {
+    $loc{$1} = "$2 $3";
+  }
+}
+close FILE;
+
+open FILE, $netsfile;
+while (<FILE>) {
+  chop;
+  $net = $2 if /NetDegree\s+\:\s+(\d+)\s+(\w+)/;
+  if (/(\w+)\s+(\w+)\s+\:/) {
+    $netconn{$net} .= "$1 ";
+    $cellconn{$1} .= "$net ";
+  }
+}
+close FILE;
+
+# ----------------------------- compute HPWL
+
+$hpwl = 0;
+foreach $net (keys %netconn) {
+  @conns = split ' ',$netconn{$net};
+  $min_x = $min_y = 1e12;
+  $max_x = $max_y = -1e12;
+  foreach $cell (@conns) {
+    if (!exists $loc{$cell}) {
+      print "WARNING: Unknown cell location: $cell\n";
+    } else {
+      ($x, $y) = split ' ',$loc{$cell};
+      $min_x = $x if $x < $min_x;
+      $min_y = $y if $y < $min_y;
+      $max_x = $x if $x > $max_x;
+      $max_y = $y if $y > $max_y;
+    }
+  }
+  
+  if ($min_x eq 1e12 or $min_y eq 1e12 or
+      $max_x eq -1e12 or $max_y eq -1e12) {
+    print "WARNING: Unbounded box\n";
+  } else {
+    $hpwl = $hpwl + $max_x - $min_x + $max_y - $min_y;
+  }
+}
+
+print "HPWL = ";
+printf "%e",$hpwl;
+print "\n";
diff --git a/src/phys/place/libhmetis.h b/src/phys/place/libhmetis.h
new file mode 100644
index 00000000..051079d4
--- /dev/null
+++ b/src/phys/place/libhmetis.h
@@ -0,0 +1,31 @@
+// A. Hurst ahurst@eecs.berkeley.edu
+
+#ifndef LIBHMETIS_H_
+#define LIBHMETIS_H_
+
+static void HMETIS_PartRecursive(int nvtxs, 
+              int nhedges, 
+              int *vwgts, 
+              int *eptr,
+              int *eind,
+              int *hewgts, 
+              int nparts, 
+              int nbfactor, 
+              int *options, 
+              int *part, 
+              int *edgecnt ) {} //;
+
+
+static void HMETIS_PartKway(int nvtxs, 
+             int nhedges, 
+             int *vwgts, 
+             int *eptr, 
+             int *eind,
+             int *hewgts, 
+             int nparts, 
+             int nbfactor, 
+             int *options, 
+             int *part, 
+             int *edgecnt ) {} //;
+
+#endif
diff --git a/src/phys/place/module.make b/src/phys/place/module.make
new file mode 100644
index 00000000..98930fbe
--- /dev/null
+++ b/src/phys/place/module.make
@@ -0,0 +1,10 @@
+SRC +=  src/phys/place/place_base.c \
+    src/phys/place/place_bin.c \
+    src/phys/place/place_genqp.c \
+    src/phys/place/place_gordian.c \
+    src/phys/place/place_legalize.c \
+    src/phys/place/place_pads.c \
+    src/phys/place/place_partition.c \
+    src/phys/place/place_qpsolver.c \
+        src/phys/place/place_io.c \
+        src/phys/place/place_inc.c
diff --git a/src/phys/place/place_base.c b/src/phys/place/place_base.c
new file mode 100644
index 00000000..4e38f1d1
--- /dev/null
+++ b/src/phys/place/place_base.c
@@ -0,0 +1,345 @@
+/*===================================================================*/
+//  
+//     place_base.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+#include <string.h>
+
+#include "place_base.h"
+#include "place_gordian.h"
+
+// --------------------------------------------------------------------
+// Global variables
+//
+// --------------------------------------------------------------------
+
+int   g_place_numCells = 0;
+int   g_place_numNets = 0;
+float g_place_rowHeight = 1.0;
+
+Rect  g_place_coreBounds;
+Rect  g_place_padBounds;
+
+ConcreteCell **g_place_concreteCells = NULL;
+int            g_place_concreteCellsSize = 0;
+ConcreteNet  **g_place_concreteNets = NULL;
+int            g_place_concreteNetsSize = 0;
+
+
+// --------------------------------------------------------------------
+// getNetBBox()
+//
+/// \brief Returns the bounding box of a net.
+//
+// --------------------------------------------------------------------
+Rect   getNetBBox(const ConcreteNet *net) {
+  int t;
+  Rect r;
+
+  assert(net);
+
+  r.x = r.y = INT_MAX;
+  r.w = r.h = -INT_MAX;
+  for(t=0; t<net->m_numTerms; t++) {
+    r.x = net->m_terms[t]->m_x < r.x ? net->m_terms[t]->m_x : r.x;
+    r.y = net->m_terms[t]->m_y < r.y ? net->m_terms[t]->m_y : r.y;
+    r.w = net->m_terms[t]->m_x > r.w ? net->m_terms[t]->m_x : r.w;
+    r.h = net->m_terms[t]->m_y > r.h ? net->m_terms[t]->m_y : r.h;
+  }
+  r.w -= r.x; r.h -= r.y;
+  return r;
+}
+
+
+// --------------------------------------------------------------------
+// getNetWirelength()
+//
+/// \brief Returns the half-perimeter wirelength of a net.
+//
+// --------------------------------------------------------------------
+float getNetWirelength(const ConcreteNet *net) {
+  Rect r;
+
+  assert(net);
+
+  r = getNetBBox(net);
+  return r.w+r.h;
+}
+
+
+// --------------------------------------------------------------------
+// getTotalWirelength()
+//
+/// \brief Returns the total HPWL of all nets.
+//
+// --------------------------------------------------------------------
+float getTotalWirelength() {
+  float r = 0;
+  int n;
+  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n])
+    r += getNetWirelength(g_place_concreteNets[n]);
+  return r;
+}
+
+
+// --------------------------------------------------------------------
+// getCellArea()
+//
+// --------------------------------------------------------------------
+float getCellArea(const ConcreteCell *cell) {
+  assert(cell);
+  return cell->m_parent->m_width*cell->m_parent->m_height;
+}
+
+
+// --------------------------------------------------------------------
+// addConcreteNet()
+//
+/// \brief Adds a net to the placement database.
+///
+/// The net object must already be allocated and the ID must be set
+/// appropriately.
+//
+// --------------------------------------------------------------------
+void   addConcreteNet(ConcreteNet *net) {
+  assert(net);
+  assert(net->m_id >= 0);
+  if (net->m_id >= g_place_concreteNetsSize) {
+    g_place_concreteNetsSize = (net->m_id > g_place_concreteNetsSize ? 
+                               net->m_id : g_place_concreteNetsSize);
+    g_place_concreteNetsSize *= 1.5;
+    g_place_concreteNetsSize += 20;
+    g_place_concreteNets = (ConcreteNet**)realloc(g_place_concreteNets, 
+             sizeof(ConcreteNet*)*g_place_concreteNetsSize);
+    assert(g_place_concreteNets);
+  }
+  if (net->m_id >= g_place_numNets) {
+    memset(&(g_place_concreteNets[g_place_numNets]), 0,
+            sizeof(ConcreteNet*)*(net->m_id+1-g_place_numNets));
+    g_place_numNets = net->m_id+1;
+    assert(g_place_numNets <= g_place_concreteNetsSize);
+  }
+  g_place_concreteNets[net->m_id] = net;
+}
+
+
+// --------------------------------------------------------------------
+// delConcreteNet()
+//
+/// Does not deallocate memory.
+// --------------------------------------------------------------------
+void   delConcreteNet(ConcreteNet *net) {
+  assert(net);
+  g_place_concreteNets[net->m_id] = 0;
+  while(!g_place_concreteNets[g_place_numNets-1]) g_place_numNets--;
+}
+
+
+// --------------------------------------------------------------------
+// addConcreteCell()
+//
+/// The cell object must already be allocated and the ID must be set
+/// appropriately.
+//
+// --------------------------------------------------------------------
+void   addConcreteCell(ConcreteCell *cell) {
+  assert(cell);
+  assert(cell->m_id >= 0);
+  if (cell->m_id >= g_place_concreteCellsSize) {
+    g_place_concreteCellsSize = (cell->m_id > g_place_concreteCellsSize ? 
+                                 cell->m_id : g_place_concreteCellsSize);
+    g_place_concreteCellsSize *= 1.5;
+    g_place_concreteCellsSize += 20;
+    g_place_concreteCells = (ConcreteCell**)realloc(g_place_concreteCells, 
+          sizeof(ConcreteCell*)*g_place_concreteCellsSize);
+    assert(g_place_concreteCells);
+  }
+  if (cell->m_id >= g_place_numCells) {
+    memset(&(g_place_concreteCells[g_place_numCells]), 0,
+          sizeof(ConcreteCell*)*(cell->m_id+1-g_place_numCells));
+    g_place_numCells = cell->m_id+1;
+  }
+  g_place_concreteCells[cell->m_id] = cell;
+}
+
+
+// --------------------------------------------------------------------
+// delCellFromPartition()
+//
+// --------------------------------------------------------------------
+void delCellFromPartition(ConcreteCell *cell, Partition *p) {
+  int c;
+  bool found = false;
+
+  assert(cell);
+  assert(p);
+
+  for(c=0; c<p->m_numMembers; c++) 
+    if (p->m_members[c] == cell) {
+      p->m_members[c] = 0;
+      p->m_area -= getCellArea(cell);
+      found = true;
+      break;
+    }
+     
+  if (!found) return;
+
+  if (!p->m_leaf) {
+    delCellFromPartition(cell, p->m_sub1);
+    delCellFromPartition(cell, p->m_sub2);
+  }
+}
+
+
+// --------------------------------------------------------------------
+// delConcreteCell()
+//
+/// \brief Removes a cell from the placement database.
+///
+/// Does not deallocate memory.
+///
+/// Important: does not modify nets that may point to this
+/// cell. If these are connections are not removed, segmentation faults 
+/// and other nasty errors will occur.
+//
+// --------------------------------------------------------------------
+void   delConcreteCell(ConcreteCell *cell) {
+  assert(cell);
+  g_place_concreteCells[cell->m_id] = 0;
+  while(!g_place_concreteCells[g_place_numCells-1]) g_place_numCells--;
+
+  if (g_place_rootPartition) delCellFromPartition(cell, g_place_rootPartition);
+}
+
+
+// --------------------------------------------------------------------
+// netSortByX...
+//
+/// \brief Sorts nets by position of one of its corners.
+//
+/// These are for use with qsort().
+///
+/// Can tolerate pointers to NULL objects.
+///
+// --------------------------------------------------------------------
+int netSortByL(const void *a, const void *b) {
+  const ConcreteNet *pa = *(const ConcreteNet **)a;
+  const ConcreteNet *pb = *(const ConcreteNet **)b;
+  Rect ba, bb;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  ba = getNetBBox(pa), bb = getNetBBox(pb);
+  if (ba.x < bb.x) return -1;
+  if (ba.x > bb.x) return 1;
+  return 0;
+}
+
+int netSortByR(const void *a, const void *b) {
+  const ConcreteNet *pa = *(const ConcreteNet **)a;
+  const ConcreteNet *pb = *(const ConcreteNet **)b;
+  Rect ba, bb;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  ba = getNetBBox(pa), bb = getNetBBox(pb);
+  if (ba.x + ba.w < bb.x + bb.w) return -1;
+  if (ba.x + ba.w > bb.x + bb.w) return 1;
+  return 0;
+}
+
+int netSortByB(const void *a, const void *b) {
+  const ConcreteNet *pa = *(const ConcreteNet **)a;
+  const ConcreteNet *pb = *(const ConcreteNet **)b;
+  Rect ba, bb;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  ba = getNetBBox(pa), bb = getNetBBox(pb);
+  if (ba.y + ba.h < bb.y + bb.h) return -1;
+  if (ba.y + ba.h > bb.y + bb.h) return 1;
+  return 0;
+}
+
+int netSortByT(const void *a, const void *b) {
+  const ConcreteNet *pa = *(const ConcreteNet **)a;
+  const ConcreteNet *pb = *(const ConcreteNet **)b;
+  Rect ba, bb;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  ba = getNetBBox(pa), bb = getNetBBox(pb);
+  if (ba.y < bb.y) return -1;
+  if (ba.y > bb.y) return 1;
+  return 0;
+}
+
+int netSortByID(const void *a, const void *b) {
+  const ConcreteNet *pa = *(const ConcreteNet **)a;
+  const ConcreteNet *pb = *(const ConcreteNet **)b;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  if (pa->m_id < pb->m_id) return -1;
+  if (pa->m_id > pb->m_id) return 1;
+  return 0;
+}
+
+
+// --------------------------------------------------------------------
+// cellSortByX...
+//
+/// \brief Sorts cells by either position coordinate.
+//
+/// These are for use with qsort().
+///
+/// Can tolerate pointers to NULL objects.
+//
+// --------------------------------------------------------------------
+int cellSortByX(const void *a, const void *b) {
+  const ConcreteCell *pa = *(const ConcreteCell **)a;
+  const ConcreteCell *pb = *(const ConcreteCell **)b;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  if (pa->m_x < pb->m_x) return -1;
+  if (pa->m_x > pb->m_x) return 1;
+  return 0;
+}
+
+int cellSortByY(const void *a, const void *b) {
+  const ConcreteCell *pa = *(const ConcreteCell **)a;
+  const ConcreteCell *pb = *(const ConcreteCell **)b;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  if (pa->m_y < pb->m_y) return -1;
+  if (pa->m_y > pb->m_y) return 1;
+  return 0;
+}
+
+int cellSortByID(const void *a, const void *b) {
+  const ConcreteCell *pa = *(const ConcreteCell **)a;
+  const ConcreteCell *pb = *(const ConcreteCell **)b;
+
+  if (!pa && !pb) return 0;
+  else if (!pa) return -1;
+  else if (!pb) return 1;
+  if (pa->m_id < pb->m_id) return -1;
+  if (pa->m_id > pb->m_id) return 1;
+  return 0;
+}
diff --git a/src/phys/place/place_base.h b/src/phys/place/place_base.h
new file mode 100644
index 00000000..e5e7ecef
--- /dev/null
+++ b/src/phys/place/place_base.h
@@ -0,0 +1,137 @@
+/*===================================================================*/
+//  
+//     place_base.h
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#if !defined(PLACE_BASE_H_)
+#define PLACE_BASE_H_
+
+// --------------------------------------------------------------------
+// Data structures
+//
+// --------------------------------------------------------------------
+
+// --- a C++ bool-like type
+//typedef char bool;
+#ifndef bool
+#define bool int
+#endif
+
+#define true 1
+#define false 0
+
+
+// --- Rect - rectangle
+
+typedef struct Rect {
+  float x, y;
+  float w, h;
+} Rect;
+
+
+// --- AbstractCell - a definition of a cell type
+
+typedef struct AbstractCell {
+  char *m_label;            // string description
+
+  float m_width, m_height;  // dimensions
+
+  bool  m_pad;              // a pad (external I/O) cell?
+} AbstractCell;
+
+
+// --- ConcreteCell - a design object
+
+typedef struct ConcreteCell {
+  int           m_id;       // a unique ID (see below)
+  char         *m_label;    // string description
+
+  AbstractCell *m_parent;   // cell type
+
+  bool          m_fixed;    // position is fixed?
+  float         m_x, m_y;   // center of cell
+
+  int           m_data;
+} ConcreteCell;
+
+
+// --- ConcreteNet - a design net
+
+typedef struct ConcreteNet {
+  int            m_id;       // a unique ID (see below)
+
+  int            m_numTerms; // num. of connected cells
+  ConcreteCell **m_terms;    // connected cells
+
+  float          m_weight;   // relative weight
+
+  int            m_data;
+} ConcreteNet;
+
+
+// A note about IDs - the IDs are non-nonegative integers. They need not
+// be contiguous, but this is certainly a good idea, as they are stored
+// in a non-sparse array.
+// Cells and nets have separate ID spaces.
+
+// --------------------------------------------------------------------
+// Global variable prototypes
+//
+// --------------------------------------------------------------------
+
+// NOTE: None of these need to be managed externally.
+
+extern int   g_place_numCells;   // number of cells
+extern int   g_place_numNets;    // number of nets
+extern float g_place_rowHeight;  // height of placement row
+extern Rect  g_place_coreBounds; // border of placeable area
+                                 // (x,y) = corner
+extern Rect  g_place_padBounds;  // border of total die area
+                                 // (x,y) = corner
+
+extern ConcreteCell **g_place_concreteCells; // all concrete cells
+extern ConcreteNet  **g_place_concreteNets;  // all concrete nets
+
+
+// --------------------------------------------------------------------
+// Function prototypes
+//
+// --------------------------------------------------------------------
+
+void   addConcreteNet(ConcreteNet *net);
+void   addConcreteCell(ConcreteCell *cell);
+void   delConcreteNet(ConcreteNet *net);
+void   delConcreteCell(ConcreteCell *cell);
+
+void   globalPreplace(float utilization);
+void   globalPlace();
+void   globalIncremental();
+void   globalFixDensity(int numBins, float maxMovement);
+
+float fastEstimate(ConcreteCell *cell,
+                   int numNets, ConcreteNet *nets[]);
+float fastTopoPlace(int numCells, ConcreteCell *cells[], 
+                    int numNets, ConcreteNet *nets[]);
+
+Rect   getNetBBox(const ConcreteNet *net);
+float  getNetWirelength(const ConcreteNet *net);
+float  getTotalWirelength();
+float  getCellArea(const ConcreteCell *cell);
+
+void   writeBookshelf(const char *filename);
+
+// comparative qsort-style functions
+int    netSortByL(const void *a, const void *b);
+int    netSortByR(const void *a, const void *b);
+int    netSortByB(const void *a, const void *b);
+int    netSortByT(const void *a, const void *b);
+int    netSortByID(const void *a, const void *b);
+int    cellSortByX(const void *a, const void *b);
+int    cellSortByY(const void *a, const void *b);
+int    cellSortByID(const void *a, const void *b);
+
+#endif
diff --git a/src/phys/place/place_bin.c b/src/phys/place/place_bin.c
new file mode 100644
index 00000000..86ec3506
--- /dev/null
+++ b/src/phys/place/place_bin.c
@@ -0,0 +1,277 @@
+/*===================================================================*/
+//  
+//     place_bin.c
+//
+//        Aaron P. Hurst, 2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <limits.h>
+#include <assert.h>
+
+//#define DEBUG
+
+#include "place_base.h"
+
+// --------------------------------------------------------------------
+// Global variables
+//
+// --------------------------------------------------------------------
+
+
+// --------------------------------------------------------------------
+// Function prototypes and local data structures
+//
+// --------------------------------------------------------------------
+
+void spreadDensityX(int numBins, float maxMovement);
+void spreadDensityY(int numBins, float maxMovement);
+
+
+// --------------------------------------------------------------------
+// globalFixDensity()
+//
+/// Doesn't deal well with fixed cells in the core area.
+// --------------------------------------------------------------------
+void globalFixDensity(int numBins, float maxMovement) {
+  
+  printf("QCLN-10 : \tbin-based density correction\n");
+    
+  spreadDensityX(numBins, maxMovement);
+  // spreadDensityY(numBins, maxMovement);
+}
+
+
+// --------------------------------------------------------------------
+// spreadDensityX()
+//
+// --------------------------------------------------------------------
+void spreadDensityX(int numBins, float maxMovement) {
+
+  int c, c2, c3, x, y;
+  float totalArea = 0;
+  int moveableCells = 0;
+  float yBinArea = 0,  yCumArea = 0;
+  int   yBinStart = 0, yBinCount = 0;
+  int  xBinCount, xBinStart;
+  float xBinArea, xCumArea;
+  float lastOldEdge;
+  float lastNewEdge;
+  float curOldEdge, curNewEdge;
+  float stretch, w;
+  ConcreteCell *xCell, *yCell;
+  ConcreteCell **binCells;
+  ConcreteCell **allCells;
+
+  binCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);
+  allCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);
+
+  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) {
+      allCells[moveableCells++] = cell;
+      totalArea += getCellArea(cell);
+    }
+  }
+  
+  // spread X
+  qsort(allCells, moveableCells, sizeof(ConcreteCell*), cellSortByY);
+
+  y = 0;
+
+  // for each y-bin...
+  for(c=0; c<moveableCells; c++) {
+    yCell = allCells[c];
+    yBinArea += getCellArea(yCell);
+    yCumArea += getCellArea(yCell);
+    yBinCount++;
+
+    // have we filled up a y-bin?
+    if (yCumArea >= totalArea*(y+1)/numBins && yBinArea > 0) {
+      memcpy(binCells, &(allCells[yBinStart]), sizeof(ConcreteCell*)*yBinCount);
+      qsort(binCells, yBinCount, sizeof(ConcreteCell*), cellSortByX);
+
+#if defined(DEBUG)
+      printf("y-bin %d count=%d area=%f\n",y,yBinCount, yBinArea);
+#endif
+
+      x = 0;
+      xBinCount = 0, xBinStart =  0;
+      xBinArea = 0, xCumArea = 0;
+      lastOldEdge = g_place_coreBounds.x;
+      lastNewEdge = g_place_coreBounds.x;
+
+      // for each x-bin...
+      for(c2=0; c2<yBinCount; c2++) {
+        xCell = binCells[c2];
+        xBinArea += getCellArea(xCell);
+        xCumArea += getCellArea(xCell);
+        xBinCount++;
+        curOldEdge = xCell->m_x;
+        
+        printf("%.3f ", xCell->m_x);
+
+        // have we filled up an x-bin?
+        if (xCumArea >= yBinArea*(x+1)/numBins && xBinArea > 0) {
+          curNewEdge = lastNewEdge + g_place_coreBounds.w*xBinArea/yBinArea;
+
+          if (curNewEdge > g_place_coreBounds.x+g_place_coreBounds.w) 
+            curNewEdge = g_place_coreBounds.x+g_place_coreBounds.w;
+          if ((curNewEdge-curOldEdge)>maxMovement) curNewEdge = curOldEdge + maxMovement;
+          if ((curOldEdge-curNewEdge)>maxMovement) curNewEdge = curOldEdge - maxMovement;
+
+#if defined(DEBUG)
+          printf("->\tx-bin %d count=%d area=%f (%f,%f)->(%f,%f)\n",x, xBinCount, xBinArea,
+                 curOldEdge, lastOldEdge, curNewEdge, lastNewEdge);
+#endif
+          
+          stretch = (curNewEdge-lastNewEdge)/(curOldEdge-lastOldEdge);
+          
+          // stretch!
+          for(c3=xBinStart; c3<xBinStart+xBinCount; c3++) {
+            if (curOldEdge == lastOldEdge)
+              binCells[c3]->m_x = lastNewEdge+(c3-xBinStart)*(curNewEdge-lastNewEdge);
+            else
+              binCells[c3]->m_x = lastNewEdge+(binCells[c3]->m_x-lastOldEdge)*stretch;
+            
+              // force within core
+            w = binCells[c3]->m_parent->m_width*0.5;
+            if (binCells[c3]->m_x-w < g_place_coreBounds.x)
+              binCells[c3]->m_x = g_place_coreBounds.x+w;
+            if (binCells[c3]->m_x+w > g_place_coreBounds.x+g_place_coreBounds.w)
+              binCells[c3]->m_x = g_place_coreBounds.x+g_place_coreBounds.w-w;
+          }
+          
+          lastOldEdge = curOldEdge;
+          lastNewEdge = curNewEdge;
+          x++;
+          xBinCount = 0;
+          xBinArea = 0;
+          xBinStart = c2+1;
+        }
+      }
+      
+      y++;
+      yBinCount = 0;
+      yBinArea = 0;
+      yBinStart = c+1;
+    }
+  }
+
+  free(binCells);
+  free(allCells);
+}
+
+
+// --------------------------------------------------------------------
+// spreadDensityY()
+//
+// --------------------------------------------------------------------
+void spreadDensityY(int numBins, float maxMovement) {
+
+  int c, c2, c3, x, y;
+  float totalArea = 0;
+  int moveableCells = 0;
+  float xBinArea = 0,  xCumArea = 0;
+  int   xBinStart = 0, xBinCount = 0;
+  int   yBinCount, yBinStart;
+  float yBinArea, yCumArea;
+  float lastOldEdge;
+  float lastNewEdge;
+  float curOldEdge, curNewEdge;
+  float stretch, h;
+  ConcreteCell *xCell, *yCell;
+  ConcreteCell **binCells;
+  ConcreteCell **allCells;
+
+  binCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);
+  allCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells);
+
+  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) {
+      allCells[moveableCells++] = cell;
+      totalArea += getCellArea(cell);
+    }
+  }
+  
+  // spread Y
+  qsort(allCells, moveableCells, sizeof(ConcreteCell*), cellSortByX);
+
+  x = 0;
+
+  // for each x-bin...
+  for(c=0; c<moveableCells; c++) {
+    xCell = allCells[c];
+    xBinArea += getCellArea(xCell);
+    xCumArea += getCellArea(xCell);
+    xBinCount++;
+
+    // have we filled up an x-bin?
+    if (xCumArea >= totalArea*(x+1)/numBins && xBinArea > 0) {
+      memcpy(binCells, &(allCells[xBinStart]), sizeof(ConcreteCell*)*xBinCount);
+      qsort(binCells, xBinCount, sizeof(ConcreteCell*), cellSortByY);
+
+      // printf("x-bin %d count=%d area=%f\n",y,yBinCount, yBinArea);
+
+      y = 0;
+      yBinCount = 0, yBinStart =  0;
+      yBinArea = 0, yCumArea = 0;
+      lastOldEdge = g_place_coreBounds.y;
+      lastNewEdge = g_place_coreBounds.y;
+      
+      // for each y-bin...
+      for(c2=0; c2<xBinCount; c2++) {
+        yCell = binCells[c2];
+        yBinArea += getCellArea(yCell);
+        yCumArea += getCellArea(yCell);
+        yBinCount++;
+        curOldEdge = yCell->m_y;
+        
+        // have we filled up an x-bin?
+        if (yCumArea >= xBinArea*(y+1)/numBins && yBinArea > 0) {
+          curNewEdge = lastNewEdge + g_place_coreBounds.h*yBinArea/xBinArea;
+
+          if (curNewEdge > g_place_coreBounds.y+g_place_coreBounds.h) 
+            curNewEdge = g_place_coreBounds.y+g_place_coreBounds.h;
+          if ((curNewEdge-curOldEdge)>maxMovement) curNewEdge = curOldEdge + maxMovement;
+          if ((curOldEdge-curNewEdge)>maxMovement) curNewEdge = curOldEdge - maxMovement;
+
+          if (curOldEdge == lastOldEdge) continue; // hmmm
+          stretch = (curNewEdge-lastNewEdge)/(curOldEdge-lastOldEdge);
+
+          // stretch!
+          for(c3=yBinStart; c3<yBinStart+yBinCount; c3++) {
+            binCells[c3]->m_y = lastNewEdge+(binCells[c3]->m_y-lastOldEdge)*stretch;
+
+            // force within core
+            h = binCells[c3]->m_parent->m_height;
+            if (binCells[c3]->m_y-h < g_place_coreBounds.y)
+              binCells[c3]->m_y = g_place_coreBounds.y+h;
+            if (binCells[c3]->m_y+h > g_place_coreBounds.y+g_place_coreBounds.h)
+              binCells[c3]->m_y = g_place_coreBounds.y+g_place_coreBounds.h-h;
+          }
+
+          lastOldEdge = curOldEdge;
+          lastNewEdge = curNewEdge;
+          y++;
+          yBinCount = 0;
+          yBinArea = 0;
+          yBinStart = c2+1;
+        }
+      }
+
+      x++;
+      xBinCount = 0;
+      xBinArea = 0;
+      xBinStart = c+1;
+    }
+  }
+
+  free(binCells);
+  free(allCells);
+}
diff --git a/src/phys/place/place_genqp.c b/src/phys/place/place_genqp.c
new file mode 100644
index 00000000..5b6c7027
--- /dev/null
+++ b/src/phys/place/place_genqp.c
@@ -0,0 +1,309 @@
+/*===================================================================*/
+//  
+//     place_genqp.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <math.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+
+#include "place_base.h"
+#include "place_qpsolver.h"
+#include "place_gordian.h"
+
+// --------------------------------------------------------------------
+// Global variables
+//
+// --------------------------------------------------------------------
+
+qps_problem_t *g_place_qpProb = NULL;
+
+
+// --------------------------------------------------------------------
+// splitPenalty()
+//
+/// \brief Returns a weight for all of the edges in the clique for a multipin net.
+//
+// --------------------------------------------------------------------
+float splitPenalty(int pins) {
+
+  if (pins > 1) {
+    return 1.0 + CLIQUE_PENALTY/(pins - 1);
+    // return pow(pins - 1, CLIQUE_PENALTY);
+  }
+  return 1.0 + CLIQUE_PENALTY;
+}
+
+
+// --------------------------------------------------------------------
+// constructQuadraticProblem()
+//
+/// \brief Constructs the matrices necessary to do analytical placement.
+//
+// --------------------------------------------------------------------
+void constructQuadraticProblem() {
+  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);
+}
+
+typedef struct reverseCOG {
+  float      x,y;
+  Partition *part;
+  float      delta;
+} reverseCOG;
+
+
+// --------------------------------------------------------------------
+// generateCoGConstraints()
+//
+/// \brief Generates center of gravity constraints.
+//
+// --------------------------------------------------------------------
+int generateCoGConstraints(reverseCOG COG_rev[]) {
+  int numConstraints = 0; // actual num contraints
+  int cogRevNum = 0;
+  Partition **stack = malloc(sizeof(Partition*)*g_place_numPartitions*2);
+  int stackPtr = 0;
+  Partition *p;
+  float cgx, cgy;
+  int next_index = 0, last_constraint = 0;
+  bool isTrueConstraint = false;
+  int i, m;
+  float totarea;
+  ConcreteCell *cell;
+
+  // each partition may give rise to a center-of-gravity constraint
+  stack[stackPtr] = g_place_rootPartition;
+  while(stackPtr >= 0) {
+    p = stack[stackPtr--];
+    assert(p);
+
+    // traverse down the partition tree to leaf nodes-only
+    if (!p->m_leaf) {
+      stack[++stackPtr] = p->m_sub1;
+      stack[++stackPtr] = p->m_sub2;
+    } else {
+      /*
+      cout << "adding a COG constraint for box "
+       << p->bounds.x << ","
+       << p->bounds.y << " of size"
+       << p->bounds.w << "x"
+       << p->bounds.h
+       << endl;
+      */
+      cgx = p->m_bounds.x + p->m_bounds.w*0.5;
+      cgy = p->m_bounds.y + p->m_bounds.h*0.5;
+      COG_rev[cogRevNum].x = cgx;
+      COG_rev[cogRevNum].y = cgy;
+      COG_rev[cogRevNum].part = p;
+      COG_rev[cogRevNum].delta = 0;
+
+      cogRevNum++;
+    }
+  }
+
+  assert(cogRevNum == g_place_numPartitions);
+  
+  for (i = 0; i < g_place_numPartitions; i++) {
+    p = COG_rev[i].part;
+    assert(p);
+    g_place_qpProb->cog_x[numConstraints] = COG_rev[i].x;
+    g_place_qpProb->cog_y[numConstraints] = COG_rev[i].y;
+    totarea = 0.0;
+    for(m=0; m<p->m_numMembers; m++) if (p->m_members[m]) {
+      cell = p->m_members[m];
+      assert(cell);
+
+      if (!cell->m_fixed && !cell->m_parent->m_pad) {
+    isTrueConstraint = true;
+      }
+      else {
+    continue;
+      }
+      g_place_qpProb->cog_list[next_index++] = cell->m_id;
+      totarea += getCellArea(cell);
+    }
+    if (totarea == 0.0) {
+      isTrueConstraint = false;
+    }
+    if (isTrueConstraint) {
+      numConstraints++;
+      g_place_qpProb->cog_list[next_index++] = -1;
+      last_constraint = next_index;
+    }
+    else {
+      next_index = last_constraint;
+    }
+  }
+
+  free(stack);
+
+  return --numConstraints;
+}
+
+
+// --------------------------------------------------------------------
+// solveQuadraticProblem()
+//
+/// \brief Calls quadratic solver.
+//
+// --------------------------------------------------------------------
+void solveQuadraticProblem(bool useCOG) {
+  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);
+}
diff --git a/src/phys/place/place_gordian.c b/src/phys/place/place_gordian.c
new file mode 100644
index 00000000..2929bf95
--- /dev/null
+++ b/src/phys/place/place_gordian.c
@@ -0,0 +1,160 @@
+/*===================================================================*/
+//  
+//     place_gordian.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <assert.h>
+#include <limits.h>
+
+#include "place_gordian.h"
+#include "place_base.h"
+
+
+// --------------------------------------------------------------------
+// Global variables
+//
+// --------------------------------------------------------------------
+
+int g_place_numPartitions;
+
+
+// --------------------------------------------------------------------
+// globalPlace()
+//
+/// \brief Performs analytic placement using a GORDIAN-like algorithm.
+//
+/// Updates the positions of all non-fixed non-pad cells.
+///
+// --------------------------------------------------------------------
+void globalPlace() {
+  bool completionFlag = false;
+  int iteration = 0;  
+
+  printf("PLAC-10 : Global placement (wirelength-driven Gordian)\n");
+
+  initPartitioning();
+
+  // build matrices representing interconnections
+  printf("QMAN-00 : \tconstructing initial quadratic problem...\n");
+  constructQuadraticProblem();
+
+  // iterate placement until termination condition is met
+  while(!completionFlag) {
+    printf("QMAN-01 : \titeration %d numPartitions = %d\n",iteration,g_place_numPartitions);
+    
+    // do the global optimization in each direction
+    printf("QMAN-01 : \t\tglobal optimization\n");
+    solveQuadraticProblem(!IGNORE_COG);
+      
+    // -------- PARTITIONING BASED CELL SPREADING ------
+
+    // bisection
+    printf("QMAN-01 : \t\tpartition refinement\n");
+    if (REALLOCATE_PARTITIONS) reallocPartitions();
+    completionFlag |= refinePartitions();
+      
+    printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+      
+    iteration++;
+  }
+  
+  // final global optimization
+  printf("QMAN-02 : \t\tfinal pass\n");
+  if (FINAL_REALLOCATE_PARTITIONS) reallocPartitions();
+  solveQuadraticProblem(!IGNORE_COG);
+  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+
+  // clean up
+  sanitizePlacement();
+  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+  globalFixDensity(25, g_place_rowHeight*5);
+  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+}
+
+
+// --------------------------------------------------------------------
+// globalIncremental()
+//
+/// \brief Performs analytic placement using a GORDIAN-like algorithm.
+//
+/// Requires a valid set of partitions.
+///
+// --------------------------------------------------------------------
+
+void   globalIncremental() {
+  if (!g_place_rootPartition) {
+    printf("WARNING: Can not perform incremental placement\n");
+    globalPlace();
+    return;
+  }
+
+  printf("PLAC-10 : Incremental global placement\n");
+
+  incrementalPartition();
+
+  printf("QMAN-00 : \tconstructing initial quadratic problem...\n");
+  constructQuadraticProblem();
+
+  solveQuadraticProblem(!IGNORE_COG);
+  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+  
+  // clean up
+  sanitizePlacement();
+  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+  globalFixDensity(25, g_place_rowHeight*5);
+  printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
+}
+
+
+// --------------------------------------------------------------------
+// sanitizePlacement()
+//
+/// \brief Moves any cells that are outside of the core bounds to the nearest location within.
+//
+// --------------------------------------------------------------------
+void sanitizePlacement() { 
+  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;
+  }
+}
diff --git a/src/phys/place/place_gordian.h b/src/phys/place/place_gordian.h
new file mode 100644
index 00000000..67eb1479
--- /dev/null
+++ b/src/phys/place/place_gordian.h
@@ -0,0 +1,78 @@
+/*===================================================================*/
+//  
+//     place_gordian.h
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#if !defined(PLACE_GORDIAN_H_)
+#define PLACE_GORDIAN_H_
+
+#include "place_base.h"
+#include "place_qpsolver.h"
+
+// Parameters for analytic placement
+#define CLIQUE_PENALTY 1.0
+#define IGNORE_NETSIZE 20
+
+// Parameters for partitioning
+#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
+
+// Parameters for re-partitioning
+#define REPARTITION_LEVEL_DEPTH 4
+#define REPARTITION_TARGET_FRACTION 0.15
+#define REPARTITION_FM false
+#define REPARTITION_HMETIS true
+
+// Parameters for F-M re-partitioning
+#define FM_MAX_BIN 10
+#define FM_MAX_PASSES 10
+
+extern int g_place_numPartitions;
+
+extern qps_problem_t *g_place_qpProb;
+
+typedef struct Partition {
+
+  int               m_numMembers;
+  ConcreteCell    **m_members;
+  Rect              m_bounds;
+  bool              m_done, 
+                    m_leaf, 
+                    m_vertical;
+  float             m_area;
+  int               m_level;
+  struct Partition *m_sub1, *m_sub2;
+} Partition;
+
+extern Partition *g_place_rootPartition;
+
+void initPartitioning();
+
+void incrementalPartition();
+
+bool refinePartitions();
+void reallocPartitions();
+bool refinePartition(Partition *p);
+void resizePartition(Partition *p);
+void reallocPartition(Partition *p);
+
+void repartitionHMetis(Partition *parent);
+void repartitionFM(Partition *parent);
+
+void partitionScanlineMincut(Partition *parent);
+void partitionEqualArea(Partition *parent);
+
+void sanitizePlacement();
+
+void constructQuadraticProblem();
+void solveQuadraticProblem(bool useCOG);
+
+#endif
diff --git a/src/phys/place/place_inc.c b/src/phys/place/place_inc.c
new file mode 100644
index 00000000..7e2d847c
--- /dev/null
+++ b/src/phys/place/place_inc.c
@@ -0,0 +1,106 @@
+/*===================================================================*/
+//  
+//     place_inc.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+#include <string.h>
+
+#include "place_base.h"
+#include "place_gordian.h"
+
+inline int sqHashId(int id, int max) {
+  return ((id * (id+17)) % max);
+}
+
+#if 0
+// --------------------------------------------------------------------
+// fastPlace()
+//
+/// The first cell is assumed to be the "output".
+// --------------------------------------------------------------------
+float fastPlace(int numCells, ConcreteCell *cells[], 
+                int numNets, ConcreteNet *nets[]) {
+  
+  int n, t, c, i, local_id = 0, pass;
+  const int NUM_PASSES = 4;
+  int *cell_numTerms = calloc(numCells, sizeof(int));
+  ConcreteNet **cell_terms;
+  ConcreteNet  *net;
+  Rect outputBox;
+
+  outputBox = getNetBBox(nets[0]);
+
+  // assign local ids
+  // put cells in reasonable initial location
+  for(n=0; n<numNets; n++)
+    for(t=0; nets[n]->m_numTerms; t++)
+      nets[n]->m_terms[t]->m_data = -1;
+
+  for(c=0; c<numCells; c++) {
+    cells[c]->m_data = local_id;
+    cells[c]->m_x = outputBox.x + 0.5*outputBox.w;
+    cells[c]->m_y = outputBox.y + 0.5*outputBox.h;
+  }
+
+  // build reverse map of cells to nets
+  for(n=0; n<numNets; n++)
+    for(t=0; nets[n]->m_numTerms; t++) {
+      local_id = nets[n]->m_terms[t]->m_data;
+      if (local_id >= 0)
+        cell_numTerms[local_id]++;
+    }
+
+  for(c=0; c<numCells; c++) {
+    cell_terms[c] = malloc(sizeof(ConcreteNet*)*cell_numTerms[c]);
+    cell_numTerms[c] = 0;
+  }
+
+  for(n=0; n<numNets; n++)
+    for(t=0; nets[n]->m_numTerms; t++) {
+      local_id = nets[n]->m_terms[t]->m_data;
+      if (local_id >= 0)
+        cell_terms[cell_numTerms[local_id]++] = nets[n];
+    }
+
+  // topological order?
+  
+  // iterative linear 
+  for(pass=0; pass<NUM_PASSES; pass++)
+    for(c=0; c<numCells; c++) {
+      for(n=0; n<cell_numTerms[c]; n++) {
+        net = cell_terms[c];
+        for(t=0; t<net->m_numTerms; t++);
+      }
+    }
+}
+#endif
+
+// --------------------------------------------------------------------
+// fastEstimate()
+//
+// --------------------------------------------------------------------
+float fastEstimate(ConcreteCell *cell, 
+                   int numNets, ConcreteNet *nets[]) {
+  float len = 0;
+  int n;
+  Rect box;
+
+  assert(cell);
+
+  for(n=0; n<numNets; n++) {
+    box = getNetBBox(nets[n]);
+    if (cell->m_x < box.x) len += (box.x - cell->m_x);
+    if (cell->m_x > box.x+box.w) len += (cell->m_x-box.x-box.w);
+    if (cell->m_y < box.y) len += (box.x - cell->m_y);
+    if (cell->m_y > box.y+box.h) len += (cell->m_y-box.y-box.h);
+  }
+  
+  return len;
+}
diff --git a/src/phys/place/place_io.c b/src/phys/place/place_io.c
new file mode 100644
index 00000000..8e24ef4a
--- /dev/null
+++ b/src/phys/place/place_io.c
@@ -0,0 +1,94 @@
+/*===================================================================*/
+//  
+//     place_io.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "place_base.h"
+
+
+// --------------------------------------------------------------------
+// writeBookshelfNodes()
+//
+// --------------------------------------------------------------------
+void writeBookshelfNodes(const char *filename) {
+  
+  int c = 0;
+  int numNodes, numTerms;
+
+  FILE *nodesFile = fopen(filename, "w");
+  if (!nodesFile) {
+    printf("ERROR: Could not open .nodes file\n");
+    exit(1);
+  }
+
+  numNodes = numTerms = 0;
+  for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
+      numNodes++;
+      if (g_place_concreteCells[c]->m_parent->m_pad)
+        numTerms++;
+    }
+
+
+
+  fprintf(nodesFile, "UCLA nodes 1.0\n");
+  fprintf(nodesFile, "NumNodes : %d\n", numNodes);
+  fprintf(nodesFile, "NumTerminals : %d\n", numTerms);
+
+  for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
+    fprintf(nodesFile, "CELL%d %f %f %s\n", 
+            g_place_concreteCells[c]->m_id,
+            g_place_concreteCells[c]->m_parent->m_width,
+            g_place_concreteCells[c]->m_parent->m_height,
+            (g_place_concreteCells[c]->m_parent->m_pad ? " terminal" : ""));
+  }
+
+  fclose(nodesFile);  
+}
+
+
+// --------------------------------------------------------------------
+// writeBookshelfPl()
+//
+// --------------------------------------------------------------------
+void writeBookshelfPl(const char *filename) {
+  
+  int c = 0;
+
+  FILE *plFile = fopen(filename, "w");
+  if (!plFile) {
+    printf("ERROR: Could not open .pl file\n");
+    exit(1);
+  }
+
+  fprintf(plFile, "UCLA pl 1.0\n");
+  for(c=0; c<g_place_numCells; c++)  if (g_place_concreteCells[c]) {
+    fprintf(plFile, "CELL%d %f %f : N %s\n", 
+            g_place_concreteCells[c]->m_id,
+            g_place_concreteCells[c]->m_x,
+            g_place_concreteCells[c]->m_y,
+            (g_place_concreteCells[c]->m_fixed ? "\\FIXED" : ""));
+  }
+
+  fclose(plFile);  
+
+}
+
+
+// --------------------------------------------------------------------
+// writeBookshelf()
+//
+// --------------------------------------------------------------------
+void writeBookshelf(const char *filename) {
+  writeBookshelfNodes("out.nodes");
+  writeBookshelfPl("out.pl");
+}
diff --git a/src/phys/place/place_legalize.c b/src/phys/place/place_legalize.c
new file mode 100644
index 00000000..950902f4
--- /dev/null
+++ b/src/phys/place/place_legalize.c
@@ -0,0 +1,23 @@
+/*===================================================================*/
+//  
+//     place_legalize.c
+//
+//        Aaron P. Hurst, 2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <limits.h>
+#include <assert.h>
+
+#include "place_base.h"
+
+
+// --------------------------------------------------------------------
+// legalize()
+//
+// --------------------------------------------------------------------
+void legalize() {
+  // UNIMPLEMENTED
+}
+
diff --git a/src/phys/place/place_pads.c b/src/phys/place/place_pads.c
new file mode 100644
index 00000000..361fac7f
--- /dev/null
+++ b/src/phys/place/place_pads.c
@@ -0,0 +1,141 @@
+/*===================================================================*/
+//  
+//     place_pads.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <limits.h>
+
+#include "place_base.h"
+
+// --------------------------------------------------------------------
+// globalPreplace()
+//
+/// \brief Place pad ring, leaving a core area to meet a desired utilization.
+//
+/// Sets the position of pads that aren't already fixed.
+///
+/// Computes g_place_coreBounds and g_place_padBounds.  Determines
+/// g_place_rowHeight.
+//
+// --------------------------------------------------------------------
+void globalPreplace(float utilization) {
+  int i, c, h, numRows;
+  float coreArea = 0, totalArea = 0;
+  int padCount = 0;
+  float area;
+  ConcreteCell **padCells = NULL;
+  AbstractCell *padType = NULL;
+  ConcreteCell *cell;
+  float nextPos;
+  int remainingPads, northPads, southPads, eastPads, westPads;
+
+  printf("PLAC-00 : Placing IO pads\n");;
+
+  // identify the pads and compute the total core area
+  g_place_coreBounds.x = g_place_coreBounds.y = 0;
+  g_place_coreBounds.w = g_place_coreBounds.h = -INT_MAX;
+
+  for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
+    cell = g_place_concreteCells[c];
+    area = getCellArea(cell);
+    if (cell->m_parent->m_pad) {
+      padType = cell->m_parent;
+    } else {
+      coreArea += area;
+      g_place_rowHeight = cell->m_parent->m_height;
+    }
+
+    if (cell->m_fixed) {
+      g_place_coreBounds.x = g_place_coreBounds.x < cell->m_x ? g_place_coreBounds.x : cell->m_x;
+      g_place_coreBounds.y = g_place_coreBounds.y < cell->m_y ? g_place_coreBounds.y : cell->m_y;
+      g_place_coreBounds.w = g_place_coreBounds.w > cell->m_x ? g_place_coreBounds.w : cell->m_x;
+      g_place_coreBounds.h = g_place_coreBounds.h > cell->m_y ? g_place_coreBounds.h : cell->m_y;
+    } else if (cell->m_parent->m_pad) {
+      padCells = realloc(padCells, sizeof(ConcreteCell **)*(padCount+1));
+      padCells[padCount++] = cell;
+    }
+    totalArea += area;
+  }
+  if (!padType) {
+    printf("ERROR: No pad cells\n");
+    exit(1);
+  }
+  g_place_padBounds.w -= g_place_padBounds.x;
+  g_place_padBounds.h -= g_place_padBounds.y;
+
+  coreArea /= utilization;
+
+  // create the design boundaries
+  numRows = sqrt(coreArea)/g_place_rowHeight+1;
+  h = numRows * g_place_rowHeight;
+  g_place_coreBounds.h = g_place_coreBounds.h > h ? g_place_coreBounds.h : h;
+  g_place_coreBounds.w = g_place_coreBounds.w > coreArea/g_place_coreBounds.h ? 
+    g_place_coreBounds.w : coreArea/g_place_coreBounds.h;
+  // increase the dimensions by the width of the padring
+  g_place_padBounds = g_place_coreBounds;
+  if (padCount) {
+    printf("PLAC-05 : \tpreplacing %d pad cells\n", padCount);
+    g_place_padBounds.x -= padType->m_width;
+    g_place_padBounds.y -= padType->m_height;
+    g_place_padBounds.w = g_place_coreBounds.w+2*padType->m_width;
+    g_place_padBounds.h = g_place_coreBounds.h+2*padType->m_height;
+  }
+
+  printf("PLAC-05 : \tplaceable rows  : %d\n", numRows);
+  printf("PLAC-05 : \tcore dimensions : %.0fx%.0f\n",
+         g_place_coreBounds.w, g_place_coreBounds.h);
+  printf("PLAC-05 : \tchip dimensions : %.0fx%.0f\n",
+         g_place_padBounds.w, g_place_padBounds.h);
+  
+  remainingPads = padCount;
+  c = 0;
+
+  // north pads
+  northPads = remainingPads/4; remainingPads -= northPads;
+  nextPos = 0;
+  for(i=0; i<northPads; i++) {
+    cell = padCells[c++];
+    cell->m_x = g_place_padBounds.x+cell->m_parent->m_width*0.5 + nextPos;
+    cell->m_y = g_place_padBounds.y+cell->m_parent->m_height*0.5;
+    nextPos += (g_place_padBounds.w-padType->m_width) / northPads;
+  }
+  
+  // south pads
+  southPads = remainingPads/3; remainingPads -= southPads;
+  nextPos = 0;
+  for(i=0; i<southPads; i++) {
+    cell = padCells[c++];
+    cell->m_x = g_place_padBounds.w+g_place_padBounds.x-cell->m_parent->m_width*0.5 - nextPos;
+    cell->m_y = g_place_padBounds.h+g_place_padBounds.y-cell->m_parent->m_height*0.5;
+    nextPos += (g_place_padBounds.w-2*padType->m_width) / southPads;
+  }
+
+  // east pads
+  eastPads = remainingPads/2; remainingPads -= eastPads;
+  nextPos = 0;
+  for(i=0; i<eastPads; i++) {
+    cell = padCells[c++];
+    cell->m_x = g_place_padBounds.w+g_place_padBounds.x-cell->m_parent->m_width*0.5;
+    cell->m_y = g_place_padBounds.y+cell->m_parent->m_height*0.5 + nextPos;
+    nextPos += (g_place_padBounds.h-padType->m_height) / eastPads;
+  }
+
+  // west pads
+  westPads = remainingPads;
+  nextPos = 0;
+  for(i=0; i<westPads; i++) {
+    cell = padCells[c++];
+    cell->m_x = g_place_padBounds.x+cell->m_parent->m_width*0.5;
+    cell->m_y = g_place_padBounds.h+g_place_padBounds.y-cell->m_parent->m_height*0.5 - nextPos;
+    nextPos += (g_place_padBounds.h-padType->m_height) / westPads;
+  }
+
+}
+
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);
+}
diff --git a/src/phys/place/place_qpsolver.c b/src/phys/place/place_qpsolver.c
new file mode 100644
index 00000000..9df9c6dc
--- /dev/null
+++ b/src/phys/place/place_qpsolver.c
@@ -0,0 +1,1270 @@
+/*===================================================================*/
+//  
+//     place_qpsolver.c
+//
+//        Philip Chong
+//              pchong@cadence.com
+//
+/*===================================================================*/
+
+#include <assert.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "place_qpsolver.h"
+
+#undef  QPS_DEBUG
+
+#define QPS_TOL 1.0e-3
+#define QPS_EPS (QPS_TOL * QPS_TOL)
+
+#define QPS_MAX_TOL 0.1
+#define QPS_LOOP_TOL 1.0e-3
+
+#define QPS_RELAX_ITER 180
+#define QPS_MAX_ITER 200
+#define QPS_STEPSIZE_RETRIES 2
+#define QPS_MINSTEP 1.0e-6
+#define QPS_DEC_CHANGE 0.01
+
+#define QPS_PRECON
+#define QPS_PRECON_EPS 1.0e-9
+
+#undef QPS_HOIST
+
+#if defined(QPS_DEBUG)
+#define QPS_DEBUG_FILE "/tmp/qps_debug.log"
+#endif
+
+#if 0
+  /* ii is an array [0..p->num_cells-1] of indices from cells of original
+     problem to modified problem variables.  If ii[k] >= 0, cell is an
+     independent cell; ii[k], ii[k]+1 are the indices of the corresponding
+     variables for the modified problem.  If ii[k] == -1, cell is a fixed
+     cell.  If ii[k] <= -2, cell is a dependent cell; -(ii[k]+2) is the index 
+     of the corresponding COG constraint. */
+int *ii;
+
+  /* gt is an array [0..p->cog_num-1] of indices from COG constraints to
+     locations in the gl array (in qps_problem_t).  gt[k] is the offset into
+     gl where the kth constraint begins. */
+int *gt;
+
+  /* n is the number of variables in the modified problem.  n should be twice
+     the number of independent cells. */
+int n;
+
+qps_float_t *cp;        /* current location during CG iteration */
+qps_float_t f;            /* value of cost function at p */
+
+#endif
+
+/**********************************************************************/
+
+static void
+qps_settp(qps_problem_t * p)
+{
+  /* Fill in the p->priv_tp array with the current locations of all cells
+     (independent, dependent and fixed). */
+
+  int i;
+  int t, u;
+  int pr;
+  qps_float_t rx, ry;
+  qps_float_t ta;
+
+  int *ii = p->priv_ii;
+  qps_float_t *tp = p->priv_tp;
+  qps_float_t *cp = p->priv_cp;
+
+  /* do independent and fixed cells first */
+  for (i = p->num_cells; i--;) {
+    t = ii[i];
+    if (t >= 0) {        /* indep cell */
+      tp[i * 2] = cp[t];
+      tp[i * 2 + 1] = cp[t + 1];
+    }
+    else if (t == -1) {        /* fixed cell */
+      tp[i * 2] = p->x[i];
+      tp[i * 2 + 1] = p->y[i];
+    }
+  }
+  /* now do dependent cells */
+  for (i = p->num_cells; i--;) {
+    if (ii[i] < -1) {
+      t = -(ii[i] + 2);        /* index of COG constraint */
+      ta = 0.0;
+      rx = 0.0;
+      ry = 0.0;
+      pr = p->priv_gt[t];
+      while ((u = p->cog_list[pr++]) >= 0) {
+    ta += p->area[u];
+    if (u != i) {
+      rx -= p->area[u] * tp[u * 2];
+      ry -= p->area[u] * tp[u * 2 + 1];
+    }
+      }
+      rx += p->cog_x[t] * ta;
+      ry += p->cog_y[t] * ta;
+      tp[i * 2] = rx / p->area[i];
+      tp[i * 2 + 1] = ry / p->area[i];
+    }
+  }
+
+#if (QPS_DEBUG > 5)
+  fprintf(p->priv_fp, "### qps_settp()\n");
+  for (i = 0; i < p->num_cells; i++) {
+    fprintf(p->priv_fp, "%f %f\n", tp[i * 2], tp[i * 2 + 1]);
+  }
+#endif
+}
+
+/**********************************************************************/
+
+static qps_float_t
+qps_func(qps_problem_t * p)
+{
+  /* Return f(p).  qps_settp() should have already been called before
+     entering here */
+
+  int j, k;
+  int pr;
+  qps_float_t jx, jy, tx, ty;
+  qps_float_t f;
+  qps_float_t w;
+
+#if !defined(QPS_HOIST)
+  int i;
+  int st;
+  qps_float_t kx, ky, sx, sy;
+  qps_float_t t;
+#endif
+
+  qps_float_t *tp = p->priv_tp;
+
+  f = 0.0;
+  pr = 0;
+  for (j = 0; j < p->num_cells; j++) {
+    jx = tp[j * 2];
+    jy = tp[j * 2 + 1];
+    while ((k = p->priv_cc[pr]) >= 0) {
+      w = p->priv_cw[pr];
+      tx = tp[k * 2] - jx;
+      ty = tp[k * 2 + 1] - jy;
+      f += w * (tx * tx + ty * ty);
+      pr++;
+    }
+    pr++;
+  }
+  p->f = f;
+
+#if !defined(QPS_HOIST)
+  /* loop penalties */
+  pr = 0;
+  for (i = 0; i < p->loop_num; i++) {
+    t = 0.0;
+    j = st = p->loop_list[pr++];
+    jx = sx = tp[j * 2];
+    jy = sy = tp[j * 2 + 1];
+    while ((k = p->loop_list[pr]) >= 0) {
+      kx = tp[k * 2];
+      ky = tp[k * 2 + 1];
+      tx = jx - kx;
+      ty = jy - ky;
+      t += tx * tx + ty * ty;
+      j = k;
+      jx = kx;
+      jy = ky;
+      pr++;
+    }
+    tx = jx - sx;
+    ty = jy - sy;
+    t += tx * tx + ty * ty;
+    t -= p->loop_max[i];
+#if (QPS_DEBUG > 5)
+    fprintf(p->priv_fp, "### qps_penalty() %d %f %f\n",
+        i, p->loop_max[i], t);
+#endif
+    p->priv_lt[i] = t;
+    f += p->loop_penalty[i] * t;
+    pr++;
+  }
+#endif /* QPS_HOIST */
+
+  if (p->max_enable) {
+    for (j = p->num_cells; j--;) {
+      f += p->priv_mxl[j] * (-tp[j * 2]);
+      f += p->priv_mxh[j] * (tp[j * 2] - p->max_x);
+      f += p->priv_myl[j] * (-tp[j * 2 + 1]);
+      f += p->priv_myh[j] * (tp[j * 2 + 1] - p->max_y);
+    }
+  }
+
+#if (QPS_DEBUG > 5)
+  fprintf(p->priv_fp, "### qps_func() %f %f\n", f, p->f);
+#endif
+  return f;
+}
+
+/**********************************************************************/
+
+static void
+qps_dfunc(qps_problem_t * p, qps_float_t * d)
+{
+  /* Set d to grad f(p).  First computes partial derivatives wrt all cells
+     then finds gradient wrt only the independent cells.  qps_settp() should
+     have already been called before entering here */
+
+  int i, j, k;
+  int pr = 0;
+  qps_float_t jx, jy, kx, ky, tx, ty;
+  int ji, ki;
+  qps_float_t w;
+
+#if !defined(QPS_HOIST)
+  qps_float_t sx, sy;
+  int st;
+#endif
+
+  qps_float_t *tp = p->priv_tp;
+  qps_float_t *tp2 = p->priv_tp2;
+
+  /* compute partials and store in tp2 */
+  for (i = p->num_cells; i--;) {
+    tp2[i * 2] = 0.0;
+    tp2[i * 2 + 1] = 0.0;
+  }
+  for (j = 0; j < p->num_cells; j++) {
+    jx = tp[j * 2];
+    jy = tp[j * 2 + 1];
+    while ((k = p->priv_cc[pr]) >= 0) {
+      w = 2.0 * p->priv_cw[pr];
+      kx = tp[k * 2];
+      ky = tp[k * 2 + 1];
+      tx = w * (jx - kx);
+      ty = w * (jy - ky);
+      tp2[j * 2] += tx;
+      tp2[k * 2] -= tx;
+      tp2[j * 2 + 1] += ty;
+      tp2[k * 2 + 1] -= ty;
+      pr++;
+    }
+    pr++;
+  }
+
+#if !defined(QPS_HOIST)
+  /* loop penalties */
+  pr = 0;
+  for (i = 0; i < p->loop_num; i++) {
+    j = st = p->loop_list[pr++];
+    jx = sx = tp[j * 2];
+    jy = sy = tp[j * 2 + 1];
+    w = 2.0 * p->loop_penalty[i];
+    while ((k = p->loop_list[pr]) >= 0) {
+      kx = tp[k * 2];
+      ky = tp[k * 2 + 1];
+      tx = w * (jx - kx);
+      ty = w * (jy - ky);
+      tp2[j * 2] += tx;
+      tp2[k * 2] -= tx;
+      tp2[j * 2 + 1] += ty;
+      tp2[k * 2 + 1] -= ty;
+      j = k;
+      jx = kx;
+      jy = ky;
+      pr++;
+    }
+    tx = w * (jx - sx);
+    ty = w * (jy - sy);
+    tp2[j * 2] += tx;
+    tp2[st * 2] -= tx;
+    tp2[j * 2 + 1] += ty;
+    tp2[st * 2 + 1] -= ty;
+    pr++;
+  }
+#endif /* QPS_HOIST */
+
+  if (p->max_enable) {
+    for (j = p->num_cells; j--;) {
+      tp2[j * 2] += p->priv_mxh[j] - p->priv_mxl[j];
+      tp2[j * 2 + 1] += p->priv_myh[j] - p->priv_myl[j];
+    }
+  }
+
+#if (QPS_DEBUG > 5)
+  fprintf(p->priv_fp, "### qps_dfunc() partials\n");
+  for (j = 0; j < p->num_cells; j++) {
+    fprintf(p->priv_fp, "%f %f\n", tp2[j * 2], tp2[j * 2 + 1]);
+  }
+#endif
+
+  /* translate partials to independent variables */
+  for (j = p->priv_n; j--;) {
+    d[j] = 0.0;
+  }
+  for (j = p->num_cells; j--;) {
+    ji = p->priv_ii[j];
+    if (ji >= 0) {        /* indep var */
+      d[ji] += tp2[j * 2];
+      d[ji + 1] += tp2[j * 2 + 1];
+    }
+    else if (ji < -1) {        /* dependent variable */
+      ji = -(ji + 2);        /* get COG index */
+      pr = p->priv_gt[ji];
+      while ((k = p->cog_list[pr]) >= 0) {
+    ki = p->priv_ii[k];
+    if (ki >= 0) {
+      w = p->priv_gw[pr];
+#if (QPS_DEBUG > 0)
+      assert(fabs(w - p->area[k] / p->area[j]) < 1.0e-6);
+#endif
+      d[ki] -= tp2[j * 2] * w;
+      d[ki + 1] -= tp2[j * 2 + 1] * w;
+    }
+    pr++;
+      }
+    }
+  }
+
+#if (QPS_DEBUG > 5)
+  fprintf(p->priv_fp, "### qps_dfunc() gradient\n");
+  for (j = 0; j < p->priv_n; j++) {
+    fprintf(p->priv_fp, "%f\n", d[j]);
+  }
+#endif
+}
+
+/**********************************************************************/
+
+static void
+qps_linmin(qps_problem_t * p, qps_float_t dgg, qps_float_t * h)
+{
+  /* Perform line minimization.  p->priv_cp is the current location, h is
+     direction of the gradient.  Updates p->priv_cp to line minimal position
+     based on formulas from "Handbook of Applied Optimization", Pardalos and
+     Resende, eds., Oxford Univ. Press, 2002.  qps_settp() should have
+     already been called before entering here.  Since p->priv_cp is changed,
+     p->priv_tp array becomes invalid following this routine. */
+
+  int i, j, k;
+  int pr;
+  int ji, ki;
+  qps_float_t jx, jy, kx, ky;
+  qps_float_t f = 0.0;
+  qps_float_t w;
+
+#if !defined(QPS_HOIST)
+  int st;
+  qps_float_t sx, sy, tx, ty;
+  qps_float_t t;
+#endif
+
+  qps_float_t *tp = p->priv_tp;
+
+  /* translate h vector to partials over all variables and store in tp */
+  for (i = p->num_cells; i--;) {
+    tp[i * 2] = 0.0;
+    tp[i * 2 + 1] = 0.0;
+  }
+  for (j = p->num_cells; j--;) {
+    ji = p->priv_ii[j];
+    if (ji >= 0) {        /* indep cell */
+      tp[j * 2] = h[ji];
+      tp[j * 2 + 1] = h[ji + 1];
+    }
+    else if (ji < -1) {        /* dep cell */
+      ji = -(ji + 2);        /* get COG index */
+      pr = p->priv_gt[ji];
+      while ((k = p->cog_list[pr]) >= 0) {
+    ki = p->priv_ii[k];
+    if (ki >= 0) {
+      w = p->priv_gw[pr];
+#if (QPS_DEBUG > 0)
+      assert(fabs(w - p->area[k] / p->area[j]) < 1.0e-6);
+#endif
+      tp[j * 2] -= h[ki] * w;
+      tp[j * 2 + 1] -= h[ki + 1] * w;
+    }
+    pr++;
+      }
+    }
+  }
+
+  /* take product x^T Z^T C Z x */
+  pr = 0;
+  for (j = 0; j < p->num_cells; j++) {
+    jx = tp[j * 2];
+    jy = tp[j * 2 + 1];
+    while ((k = p->priv_cc[pr]) >= 0) {
+      w = p->priv_cw[pr];
+      kx = tp[k * 2] - jx;
+      ky = tp[k * 2 + 1] - jy;
+      f += w * (kx * kx + ky * ky);
+      pr++;
+    }
+    pr++;
+  }
+
+#if !defined(QPS_HOIST)
+  /* add loop penalties */
+  pr = 0;
+  for (i = 0; i < p->loop_num; i++) {
+    t = 0.0;
+    j = st = p->loop_list[pr++];
+    jx = sx = tp[j * 2];
+    jy = sy = tp[j * 2 + 1];
+    while ((k = p->loop_list[pr]) >= 0) {
+      kx = tp[k * 2];
+      ky = tp[k * 2 + 1];
+      tx = jx - kx;
+      ty = jy - ky;
+      t += tx * tx + ty * ty;
+      j = k;
+      jx = kx;
+      jy = ky;
+      pr++;
+    }
+    tx = jx - sx;
+    ty = jy - sy;
+    t += tx * tx + ty * ty;
+    f += p->loop_penalty[i] * t;
+    pr++;
+  }
+#endif /* QPS_HOIST */
+
+#if (QPS_DEBUG > 0)
+  assert(f);
+#endif
+
+  /* compute step size */
+  f = (dgg / f) / 2.0;
+  for (j = p->priv_n; j--;) {
+    p->priv_cp[j] += f * h[j];
+  }
+#if (QPS_DEBUG > 5)
+  fprintf(p->priv_fp, "### qps_linmin() step %f\n", f);
+  for (j = 0; j < p->priv_n; j++) {
+    fprintf(p->priv_fp, "%f\n", p->priv_cp[j]);
+  }
+#endif
+}
+
+/**********************************************************************/
+
+static void
+qps_cgmin(qps_problem_t * p)
+{
+  /* Perform CG minimization. Mostly from "Numerical Recipes", Press et al.,
+     Cambridge Univ. Press, 1992, with some changes to help performance in
+     our restricted problem domain. */
+
+  qps_float_t fp, gg, dgg, gam;
+  qps_float_t t;
+  int i, j;
+
+  int n = p->priv_n;
+  qps_float_t *g = p->priv_g;
+  qps_float_t *h = p->priv_h;
+  qps_float_t *xi = p->priv_xi;
+
+  qps_settp(p);
+  fp = qps_func(p);
+  qps_dfunc(p, g);
+
+  dgg = 0.0;
+  for (j = n; j--;) {
+    g[j] = -g[j];
+    h[j] = g[j];
+#if defined(QPS_PRECON)
+    h[j] *= p->priv_pcgt[j];
+#endif
+    dgg += g[j] * h[j];
+  }
+
+  for (i = 0; i < 2 * n; i++) {
+
+#if (QPS_DEBUG > 5)
+    fprintf(p->priv_fp, "### qps_cgmin() top\n");
+    for (j = 0; j < p->priv_n; j++) {
+      fprintf(p->priv_fp, "%f\n", p->priv_cp[j]);
+    }
+#endif
+
+    if (dgg == 0.0) {
+      break;
+    }
+    qps_linmin(p, dgg, h);
+    qps_settp(p);
+    p->priv_f = qps_func(p);
+    if (fabs((p->priv_f) - fp) <=
+    (fabs(p->priv_f) + fabs(fp) + QPS_EPS) * QPS_TOL / 2.0) {
+      break;
+    }
+    fp = p->priv_f;
+    qps_dfunc(p, xi);
+    gg = dgg;
+    dgg = 0.0;
+    for (j = n; j--;) {
+      t = xi[j] * xi[j];
+#if defined(QPS_PRECON)
+      t *= p->priv_pcgt[j];
+#endif
+      dgg += t;
+    }
+    gam = dgg / gg;
+    for (j = n; j--;) {
+      g[j] = -xi[j];
+      t = g[j];
+#if defined(QPS_PRECON)
+      t *= p->priv_pcgt[j];
+#endif
+      h[j] = t + gam * h[j];
+    }
+  }
+#if (QPS_DEBUG > 0)
+  fprintf(p->priv_fp, "### CG ITERS=%d %d %d\n", i, p->cog_num, p->loop_num);
+#endif
+  if (i == 2 * n) {
+    fprintf(stderr, "### Too many iterations in qps_cgmin()\n");
+#if defined(QPS_DEBUG)
+    fprintf(p->priv_fp, "### Too many iterations in qps_cgmin()\n");
+#endif
+  }
+}
+
+/**********************************************************************/
+
+void
+qps_init(qps_problem_t * p)
+{
+  int i, j;
+  int pr, pw;
+
+#if defined(QPS_DEBUG)
+  p->priv_fp = fopen(QPS_DEBUG_FILE, "a");
+  assert(p->priv_fp);
+#endif
+
+#if (QPS_DEBUG > 5)
+  fprintf(p->priv_fp, "### n=%d gn=%d ln=%d\n", p->num_cells, p->cog_num,
+      p->loop_num);
+  pr = 0;
+  fprintf(p->priv_fp, "### (c w) values\n");
+  for (i = 0; i < p->num_cells; i++) {
+    fprintf(p->priv_fp, "net %d: ", i);
+    while (p->connect[pr] >= 0) {
+      fprintf(p->priv_fp, "(%d %f) ", p->connect[pr], p->edge_weight[pr]);
+      pr++;
+    }
+    fprintf(p->priv_fp, "(-1 -1.0)\n");
+    pr++;
+  }
+  fprintf(p->priv_fp, "### (x y f) values\n");
+  for (i = 0; i < p->num_cells; i++) {
+    fprintf(p->priv_fp, "cell %d: (%f %f %d)\n", i, p->x[i], p->y[i],
+        p->fixed[i]);
+  }
+#if 0
+  if (p->cog_num) {
+    fprintf(p->priv_fp, "### ga values\n");
+    for (i = 0; i < p->num_cells; i++) {
+      fprintf(p->priv_fp, "cell %d: (%f)\n", i, p->area[i]);
+    }
+  }
+  pr = 0;
+  fprintf(p->priv_fp, "### gl values\n");
+  for (i = 0; i < p->cog_num; i++) {
+    fprintf(p->priv_fp, "cog %d: ", i);
+    while (p->cog_list[pr] >= 0) {
+      fprintf(p->priv_fp, "%d ", p->cog_list[pr]);
+      pr++;
+    }
+    fprintf(p->priv_fp, "-1\n");
+    pr++;
+  }
+  fprintf(p->priv_fp, "### (gx gy) values\n");
+  for (i = 0; i < p->cog_num; i++) {
+    fprintf(p->priv_fp, "cog %d: (%f %f)\n", i, p->cog_x[i], p->cog_y[i]);
+  }
+#endif
+#endif /* QPS_DEBUG */
+
+  p->priv_ii = (int *)malloc(p->num_cells * sizeof(int));
+  assert(p->priv_ii);
+
+  p->max_enable = 0;
+
+  p->priv_fopt = 0.0;
+
+  /* canonify c and w */
+  pr = pw = 0;
+  for (i = 0; i < p->num_cells; i++) {
+    while ((j = p->connect[pr]) >= 0) {
+      if (j > i) {
+    pw++;
+      }
+      pr++;
+    }
+    pw++;
+    pr++;
+  }
+  p->priv_cc = (int *)malloc(pw * sizeof(int));
+  assert(p->priv_cc);
+  p->priv_cr = (int *)malloc(p->num_cells * sizeof(int));
+  assert(p->priv_cr);
+  p->priv_cw = (qps_float_t*)malloc(pw * sizeof(qps_float_t));
+  assert(p->priv_cw);
+  p->priv_ct = (qps_float_t*)malloc(pw * sizeof(qps_float_t));
+  assert(p->priv_ct);
+  p->priv_cm = pw;
+  pr = pw = 0;
+  for (i = 0; i < p->num_cells; i++) {
+    p->priv_cr[i] = pw;
+    while ((j = p->connect[pr]) >= 0) {
+      if (j > i) {
+    p->priv_cc[pw] = p->connect[pr];
+    p->priv_ct[pw] = p->edge_weight[pr];
+    pw++;
+      }
+      pr++;
+    }
+    p->priv_cc[pw] = -1;
+    p->priv_ct[pw] = -1.0;
+    pw++;
+    pr++;
+  }
+  assert(pw == p->priv_cm);
+
+  /* temp arrays for function eval */
+  p->priv_tp = (qps_float_t *) malloc(4 * p->num_cells * sizeof(qps_float_t));
+  assert(p->priv_tp);
+  p->priv_tp2 = p->priv_tp + 2 * p->num_cells;
+}
+
+/**********************************************************************/
+
+static qps_float_t
+qps_estopt(qps_problem_t * p)
+{
+  int i, j, cell;
+  qps_float_t r;
+  qps_float_t *t1, *t2;
+  qps_float_t t;
+
+  if (p->max_enable) {
+    r = 0.0;
+    t1 = (qps_float_t *) malloc(2 * p->num_cells * sizeof(qps_float_t));
+#if (QPS_DEBUG > 0)
+    assert(t1);
+#endif
+    for (i = 2 * p->num_cells; i--;) {
+      t1[i] = 0.0;
+    }
+    j = 0;
+    for (i = 0; i < p->cog_num; i++) {
+      while ((cell = p->cog_list[j]) >= 0) {
+    t1[cell * 2] = p->cog_x[i];
+    t1[cell * 2 + 1] = p->cog_y[i];
+    j++;
+      }
+      j++;
+    }
+    t2 = p->priv_tp;
+    p->priv_tp = t1;
+    r = qps_func(p);
+    p->priv_tp = t2;
+    free(t1);
+    t = (p->max_x * p->max_x + p->max_y * p->max_y);
+    t *= p->num_cells;
+    for (i = p->num_cells; i--;) {
+      if (p->fixed[i]) {
+    r += t;
+      }
+    }
+  }
+  else {
+    r = p->priv_f;
+  }
+  if (p->loop_num) {
+    /* FIXME hacky */
+    r *= 8.0;
+  }
+  return r;
+}
+
+/**********************************************************************/
+
+static void
+qps_solve_inner(qps_problem_t * p)
+{
+  int i;
+  qps_float_t t;
+  qps_float_t z;
+  qps_float_t pm1, pm2, tp;
+  qps_float_t *tw;
+#if defined(QPS_HOIST)
+  int j, k;
+  qps_float_t jx, jy, kx, ky, sx, sy, tx, ty;
+  int pr, st;
+#endif
+
+  tw = p->priv_cw;
+#if defined(QPS_HOIST)
+  if (!p->loop_num) {
+    p->priv_cw = p->priv_ct;
+  }
+  else {
+    for(i=p->priv_cm; i--;) {
+      p->priv_cw[i] = p->priv_ct[i];
+    }
+    /* augment with loop penalties */
+    pr = 0;
+    for (i = 0; i < p->loop_num; i++) {
+      while ((j = p->priv_la[pr++]) != -1) {
+    if (j >= 0) {
+      p->priv_cw[j] += p->loop_penalty[i];
+    }
+      }
+      pr++;
+    }
+  }
+#else /* !QPS_HOIST */
+  p->priv_cw = p->priv_ct;
+#endif /* QPS_HOIST */
+
+  qps_cgmin(p);
+
+  if (p->max_enable || p->loop_num) {
+    if (p->max_enable == 1 || (p->loop_num && p->loop_k == 0)) {
+      p->priv_eps = 2.0;
+      p->priv_fmax = p->priv_f;
+      p->priv_fprev = p->priv_f;
+      p->priv_fopt = qps_estopt(p);
+      p->priv_pn = 0;
+      p->loop_fail = 0;
+    }
+    else {
+      if (p->priv_f < p->priv_fprev &&
+      (p->priv_fprev - p->priv_f) >
+      QPS_DEC_CHANGE * fabs(p->priv_fprev)) {
+    if (p->priv_pn++ >= QPS_STEPSIZE_RETRIES) {
+      p->priv_eps /= 2.0;
+      p->priv_pn = 0;
+    }
+      }
+      p->priv_fprev = p->priv_f;
+      if (p->priv_fmax < p->priv_f) {
+    p->priv_fmax = p->priv_f;
+      }
+      if (p->priv_f >= p->priv_fopt) {
+    p->priv_fopt = p->priv_fmax * 2.0;
+    p->loop_fail |= 2;
+#if (QPS_DEBUG > 0)
+    fprintf(p->priv_fp, "### warning: changing fopt\n");
+#endif
+      }
+    }
+#if (QPS_DEBUG > 0)
+    fprintf(p->priv_fp, "### max_stat %.2e %.2e %.2e %.2e\n",
+        p->priv_f, p->priv_eps, p->priv_fmax, p->priv_fopt);
+    fflush(p->priv_fp);
+#endif
+  }
+
+  p->loop_done = 1;
+  if (p->loop_num) {
+#if (QPS_DEBUG > 0)
+    fprintf(p->priv_fp, "### begin_update %d\n", p->loop_k);
+#endif
+    p->loop_k++;
+
+#if defined(QPS_HOIST)
+    /* calc loop penalties */
+    pr = 0;
+    for (i = 0; i < p->loop_num; i++) {
+      t = 0.0;
+      j = st = p->loop_list[pr++];
+      jx = sx = p->priv_tp[j * 2];
+      jy = sy = p->priv_tp[j * 2 + 1];
+      while ((k = p->loop_list[pr]) >= 0) {
+    kx = p->priv_tp[k * 2];
+    ky = p->priv_tp[k * 2 + 1];
+    tx = jx - kx;
+    ty = jy - ky;
+    t += tx * tx + ty * ty;
+    j = k;
+    jx = kx;
+    jy = ky;
+    pr++;
+      }
+      tx = jx - sx;
+      ty = jy - sy;
+      t += tx * tx + ty * ty;
+      p->priv_lt[i] = t - p->loop_max[i];
+      pr++;
+    }
+#endif /* QPS_HOIST */
+
+    /* check KKT conditions */
+#if (QPS_DEBUG > 1)
+    for (i = p->loop_num; i--;) {
+      if (p->loop_penalty[i] != 0.0) {
+    fprintf(p->priv_fp, "### penalty %d %.2e\n", i, p->loop_penalty[i]);
+      }
+    }
+#endif
+    t = 0.0;
+    for (i = p->loop_num; i--;) {
+      if (p->priv_lt[i] > 0.0 || p->loop_penalty[i] > 0.0) {
+    t += p->priv_lt[i] * p->priv_lt[i];
+      }
+      if (fabs(p->priv_lt[i]) < QPS_LOOP_TOL) {
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### skip %d %f\n", i, p->priv_lt[i]);
+#endif
+    continue;
+      }
+      z = QPS_LOOP_TOL * p->loop_max[i];
+      if (p->priv_lt[i] > z || (p->loop_k < QPS_RELAX_ITER &&
+                p->loop_penalty[i] * p->priv_lt[i] < -z)) {
+    p->loop_done = 0;
+#if (QPS_DEBUG > 1)
+    fprintf(p->priv_fp, "### not_done %d %f %f %f %f\n", i,
+        p->priv_lt[i], z, p->loop_max[i], p->loop_penalty[i]);
+#endif
+      }
+#if (QPS_DEBUG > 5)
+      else {
+    fprintf(p->priv_fp, "### done %d %f %f %f %f\n", i,
+        p->priv_lt[i], z, p->loop_max[i], p->loop_penalty[i]);
+      }
+#endif
+    }
+    /* update penalties */
+    if (!p->loop_done) {
+      t = p->priv_eps * (p->priv_fopt - p->priv_f) / t;
+      tp = 0.0;
+      for (i = p->loop_num; i--;) {
+    pm1 = p->loop_penalty[i];
+#if (QPS_DEBUG > 5)
+    fprintf(p->priv_fp, "### update %d %.2e %.2e %.2e %.2e %.2e\n", i,
+        t, p->priv_lt[i], t * p->priv_lt[i], pm1, p->loop_max[i]);
+#endif
+    p->loop_penalty[i] += t * p->priv_lt[i];
+    if (p->loop_penalty[i] < 0.0) {
+      p->loop_penalty[i] = 0.0;
+    }
+    pm2 = p->loop_penalty[i];
+    tp += fabs(pm1 - pm2);
+      }
+#if (QPS_DEBUG > 4)
+      fprintf(p->priv_fp, "### penalty mag %f\n", tp);
+#endif
+    }
+  }
+
+  p->max_done = 1;
+  if (p->max_enable) {
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### begin_max_update %d\n", p->max_enable);
+#endif
+    t = 0.0;
+    for (i = p->num_cells; i--;) {
+      z = -(p->x[i]);
+      t += z * z;
+      if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER &&
+              p->priv_mxl[i] * z < -QPS_MAX_TOL)) {
+    p->max_done = 0;
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### nxl %d %f %f\n", i, z, p->priv_mxl[i]);
+#endif
+      }
+      z = (p->x[i] - p->max_x);
+      t += z * z;
+      if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER &&
+              p->priv_mxh[i] * z < -QPS_MAX_TOL)) {
+    p->max_done = 0;
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### nxh %d %f %f\n", i, z, p->priv_mxh[i]);
+#endif
+      }
+      z = -(p->y[i]);
+      t += z * z;
+      if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER &&
+              p->priv_myl[i] * z < -QPS_MAX_TOL)) {
+    p->max_done = 0;
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### nyl %d %f %f\n", i, z, p->priv_myl[i]);
+#endif
+      }
+      z = (p->y[i] - p->max_y);
+      t += z * z;
+      if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER &&
+              p->priv_myh[i] * z < -QPS_MAX_TOL)) {
+    p->max_done = 0;
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### nyh %d %f %f\n", i, z, p->priv_myh[i]);
+#endif
+      }
+    }
+#if (QPS_DEBUG > 4)
+    fprintf(p->priv_fp, "### max_done %d %f\n", p->max_done, t);
+#endif
+    if (!p->max_done) {
+      t = p->priv_eps * (p->priv_fopt - p->priv_f) / t;
+      tp = 0.0;
+      for (i = p->num_cells; i--;) {
+    z = -(p->x[i]);
+    pm1 = p->priv_mxl[i];
+    p->priv_mxl[i] += t * z;
+    if (p->priv_mxl[i] < 0.0) {
+      p->priv_mxl[i] = 0.0;
+    }
+    pm2 = p->priv_mxl[i];
+    tp += fabs(pm1 - pm2);
+
+    z = (p->x[i] - p->max_x);
+    pm1 = p->priv_mxh[i];
+    p->priv_mxh[i] += t * z;
+    if (p->priv_mxh[i] < 0.0) {
+      p->priv_mxh[i] = 0.0;
+    }
+    pm2 = p->priv_mxh[i];
+    tp += fabs(pm1 - pm2);
+
+    z = -(p->y[i]);
+    pm1 = p->priv_myl[i];
+    p->priv_myl[i] += t * z;
+    if (p->priv_myl[i] < 0.0) {
+      p->priv_myl[i] = 0.0;
+    }
+    pm2 = p->priv_myl[i];
+    tp += fabs(pm1 - pm2);
+
+    z = (p->y[i] - p->max_y);
+    pm1 = p->priv_myh[i];
+    p->priv_myh[i] += t * z;
+    if (p->priv_myh[i] < 0.0) {
+      p->priv_myh[i] = 0.0;
+    }
+    pm2 = p->priv_myh[i];
+    tp += fabs(pm1 - pm2);
+      }
+    }
+#if (QPS_DEBUG > 4)
+    for (i = p->num_cells; i--;) {
+      fprintf(p->priv_fp, "### max_penalty %d %f %f %f %f\n", i,
+          p->priv_mxl[i], p->priv_mxh[i], p->priv_myl[i], p->priv_myh[i]);
+    }
+#endif
+    p->max_enable++;
+  }
+
+  if (p->loop_k >= QPS_MAX_ITER || p->priv_eps < QPS_MINSTEP) {
+    p->loop_fail |= 1;
+  }
+
+  if (p->loop_fail) {
+    p->loop_done = 1;
+  }
+
+  p->priv_cw = tw;
+}
+
+/**********************************************************************/
+
+void
+qps_solve(qps_problem_t * p)
+{
+  int i, j;
+  int pr, pw;
+  qps_float_t bk;
+  int tk;
+
+#if defined(QPS_PRECON)
+  int c;
+  qps_float_t t;
+#endif
+
+#if defined(QPS_HOIST)
+  int k;
+  int st;
+  int m1, m2;
+#endif
+
+  if (p->max_enable) {
+    p->priv_mxl = (qps_float_t *)
+    malloc(4 * p->num_cells * sizeof(qps_float_t));
+    assert(p->priv_mxl);
+    p->priv_mxh = p->priv_mxl + p->num_cells;
+    p->priv_myl = p->priv_mxl + 2 * p->num_cells;
+    p->priv_myh = p->priv_mxl + 3 * p->num_cells;
+    for (i = 4 * p->num_cells; i--;) {
+      p->priv_mxl[i] = 0.0;
+    }
+  }
+
+  /* flag fixed cells with -1 */
+  for (i = p->num_cells; i--;) {
+    p->priv_ii[i] = (p->fixed[i]) ? (-1) : (0);
+  }
+
+  /* read gl and set up dependent variables */
+  if (p->cog_num) {
+    p->priv_gt = (int *)malloc(p->cog_num * sizeof(int));
+    assert(p->priv_gt);
+    p->priv_gm = (qps_float_t*)malloc(p->cog_num * sizeof(qps_float_t));
+    assert(p->priv_gm);
+    pr = 0;
+    for (i = 0; i < p->cog_num; i++) {
+      tk = -1;
+      bk = -1.0;
+      pw = pr;
+      while ((j = p->cog_list[pr++]) >= 0) {
+    if (!p->fixed[j]) {
+      /* use largest entry for numerical stability; see Gordian paper */
+      if (p->area[j] > bk) {
+        tk = j;
+        bk = p->area[j];
+      }
+    }
+      }
+      assert(bk > 0.0);
+      /* dependent variables have index=(-2-COG_constraint) */
+      p->priv_ii[tk] = -2 - i;
+      p->priv_gt[i] = pw;
+      p->priv_gm[i] = bk;
+    }
+    p->priv_gw = (qps_float_t*)malloc(pr * sizeof(qps_float_t));
+    assert(p->priv_gw);
+    pr = 0;
+    for (i = 0; i < p->cog_num; i++) {
+      while ((j = p->cog_list[pr]) >= 0) {
+    p->priv_gw[pr] = p->area[j] / p->priv_gm[i];
+    pr++;
+      }
+      p->priv_gw[pr] = -1.0;
+      pr++;
+    }
+  }
+
+  /* set up indexes from independent floating cells to variables */
+  p->priv_n = 0;
+  for (i = p->num_cells; i--;) {
+    if (!p->priv_ii[i]) {
+      p->priv_ii[i] = 2 * (p->priv_n++);
+    }
+  }
+  p->priv_n *= 2;
+
+#if (QPS_DEBUG > 5)
+  for (i = 0; i < p->num_cells; i++) {
+    fprintf(p->priv_fp, "### ii %d %d\n", i, p->priv_ii[i]);
+  }
+#endif
+
+#if defined(QPS_PRECON)
+  p->priv_pcg = (qps_float_t *) malloc(p->num_cells * sizeof(qps_float_t));
+  assert(p->priv_pcg);
+  p->priv_pcgt = (qps_float_t *) malloc(p->priv_n * sizeof(qps_float_t));
+  assert(p->priv_pcgt);
+  for (i = p->num_cells; i--;) {
+    p->priv_pcg[i] = 0.0;
+  }
+  pr = 0;
+  for (i = 0; i < p->num_cells; i++) {
+    while ((c = p->priv_cc[pr]) >= 0) {
+      t = p->priv_ct[pr];
+      p->priv_pcg[i] += t;
+      p->priv_pcg[c] += t;
+      pr++;
+    }
+    pr++;
+  }
+  pr = 0;
+  for (i = 0; i < p->loop_num; i++) {
+    t = 2.0 * p->loop_penalty[i];
+    while ((c = p->loop_list[pr++]) >= 0) {
+      p->priv_pcg[c] += t;
+    }
+    pr++;
+  }
+#if (QPS_DEBUG > 6)
+  for (i = p->num_cells; i--;) {
+    fprintf(p->priv_fp, "### precon %d %.2e\n", i, p->priv_pcg[i]);
+  }
+#endif
+  for (i = p->priv_n; i--;) {
+      p->priv_pcgt[i] = 0.0;
+  }
+  for (i = 0; i < p->num_cells; i++) {
+    c = p->priv_ii[i];
+    if (c >= 0) {
+      t = p->priv_pcg[i];
+      p->priv_pcgt[c] += t;
+      p->priv_pcgt[c + 1] += t;
+    }
+#if 0
+    else if (c < -1) {
+      pr = p->priv_gt[-(c+2)];
+      while ((j = p->cog_list[pr++]) >= 0) {
+    ji = p->priv_ii[j];
+    if (ji >= 0) {
+      w = p->area[j] / p->area[i];
+      t = w * w * p->priv_pcg[i];
+      p->priv_pcgt[ji] += t;
+      p->priv_pcgt[ji + 1] += t;
+    }
+      }
+    }
+#endif
+  }
+  for (i = 0; i < p->priv_n; i++) {
+    t = p->priv_pcgt[i];
+    if (fabs(t) < QPS_PRECON_EPS || fabs(t) > 1.0/QPS_PRECON_EPS) {
+      p->priv_pcgt[i] = 1.0;
+    }
+    else {
+      p->priv_pcgt[i] = 1.0 / p->priv_pcgt[i];
+    }
+  }
+#endif
+
+  /* allocate variable storage */
+  p->priv_cp = (qps_float_t *) malloc(4 * p->priv_n * sizeof(qps_float_t));
+  assert(p->priv_cp);
+
+  /* temp arrays for cg */
+  p->priv_g = p->priv_cp + p->priv_n;
+  p->priv_h = p->priv_cp + 2 * p->priv_n;
+  p->priv_xi = p->priv_cp + 3 * p->priv_n;
+
+  /* set values */
+  for (i = p->num_cells; i--;) {
+    if (p->priv_ii[i] >= 0) {
+      p->priv_cp[p->priv_ii[i]] = p->x[i];
+      p->priv_cp[p->priv_ii[i] + 1] = p->y[i];
+    }
+  }
+
+  if (p->loop_num) {
+    p->priv_lt = (qps_float_t *) malloc(p->loop_num * sizeof(qps_float_t));
+    assert(p->priv_lt);
+#if defined(QPS_HOIST)
+    pr = 0;
+    for (i=p->loop_num; i--;) {
+      while (p->loop_list[pr++] >= 0) {
+      }
+      pr++;
+    }
+    p->priv_lm = pr;
+    p->priv_la = (int *) malloc(pr * sizeof(int));
+    assert(p->priv_la);
+    pr = 0;
+    for (i = 0; i < p->loop_num; i++) {
+      j = st = p->loop_list[pr++];
+      while ((k = p->loop_list[pr]) >= 0) {
+    if (j > k) {
+      m1 = k;
+      m2 = j;
+    }
+    else {
+      assert(k > j);
+      m1 = j;
+      m2 = k;
+    }
+    pw = p->priv_cr[m1];
+    while (p->priv_cc[pw] != m2) {
+/*      assert(p->priv_cc[pw] >= 0); */
+      if (p->priv_cc[pw] < 0) {
+        pw = -2;
+        break;
+      }
+      pw++;
+    }
+    p->priv_la[pr-1] = pw;
+    j = k;
+    pr++;
+      }
+      if (j > st) {
+    m1 = st;
+    m2 = j;
+      }
+      else {
+    assert(st > j);
+    m1 = j;
+    m2 = st;
+      }
+      pw = p->priv_cr[m1];
+      while (p->priv_cc[pw] != m2) {
+/*    assert(p->priv_cc[pw] >= 0); */
+    if (p->priv_cc[pw] < 0) {
+      pw = -2;
+      break;
+    }
+    pw++;
+      }
+      p->priv_la[pr-1] = pw;
+      p->priv_la[pr] = -1;
+      pr++;
+    }
+#endif /* QPS_HOIST */
+  }
+
+  do {
+    qps_solve_inner(p);
+  } while (!p->loop_done || !p->max_done);
+
+  /* retrieve values */
+  /* qps_settp() should have already been called at this point */
+  for (i = p->num_cells; i--;) {
+    p->x[i] = p->priv_tp[i * 2];
+    p->y[i] = p->priv_tp[i * 2 + 1];
+  }
+#if (QPS_DEBUG > 5)
+  for (i = p->num_cells; i--;) {
+    fprintf(p->priv_fp, "### cloc %d %f %f\n", i, p->x[i], p->y[i]);
+  }
+#endif
+
+  free(p->priv_cp);
+  if (p->max_enable) {
+    free(p->priv_mxl);
+  }
+  if (p->cog_num) {
+    free(p->priv_gt);
+    free(p->priv_gm);
+    free(p->priv_gw);
+  }
+  if(p->loop_num) {
+    free(p->priv_lt);
+#if defined(QPS_HOIST)
+    free(p->priv_la);
+#endif
+  }
+
+#if defined(QPS_PRECON)
+  free(p->priv_pcg);
+  free(p->priv_pcgt);
+#endif
+}
+
+/**********************************************************************/
+
+void
+qps_clean(qps_problem_t * p)
+{
+  free(p->priv_tp);
+  free(p->priv_ii);
+  free(p->priv_cc);
+  free(p->priv_cr);
+  free(p->priv_cw);
+  free(p->priv_ct);
+
+#if defined(QPS_DEBUG)
+  fclose(p->priv_fp);
+#endif /* QPS_DEBUG */
+}
+
+/**********************************************************************/
diff --git a/src/phys/place/place_qpsolver.h b/src/phys/place/place_qpsolver.h
new file mode 100644
index 00000000..08771d6b
--- /dev/null
+++ b/src/phys/place/place_qpsolver.h
@@ -0,0 +1,140 @@
+/*===================================================================*/
+//  
+//     place_qpsolver.h
+//
+//        Philip Chong
+//              pchong@cadence.com
+//
+/*===================================================================*/
+
+#if !defined(_QPS_H)
+#define _QPS_H
+
+#include <stdio.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif                /* __cplusplus */
+
+  typedef float qps_float_t;
+
+  typedef struct qps_problem {
+
+    /* Basic stuff */
+    int num_cells;        /* Total number of cells (both fixed and
+                   floating) to be placed. */
+    int *connect;        /* Connectivity array.  Must contain at least 
+                   num_cells elements with value -1. The
+                   entries which precede the first element
+                   with value -1 are the indices of the cells 
+                   which connect to cell 0; the entries
+                   which lie between the first and second
+                   elements with value -1 are the indices of
+                   the cells which connect to cell 1; etc.
+                   Example: cells 0 and 1 are connected
+                   together, and 1 and 2 are connected as
+                   well.  *connect = { 1, -1, 0, 2, -1, 1, -1
+                   }. */
+    qps_float_t *edge_weight;    /* Same structure as connectivity array, but
+                   giving the weights assigned to each edge
+                   instead. */
+    qps_float_t *x;        /* num_cells element array which contains the
+                   x-coordinates of the cells. This is used
+                   for the initial values in the iterative
+                   solution of floating cells, and for the
+                   fixed location of fixed cells. */
+    qps_float_t *y;        /* num_cells element array of
+                   y-coordinates. */
+    int *fixed;            /* num_cells element array with value 1 if
+                   corresponding cell is fixed, 0 if
+                   floating. */
+    qps_float_t f;        /* return value for sum-of-square
+                   wirelengths. */
+
+    /* COG stuff */
+    int cog_num;        /* Number of COG constraints. */
+    int *cog_list;        /* Array indicating for each COG constraint
+                   which cells belong to that constraint.
+                   Format is similar to c array: there must
+                   be at least cog_num elements with value
+                   -1.  The entries of cog_list preceding the 
+                   first -1 element are the indices of the
+                   cells which belong to the first COG
+                   constraint; etc.  Example: cells 0 and 1
+                   belong to one COG constraint, cells 4 and
+                   5 belong to another.  *cog_list= { 0, 1,
+                   -1, 4, 5, -1 }. */
+    qps_float_t *cog_x;        /* cog_num element array whose values are the
+                   x-coordinates for the corresponding COG
+                   constraints. */
+    qps_float_t *cog_y;        /* cog_num element array whose values are the
+                   y-coordinates for the corresponding COG
+                   constraints. */
+    qps_float_t *area;         /* num_cells element array whose values are
+                   the areas for the corresponding cells;
+                   only useful with COG constraints. */
+
+    /* Loop constraint stuff */
+    int loop_num;        /* Number of loop constraints. */
+    int *loop_list;        /* Array with list of cells for each loop
+                   constraint. Format is similar to cog_list. 
+                 */
+    qps_float_t *loop_max;    /* loop_num element array indicating maximum
+                   distance for each loop. */
+    qps_float_t *loop_penalty;    /* loop_num element array indicating penalty
+                   for each loop. */
+    int loop_k;            /* Current iteration for loop optimization. */
+    int loop_done;        /* Done flag for loop optimization. */
+    int loop_fail;
+
+    /* max_x/max_y stuff */
+    qps_float_t max_x;        /* max x location;  only used in
+                   constrained optimization. */
+    qps_float_t max_y;        /* max y location;  only used in
+                   constrained optimization. */
+    int max_enable;        /* Set to 1 after qps_init() to enable
+                   max_x/max_y. */
+    int max_done;        /* Done flag for max optimization. */
+
+    /* Private stuff */
+    int *priv_ii;
+    int *priv_cc, *priv_cr;
+    qps_float_t *priv_cw, *priv_ct;
+    int priv_cm;
+    int *priv_gt;
+    int *priv_la;
+    int priv_lm;
+    qps_float_t *priv_gm, *priv_gw;
+    qps_float_t *priv_g, *priv_h, *priv_xi;
+    qps_float_t *priv_tp, *priv_tp2;
+    int priv_n;
+    qps_float_t *priv_cp;
+    qps_float_t priv_f;
+    qps_float_t *priv_lt;
+    qps_float_t *priv_pcg, *priv_pcgt;
+    qps_float_t priv_fmax;
+    qps_float_t priv_fprev;
+    qps_float_t priv_fopt;
+    qps_float_t priv_eps;
+    int priv_pn;
+    qps_float_t *priv_mxl, *priv_mxh, *priv_myl, *priv_myh;
+    int priv_ik;
+    FILE *priv_fp;
+
+  } qps_problem_t;
+
+  /* call qps_init() as soon as the qps_problem_t has been set up */
+  /* this initializes some private data structures */
+  extern void qps_init(qps_problem_t *);
+
+  /* call qps_solve() to solve the given qp problem */
+  extern void qps_solve(qps_problem_t *);
+
+  /* call qps_clean() when finished with the qps_problem_t */
+  /* this discards the private data structures assigned by qps_init() */
+  extern void qps_clean(qps_problem_t *);
+
+#if defined(__cplusplus)
+}
+#endif                /* __cplusplus */
+#endif                /* _QPS_H */
diff --git a/src/phys/place/place_test.c b/src/phys/place/place_test.c
new file mode 100644
index 00000000..ea706a09
--- /dev/null
+++ b/src/phys/place/place_test.c
@@ -0,0 +1,360 @@
+/*===================================================================*/
+//  
+//     place_test.c
+//
+//        Aaron P. Hurst, 2003-2007
+//              ahurst@eecs.berkeley.edu
+//
+/*===================================================================*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#include "place_base.h"
+
+
+// --------------------------------------------------------------------
+// Hash type/functions
+//
+// --------------------------------------------------------------------
+
+struct hash_element {
+  ConcreteCell        *obj;
+  struct hash_element *next;
+} hash_element;
+
+int hash_string(int hash_max, const char *str) {
+  unsigned int hash = 0;
+  int p;
+  for(p = 0; p<strlen(str); p++)
+    hash += str[p]*p;
+  return hash % hash_max;
+}
+
+void hash_add(struct hash_element **hash, int hash_max,
+              ConcreteCell *cell) {
+  int key = hash_string(hash_max, cell->m_label);
+  // printf("adding %s key = %d\n", cell->m_label, key);
+  struct hash_element *element = malloc(sizeof(struct hash_element));
+  assert(element);
+  element->obj = cell;
+  element->next = hash[key];
+  hash[key] = element;
+}
+
+ConcreteCell *hash_find(struct hash_element **hash, int hash_max, const char *str) {
+  int key = hash_string(hash_max, str);
+  // printf("looking for %s key = %d\n", str, key);
+  struct hash_element *next = hash[key];
+  while(next) {
+    if (!strcmp(str, next->obj->m_label))
+      return next->obj;
+    next = next->next;
+  }
+  return 0;
+}
+
+// --------------------------------------------------------------------
+// Global variables
+//
+// --------------------------------------------------------------------
+
+struct hash_element **hash_cellname;
+
+int numCells = 0, numNets = 0;
+
+AbstractCell *abstractCells;
+ConcreteCell *concreteCells;
+ConcreteNet  *concreteNets;
+
+// --------------------------------------------------------------------
+// Function implementations
+//
+// --------------------------------------------------------------------
+
+void readBookshelfNets(char *filename) {
+  char *tok;
+  char buf[1024];
+  const char *DELIMITERS = " \n\t:";
+  int id = 0;
+  int t;
+  ConcreteCell *cell;
+
+  FILE *netsFile = fopen(filename, "r");
+  if (!netsFile) {
+    printf("ERROR: Could not open .nets file\n");
+    exit(1);
+  }
+
+  // line 1 : version
+  while (fgets(buf, 1024, netsFile) && (buf[0] == '\n' || buf[0] == '#'));
+
+  // line 2 : number of nets
+  while (fgets(buf, 1024, netsFile) && (buf[0] == '\n' || buf[0] == '#'));
+  tok = strtok(buf, DELIMITERS);
+  tok = strtok(NULL, DELIMITERS);
+  numNets = atoi(tok);
+  printf("READ-20 : number of nets = %d\n", numNets);
+  concreteNets = malloc(sizeof(ConcreteNet)*numNets);
+
+  // line 3 : number of pins
+  while (fgets(buf, 1024, netsFile) && (buf[0] == '\n' || buf[0] == '#'));
+
+  // line XXX : net definitions
+  while(fgets(buf, 1024, netsFile)) {
+    if (buf[0] == '\n' || buf[0] == '#') continue;
+
+    concreteNets[id].m_id = id;
+    concreteNets[id].m_weight = 1.0;
+
+    tok = strtok(buf, DELIMITERS);
+    if (!!strcmp(tok, "NetDegree")) {
+      printf("%s\n",buf);
+      printf("ERROR: Incorrect format in .nets file\n");
+      exit(1);
+    }
+
+    tok = strtok(NULL, DELIMITERS);
+    concreteNets[id].m_numTerms = atoi(tok);
+    if (concreteNets[id].m_numTerms < 0 ||
+        concreteNets[id].m_numTerms > 100000) {
+      printf("ERROR: Bad net degree\n");
+      exit(1); 
+    }
+    concreteNets[id].m_terms = malloc(sizeof(ConcreteCell*)*
+         concreteNets[id].m_numTerms);
+
+    // read terms
+    t = 0;
+    while(t < concreteNets[id].m_numTerms &&
+          fgets(buf, 1024, netsFile)) {
+      if (buf[0] == '\n' || buf[0] == '#') continue;
+      
+      // cell name
+      tok = strtok(buf, DELIMITERS);
+      cell = hash_find(hash_cellname, numCells, tok);
+      if (!cell) {
+        printf("ERROR: Could not find cell %s in .nodes file\n", tok);
+        exit(1);
+      }
+      concreteNets[id].m_terms[t] = cell;
+      t++;
+    }
+
+    // add!
+    addConcreteNet(&(concreteNets[id]));
+
+    id++;
+  }
+
+  fclose(netsFile);
+}
+
+void readBookshelfNodes(char *filename) {
+  char *tok;
+  char buf[1024];
+  const char *DELIMITERS = " \n\t:";
+  int id = 0;
+
+  FILE *nodesFile = fopen(filename, "r");
+  if (!nodesFile) {
+    printf("ERROR: Could not open .nodes file\n");
+    exit(1);
+  }
+
+  // line 1 : version
+  while (fgets(buf, 1024, nodesFile) && (buf[0] == '\n' || buf[0] == '#'));
+
+  // line 2 : num nodes
+  while (fgets(buf, 1024, nodesFile) && (buf[0] == '\n' || buf[0] == '#'));
+  tok = strtok(buf, DELIMITERS);
+  tok = strtok(NULL, DELIMITERS);
+  numCells = atoi(tok);
+  printf("READ-10 : number of cells = %d\n", numCells);
+  concreteCells = malloc(sizeof(ConcreteCell)*numCells);
+  abstractCells = malloc(sizeof(AbstractCell)*numCells);
+  hash_cellname = calloc(numCells, sizeof(struct hash_element*));
+
+  // line 3 : num terminals
+  while (fgets(buf, 1024, nodesFile) && (buf[0] == '\n' || buf[0] == '#'));
+
+  // line XXX : cell definitions
+  while(fgets(buf, 1024, nodesFile)) {
+    if (buf[0] == '\n' || buf[0] == '#') continue;
+
+    tok = strtok(buf, DELIMITERS);
+    concreteCells[id].m_id = id;;
+    
+    // label
+    concreteCells[id].m_parent = &(abstractCells[id]);
+    concreteCells[id].m_label = malloc(sizeof(char)*strlen(tok)+1);
+    strcpy(concreteCells[id].m_label, tok);
+    abstractCells[id].m_label = concreteCells[id].m_label;
+    hash_add(hash_cellname, numCells, 
+             &(concreteCells[id]));
+
+    // dimensions
+    tok = strtok(NULL, DELIMITERS);
+    abstractCells[id].m_width = atof(tok);
+    tok = strtok(NULL, DELIMITERS);
+    abstractCells[id].m_height = atof(tok);
+    tok = strtok(NULL, DELIMITERS);
+    // terminal
+    abstractCells[id].m_pad = tok && !strcmp(tok, "terminal");
+
+    // add!
+    addConcreteCell(&(concreteCells[id]));
+
+    // DEBUG
+    /*
+    printf("\"%s\" : %f x %f\n", concreteCells[id].m_label,
+           abstractCells[id].m_width,
+           abstractCells[id].m_height);
+    */
+    id++;
+  }
+
+  fclose(nodesFile);
+}
+
+void readBookshelfPlacement(char *filename) {
+  char *tok;
+  char buf[1024];
+  const char *DELIMITERS = " \n\t:";
+  ConcreteCell *cell;
+
+  FILE *plFile = fopen(filename, "r");
+  FILE *netsFile = fopen(filename, "r");
+  if (!plFile) {
+    printf("ERROR: Could not open .pl file\n");
+    exit(1);
+  }
+  if (!netsFile) {
+    printf("ERROR: Could not open .nets file\n");
+    exit(1);
+  }
+
+  // line 1 : version
+  while (fgets(buf, 1024, plFile) && (buf[0] == '\n' || buf[0] == '#'));
+
+  // line XXX : placement definitions
+  while(fgets(buf, 1024, plFile)) {
+    if (buf[0] == '\n' || buf[0] == '#') continue;
+
+    tok = strtok(buf, DELIMITERS);
+
+    // cell name
+    cell = hash_find(hash_cellname, numCells, tok);
+    if (!cell) {
+      printf("ERROR: Could not find cell %s in .nodes file\n",tok);
+      exit(1);
+    }
+
+    // position
+    tok = strtok(NULL, DELIMITERS);
+    cell->m_x = atof(tok);
+    tok = strtok(NULL, DELIMITERS);
+    cell->m_y = atof(tok);
+
+    // hfixed
+    cell->m_fixed = strtok(NULL, DELIMITERS) && 
+      (tok = strtok(NULL, DELIMITERS)) &&
+      !strcmp(tok, "\\FIXED");
+  }
+  
+  fclose(plFile);
+}
+
+void writeBookshelfPlacement(char *filename) {
+  int c = 0;
+
+  FILE *plFile = fopen(filename, "w");
+  if (!plFile) {
+    printf("ERROR: Could not open .pl file\n");
+    exit(1);
+  }
+
+  fprintf(plFile, "UCLA pl 1.0\n");
+  for(c=0; c<numCells; c++) {
+    fprintf(plFile, "%s %f %f : N %s\n", 
+            concreteCells[c].m_label,
+            concreteCells[c].m_x,
+            concreteCells[c].m_y,
+            (concreteCells[c].m_fixed ? "\\FIXED" : ""));
+  }
+
+  fclose(plFile);
+}
+
+// deletes all connections to a cell
+void delNetConnections(ConcreteCell *cell) {
+  int n, t, t2, count = 0;
+  ConcreteCell **old = malloc(sizeof(ConcreteCell*)*g_place_numCells);
+
+  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) {
+    ConcreteNet *net = g_place_concreteNets[n];
+    count = 0;
+    for(t=0; t<net->m_numTerms; t++)
+      if (net->m_terms[t] == cell) count++;
+    if (count) {
+      memcpy(old, net->m_terms, sizeof(ConcreteCell*)*net->m_numTerms);
+      net->m_terms = realloc(net->m_terms, 
+                             sizeof(ConcreteCell*)*(net->m_numTerms-count));
+      t2 = 0;
+      for(t=0; t<net->m_numTerms; t++)
+        if (old[t] != cell) net->m_terms[t2++] = old[t];
+      net->m_numTerms -= count;
+    }
+  }
+  free(old);
+}
+
+int main(int argc, char **argv) {
+
+  if (argc != 4) {
+    printf("Usage: %s [nodes] [nets] [pl]\n", argv[0]);
+    exit(1);
+  }
+
+  readBookshelfNodes(argv[1]);
+  readBookshelfNets(argv[2]);
+  readBookshelfPlacement(argv[3]);
+
+  globalPreplace(0.8);
+  globalPlace();
+
+  // DEBUG net/cell removal/addition
+  /*
+  int i;
+  for(i=1000; i<2000; i++) {
+    delConcreteNet(g_place_concreteNets[i]);
+    delNetConnections(g_place_concreteCells[i]);
+    delConcreteCell(g_place_concreteCells[i]);
+  }
+  
+  ConcreteCell newCell[2];
+  newCell[0].m_id = g_place_numCells+1;
+  newCell[0].m_x = 1000;
+  newCell[0].m_y = 1000;
+  newCell[0].m_fixed = false;
+  newCell[0].m_parent = &(abstractCells[1000]);
+  newCell[0].m_label = " ";
+  addConcreteCell(&newCell[0]);
+  newCell[1].m_id = g_place_numCells+3;
+  newCell[1].m_x = 1000;
+  newCell[1].m_y = 1000;
+  newCell[1].m_fixed = false;
+  newCell[1].m_parent = &(abstractCells[1000]);
+  newCell[1].m_label = " ";
+  addConcreteCell(&newCell[1]);
+  */
+
+  globalIncremental();
+
+  writeBookshelfPlacement(argv[3]);
+
+  free(hash_cellname);
+
+  return 0;
+}