summaryrefslogtreecommitdiffstats
path: root/src/phys/place/place_genqp.c
diff options
context:
space:
mode:
authorAlan Mishchenko <alanmi@berkeley.edu>2008-01-30 08:01:00 -0800
committerAlan Mishchenko <alanmi@berkeley.edu>2008-01-30 08:01:00 -0800
commit4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (patch)
tree366355938a4af0a92f848841ac65374f338d691b /src/phys/place/place_genqp.c
parent6537f941887b06e588d3acfc97b5fdf48875cc4e (diff)
downloadabc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.gz
abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.bz2
abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.zip
Version abc80130
Diffstat (limited to 'src/phys/place/place_genqp.c')
-rw-r--r--src/phys/place/place_genqp.c309
1 files changed, 0 insertions, 309 deletions
diff --git a/src/phys/place/place_genqp.c b/src/phys/place/place_genqp.c
deleted file mode 100644
index 5b6c7027..00000000
--- a/src/phys/place/place_genqp.c
+++ /dev/null
@@ -1,309 +0,0 @@
-/*===================================================================*/
-//
-// place_genqp.c
-//
-// Aaron P. Hurst, 2003-2007
-// ahurst@eecs.berkeley.edu
-//
-/*===================================================================*/
-
-#include <stdlib.h>
-#include <math.h>
-#include <stdio.h>
-#include <string.h>
-#include <assert.h>
-
-#include "place_base.h"
-#include "place_qpsolver.h"
-#include "place_gordian.h"
-
-// --------------------------------------------------------------------
-// Global variables
-//
-// --------------------------------------------------------------------
-
-qps_problem_t *g_place_qpProb = NULL;
-
-
-// --------------------------------------------------------------------
-// splitPenalty()
-//
-/// \brief Returns a weight for all of the edges in the clique for a multipin net.
-//
-// --------------------------------------------------------------------
-float splitPenalty(int pins) {
-
- if (pins > 1) {
- return 1.0 + CLIQUE_PENALTY/(pins - 1);
- // return pow(pins - 1, CLIQUE_PENALTY);
- }
- return 1.0 + CLIQUE_PENALTY;
-}
-
-
-// --------------------------------------------------------------------
-// constructQuadraticProblem()
-//
-/// \brief Constructs the matrices necessary to do analytical placement.
-//
-// --------------------------------------------------------------------
-void constructQuadraticProblem() {
- int maxConnections = 1;
- int ignoreNum = 0;
- int n,t,c,c2,p;
- ConcreteCell *cell;
- ConcreteNet *net;
- int *cell_numTerms = calloc(g_place_numCells, sizeof(int));
- ConcreteNet ***cell_terms = calloc(g_place_numCells, sizeof(ConcreteNet**));
- bool incremental = false;
- int nextIndex = 1;
- int *seen = calloc(g_place_numCells, sizeof(int));
- float weight;
- int last_index;
-
- // create problem object
- if (!g_place_qpProb) {
- g_place_qpProb = malloc(sizeof(qps_problem_t));
- g_place_qpProb->area = NULL;
- g_place_qpProb->x = NULL;
- g_place_qpProb->y = NULL;
- g_place_qpProb->fixed = NULL;
- g_place_qpProb->connect = NULL;
- g_place_qpProb->edge_weight = NULL;
- }
-
- // count the maximum possible number of non-sparse entries
- for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) {
- ConcreteNet *net = g_place_concreteNets[n];
- if (net->m_numTerms > IGNORE_NETSIZE) {
- ignoreNum++;
- }
- else {
- maxConnections += net->m_numTerms*(net->m_numTerms-1);
- for(t=0; t<net->m_numTerms; t++) {
- c = net->m_terms[t]->m_id;
- p = ++cell_numTerms[c];
- cell_terms[c] = (ConcreteNet**)realloc(cell_terms[c], p*sizeof(ConcreteNet*));
- cell_terms[c][p-1] = net;
- }
- }
- }
- if(ignoreNum) {
- printf("QMAN-10 : \t\t%d large nets ignored\n", ignoreNum);
- }
-
- // initialize the data structures
- g_place_qpProb->num_cells = g_place_numCells;
- maxConnections += g_place_numCells + 1;
-
- g_place_qpProb->area = realloc(g_place_qpProb->area,
- sizeof(float)*g_place_numCells);// "area" matrix
- g_place_qpProb->edge_weight = realloc(g_place_qpProb->edge_weight,
- sizeof(float)*maxConnections); // "weight" matrix
- g_place_qpProb->connect = realloc(g_place_qpProb->connect,
- sizeof(int)*maxConnections); // "connectivity" matrix
- g_place_qpProb->fixed = realloc(g_place_qpProb->fixed,
- sizeof(int)*g_place_numCells); // "fixed" matrix
-
- // initialize or keep preexisting locations
- if (g_place_qpProb->x != NULL && g_place_qpProb->y != NULL) {
- printf("QMAN-10 :\tperforming incremental placement\n");
- incremental = true;
- }
- g_place_qpProb->x = (float*)realloc(g_place_qpProb->x, sizeof(float)*g_place_numCells);
- g_place_qpProb->y = (float*)realloc(g_place_qpProb->y, sizeof(float)*g_place_numCells);
-
- // form a row for each cell
- // build data
- for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) {
- cell = g_place_concreteCells[c];
-
- // fill in the characteristics for this cell
- g_place_qpProb->area[c] = getCellArea(cell);
- if (cell->m_fixed || cell->m_parent->m_pad) {
- g_place_qpProb->x[c] = cell->m_x;
- g_place_qpProb->y[c] = cell->m_y;
- g_place_qpProb->fixed[c] = 1;
- } else {
- if (!incremental) {
- g_place_qpProb->x[c] = g_place_coreBounds.x+g_place_coreBounds.w*0.5;
- g_place_qpProb->y[c] = g_place_coreBounds.y+g_place_coreBounds.h*0.5;
- }
- g_place_qpProb->fixed[c] = 0;
- }
-
- // update connectivity matrices
- last_index = nextIndex;
- for(n=0; n<cell_numTerms[c]; n++) {
- net = cell_terms[c][n];
- weight = net->m_weight / splitPenalty(net->m_numTerms);
- for(t=0; t<net->m_numTerms; t++) {
- c2 = net->m_terms[t]->m_id;
- if (c2 == c) continue;
- if (seen[c2] < last_index) {
- // not seen
- g_place_qpProb->connect[nextIndex-1] = c2;
- g_place_qpProb->edge_weight[nextIndex-1] = weight;
- seen[c2] = nextIndex;
- nextIndex++;
- } else {
- // seen
- g_place_qpProb->edge_weight[seen[c2]-1] += weight;
- }
- }
- }
- g_place_qpProb->connect[nextIndex-1] = -1;
- g_place_qpProb->edge_weight[nextIndex-1] = -1.0;
- nextIndex++;
- } else {
- // fill in dummy values for connectivity matrices
- g_place_qpProb->connect[nextIndex-1] = -1;
- g_place_qpProb->edge_weight[nextIndex-1] = -1.0;
- nextIndex++;
- }
-
- free(cell_numTerms);
- free(cell_terms);
- free(seen);
-}
-
-typedef struct reverseCOG {
- float x,y;
- Partition *part;
- float delta;
-} reverseCOG;
-
-
-// --------------------------------------------------------------------
-// generateCoGConstraints()
-//
-/// \brief Generates center of gravity constraints.
-//
-// --------------------------------------------------------------------
-int generateCoGConstraints(reverseCOG COG_rev[]) {
- int numConstraints = 0; // actual num contraints
- int cogRevNum = 0;
- Partition **stack = malloc(sizeof(Partition*)*g_place_numPartitions*2);
- int stackPtr = 0;
- Partition *p;
- float cgx, cgy;
- int next_index = 0, last_constraint = 0;
- bool isTrueConstraint = false;
- int i, m;
- float totarea;
- ConcreteCell *cell;
-
- // each partition may give rise to a center-of-gravity constraint
- stack[stackPtr] = g_place_rootPartition;
- while(stackPtr >= 0) {
- p = stack[stackPtr--];
- assert(p);
-
- // traverse down the partition tree to leaf nodes-only
- if (!p->m_leaf) {
- stack[++stackPtr] = p->m_sub1;
- stack[++stackPtr] = p->m_sub2;
- } else {
- /*
- cout << "adding a COG constraint for box "
- << p->bounds.x << ","
- << p->bounds.y << " of size"
- << p->bounds.w << "x"
- << p->bounds.h
- << endl;
- */
- cgx = p->m_bounds.x + p->m_bounds.w*0.5;
- cgy = p->m_bounds.y + p->m_bounds.h*0.5;
- COG_rev[cogRevNum].x = cgx;
- COG_rev[cogRevNum].y = cgy;
- COG_rev[cogRevNum].part = p;
- COG_rev[cogRevNum].delta = 0;
-
- cogRevNum++;
- }
- }
-
- assert(cogRevNum == g_place_numPartitions);
-
- for (i = 0; i < g_place_numPartitions; i++) {
- p = COG_rev[i].part;
- assert(p);
- g_place_qpProb->cog_x[numConstraints] = COG_rev[i].x;
- g_place_qpProb->cog_y[numConstraints] = COG_rev[i].y;
- totarea = 0.0;
- for(m=0; m<p->m_numMembers; m++) if (p->m_members[m]) {
- cell = p->m_members[m];
- assert(cell);
-
- if (!cell->m_fixed && !cell->m_parent->m_pad) {
- isTrueConstraint = true;
- }
- else {
- continue;
- }
- g_place_qpProb->cog_list[next_index++] = cell->m_id;
- totarea += getCellArea(cell);
- }
- if (totarea == 0.0) {
- isTrueConstraint = false;
- }
- if (isTrueConstraint) {
- numConstraints++;
- g_place_qpProb->cog_list[next_index++] = -1;
- last_constraint = next_index;
- }
- else {
- next_index = last_constraint;
- }
- }
-
- free(stack);
-
- return --numConstraints;
-}
-
-
-// --------------------------------------------------------------------
-// solveQuadraticProblem()
-//
-/// \brief Calls quadratic solver.
-//
-// --------------------------------------------------------------------
-void solveQuadraticProblem(bool useCOG) {
- int c;
-
- reverseCOG *COG_rev = malloc(sizeof(reverseCOG)*g_place_numPartitions);
-
- g_place_qpProb->cog_list = malloc(sizeof(int)*(g_place_numPartitions+g_place_numCells));
- g_place_qpProb->cog_x = malloc(sizeof(float)*g_place_numPartitions);
- g_place_qpProb->cog_y = malloc(sizeof(float)*g_place_numPartitions);
-
- // memset(g_place_qpProb->x, 0, sizeof(float)*g_place_numCells);
- // memset(g_place_qpProb->y, 0, sizeof(float)*g_place_numCells);
-
- qps_init(g_place_qpProb);
-
- if (useCOG)
- g_place_qpProb->cog_num = generateCoGConstraints(COG_rev);
- else
- g_place_qpProb->cog_num = 0;
-
- g_place_qpProb->loop_num = 0;
-
- qps_solve(g_place_qpProb);
-
- qps_clean(g_place_qpProb);
-
- // set the positions
- for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) {
- g_place_concreteCells[c]->m_x = g_place_qpProb->x[c];
- g_place_concreteCells[c]->m_y = g_place_qpProb->y[c];
- }
-
- // clean up
- free(g_place_qpProb->cog_list);
- free(g_place_qpProb->cog_x);
- free(g_place_qpProb->cog_y);
-
- free(COG_rev);
-}