Version abc80130_2

1 files changed, 309 insertions, 0 deletions

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