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, 0 insertions, 4753 deletions
diff --git a/src/phys/place/Makefile b/src/phys/place/Makefile
deleted file mode 100644
index 1f700105..00000000
--- a/src/phys/place/Makefile
+++ /dev/null
@@ -1,30 +0,0 @@
-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
deleted file mode 100644
index d4f8ac8f..00000000
--- a/src/phys/place/README
+++ /dev/null
@@ -1,50 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index f69a1d05..00000000
--- a/src/phys/place/hpwl
+++ /dev/null
@@ -1,57 +0,0 @@
-#! /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
deleted file mode 100644
index 051079d4..00000000
--- a/src/phys/place/libhmetis.h
+++ /dev/null
@@ -1,31 +0,0 @@
-// 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
deleted file mode 100644
index 98930fbe..00000000
--- a/src/phys/place/module.make
+++ /dev/null
@@ -1,10 +0,0 @@
-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
deleted file mode 100644
index 4e38f1d1..00000000
--- a/src/phys/place/place_base.c
+++ /dev/null
@@ -1,345 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index e5e7ecef..00000000
--- a/src/phys/place/place_base.h
+++ /dev/null
@@ -1,137 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 86ec3506..00000000
--- a/src/phys/place/place_bin.c
+++ /dev/null
@@ -1,277 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 5b6c7027..00000000
--- a/src/phys/place/place_genqp.c
+++ /dev/null
@@ -1,309 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 2929bf95..00000000
--- a/src/phys/place/place_gordian.c
+++ /dev/null
@@ -1,160 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 67eb1479..00000000
--- a/src/phys/place/place_gordian.h
+++ /dev/null
@@ -1,78 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 7e2d847c..00000000
--- a/src/phys/place/place_inc.c
+++ /dev/null
@@ -1,106 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 8e24ef4a..00000000
--- a/src/phys/place/place_io.c
+++ /dev/null
@@ -1,94 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 950902f4..00000000
--- a/src/phys/place/place_legalize.c
+++ /dev/null
@@ -1,23 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 361fac7f..00000000
--- a/src/phys/place/place_pads.c
+++ /dev/null
@@ -1,141 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index ea57cd1c..00000000
--- a/src/phys/place/place_partition.c
+++ /dev/null
@@ -1,1135 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 9df9c6dc..00000000
--- a/src/phys/place/place_qpsolver.c
+++ /dev/null
@@ -1,1270 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index 08771d6b..00000000
--- a/src/phys/place/place_qpsolver.h
+++ /dev/null
@@ -1,140 +0,0 @@
-/*===================================================================*/
-//
-// 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
deleted file mode 100644
index ea706a09..00000000
--- a/src/phys/place/place_test.c
+++ /dev/null
@@ -1,360 +0,0 @@
-/*===================================================================*/
-//
-// 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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 01:51:06 +0000