summaryrefslogtreecommitdiffstats
path: root/src/phys
diff options
context:
space:
mode:
Diffstat (limited to 'src/phys')
-rw-r--r--src/phys/place/Makefile30
-rw-r--r--src/phys/place/README50
-rw-r--r--src/phys/place/hpwl57
-rw-r--r--src/phys/place/libhmetis.h31
-rw-r--r--src/phys/place/module.make10
-rw-r--r--src/phys/place/place_base.c345
-rw-r--r--src/phys/place/place_base.h137
-rw-r--r--src/phys/place/place_bin.c277
-rw-r--r--src/phys/place/place_genqp.c309
-rw-r--r--src/phys/place/place_gordian.c160
-rw-r--r--src/phys/place/place_gordian.h78
-rw-r--r--src/phys/place/place_inc.c106
-rw-r--r--src/phys/place/place_io.c94
-rw-r--r--src/phys/place/place_legalize.c23
-rw-r--r--src/phys/place/place_pads.c141
-rw-r--r--src/phys/place/place_partition.c1135
-rw-r--r--src/phys/place/place_qpsolver.c1270
-rw-r--r--src/phys/place/place_qpsolver.h140
-rw-r--r--src/phys/place/place_test.c360
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;
+}