abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
place_genqp.c
Go to the documentation of this file.
1 /*===================================================================*/
2 //
3 // place_genqp.c
4 //
5 // Aaron P. Hurst, 2003-2007
6 // ahurst@eecs.berkeley.edu
7 //
8 /*===================================================================*/
9 
10 #include <stdlib.h>
11 #include <math.h>
12 #include <stdio.h>
13 #include <string.h>
14 #include <assert.h>
15 
16 #include "place_base.h"
17 #include "place_qpsolver.h"
18 #include "place_gordian.h"
19 
21 
22 
23 // --------------------------------------------------------------------
24 // Global variables
25 //
26 // --------------------------------------------------------------------
27 
29 
30 
31 // --------------------------------------------------------------------
32 // splitPenalty()
33 //
34 /// \brief Returns a weight for all of the edges in the clique for a multipin net.
35 //
36 // --------------------------------------------------------------------
37 float splitPenalty(int pins) {
38 
39  if (pins > 1) {
40  return 1.0 + CLIQUE_PENALTY/(pins - 1);
41  // return pow(pins - 1, CLIQUE_PENALTY);
42  }
43  return 1.0 + CLIQUE_PENALTY;
44 }
45 
46 
47 // --------------------------------------------------------------------
48 // constructQuadraticProblem()
49 //
50 /// \brief Constructs the matrices necessary to do analytical placement.
51 //
52 // --------------------------------------------------------------------
54  int maxConnections = 1;
55  int ignoreNum = 0;
56  int n,t,c,c2,p;
57  ConcreteCell *cell;
58  ConcreteNet *net;
59  int *cell_numTerms = calloc(g_place_numCells, sizeof(int));
60  ConcreteNet ***cell_terms = calloc(g_place_numCells, sizeof(ConcreteNet**));
61  bool incremental = false;
62  int nextIndex = 1;
63  int *seen = calloc(g_place_numCells, sizeof(int));
64  float weight;
65  int last_index;
66 
67  // create problem object
68  if (!g_place_qpProb) {
69  g_place_qpProb = malloc(sizeof(qps_problem_t));
70  g_place_qpProb->area = NULL;
71  g_place_qpProb->x = NULL;
72  g_place_qpProb->y = NULL;
73  g_place_qpProb->fixed = NULL;
74  g_place_qpProb->connect = NULL;
75  g_place_qpProb->edge_weight = NULL;
76  }
77 
78  // count the maximum possible number of non-sparse entries
79  for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) {
81  if (net->m_numTerms > IGNORE_NETSIZE) {
82  ignoreNum++;
83  }
84  else {
85  maxConnections += net->m_numTerms*(net->m_numTerms-1);
86  for(t=0; t<net->m_numTerms; t++) {
87  c = net->m_terms[t]->m_id;
88  p = ++cell_numTerms[c];
89  cell_terms[c] = (ConcreteNet**)realloc(cell_terms[c], p*sizeof(ConcreteNet*));
90  cell_terms[c][p-1] = net;
91  }
92  }
93  }
94  if(ignoreNum) {
95  printf("QMAN-10 : \t\t%d large nets ignored\n", ignoreNum);
96  }
97 
98  // initialize the data structures
99  g_place_qpProb->num_cells = g_place_numCells;
100  maxConnections += g_place_numCells + 1;
101 
102  g_place_qpProb->area = realloc(g_place_qpProb->area,
103  sizeof(float)*g_place_numCells);// "area" matrix
104  g_place_qpProb->edge_weight = realloc(g_place_qpProb->edge_weight,
105  sizeof(float)*maxConnections); // "weight" matrix
106  g_place_qpProb->connect = realloc(g_place_qpProb->connect,
107  sizeof(int)*maxConnections); // "connectivity" matrix
108  g_place_qpProb->fixed = realloc(g_place_qpProb->fixed,
109  sizeof(int)*g_place_numCells); // "fixed" matrix
110 
111  // initialize or keep preexisting locations
112  if (g_place_qpProb->x != NULL && g_place_qpProb->y != NULL) {
113  printf("QMAN-10 :\tperforming incremental placement\n");
114  incremental = true;
115  }
116  g_place_qpProb->x = (float*)realloc(g_place_qpProb->x, sizeof(float)*g_place_numCells);
117  g_place_qpProb->y = (float*)realloc(g_place_qpProb->y, sizeof(float)*g_place_numCells);
118 
119  // form a row for each cell
120  // build data
121  for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) {
122  cell = g_place_concreteCells[c];
123 
124  // fill in the characteristics for this cell
125  g_place_qpProb->area[c] = getCellArea(cell);
126  if (cell->m_fixed || cell->m_parent->m_pad) {
127  g_place_qpProb->x[c] = cell->m_x;
128  g_place_qpProb->y[c] = cell->m_y;
129  g_place_qpProb->fixed[c] = 1;
130  } else {
131  if (!incremental) {
132  g_place_qpProb->x[c] = g_place_coreBounds.x+g_place_coreBounds.w*0.5;
133  g_place_qpProb->y[c] = g_place_coreBounds.y+g_place_coreBounds.h*0.5;
134  }
135  g_place_qpProb->fixed[c] = 0;
136  }
137 
138  // update connectivity matrices
139  last_index = nextIndex;
140  for(n=0; n<cell_numTerms[c]; n++) {
141  net = cell_terms[c][n];
142  weight = net->m_weight / splitPenalty(net->m_numTerms);
143  for(t=0; t<net->m_numTerms; t++) {
144  c2 = net->m_terms[t]->m_id;
145  if (c2 == c) continue;
146  if (seen[c2] < last_index) {
147  // not seen
148  g_place_qpProb->connect[nextIndex-1] = c2;
149  g_place_qpProb->edge_weight[nextIndex-1] = weight;
150  seen[c2] = nextIndex;
151  nextIndex++;
152  } else {
153  // seen
154  g_place_qpProb->edge_weight[seen[c2]-1] += weight;
155  }
156  }
157  }
158  g_place_qpProb->connect[nextIndex-1] = -1;
159  g_place_qpProb->edge_weight[nextIndex-1] = -1.0;
160  nextIndex++;
161  } else {
162  // fill in dummy values for connectivity matrices
163  g_place_qpProb->connect[nextIndex-1] = -1;
164  g_place_qpProb->edge_weight[nextIndex-1] = -1.0;
165  nextIndex++;
166  }
167 
168  free(cell_numTerms);
169  free(cell_terms);
170  free(seen);
171 }
172 
173 typedef struct reverseCOG {
174  float x,y;
176  float delta;
177 } reverseCOG;
178 
179 
180 // --------------------------------------------------------------------
181 // generateCoGConstraints()
182 //
183 /// \brief Generates center of gravity constraints.
184 //
185 // --------------------------------------------------------------------
187  int numConstraints = 0; // actual num constraints
188  int cogRevNum = 0;
189  Partition **stack = malloc(sizeof(Partition*)*g_place_numPartitions*2);
190  int stackPtr = 0;
191  Partition *p;
192  float cgx, cgy;
193  int next_index = 0, last_constraint = 0;
194  bool isTrueConstraint = false;
195  int i, m;
196  float totarea;
197  ConcreteCell *cell;
198 
199  // each partition may give rise to a center-of-gravity constraint
200  stack[stackPtr] = g_place_rootPartition;
201  while(stackPtr >= 0) {
202  p = stack[stackPtr--];
203  assert(p);
204 
205  // traverse down the partition tree to leaf nodes-only
206  if (!p->m_leaf) {
207  stack[++stackPtr] = p->m_sub1;
208  stack[++stackPtr] = p->m_sub2;
209  } else {
210  /*
211  cout << "adding a COG constraint for box "
212  << p->bounds.x << ","
213  << p->bounds.y << " of size"
214  << p->bounds.w << "x"
215  << p->bounds.h
216  << endl;
217  */
218  cgx = p->m_bounds.x + p->m_bounds.w*0.5;
219  cgy = p->m_bounds.y + p->m_bounds.h*0.5;
220  COG_rev[cogRevNum].x = cgx;
221  COG_rev[cogRevNum].y = cgy;
222  COG_rev[cogRevNum].part = p;
223  COG_rev[cogRevNum].delta = 0;
224 
225  cogRevNum++;
226  }
227  }
228 
229  assert(cogRevNum == g_place_numPartitions);
230 
231  for (i = 0; i < g_place_numPartitions; i++) {
232  p = COG_rev[i].part;
233  assert(p);
234  g_place_qpProb->cog_x[numConstraints] = COG_rev[i].x;
235  g_place_qpProb->cog_y[numConstraints] = COG_rev[i].y;
236  totarea = 0.0;
237  for(m=0; m<p->m_numMembers; m++) if (p->m_members[m]) {
238  cell = p->m_members[m];
239  assert(cell);
240 
241  if (!cell->m_fixed && !cell->m_parent->m_pad) {
242  isTrueConstraint = true;
243  }
244  else {
245  continue;
246  }
247  g_place_qpProb->cog_list[next_index++] = cell->m_id;
248  totarea += getCellArea(cell);
249  }
250  if (totarea == 0.0) {
251  isTrueConstraint = false;
252  }
253  if (isTrueConstraint) {
254  numConstraints++;
255  g_place_qpProb->cog_list[next_index++] = -1;
256  last_constraint = next_index;
257  }
258  else {
259  next_index = last_constraint;
260  }
261  }
262 
263  free(stack);
264 
265  return --numConstraints;
266 }
267 
268 
269 // --------------------------------------------------------------------
270 // solveQuadraticProblem()
271 //
272 /// \brief Calls quadratic solver.
273 //
274 // --------------------------------------------------------------------
275 void solveQuadraticProblem(bool useCOG) {
276  int c;
277 
279 
280  g_place_qpProb->cog_list = malloc(sizeof(int)*(g_place_numPartitions+g_place_numCells));
281  g_place_qpProb->cog_x = malloc(sizeof(float)*g_place_numPartitions);
282  g_place_qpProb->cog_y = malloc(sizeof(float)*g_place_numPartitions);
283 
284  // memset(g_place_qpProb->x, 0, sizeof(float)*g_place_numCells);
285  // memset(g_place_qpProb->y, 0, sizeof(float)*g_place_numCells);
286 
287  qps_init(g_place_qpProb);
288 
289  if (useCOG)
290  g_place_qpProb->cog_num = generateCoGConstraints(COG_rev);
291  else
292  g_place_qpProb->cog_num = 0;
293 
294  g_place_qpProb->loop_num = 0;
295 
296  qps_solve(g_place_qpProb);
297 
298  qps_clean(g_place_qpProb);
299 
300  // set the positions
301  for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) {
302  g_place_concreteCells[c]->m_x = g_place_qpProb->x[c];
303  g_place_concreteCells[c]->m_y = g_place_qpProb->y[c];
304  }
305 
306  // clean up
307  free(g_place_qpProb->cog_list);
308  free(g_place_qpProb->cog_x);
309  free(g_place_qpProb->cog_y);
310 
311  free(COG_rev);
312 }
314 
struct Partition * m_sub1
Definition: place_gordian.h:56
char * malloc()
void qps_solve(qps_problem_t *p)
AbstractCell * m_parent
Definition: place_base.h:57
ABC_NAMESPACE_IMPL_START int g_place_numPartitions
Definition: place_gordian.c:28
VOID_HACK free()
void qps_clean(qps_problem_t *p)
ConcreteNet ** g_place_concreteNets
Definition: place_base.c:35
float h
Definition: place_base.h:36
float x
Definition: place_base.h:35
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Partition * g_place_rootPartition
float delta
Definition: place_genqp.c:176
float splitPenalty(int pins)
Returns a weight for all of the edges in the clique for a multipin net.
Definition: place_genqp.c:37
float m_weight
Definition: place_base.h:74
void constructQuadraticProblem()
Constructs the matrices necessary to do analytical placement.
Definition: place_genqp.c:53
float y
Definition: place_base.h:35
ConcreteCell ** g_place_concreteCells
Definition: place_base.c:33
char * realloc()
qps_float_t * y
struct Partition * m_sub2
Definition: place_gordian.h:56
float getCellArea(const ConcreteCell *cell)
Definition: place_base.c:99
bool m_fixed
Definition: place_base.h:59
qps_float_t * area
ConcreteCell ** m_terms
Definition: place_base.h:72
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Partition * part
Definition: place_genqp.c:175
qps_float_t * x
qps_float_t * cog_x
int generateCoGConstraints(reverseCOG COG_rev[])
Generates center of gravity constraints.
Definition: place_genqp.c:186
#define IGNORE_NETSIZE
Definition: place_gordian.h:22
ConcreteCell ** m_members
Definition: place_gordian.h:49
qps_float_t * edge_weight
int m_numTerms
Definition: place_base.h:71
Rect g_place_coreBounds
Definition: place_base.c:30
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
float w
Definition: place_base.h:36
int g_place_numNets
Definition: place_base.c:27
ABC_NAMESPACE_IMPL_START qps_problem_t * g_place_qpProb
Definition: place_genqp.c:28
struct reverseCOG reverseCOG
char * calloc()
qps_float_t * cog_y
void qps_init(qps_problem_t *p)
Rect m_bounds
Definition: place_gordian.h:50
#define CLIQUE_PENALTY
Definition: place_gordian.h:21
int m_numMembers
Definition: place_gordian.h:48
#define assert(ex)
Definition: util_old.h:213
ABC_NAMESPACE_IMPL_START int g_place_numCells
Definition: place_base.c:26
void solveQuadraticProblem(bool useCOG)
Calls quadratic solver.
Definition: place_genqp.c:275