From e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 30 Sep 2007 08:01:00 -0700 Subject: Version abc70930 --- src/phys/place/Makefile | 30 - src/phys/place/README | 50 -- src/phys/place/hpwl | 57 -- src/phys/place/libhmetis.h | 31 - src/phys/place/module.make | 10 - src/phys/place/place_base.c | 345 ----------- src/phys/place/place_base.h | 137 ---- src/phys/place/place_bin.c | 277 --------- src/phys/place/place_genqp.c | 309 ---------- src/phys/place/place_gordian.c | 160 ----- src/phys/place/place_gordian.h | 78 --- src/phys/place/place_inc.c | 106 ---- src/phys/place/place_io.c | 94 --- src/phys/place/place_legalize.c | 23 - src/phys/place/place_pads.c | 141 ----- src/phys/place/place_partition.c | 1135 ---------------------------------- src/phys/place/place_qpsolver.c | 1270 -------------------------------------- src/phys/place/place_qpsolver.h | 140 ----- src/phys/place/place_test.c | 360 ----------- 19 files changed, 4753 deletions(-) delete mode 100644 src/phys/place/Makefile delete mode 100644 src/phys/place/README delete mode 100644 src/phys/place/hpwl delete mode 100644 src/phys/place/libhmetis.h delete mode 100644 src/phys/place/module.make delete mode 100644 src/phys/place/place_base.c delete mode 100644 src/phys/place/place_base.h delete mode 100644 src/phys/place/place_bin.c delete mode 100644 src/phys/place/place_genqp.c delete mode 100644 src/phys/place/place_gordian.c delete mode 100644 src/phys/place/place_gordian.h delete mode 100644 src/phys/place/place_inc.c delete mode 100644 src/phys/place/place_io.c delete mode 100644 src/phys/place/place_legalize.c delete mode 100644 src/phys/place/place_pads.c delete mode 100644 src/phys/place/place_partition.c delete mode 100644 src/phys/place/place_qpsolver.c delete mode 100644 src/phys/place/place_qpsolver.h delete mode 100644 src/phys/place/place_test.c (limited to 'src/phys') diff --git a/src/phys/place/Makefile b/src/phys/place/Makefile deleted file mode 100644 index 1f700105..00000000 --- a/src/phys/place/Makefile +++ /dev/null @@ -1,30 +0,0 @@ -TARGETS = place_test BookshelfView.class - -CFLAGS = -g -pedantic -Wall - -STATIC_LIBS = libhmetis.a -DYNAMIC_LIBS = -lm - -OBJECTS = place_test.o place_qpsolver.o place_base.o place_pads.o place_genqp.o place_gordian.o \ - place_partition.o place_legalize.o place_bin.o - - -# For hMetis free code, uncomment the following lines -# -# CFLAGS = -g -pedantic -Wall -DNO_HMETIS -# STATIC_LIBS = - - -all: $(TARGETS) - -%.o: %.c *.h - gcc $(CFLAGS) -c -o $@ $< - -place_test: $(OBJECTS) - gcc *.o $(STATIC_LIBS) $(DYNAMIC_LIBS) -o place_test - -BookshelfView.class: BookshelfView.java - javac BookshelfView.java - -clean: - rm -rf *.o place_test *.class *~ diff --git a/src/phys/place/README b/src/phys/place/README deleted file mode 100644 index d4f8ac8f..00000000 --- a/src/phys/place/README +++ /dev/null @@ -1,50 +0,0 @@ -/*===================================================================*/ -// -// GORDIAN-like placement package -// -// Aaron P. Hurst (ahurst@eecs.berkeley.edu) -// Addl code from Philip Chong (pchong@cadence.com) -// hMetis partitioner (www.cs.umn.edu/~metis) -// -/*===================================================================*/ - -1. Requirements - -An i386 Linux system (though others will certainly work with some tweaks). -A standard ANSI C development platform. - -The following are optional, but useful: - -- hMetis partitioner. This can be obtained from (www.cs.umn.edu/~metis) - Place (links to) the files "libhmetis.a" and "libhtmetis.h" in this directory. - Otherwise, #define NO_HMETIS in the file "place_gordian.h" -- Java SDK, if compiling BookshelfView is desired. -- Perl, if additional script utilities are desired. - -2. Descriptions of contents: - -place_base.h contains the basic data structures and "external" API. -place_gordian.h contains the "internal" API and configuration options. - -There are also several utilities: - -i) place_test - -Reads a netlist description in GSRC Bookshelf format, performs global placement, -and rewrites the placement file. An example usage: - -./place_test ac97_emap.nodes ac97_emap.nets ac97_emap.pl - -ii) BookshelfView - -A simple Java GUI to view the resulting placements. It has been tested with -Java 5 and 6. Usage: - -java BookshelfView ac97_emap.nodes ac97_emap.pl - -iii) hpwl - -A perl script to print the half-perimeter wirelength of a placement. Usage: - -./hpwl ac97_emap.nets ac97_emal.pl - diff --git a/src/phys/place/hpwl b/src/phys/place/hpwl deleted file mode 100644 index f69a1d05..00000000 --- a/src/phys/place/hpwl +++ /dev/null @@ -1,57 +0,0 @@ -#! /usr/bin/perl - -$netsfile = shift; -$plfile = shift; - -# ------------------------------ read placement - -open FILE, $plfile; -while () { - chop; - if (/(\w+)\s+([\-\d\.]+)\s+([\-\d\.]+)\s+\:/) { - $loc{$1} = "$2 $3"; - } -} -close FILE; - -open FILE, $netsfile; -while () { - chop; - $net = $2 if /NetDegree\s+\:\s+(\d+)\s+(\w+)/; - if (/(\w+)\s+(\w+)\s+\:/) { - $netconn{$net} .= "$1 "; - $cellconn{$1} .= "$net "; - } -} -close FILE; - -# ----------------------------- compute HPWL - -$hpwl = 0; -foreach $net (keys %netconn) { - @conns = split ' ',$netconn{$net}; - $min_x = $min_y = 1e12; - $max_x = $max_y = -1e12; - foreach $cell (@conns) { - if (!exists $loc{$cell}) { - print "WARNING: Unknown cell location: $cell\n"; - } else { - ($x, $y) = split ' ',$loc{$cell}; - $min_x = $x if $x < $min_x; - $min_y = $y if $y < $min_y; - $max_x = $x if $x > $max_x; - $max_y = $y if $y > $max_y; - } - } - - if ($min_x eq 1e12 or $min_y eq 1e12 or - $max_x eq -1e12 or $max_y eq -1e12) { - print "WARNING: Unbounded box\n"; - } else { - $hpwl = $hpwl + $max_x - $min_x + $max_y - $min_y; - } -} - -print "HPWL = "; -printf "%e",$hpwl; -print "\n"; diff --git a/src/phys/place/libhmetis.h b/src/phys/place/libhmetis.h deleted file mode 100644 index 051079d4..00000000 --- a/src/phys/place/libhmetis.h +++ /dev/null @@ -1,31 +0,0 @@ -// A. Hurst ahurst@eecs.berkeley.edu - -#ifndef LIBHMETIS_H_ -#define LIBHMETIS_H_ - -static void HMETIS_PartRecursive(int nvtxs, - int nhedges, - int *vwgts, - int *eptr, - int *eind, - int *hewgts, - int nparts, - int nbfactor, - int *options, - int *part, - int *edgecnt ) {} //; - - -static void HMETIS_PartKway(int nvtxs, - int nhedges, - int *vwgts, - int *eptr, - int *eind, - int *hewgts, - int nparts, - int nbfactor, - int *options, - int *part, - int *edgecnt ) {} //; - -#endif diff --git a/src/phys/place/module.make b/src/phys/place/module.make deleted file mode 100644 index 98930fbe..00000000 --- a/src/phys/place/module.make +++ /dev/null @@ -1,10 +0,0 @@ -SRC += src/phys/place/place_base.c \ - src/phys/place/place_bin.c \ - src/phys/place/place_genqp.c \ - src/phys/place/place_gordian.c \ - src/phys/place/place_legalize.c \ - src/phys/place/place_pads.c \ - src/phys/place/place_partition.c \ - src/phys/place/place_qpsolver.c \ - src/phys/place/place_io.c \ - src/phys/place/place_inc.c diff --git a/src/phys/place/place_base.c b/src/phys/place/place_base.c deleted file mode 100644 index 4e38f1d1..00000000 --- a/src/phys/place/place_base.c +++ /dev/null @@ -1,345 +0,0 @@ -/*===================================================================*/ -// -// place_base.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include - -#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; tm_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; nm_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; cm_numMembers; c++) - if (p->m_members[c] == cell) { - p->m_members[c] = 0; - p->m_area -= getCellArea(cell); - found = true; - break; - } - - if (!found) return; - - if (!p->m_leaf) { - delCellFromPartition(cell, p->m_sub1); - delCellFromPartition(cell, p->m_sub2); - } -} - - -// -------------------------------------------------------------------- -// delConcreteCell() -// -/// \brief Removes a cell from the placement database. -/// -/// Does not deallocate memory. -/// -/// Important: does not modify nets that may point to this -/// cell. If these are connections are not removed, segmentation faults -/// and other nasty errors will occur. -// -// -------------------------------------------------------------------- -void delConcreteCell(ConcreteCell *cell) { - assert(cell); - g_place_concreteCells[cell->m_id] = 0; - while(!g_place_concreteCells[g_place_numCells-1]) g_place_numCells--; - - if (g_place_rootPartition) delCellFromPartition(cell, g_place_rootPartition); -} - - -// -------------------------------------------------------------------- -// netSortByX... -// -/// \brief Sorts nets by position of one of its corners. -// -/// These are for use with qsort(). -/// -/// Can tolerate pointers to NULL objects. -/// -// -------------------------------------------------------------------- -int netSortByL(const void *a, const void *b) { - const ConcreteNet *pa = *(const ConcreteNet **)a; - const ConcreteNet *pb = *(const ConcreteNet **)b; - Rect ba, bb; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - ba = getNetBBox(pa), bb = getNetBBox(pb); - if (ba.x < bb.x) return -1; - if (ba.x > bb.x) return 1; - return 0; -} - -int netSortByR(const void *a, const void *b) { - const ConcreteNet *pa = *(const ConcreteNet **)a; - const ConcreteNet *pb = *(const ConcreteNet **)b; - Rect ba, bb; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - ba = getNetBBox(pa), bb = getNetBBox(pb); - if (ba.x + ba.w < bb.x + bb.w) return -1; - if (ba.x + ba.w > bb.x + bb.w) return 1; - return 0; -} - -int netSortByB(const void *a, const void *b) { - const ConcreteNet *pa = *(const ConcreteNet **)a; - const ConcreteNet *pb = *(const ConcreteNet **)b; - Rect ba, bb; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - ba = getNetBBox(pa), bb = getNetBBox(pb); - if (ba.y + ba.h < bb.y + bb.h) return -1; - if (ba.y + ba.h > bb.y + bb.h) return 1; - return 0; -} - -int netSortByT(const void *a, const void *b) { - const ConcreteNet *pa = *(const ConcreteNet **)a; - const ConcreteNet *pb = *(const ConcreteNet **)b; - Rect ba, bb; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - ba = getNetBBox(pa), bb = getNetBBox(pb); - if (ba.y < bb.y) return -1; - if (ba.y > bb.y) return 1; - return 0; -} - -int netSortByID(const void *a, const void *b) { - const ConcreteNet *pa = *(const ConcreteNet **)a; - const ConcreteNet *pb = *(const ConcreteNet **)b; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - if (pa->m_id < pb->m_id) return -1; - if (pa->m_id > pb->m_id) return 1; - return 0; -} - - -// -------------------------------------------------------------------- -// cellSortByX... -// -/// \brief Sorts cells by either position coordinate. -// -/// These are for use with qsort(). -/// -/// Can tolerate pointers to NULL objects. -// -// -------------------------------------------------------------------- -int cellSortByX(const void *a, const void *b) { - const ConcreteCell *pa = *(const ConcreteCell **)a; - const ConcreteCell *pb = *(const ConcreteCell **)b; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - if (pa->m_x < pb->m_x) return -1; - if (pa->m_x > pb->m_x) return 1; - return 0; -} - -int cellSortByY(const void *a, const void *b) { - const ConcreteCell *pa = *(const ConcreteCell **)a; - const ConcreteCell *pb = *(const ConcreteCell **)b; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - if (pa->m_y < pb->m_y) return -1; - if (pa->m_y > pb->m_y) return 1; - return 0; -} - -int cellSortByID(const void *a, const void *b) { - const ConcreteCell *pa = *(const ConcreteCell **)a; - const ConcreteCell *pb = *(const ConcreteCell **)b; - - if (!pa && !pb) return 0; - else if (!pa) return -1; - else if (!pb) return 1; - if (pa->m_id < pb->m_id) return -1; - if (pa->m_id > pb->m_id) return 1; - return 0; -} diff --git a/src/phys/place/place_base.h b/src/phys/place/place_base.h deleted file mode 100644 index e5e7ecef..00000000 --- a/src/phys/place/place_base.h +++ /dev/null @@ -1,137 +0,0 @@ -/*===================================================================*/ -// -// place_base.h -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#if !defined(PLACE_BASE_H_) -#define PLACE_BASE_H_ - -// -------------------------------------------------------------------- -// Data structures -// -// -------------------------------------------------------------------- - -// --- a C++ bool-like type -//typedef char bool; -#ifndef bool -#define bool int -#endif - -#define true 1 -#define false 0 - - -// --- Rect - rectangle - -typedef struct Rect { - float x, y; - float w, h; -} Rect; - - -// --- AbstractCell - a definition of a cell type - -typedef struct AbstractCell { - char *m_label; // string description - - float m_width, m_height; // dimensions - - bool m_pad; // a pad (external I/O) cell? -} AbstractCell; - - -// --- ConcreteCell - a design object - -typedef struct ConcreteCell { - int m_id; // a unique ID (see below) - char *m_label; // string description - - AbstractCell *m_parent; // cell type - - bool m_fixed; // position is fixed? - float m_x, m_y; // center of cell - - int m_data; -} ConcreteCell; - - -// --- ConcreteNet - a design net - -typedef struct ConcreteNet { - int m_id; // a unique ID (see below) - - int m_numTerms; // num. of connected cells - ConcreteCell **m_terms; // connected cells - - float m_weight; // relative weight - - int m_data; -} ConcreteNet; - - -// A note about IDs - the IDs are non-nonegative integers. They need not -// be contiguous, but this is certainly a good idea, as they are stored -// in a non-sparse array. -// Cells and nets have separate ID spaces. - -// -------------------------------------------------------------------- -// Global variable prototypes -// -// -------------------------------------------------------------------- - -// NOTE: None of these need to be managed externally. - -extern int g_place_numCells; // number of cells -extern int g_place_numNets; // number of nets -extern float g_place_rowHeight; // height of placement row -extern Rect g_place_coreBounds; // border of placeable area - // (x,y) = corner -extern Rect g_place_padBounds; // border of total die area - // (x,y) = corner - -extern ConcreteCell **g_place_concreteCells; // all concrete cells -extern ConcreteNet **g_place_concreteNets; // all concrete nets - - -// -------------------------------------------------------------------- -// Function prototypes -// -// -------------------------------------------------------------------- - -void addConcreteNet(ConcreteNet *net); -void addConcreteCell(ConcreteCell *cell); -void delConcreteNet(ConcreteNet *net); -void delConcreteCell(ConcreteCell *cell); - -void globalPreplace(float utilization); -void globalPlace(); -void globalIncremental(); -void globalFixDensity(int numBins, float maxMovement); - -float fastEstimate(ConcreteCell *cell, - int numNets, ConcreteNet *nets[]); -float fastTopoPlace(int numCells, ConcreteCell *cells[], - int numNets, ConcreteNet *nets[]); - -Rect getNetBBox(const ConcreteNet *net); -float getNetWirelength(const ConcreteNet *net); -float getTotalWirelength(); -float getCellArea(const ConcreteCell *cell); - -void writeBookshelf(const char *filename); - -// comparative qsort-style functions -int netSortByL(const void *a, const void *b); -int netSortByR(const void *a, const void *b); -int netSortByB(const void *a, const void *b); -int netSortByT(const void *a, const void *b); -int netSortByID(const void *a, const void *b); -int cellSortByX(const void *a, const void *b); -int cellSortByY(const void *a, const void *b); -int cellSortByID(const void *a, const void *b); - -#endif diff --git a/src/phys/place/place_bin.c b/src/phys/place/place_bin.c deleted file mode 100644 index 86ec3506..00000000 --- a/src/phys/place/place_bin.c +++ /dev/null @@ -1,277 +0,0 @@ -/*===================================================================*/ -// -// place_bin.c -// -// Aaron P. Hurst, 2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include -#include - -//#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; cm_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= 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; c2m_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; c3m_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; cm_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= 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; c2m_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; c3m_y = lastNewEdge+(binCells[c3]->m_y-lastOldEdge)*stretch; - - // force within core - h = binCells[c3]->m_parent->m_height; - if (binCells[c3]->m_y-h < g_place_coreBounds.y) - binCells[c3]->m_y = g_place_coreBounds.y+h; - if (binCells[c3]->m_y+h > g_place_coreBounds.y+g_place_coreBounds.h) - binCells[c3]->m_y = g_place_coreBounds.y+g_place_coreBounds.h-h; - } - - lastOldEdge = curOldEdge; - lastNewEdge = curNewEdge; - y++; - yBinCount = 0; - yBinArea = 0; - yBinStart = c2+1; - } - } - - x++; - xBinCount = 0; - xBinArea = 0; - xBinStart = c+1; - } - } - - free(binCells); - free(allCells); -} diff --git a/src/phys/place/place_genqp.c b/src/phys/place/place_genqp.c deleted file mode 100644 index 5b6c7027..00000000 --- a/src/phys/place/place_genqp.c +++ /dev/null @@ -1,309 +0,0 @@ -/*===================================================================*/ -// -// place_genqp.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include -#include - -#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; nm_numTerms > IGNORE_NETSIZE) { - ignoreNum++; - } - else { - maxConnections += net->m_numTerms*(net->m_numTerms-1); - for(t=0; tm_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; nm_weight / splitPenalty(net->m_numTerms); - for(t=0; tm_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; mm_numMembers; m++) if (p->m_members[m]) { - cell = p->m_members[m]; - assert(cell); - - if (!cell->m_fixed && !cell->m_parent->m_pad) { - isTrueConstraint = true; - } - else { - continue; - } - g_place_qpProb->cog_list[next_index++] = cell->m_id; - totarea += getCellArea(cell); - } - if (totarea == 0.0) { - isTrueConstraint = false; - } - if (isTrueConstraint) { - numConstraints++; - g_place_qpProb->cog_list[next_index++] = -1; - last_constraint = next_index; - } - else { - next_index = last_constraint; - } - } - - free(stack); - - return --numConstraints; -} - - -// -------------------------------------------------------------------- -// solveQuadraticProblem() -// -/// \brief Calls quadratic solver. -// -// -------------------------------------------------------------------- -void solveQuadraticProblem(bool useCOG) { - int c; - - reverseCOG *COG_rev = malloc(sizeof(reverseCOG)*g_place_numPartitions); - - g_place_qpProb->cog_list = malloc(sizeof(int)*(g_place_numPartitions+g_place_numCells)); - g_place_qpProb->cog_x = malloc(sizeof(float)*g_place_numPartitions); - g_place_qpProb->cog_y = malloc(sizeof(float)*g_place_numPartitions); - - // memset(g_place_qpProb->x, 0, sizeof(float)*g_place_numCells); - // memset(g_place_qpProb->y, 0, sizeof(float)*g_place_numCells); - - qps_init(g_place_qpProb); - - if (useCOG) - g_place_qpProb->cog_num = generateCoGConstraints(COG_rev); - else - g_place_qpProb->cog_num = 0; - - g_place_qpProb->loop_num = 0; - - qps_solve(g_place_qpProb); - - qps_clean(g_place_qpProb); - - // set the positions - for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) { - g_place_concreteCells[c]->m_x = g_place_qpProb->x[c]; - g_place_concreteCells[c]->m_y = g_place_qpProb->y[c]; - } - - // clean up - free(g_place_qpProb->cog_list); - free(g_place_qpProb->cog_x); - free(g_place_qpProb->cog_y); - - free(COG_rev); -} diff --git a/src/phys/place/place_gordian.c b/src/phys/place/place_gordian.c deleted file mode 100644 index 2929bf95..00000000 --- a/src/phys/place/place_gordian.c +++ /dev/null @@ -1,160 +0,0 @@ -/*===================================================================*/ -// -// place_gordian.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include -#include - -#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; cm_fixed || cell->m_parent->m_pad) { - continue; - } - // the new locations of the cells will be distributed within - // a small margin inside the border so that ordering is preserved - order_width = g_place_rowHeight; - - x = cell->m_x, y = cell->m_y, - w = cell->m_parent->m_width, h = cell->m_parent->m_height; - - if ((edge=x-w*0.5) < g_place_coreBounds.x) { - x = g_place_coreBounds.x+w*0.5 + - order_width/(1.0+g_place_coreBounds.x-edge); - } - else if ((edge=x+w*0.5) > g_place_coreBounds.x+g_place_coreBounds.w) { - x = g_place_coreBounds.x+g_place_coreBounds.w-w*0.5 - - order_width/(1.0+edge-g_place_coreBounds.x-g_place_coreBounds.w); - } - if ((edge=y-h*0.5) < g_place_coreBounds.y) { - y = g_place_coreBounds.y+h*0.5 + - order_width/(1.0+g_place_coreBounds.y-edge); - } - else if ((edge=y+h*0.5) > g_place_coreBounds.y+g_place_coreBounds.h) { - y = g_place_coreBounds.y+g_place_coreBounds.h-h*0.5 - - order_width/(1.0+edge-g_place_coreBounds.x-g_place_coreBounds.w); - } - cell->m_x = x; - cell->m_y = y; - } -} diff --git a/src/phys/place/place_gordian.h b/src/phys/place/place_gordian.h deleted file mode 100644 index 67eb1479..00000000 --- a/src/phys/place/place_gordian.h +++ /dev/null @@ -1,78 +0,0 @@ -/*===================================================================*/ -// -// place_gordian.h -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#if !defined(PLACE_GORDIAN_H_) -#define PLACE_GORDIAN_H_ - -#include "place_base.h" -#include "place_qpsolver.h" - -// Parameters for analytic placement -#define CLIQUE_PENALTY 1.0 -#define IGNORE_NETSIZE 20 - -// Parameters for partitioning -#define LARGEST_FINAL_SIZE 20 -#define PARTITION_AREA_ONLY true -#define REALLOCATE_PARTITIONS false -#define FINAL_REALLOCATE_PARTITIONS false -#define IGNORE_COG false -#define MAX_PARTITION_NONSYMMETRY 0.30 - -// Parameters for re-partitioning -#define REPARTITION_LEVEL_DEPTH 4 -#define REPARTITION_TARGET_FRACTION 0.15 -#define REPARTITION_FM false -#define REPARTITION_HMETIS true - -// Parameters for F-M re-partitioning -#define FM_MAX_BIN 10 -#define FM_MAX_PASSES 10 - -extern int g_place_numPartitions; - -extern qps_problem_t *g_place_qpProb; - -typedef struct Partition { - - int m_numMembers; - ConcreteCell **m_members; - Rect m_bounds; - bool m_done, - m_leaf, - m_vertical; - float m_area; - int m_level; - struct Partition *m_sub1, *m_sub2; -} Partition; - -extern Partition *g_place_rootPartition; - -void initPartitioning(); - -void incrementalPartition(); - -bool refinePartitions(); -void reallocPartitions(); -bool refinePartition(Partition *p); -void resizePartition(Partition *p); -void reallocPartition(Partition *p); - -void repartitionHMetis(Partition *parent); -void repartitionFM(Partition *parent); - -void partitionScanlineMincut(Partition *parent); -void partitionEqualArea(Partition *parent); - -void sanitizePlacement(); - -void constructQuadraticProblem(); -void solveQuadraticProblem(bool useCOG); - -#endif diff --git a/src/phys/place/place_inc.c b/src/phys/place/place_inc.c deleted file mode 100644 index 7e2d847c..00000000 --- a/src/phys/place/place_inc.c +++ /dev/null @@ -1,106 +0,0 @@ -/*===================================================================*/ -// -// place_inc.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include - -#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; nm_numTerms; t++) - nets[n]->m_terms[t]->m_data = -1; - - for(c=0; cm_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; nm_numTerms; t++) { - local_id = nets[n]->m_terms[t]->m_data; - if (local_id >= 0) - cell_numTerms[local_id]++; - } - - for(c=0; cm_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; passm_numTerms; t++); - } - } -} -#endif - -// -------------------------------------------------------------------- -// fastEstimate() -// -// -------------------------------------------------------------------- -float fastEstimate(ConcreteCell *cell, - int numNets, ConcreteNet *nets[]) { - float len = 0; - int n; - Rect box; - - assert(cell); - - for(n=0; nm_x < box.x) len += (box.x - cell->m_x); - if (cell->m_x > box.x+box.w) len += (cell->m_x-box.x-box.w); - if (cell->m_y < box.y) len += (box.x - cell->m_y); - if (cell->m_y > box.y+box.h) len += (cell->m_y-box.y-box.h); - } - - return len; -} diff --git a/src/phys/place/place_io.c b/src/phys/place/place_io.c deleted file mode 100644 index 8e24ef4a..00000000 --- a/src/phys/place/place_io.c +++ /dev/null @@ -1,94 +0,0 @@ -/*===================================================================*/ -// -// place_io.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include -#include - -#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; cm_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; cm_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; cm_id, - g_place_concreteCells[c]->m_x, - g_place_concreteCells[c]->m_y, - (g_place_concreteCells[c]->m_fixed ? "\\FIXED" : "")); - } - - fclose(plFile); - -} - - -// -------------------------------------------------------------------- -// writeBookshelf() -// -// -------------------------------------------------------------------- -void writeBookshelf(const char *filename) { - writeBookshelfNodes("out.nodes"); - writeBookshelfPl("out.pl"); -} diff --git a/src/phys/place/place_legalize.c b/src/phys/place/place_legalize.c deleted file mode 100644 index 950902f4..00000000 --- a/src/phys/place/place_legalize.c +++ /dev/null @@ -1,23 +0,0 @@ -/*===================================================================*/ -// -// place_legalize.c -// -// Aaron P. Hurst, 2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include - -#include "place_base.h" - - -// -------------------------------------------------------------------- -// legalize() -// -// -------------------------------------------------------------------- -void legalize() { - // UNIMPLEMENTED -} - diff --git a/src/phys/place/place_pads.c b/src/phys/place/place_pads.c deleted file mode 100644 index 361fac7f..00000000 --- a/src/phys/place/place_pads.c +++ /dev/null @@ -1,141 +0,0 @@ -/*===================================================================*/ -// -// place_pads.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include - -#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; cm_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; im_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; im_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; im_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; im_x = g_place_padBounds.x+cell->m_parent->m_width*0.5; - cell->m_y = g_place_padBounds.h+g_place_padBounds.y-cell->m_parent->m_height*0.5 - nextPos; - nextPos += (g_place_padBounds.h-padType->m_height) / westPads; - } - -} - diff --git a/src/phys/place/place_partition.c b/src/phys/place/place_partition.c deleted file mode 100644 index ea57cd1c..00000000 --- a/src/phys/place/place_partition.c +++ /dev/null @@ -1,1135 +0,0 @@ -/*===================================================================*/ -// -// place_partition.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include -#include -#include -//#include -//#include - -#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; im_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; im_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; im_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; nm_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; cm_x < initial_cut) - partitionAssignment[c] = 0; - else - partitionAssignment[c] = 1; - } - - // initialize cells in partition 1 - for(t=0; tm_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; tm_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; cm_y < initial_cut) - partitionAssignment[c] = 0; - else - partitionAssignment[c] = 1; - } - - // initialize cells in partition 1 - for(t=0; tm_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; tm_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; nm_numTerms > 1) - for(t=0; tm_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; tm_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::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::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::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::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::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::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::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::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::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(; im_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::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::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::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::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; cm_x < cut_loc) - newCells1[numNewCells1++] = newCells[c]; - else - newCells2[numNewCells2++] = newCells[c]; - } else { - cut_loc = p->m_sub2->m_bounds.y; - for(c=0; cm_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(; cm_numMembers && - allCells[c]->m_id > g_place_rootPartition->m_members[c2]->m_id) c2++; - while(c < g_place_numCells && - (c2 >= g_place_rootPartition->m_numMembers || - allCells[c]->m_id < g_place_rootPartition->m_members[c2]->m_id)) { - // a new cell! - newCells[numNewCells++] = allCells[c]; - c++; - } - } - - printf("QPRT-50 : \tincremental partitioning with %d new cells\n", numNewCells); - if (numNewCells>0) incrementalSubpartition(g_place_rootPartition, newCells, numNewCells); - - free(allCells); - free(newCells); -} diff --git a/src/phys/place/place_qpsolver.c b/src/phys/place/place_qpsolver.c deleted file mode 100644 index 9df9c6dc..00000000 --- a/src/phys/place/place_qpsolver.c +++ /dev/null @@ -1,1270 +0,0 @@ -/*===================================================================*/ -// -// place_qpsolver.c -// -// Philip Chong -// pchong@cadence.com -// -/*===================================================================*/ - -#include -#include -#include -#include - -#include "place_qpsolver.h" - -#undef QPS_DEBUG - -#define QPS_TOL 1.0e-3 -#define QPS_EPS (QPS_TOL * QPS_TOL) - -#define QPS_MAX_TOL 0.1 -#define QPS_LOOP_TOL 1.0e-3 - -#define QPS_RELAX_ITER 180 -#define QPS_MAX_ITER 200 -#define QPS_STEPSIZE_RETRIES 2 -#define QPS_MINSTEP 1.0e-6 -#define QPS_DEC_CHANGE 0.01 - -#define QPS_PRECON -#define QPS_PRECON_EPS 1.0e-9 - -#undef QPS_HOIST - -#if defined(QPS_DEBUG) -#define QPS_DEBUG_FILE "/tmp/qps_debug.log" -#endif - -#if 0 - /* ii is an array [0..p->num_cells-1] of indices from cells of original - problem to modified problem variables. If ii[k] >= 0, cell is an - independent cell; ii[k], ii[k]+1 are the indices of the corresponding - variables for the modified problem. If ii[k] == -1, cell is a fixed - cell. If ii[k] <= -2, cell is a dependent cell; -(ii[k]+2) is the index - of the corresponding COG constraint. */ -int *ii; - - /* gt is an array [0..p->cog_num-1] of indices from COG constraints to - locations in the gl array (in qps_problem_t). gt[k] is the offset into - gl where the kth constraint begins. */ -int *gt; - - /* n is the number of variables in the modified problem. n should be twice - the number of independent cells. */ -int n; - -qps_float_t *cp; /* current location during CG iteration */ -qps_float_t f; /* value of cost function at p */ - -#endif - -/**********************************************************************/ - -static void -qps_settp(qps_problem_t * p) -{ - /* Fill in the p->priv_tp array with the current locations of all cells - (independent, dependent and fixed). */ - - int i; - int t, u; - int pr; - qps_float_t rx, ry; - qps_float_t ta; - - int *ii = p->priv_ii; - qps_float_t *tp = p->priv_tp; - qps_float_t *cp = p->priv_cp; - - /* do independent and fixed cells first */ - for (i = p->num_cells; i--;) { - t = ii[i]; - if (t >= 0) { /* indep cell */ - tp[i * 2] = cp[t]; - tp[i * 2 + 1] = cp[t + 1]; - } - else if (t == -1) { /* fixed cell */ - tp[i * 2] = p->x[i]; - tp[i * 2 + 1] = p->y[i]; - } - } - /* now do dependent cells */ - for (i = p->num_cells; i--;) { - if (ii[i] < -1) { - t = -(ii[i] + 2); /* index of COG constraint */ - ta = 0.0; - rx = 0.0; - ry = 0.0; - pr = p->priv_gt[t]; - while ((u = p->cog_list[pr++]) >= 0) { - ta += p->area[u]; - if (u != i) { - rx -= p->area[u] * tp[u * 2]; - ry -= p->area[u] * tp[u * 2 + 1]; - } - } - rx += p->cog_x[t] * ta; - ry += p->cog_y[t] * ta; - tp[i * 2] = rx / p->area[i]; - tp[i * 2 + 1] = ry / p->area[i]; - } - } - -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_settp()\n"); - for (i = 0; i < p->num_cells; i++) { - fprintf(p->priv_fp, "%f %f\n", tp[i * 2], tp[i * 2 + 1]); - } -#endif -} - -/**********************************************************************/ - -static qps_float_t -qps_func(qps_problem_t * p) -{ - /* Return f(p). qps_settp() should have already been called before - entering here */ - - int j, k; - int pr; - qps_float_t jx, jy, tx, ty; - qps_float_t f; - qps_float_t w; - -#if !defined(QPS_HOIST) - int i; - int st; - qps_float_t kx, ky, sx, sy; - qps_float_t t; -#endif - - qps_float_t *tp = p->priv_tp; - - f = 0.0; - pr = 0; - for (j = 0; j < p->num_cells; j++) { - jx = tp[j * 2]; - jy = tp[j * 2 + 1]; - while ((k = p->priv_cc[pr]) >= 0) { - w = p->priv_cw[pr]; - tx = tp[k * 2] - jx; - ty = tp[k * 2 + 1] - jy; - f += w * (tx * tx + ty * ty); - pr++; - } - pr++; - } - p->f = f; - -#if !defined(QPS_HOIST) - /* loop penalties */ - pr = 0; - for (i = 0; i < p->loop_num; i++) { - t = 0.0; - j = st = p->loop_list[pr++]; - jx = sx = tp[j * 2]; - jy = sy = tp[j * 2 + 1]; - while ((k = p->loop_list[pr]) >= 0) { - kx = tp[k * 2]; - ky = tp[k * 2 + 1]; - tx = jx - kx; - ty = jy - ky; - t += tx * tx + ty * ty; - j = k; - jx = kx; - jy = ky; - pr++; - } - tx = jx - sx; - ty = jy - sy; - t += tx * tx + ty * ty; - t -= p->loop_max[i]; -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_penalty() %d %f %f\n", - i, p->loop_max[i], t); -#endif - p->priv_lt[i] = t; - f += p->loop_penalty[i] * t; - pr++; - } -#endif /* QPS_HOIST */ - - if (p->max_enable) { - for (j = p->num_cells; j--;) { - f += p->priv_mxl[j] * (-tp[j * 2]); - f += p->priv_mxh[j] * (tp[j * 2] - p->max_x); - f += p->priv_myl[j] * (-tp[j * 2 + 1]); - f += p->priv_myh[j] * (tp[j * 2 + 1] - p->max_y); - } - } - -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_func() %f %f\n", f, p->f); -#endif - return f; -} - -/**********************************************************************/ - -static void -qps_dfunc(qps_problem_t * p, qps_float_t * d) -{ - /* Set d to grad f(p). First computes partial derivatives wrt all cells - then finds gradient wrt only the independent cells. qps_settp() should - have already been called before entering here */ - - int i, j, k; - int pr = 0; - qps_float_t jx, jy, kx, ky, tx, ty; - int ji, ki; - qps_float_t w; - -#if !defined(QPS_HOIST) - qps_float_t sx, sy; - int st; -#endif - - qps_float_t *tp = p->priv_tp; - qps_float_t *tp2 = p->priv_tp2; - - /* compute partials and store in tp2 */ - for (i = p->num_cells; i--;) { - tp2[i * 2] = 0.0; - tp2[i * 2 + 1] = 0.0; - } - for (j = 0; j < p->num_cells; j++) { - jx = tp[j * 2]; - jy = tp[j * 2 + 1]; - while ((k = p->priv_cc[pr]) >= 0) { - w = 2.0 * p->priv_cw[pr]; - kx = tp[k * 2]; - ky = tp[k * 2 + 1]; - tx = w * (jx - kx); - ty = w * (jy - ky); - tp2[j * 2] += tx; - tp2[k * 2] -= tx; - tp2[j * 2 + 1] += ty; - tp2[k * 2 + 1] -= ty; - pr++; - } - pr++; - } - -#if !defined(QPS_HOIST) - /* loop penalties */ - pr = 0; - for (i = 0; i < p->loop_num; i++) { - j = st = p->loop_list[pr++]; - jx = sx = tp[j * 2]; - jy = sy = tp[j * 2 + 1]; - w = 2.0 * p->loop_penalty[i]; - while ((k = p->loop_list[pr]) >= 0) { - kx = tp[k * 2]; - ky = tp[k * 2 + 1]; - tx = w * (jx - kx); - ty = w * (jy - ky); - tp2[j * 2] += tx; - tp2[k * 2] -= tx; - tp2[j * 2 + 1] += ty; - tp2[k * 2 + 1] -= ty; - j = k; - jx = kx; - jy = ky; - pr++; - } - tx = w * (jx - sx); - ty = w * (jy - sy); - tp2[j * 2] += tx; - tp2[st * 2] -= tx; - tp2[j * 2 + 1] += ty; - tp2[st * 2 + 1] -= ty; - pr++; - } -#endif /* QPS_HOIST */ - - if (p->max_enable) { - for (j = p->num_cells; j--;) { - tp2[j * 2] += p->priv_mxh[j] - p->priv_mxl[j]; - tp2[j * 2 + 1] += p->priv_myh[j] - p->priv_myl[j]; - } - } - -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_dfunc() partials\n"); - for (j = 0; j < p->num_cells; j++) { - fprintf(p->priv_fp, "%f %f\n", tp2[j * 2], tp2[j * 2 + 1]); - } -#endif - - /* translate partials to independent variables */ - for (j = p->priv_n; j--;) { - d[j] = 0.0; - } - for (j = p->num_cells; j--;) { - ji = p->priv_ii[j]; - if (ji >= 0) { /* indep var */ - d[ji] += tp2[j * 2]; - d[ji + 1] += tp2[j * 2 + 1]; - } - else if (ji < -1) { /* dependent variable */ - ji = -(ji + 2); /* get COG index */ - pr = p->priv_gt[ji]; - while ((k = p->cog_list[pr]) >= 0) { - ki = p->priv_ii[k]; - if (ki >= 0) { - w = p->priv_gw[pr]; -#if (QPS_DEBUG > 0) - assert(fabs(w - p->area[k] / p->area[j]) < 1.0e-6); -#endif - d[ki] -= tp2[j * 2] * w; - d[ki + 1] -= tp2[j * 2 + 1] * w; - } - pr++; - } - } - } - -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_dfunc() gradient\n"); - for (j = 0; j < p->priv_n; j++) { - fprintf(p->priv_fp, "%f\n", d[j]); - } -#endif -} - -/**********************************************************************/ - -static void -qps_linmin(qps_problem_t * p, qps_float_t dgg, qps_float_t * h) -{ - /* Perform line minimization. p->priv_cp is the current location, h is - direction of the gradient. Updates p->priv_cp to line minimal position - based on formulas from "Handbook of Applied Optimization", Pardalos and - Resende, eds., Oxford Univ. Press, 2002. qps_settp() should have - already been called before entering here. Since p->priv_cp is changed, - p->priv_tp array becomes invalid following this routine. */ - - int i, j, k; - int pr; - int ji, ki; - qps_float_t jx, jy, kx, ky; - qps_float_t f = 0.0; - qps_float_t w; - -#if !defined(QPS_HOIST) - int st; - qps_float_t sx, sy, tx, ty; - qps_float_t t; -#endif - - qps_float_t *tp = p->priv_tp; - - /* translate h vector to partials over all variables and store in tp */ - for (i = p->num_cells; i--;) { - tp[i * 2] = 0.0; - tp[i * 2 + 1] = 0.0; - } - for (j = p->num_cells; j--;) { - ji = p->priv_ii[j]; - if (ji >= 0) { /* indep cell */ - tp[j * 2] = h[ji]; - tp[j * 2 + 1] = h[ji + 1]; - } - else if (ji < -1) { /* dep cell */ - ji = -(ji + 2); /* get COG index */ - pr = p->priv_gt[ji]; - while ((k = p->cog_list[pr]) >= 0) { - ki = p->priv_ii[k]; - if (ki >= 0) { - w = p->priv_gw[pr]; -#if (QPS_DEBUG > 0) - assert(fabs(w - p->area[k] / p->area[j]) < 1.0e-6); -#endif - tp[j * 2] -= h[ki] * w; - tp[j * 2 + 1] -= h[ki + 1] * w; - } - pr++; - } - } - } - - /* take product x^T Z^T C Z x */ - pr = 0; - for (j = 0; j < p->num_cells; j++) { - jx = tp[j * 2]; - jy = tp[j * 2 + 1]; - while ((k = p->priv_cc[pr]) >= 0) { - w = p->priv_cw[pr]; - kx = tp[k * 2] - jx; - ky = tp[k * 2 + 1] - jy; - f += w * (kx * kx + ky * ky); - pr++; - } - pr++; - } - -#if !defined(QPS_HOIST) - /* add loop penalties */ - pr = 0; - for (i = 0; i < p->loop_num; i++) { - t = 0.0; - j = st = p->loop_list[pr++]; - jx = sx = tp[j * 2]; - jy = sy = tp[j * 2 + 1]; - while ((k = p->loop_list[pr]) >= 0) { - kx = tp[k * 2]; - ky = tp[k * 2 + 1]; - tx = jx - kx; - ty = jy - ky; - t += tx * tx + ty * ty; - j = k; - jx = kx; - jy = ky; - pr++; - } - tx = jx - sx; - ty = jy - sy; - t += tx * tx + ty * ty; - f += p->loop_penalty[i] * t; - pr++; - } -#endif /* QPS_HOIST */ - -#if (QPS_DEBUG > 0) - assert(f); -#endif - - /* compute step size */ - f = (dgg / f) / 2.0; - for (j = p->priv_n; j--;) { - p->priv_cp[j] += f * h[j]; - } -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_linmin() step %f\n", f); - for (j = 0; j < p->priv_n; j++) { - fprintf(p->priv_fp, "%f\n", p->priv_cp[j]); - } -#endif -} - -/**********************************************************************/ - -static void -qps_cgmin(qps_problem_t * p) -{ - /* Perform CG minimization. Mostly from "Numerical Recipes", Press et al., - Cambridge Univ. Press, 1992, with some changes to help performance in - our restricted problem domain. */ - - qps_float_t fp, gg, dgg, gam; - qps_float_t t; - int i, j; - - int n = p->priv_n; - qps_float_t *g = p->priv_g; - qps_float_t *h = p->priv_h; - qps_float_t *xi = p->priv_xi; - - qps_settp(p); - fp = qps_func(p); - qps_dfunc(p, g); - - dgg = 0.0; - for (j = n; j--;) { - g[j] = -g[j]; - h[j] = g[j]; -#if defined(QPS_PRECON) - h[j] *= p->priv_pcgt[j]; -#endif - dgg += g[j] * h[j]; - } - - for (i = 0; i < 2 * n; i++) { - -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### qps_cgmin() top\n"); - for (j = 0; j < p->priv_n; j++) { - fprintf(p->priv_fp, "%f\n", p->priv_cp[j]); - } -#endif - - if (dgg == 0.0) { - break; - } - qps_linmin(p, dgg, h); - qps_settp(p); - p->priv_f = qps_func(p); - if (fabs((p->priv_f) - fp) <= - (fabs(p->priv_f) + fabs(fp) + QPS_EPS) * QPS_TOL / 2.0) { - break; - } - fp = p->priv_f; - qps_dfunc(p, xi); - gg = dgg; - dgg = 0.0; - for (j = n; j--;) { - t = xi[j] * xi[j]; -#if defined(QPS_PRECON) - t *= p->priv_pcgt[j]; -#endif - dgg += t; - } - gam = dgg / gg; - for (j = n; j--;) { - g[j] = -xi[j]; - t = g[j]; -#if defined(QPS_PRECON) - t *= p->priv_pcgt[j]; -#endif - h[j] = t + gam * h[j]; - } - } -#if (QPS_DEBUG > 0) - fprintf(p->priv_fp, "### CG ITERS=%d %d %d\n", i, p->cog_num, p->loop_num); -#endif - if (i == 2 * n) { - fprintf(stderr, "### Too many iterations in qps_cgmin()\n"); -#if defined(QPS_DEBUG) - fprintf(p->priv_fp, "### Too many iterations in qps_cgmin()\n"); -#endif - } -} - -/**********************************************************************/ - -void -qps_init(qps_problem_t * p) -{ - int i, j; - int pr, pw; - -#if defined(QPS_DEBUG) - p->priv_fp = fopen(QPS_DEBUG_FILE, "a"); - assert(p->priv_fp); -#endif - -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### n=%d gn=%d ln=%d\n", p->num_cells, p->cog_num, - p->loop_num); - pr = 0; - fprintf(p->priv_fp, "### (c w) values\n"); - for (i = 0; i < p->num_cells; i++) { - fprintf(p->priv_fp, "net %d: ", i); - while (p->connect[pr] >= 0) { - fprintf(p->priv_fp, "(%d %f) ", p->connect[pr], p->edge_weight[pr]); - pr++; - } - fprintf(p->priv_fp, "(-1 -1.0)\n"); - pr++; - } - fprintf(p->priv_fp, "### (x y f) values\n"); - for (i = 0; i < p->num_cells; i++) { - fprintf(p->priv_fp, "cell %d: (%f %f %d)\n", i, p->x[i], p->y[i], - p->fixed[i]); - } -#if 0 - if (p->cog_num) { - fprintf(p->priv_fp, "### ga values\n"); - for (i = 0; i < p->num_cells; i++) { - fprintf(p->priv_fp, "cell %d: (%f)\n", i, p->area[i]); - } - } - pr = 0; - fprintf(p->priv_fp, "### gl values\n"); - for (i = 0; i < p->cog_num; i++) { - fprintf(p->priv_fp, "cog %d: ", i); - while (p->cog_list[pr] >= 0) { - fprintf(p->priv_fp, "%d ", p->cog_list[pr]); - pr++; - } - fprintf(p->priv_fp, "-1\n"); - pr++; - } - fprintf(p->priv_fp, "### (gx gy) values\n"); - for (i = 0; i < p->cog_num; i++) { - fprintf(p->priv_fp, "cog %d: (%f %f)\n", i, p->cog_x[i], p->cog_y[i]); - } -#endif -#endif /* QPS_DEBUG */ - - p->priv_ii = (int *)malloc(p->num_cells * sizeof(int)); - assert(p->priv_ii); - - p->max_enable = 0; - - p->priv_fopt = 0.0; - - /* canonify c and w */ - pr = pw = 0; - for (i = 0; i < p->num_cells; i++) { - while ((j = p->connect[pr]) >= 0) { - if (j > i) { - pw++; - } - pr++; - } - pw++; - pr++; - } - p->priv_cc = (int *)malloc(pw * sizeof(int)); - assert(p->priv_cc); - p->priv_cr = (int *)malloc(p->num_cells * sizeof(int)); - assert(p->priv_cr); - p->priv_cw = (qps_float_t*)malloc(pw * sizeof(qps_float_t)); - assert(p->priv_cw); - p->priv_ct = (qps_float_t*)malloc(pw * sizeof(qps_float_t)); - assert(p->priv_ct); - p->priv_cm = pw; - pr = pw = 0; - for (i = 0; i < p->num_cells; i++) { - p->priv_cr[i] = pw; - while ((j = p->connect[pr]) >= 0) { - if (j > i) { - p->priv_cc[pw] = p->connect[pr]; - p->priv_ct[pw] = p->edge_weight[pr]; - pw++; - } - pr++; - } - p->priv_cc[pw] = -1; - p->priv_ct[pw] = -1.0; - pw++; - pr++; - } - assert(pw == p->priv_cm); - - /* temp arrays for function eval */ - p->priv_tp = (qps_float_t *) malloc(4 * p->num_cells * sizeof(qps_float_t)); - assert(p->priv_tp); - p->priv_tp2 = p->priv_tp + 2 * p->num_cells; -} - -/**********************************************************************/ - -static qps_float_t -qps_estopt(qps_problem_t * p) -{ - int i, j, cell; - qps_float_t r; - qps_float_t *t1, *t2; - qps_float_t t; - - if (p->max_enable) { - r = 0.0; - t1 = (qps_float_t *) malloc(2 * p->num_cells * sizeof(qps_float_t)); -#if (QPS_DEBUG > 0) - assert(t1); -#endif - for (i = 2 * p->num_cells; i--;) { - t1[i] = 0.0; - } - j = 0; - for (i = 0; i < p->cog_num; i++) { - while ((cell = p->cog_list[j]) >= 0) { - t1[cell * 2] = p->cog_x[i]; - t1[cell * 2 + 1] = p->cog_y[i]; - j++; - } - j++; - } - t2 = p->priv_tp; - p->priv_tp = t1; - r = qps_func(p); - p->priv_tp = t2; - free(t1); - t = (p->max_x * p->max_x + p->max_y * p->max_y); - t *= p->num_cells; - for (i = p->num_cells; i--;) { - if (p->fixed[i]) { - r += t; - } - } - } - else { - r = p->priv_f; - } - if (p->loop_num) { - /* FIXME hacky */ - r *= 8.0; - } - return r; -} - -/**********************************************************************/ - -static void -qps_solve_inner(qps_problem_t * p) -{ - int i; - qps_float_t t; - qps_float_t z; - qps_float_t pm1, pm2, tp; - qps_float_t *tw; -#if defined(QPS_HOIST) - int j, k; - qps_float_t jx, jy, kx, ky, sx, sy, tx, ty; - int pr, st; -#endif - - tw = p->priv_cw; -#if defined(QPS_HOIST) - if (!p->loop_num) { - p->priv_cw = p->priv_ct; - } - else { - for(i=p->priv_cm; i--;) { - p->priv_cw[i] = p->priv_ct[i]; - } - /* augment with loop penalties */ - pr = 0; - for (i = 0; i < p->loop_num; i++) { - while ((j = p->priv_la[pr++]) != -1) { - if (j >= 0) { - p->priv_cw[j] += p->loop_penalty[i]; - } - } - pr++; - } - } -#else /* !QPS_HOIST */ - p->priv_cw = p->priv_ct; -#endif /* QPS_HOIST */ - - qps_cgmin(p); - - if (p->max_enable || p->loop_num) { - if (p->max_enable == 1 || (p->loop_num && p->loop_k == 0)) { - p->priv_eps = 2.0; - p->priv_fmax = p->priv_f; - p->priv_fprev = p->priv_f; - p->priv_fopt = qps_estopt(p); - p->priv_pn = 0; - p->loop_fail = 0; - } - else { - if (p->priv_f < p->priv_fprev && - (p->priv_fprev - p->priv_f) > - QPS_DEC_CHANGE * fabs(p->priv_fprev)) { - if (p->priv_pn++ >= QPS_STEPSIZE_RETRIES) { - p->priv_eps /= 2.0; - p->priv_pn = 0; - } - } - p->priv_fprev = p->priv_f; - if (p->priv_fmax < p->priv_f) { - p->priv_fmax = p->priv_f; - } - if (p->priv_f >= p->priv_fopt) { - p->priv_fopt = p->priv_fmax * 2.0; - p->loop_fail |= 2; -#if (QPS_DEBUG > 0) - fprintf(p->priv_fp, "### warning: changing fopt\n"); -#endif - } - } -#if (QPS_DEBUG > 0) - fprintf(p->priv_fp, "### max_stat %.2e %.2e %.2e %.2e\n", - p->priv_f, p->priv_eps, p->priv_fmax, p->priv_fopt); - fflush(p->priv_fp); -#endif - } - - p->loop_done = 1; - if (p->loop_num) { -#if (QPS_DEBUG > 0) - fprintf(p->priv_fp, "### begin_update %d\n", p->loop_k); -#endif - p->loop_k++; - -#if defined(QPS_HOIST) - /* calc loop penalties */ - pr = 0; - for (i = 0; i < p->loop_num; i++) { - t = 0.0; - j = st = p->loop_list[pr++]; - jx = sx = p->priv_tp[j * 2]; - jy = sy = p->priv_tp[j * 2 + 1]; - while ((k = p->loop_list[pr]) >= 0) { - kx = p->priv_tp[k * 2]; - ky = p->priv_tp[k * 2 + 1]; - tx = jx - kx; - ty = jy - ky; - t += tx * tx + ty * ty; - j = k; - jx = kx; - jy = ky; - pr++; - } - tx = jx - sx; - ty = jy - sy; - t += tx * tx + ty * ty; - p->priv_lt[i] = t - p->loop_max[i]; - pr++; - } -#endif /* QPS_HOIST */ - - /* check KKT conditions */ -#if (QPS_DEBUG > 1) - for (i = p->loop_num; i--;) { - if (p->loop_penalty[i] != 0.0) { - fprintf(p->priv_fp, "### penalty %d %.2e\n", i, p->loop_penalty[i]); - } - } -#endif - t = 0.0; - for (i = p->loop_num; i--;) { - if (p->priv_lt[i] > 0.0 || p->loop_penalty[i] > 0.0) { - t += p->priv_lt[i] * p->priv_lt[i]; - } - if (fabs(p->priv_lt[i]) < QPS_LOOP_TOL) { -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### skip %d %f\n", i, p->priv_lt[i]); -#endif - continue; - } - z = QPS_LOOP_TOL * p->loop_max[i]; - if (p->priv_lt[i] > z || (p->loop_k < QPS_RELAX_ITER && - p->loop_penalty[i] * p->priv_lt[i] < -z)) { - p->loop_done = 0; -#if (QPS_DEBUG > 1) - fprintf(p->priv_fp, "### not_done %d %f %f %f %f\n", i, - p->priv_lt[i], z, p->loop_max[i], p->loop_penalty[i]); -#endif - } -#if (QPS_DEBUG > 5) - else { - fprintf(p->priv_fp, "### done %d %f %f %f %f\n", i, - p->priv_lt[i], z, p->loop_max[i], p->loop_penalty[i]); - } -#endif - } - /* update penalties */ - if (!p->loop_done) { - t = p->priv_eps * (p->priv_fopt - p->priv_f) / t; - tp = 0.0; - for (i = p->loop_num; i--;) { - pm1 = p->loop_penalty[i]; -#if (QPS_DEBUG > 5) - fprintf(p->priv_fp, "### update %d %.2e %.2e %.2e %.2e %.2e\n", i, - t, p->priv_lt[i], t * p->priv_lt[i], pm1, p->loop_max[i]); -#endif - p->loop_penalty[i] += t * p->priv_lt[i]; - if (p->loop_penalty[i] < 0.0) { - p->loop_penalty[i] = 0.0; - } - pm2 = p->loop_penalty[i]; - tp += fabs(pm1 - pm2); - } -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### penalty mag %f\n", tp); -#endif - } - } - - p->max_done = 1; - if (p->max_enable) { -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### begin_max_update %d\n", p->max_enable); -#endif - t = 0.0; - for (i = p->num_cells; i--;) { - z = -(p->x[i]); - t += z * z; - if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER && - p->priv_mxl[i] * z < -QPS_MAX_TOL)) { - p->max_done = 0; -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### nxl %d %f %f\n", i, z, p->priv_mxl[i]); -#endif - } - z = (p->x[i] - p->max_x); - t += z * z; - if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER && - p->priv_mxh[i] * z < -QPS_MAX_TOL)) { - p->max_done = 0; -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### nxh %d %f %f\n", i, z, p->priv_mxh[i]); -#endif - } - z = -(p->y[i]); - t += z * z; - if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER && - p->priv_myl[i] * z < -QPS_MAX_TOL)) { - p->max_done = 0; -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### nyl %d %f %f\n", i, z, p->priv_myl[i]); -#endif - } - z = (p->y[i] - p->max_y); - t += z * z; - if (z > QPS_TOL || (p->max_enable < QPS_RELAX_ITER && - p->priv_myh[i] * z < -QPS_MAX_TOL)) { - p->max_done = 0; -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### nyh %d %f %f\n", i, z, p->priv_myh[i]); -#endif - } - } -#if (QPS_DEBUG > 4) - fprintf(p->priv_fp, "### max_done %d %f\n", p->max_done, t); -#endif - if (!p->max_done) { - t = p->priv_eps * (p->priv_fopt - p->priv_f) / t; - tp = 0.0; - for (i = p->num_cells; i--;) { - z = -(p->x[i]); - pm1 = p->priv_mxl[i]; - p->priv_mxl[i] += t * z; - if (p->priv_mxl[i] < 0.0) { - p->priv_mxl[i] = 0.0; - } - pm2 = p->priv_mxl[i]; - tp += fabs(pm1 - pm2); - - z = (p->x[i] - p->max_x); - pm1 = p->priv_mxh[i]; - p->priv_mxh[i] += t * z; - if (p->priv_mxh[i] < 0.0) { - p->priv_mxh[i] = 0.0; - } - pm2 = p->priv_mxh[i]; - tp += fabs(pm1 - pm2); - - z = -(p->y[i]); - pm1 = p->priv_myl[i]; - p->priv_myl[i] += t * z; - if (p->priv_myl[i] < 0.0) { - p->priv_myl[i] = 0.0; - } - pm2 = p->priv_myl[i]; - tp += fabs(pm1 - pm2); - - z = (p->y[i] - p->max_y); - pm1 = p->priv_myh[i]; - p->priv_myh[i] += t * z; - if (p->priv_myh[i] < 0.0) { - p->priv_myh[i] = 0.0; - } - pm2 = p->priv_myh[i]; - tp += fabs(pm1 - pm2); - } - } -#if (QPS_DEBUG > 4) - for (i = p->num_cells; i--;) { - fprintf(p->priv_fp, "### max_penalty %d %f %f %f %f\n", i, - p->priv_mxl[i], p->priv_mxh[i], p->priv_myl[i], p->priv_myh[i]); - } -#endif - p->max_enable++; - } - - if (p->loop_k >= QPS_MAX_ITER || p->priv_eps < QPS_MINSTEP) { - p->loop_fail |= 1; - } - - if (p->loop_fail) { - p->loop_done = 1; - } - - p->priv_cw = tw; -} - -/**********************************************************************/ - -void -qps_solve(qps_problem_t * p) -{ - int i, j; - int pr, pw; - qps_float_t bk; - int tk; - -#if defined(QPS_PRECON) - int c; - qps_float_t t; -#endif - -#if defined(QPS_HOIST) - int k; - int st; - int m1, m2; -#endif - - if (p->max_enable) { - p->priv_mxl = (qps_float_t *) - malloc(4 * p->num_cells * sizeof(qps_float_t)); - assert(p->priv_mxl); - p->priv_mxh = p->priv_mxl + p->num_cells; - p->priv_myl = p->priv_mxl + 2 * p->num_cells; - p->priv_myh = p->priv_mxl + 3 * p->num_cells; - for (i = 4 * p->num_cells; i--;) { - p->priv_mxl[i] = 0.0; - } - } - - /* flag fixed cells with -1 */ - for (i = p->num_cells; i--;) { - p->priv_ii[i] = (p->fixed[i]) ? (-1) : (0); - } - - /* read gl and set up dependent variables */ - if (p->cog_num) { - p->priv_gt = (int *)malloc(p->cog_num * sizeof(int)); - assert(p->priv_gt); - p->priv_gm = (qps_float_t*)malloc(p->cog_num * sizeof(qps_float_t)); - assert(p->priv_gm); - pr = 0; - for (i = 0; i < p->cog_num; i++) { - tk = -1; - bk = -1.0; - pw = pr; - while ((j = p->cog_list[pr++]) >= 0) { - if (!p->fixed[j]) { - /* use largest entry for numerical stability; see Gordian paper */ - if (p->area[j] > bk) { - tk = j; - bk = p->area[j]; - } - } - } - assert(bk > 0.0); - /* dependent variables have index=(-2-COG_constraint) */ - p->priv_ii[tk] = -2 - i; - p->priv_gt[i] = pw; - p->priv_gm[i] = bk; - } - p->priv_gw = (qps_float_t*)malloc(pr * sizeof(qps_float_t)); - assert(p->priv_gw); - pr = 0; - for (i = 0; i < p->cog_num; i++) { - while ((j = p->cog_list[pr]) >= 0) { - p->priv_gw[pr] = p->area[j] / p->priv_gm[i]; - pr++; - } - p->priv_gw[pr] = -1.0; - pr++; - } - } - - /* set up indexes from independent floating cells to variables */ - p->priv_n = 0; - for (i = p->num_cells; i--;) { - if (!p->priv_ii[i]) { - p->priv_ii[i] = 2 * (p->priv_n++); - } - } - p->priv_n *= 2; - -#if (QPS_DEBUG > 5) - for (i = 0; i < p->num_cells; i++) { - fprintf(p->priv_fp, "### ii %d %d\n", i, p->priv_ii[i]); - } -#endif - -#if defined(QPS_PRECON) - p->priv_pcg = (qps_float_t *) malloc(p->num_cells * sizeof(qps_float_t)); - assert(p->priv_pcg); - p->priv_pcgt = (qps_float_t *) malloc(p->priv_n * sizeof(qps_float_t)); - assert(p->priv_pcgt); - for (i = p->num_cells; i--;) { - p->priv_pcg[i] = 0.0; - } - pr = 0; - for (i = 0; i < p->num_cells; i++) { - while ((c = p->priv_cc[pr]) >= 0) { - t = p->priv_ct[pr]; - p->priv_pcg[i] += t; - p->priv_pcg[c] += t; - pr++; - } - pr++; - } - pr = 0; - for (i = 0; i < p->loop_num; i++) { - t = 2.0 * p->loop_penalty[i]; - while ((c = p->loop_list[pr++]) >= 0) { - p->priv_pcg[c] += t; - } - pr++; - } -#if (QPS_DEBUG > 6) - for (i = p->num_cells; i--;) { - fprintf(p->priv_fp, "### precon %d %.2e\n", i, p->priv_pcg[i]); - } -#endif - for (i = p->priv_n; i--;) { - p->priv_pcgt[i] = 0.0; - } - for (i = 0; i < p->num_cells; i++) { - c = p->priv_ii[i]; - if (c >= 0) { - t = p->priv_pcg[i]; - p->priv_pcgt[c] += t; - p->priv_pcgt[c + 1] += t; - } -#if 0 - else if (c < -1) { - pr = p->priv_gt[-(c+2)]; - while ((j = p->cog_list[pr++]) >= 0) { - ji = p->priv_ii[j]; - if (ji >= 0) { - w = p->area[j] / p->area[i]; - t = w * w * p->priv_pcg[i]; - p->priv_pcgt[ji] += t; - p->priv_pcgt[ji + 1] += t; - } - } - } -#endif - } - for (i = 0; i < p->priv_n; i++) { - t = p->priv_pcgt[i]; - if (fabs(t) < QPS_PRECON_EPS || fabs(t) > 1.0/QPS_PRECON_EPS) { - p->priv_pcgt[i] = 1.0; - } - else { - p->priv_pcgt[i] = 1.0 / p->priv_pcgt[i]; - } - } -#endif - - /* allocate variable storage */ - p->priv_cp = (qps_float_t *) malloc(4 * p->priv_n * sizeof(qps_float_t)); - assert(p->priv_cp); - - /* temp arrays for cg */ - p->priv_g = p->priv_cp + p->priv_n; - p->priv_h = p->priv_cp + 2 * p->priv_n; - p->priv_xi = p->priv_cp + 3 * p->priv_n; - - /* set values */ - for (i = p->num_cells; i--;) { - if (p->priv_ii[i] >= 0) { - p->priv_cp[p->priv_ii[i]] = p->x[i]; - p->priv_cp[p->priv_ii[i] + 1] = p->y[i]; - } - } - - if (p->loop_num) { - p->priv_lt = (qps_float_t *) malloc(p->loop_num * sizeof(qps_float_t)); - assert(p->priv_lt); -#if defined(QPS_HOIST) - pr = 0; - for (i=p->loop_num; i--;) { - while (p->loop_list[pr++] >= 0) { - } - pr++; - } - p->priv_lm = pr; - p->priv_la = (int *) malloc(pr * sizeof(int)); - assert(p->priv_la); - pr = 0; - for (i = 0; i < p->loop_num; i++) { - j = st = p->loop_list[pr++]; - while ((k = p->loop_list[pr]) >= 0) { - if (j > k) { - m1 = k; - m2 = j; - } - else { - assert(k > j); - m1 = j; - m2 = k; - } - pw = p->priv_cr[m1]; - while (p->priv_cc[pw] != m2) { -/* assert(p->priv_cc[pw] >= 0); */ - if (p->priv_cc[pw] < 0) { - pw = -2; - break; - } - pw++; - } - p->priv_la[pr-1] = pw; - j = k; - pr++; - } - if (j > st) { - m1 = st; - m2 = j; - } - else { - assert(st > j); - m1 = j; - m2 = st; - } - pw = p->priv_cr[m1]; - while (p->priv_cc[pw] != m2) { -/* assert(p->priv_cc[pw] >= 0); */ - if (p->priv_cc[pw] < 0) { - pw = -2; - break; - } - pw++; - } - p->priv_la[pr-1] = pw; - p->priv_la[pr] = -1; - pr++; - } -#endif /* QPS_HOIST */ - } - - do { - qps_solve_inner(p); - } while (!p->loop_done || !p->max_done); - - /* retrieve values */ - /* qps_settp() should have already been called at this point */ - for (i = p->num_cells; i--;) { - p->x[i] = p->priv_tp[i * 2]; - p->y[i] = p->priv_tp[i * 2 + 1]; - } -#if (QPS_DEBUG > 5) - for (i = p->num_cells; i--;) { - fprintf(p->priv_fp, "### cloc %d %f %f\n", i, p->x[i], p->y[i]); - } -#endif - - free(p->priv_cp); - if (p->max_enable) { - free(p->priv_mxl); - } - if (p->cog_num) { - free(p->priv_gt); - free(p->priv_gm); - free(p->priv_gw); - } - if(p->loop_num) { - free(p->priv_lt); -#if defined(QPS_HOIST) - free(p->priv_la); -#endif - } - -#if defined(QPS_PRECON) - free(p->priv_pcg); - free(p->priv_pcgt); -#endif -} - -/**********************************************************************/ - -void -qps_clean(qps_problem_t * p) -{ - free(p->priv_tp); - free(p->priv_ii); - free(p->priv_cc); - free(p->priv_cr); - free(p->priv_cw); - free(p->priv_ct); - -#if defined(QPS_DEBUG) - fclose(p->priv_fp); -#endif /* QPS_DEBUG */ -} - -/**********************************************************************/ diff --git a/src/phys/place/place_qpsolver.h b/src/phys/place/place_qpsolver.h deleted file mode 100644 index 08771d6b..00000000 --- a/src/phys/place/place_qpsolver.h +++ /dev/null @@ -1,140 +0,0 @@ -/*===================================================================*/ -// -// place_qpsolver.h -// -// Philip Chong -// pchong@cadence.com -// -/*===================================================================*/ - -#if !defined(_QPS_H) -#define _QPS_H - -#include - -#if defined(__cplusplus) -extern "C" { -#endif /* __cplusplus */ - - typedef float qps_float_t; - - typedef struct qps_problem { - - /* Basic stuff */ - int num_cells; /* Total number of cells (both fixed and - floating) to be placed. */ - int *connect; /* Connectivity array. Must contain at least - num_cells elements with value -1. The - entries which precede the first element - with value -1 are the indices of the cells - which connect to cell 0; the entries - which lie between the first and second - elements with value -1 are the indices of - the cells which connect to cell 1; etc. - Example: cells 0 and 1 are connected - together, and 1 and 2 are connected as - well. *connect = { 1, -1, 0, 2, -1, 1, -1 - }. */ - qps_float_t *edge_weight; /* Same structure as connectivity array, but - giving the weights assigned to each edge - instead. */ - qps_float_t *x; /* num_cells element array which contains the - x-coordinates of the cells. This is used - for the initial values in the iterative - solution of floating cells, and for the - fixed location of fixed cells. */ - qps_float_t *y; /* num_cells element array of - y-coordinates. */ - int *fixed; /* num_cells element array with value 1 if - corresponding cell is fixed, 0 if - floating. */ - qps_float_t f; /* return value for sum-of-square - wirelengths. */ - - /* COG stuff */ - int cog_num; /* Number of COG constraints. */ - int *cog_list; /* Array indicating for each COG constraint - which cells belong to that constraint. - Format is similar to c array: there must - be at least cog_num elements with value - -1. The entries of cog_list preceding the - first -1 element are the indices of the - cells which belong to the first COG - constraint; etc. Example: cells 0 and 1 - belong to one COG constraint, cells 4 and - 5 belong to another. *cog_list= { 0, 1, - -1, 4, 5, -1 }. */ - qps_float_t *cog_x; /* cog_num element array whose values are the - x-coordinates for the corresponding COG - constraints. */ - qps_float_t *cog_y; /* cog_num element array whose values are the - y-coordinates for the corresponding COG - constraints. */ - qps_float_t *area; /* num_cells element array whose values are - the areas for the corresponding cells; - only useful with COG constraints. */ - - /* Loop constraint stuff */ - int loop_num; /* Number of loop constraints. */ - int *loop_list; /* Array with list of cells for each loop - constraint. Format is similar to cog_list. - */ - qps_float_t *loop_max; /* loop_num element array indicating maximum - distance for each loop. */ - qps_float_t *loop_penalty; /* loop_num element array indicating penalty - for each loop. */ - int loop_k; /* Current iteration for loop optimization. */ - int loop_done; /* Done flag for loop optimization. */ - int loop_fail; - - /* max_x/max_y stuff */ - qps_float_t max_x; /* max x location; only used in - constrained optimization. */ - qps_float_t max_y; /* max y location; only used in - constrained optimization. */ - int max_enable; /* Set to 1 after qps_init() to enable - max_x/max_y. */ - int max_done; /* Done flag for max optimization. */ - - /* Private stuff */ - int *priv_ii; - int *priv_cc, *priv_cr; - qps_float_t *priv_cw, *priv_ct; - int priv_cm; - int *priv_gt; - int *priv_la; - int priv_lm; - qps_float_t *priv_gm, *priv_gw; - qps_float_t *priv_g, *priv_h, *priv_xi; - qps_float_t *priv_tp, *priv_tp2; - int priv_n; - qps_float_t *priv_cp; - qps_float_t priv_f; - qps_float_t *priv_lt; - qps_float_t *priv_pcg, *priv_pcgt; - qps_float_t priv_fmax; - qps_float_t priv_fprev; - qps_float_t priv_fopt; - qps_float_t priv_eps; - int priv_pn; - qps_float_t *priv_mxl, *priv_mxh, *priv_myl, *priv_myh; - int priv_ik; - FILE *priv_fp; - - } qps_problem_t; - - /* call qps_init() as soon as the qps_problem_t has been set up */ - /* this initializes some private data structures */ - extern void qps_init(qps_problem_t *); - - /* call qps_solve() to solve the given qp problem */ - extern void qps_solve(qps_problem_t *); - - /* call qps_clean() when finished with the qps_problem_t */ - /* this discards the private data structures assigned by qps_init() */ - extern void qps_clean(qps_problem_t *); - -#if defined(__cplusplus) -} -#endif /* __cplusplus */ -#endif /* _QPS_H */ diff --git a/src/phys/place/place_test.c b/src/phys/place/place_test.c deleted file mode 100644 index ea706a09..00000000 --- a/src/phys/place/place_test.c +++ /dev/null @@ -1,360 +0,0 @@ -/*===================================================================*/ -// -// place_test.c -// -// Aaron P. Hurst, 2003-2007 -// ahurst@eecs.berkeley.edu -// -/*===================================================================*/ - -#include -#include -#include -#include -#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; pm_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; cm_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; tm_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; -} -- cgit v1.2.3