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