1 /**************************************************************************
2 ***
3 *** Copyright (c) 2000-2007 Regents of the University of Michigan,
4 *** Saurabh N. Adya, Hayward Chan, Jarrod A. Roy
5 *** and Igor L. Markov
6 ***
7 *** Contact author(s): sadya@umich.edu, imarkov@umich.edu
8 *** Original Affiliation: University of Michigan, EECS Dept.
9 *** Ann Arbor, MI 48109-2122 USA
10 ***
11 *** Permission is hereby granted, free of charge, to any person obtaining
12 *** a copy of this software and associated documentation files (the
13 *** "Software"), to deal in the Software without restriction, including
14 *** without limitation
15 *** the rights to use, copy, modify, merge, publish, distribute, sublicense,
16 *** and/or sell copies of the Software, and to permit persons to whom the
17 *** Software is furnished to do so, subject to the following conditions:
18 ***
19 *** The above copyright notice and this permission notice shall be included
20 *** in all copies or substantial portions of the Software.
21 ***
22 *** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
23 *** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
24 *** OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
25 *** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
26 *** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
27 *** OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
28 *** THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 ***
30 ***
31 ***************************************************************************/
32
33 #include "btreeanneal.h"
34
35 #include <algorithm>
36 #include <random>
37
38 #include "FPcommon.h"
39 #include "basepacking.h"
40 #include "btreecompact.h"
41 #include "debugflags.h"
42 #include "mixedpacking.h"
43 #include "mixedpackingfromdb.h"
44 #include "pltobtree.h"
45
46 // parquet data-structures, commented out in order to compile
47 // #include "FPcommon.h"
48 // #include "DB.h"
49 // #include "AnalytSolve.h"
50 // #include "CommandLine.h"
51 #include <algorithm>
52 #include <cfloat>
53 #include <cmath>
54 #include <deque>
55 #include <iterator>
56
57 #include "allparquet.h"
58 #include "skyline.h"
59
60 namespace parquetfp {
61
62 using std::cin;
63 using std::cout;
64 using std::endl;
65 using std::max;
66 using std::min;
67 using std::vector;
68
69 static void getObstaclesFromDB(DB* const db, BasePacking& out);
70
71 // ========================================================
BTreeAreaWireAnnealer(MixedBlockInfoType & nBlockinfo)72 BTreeAreaWireAnnealer::BTreeAreaWireAnnealer(MixedBlockInfoType& nBlockinfo)
73 : BaseAnnealer(),
74 _blockinfo_cleaner(NULL),
75 _blockinfo(nBlockinfo),
76 blockinfo(nBlockinfo),
77 in_curr_solution(_blockinfo.currDimensions),
78 in_next_solution(_blockinfo.currDimensions),
79 in_best_solution(_blockinfo.currDimensions),
80 _slackEval(NULL)
81 {
82 }
83 // --------------------------------------------------------
BTreeAreaWireAnnealer(MixedBlockInfoType & nBlockinfo,const Command_Line * const params,DB * const db)84 BTreeAreaWireAnnealer::BTreeAreaWireAnnealer(MixedBlockInfoType& nBlockinfo,
85 const Command_Line* const params,
86 DB* const db)
87 : BaseAnnealer(params, db),
88 _blockinfo_cleaner(NULL),
89 _blockinfo(nBlockinfo),
90 blockinfo(nBlockinfo),
91 in_curr_solution(_blockinfo.currDimensions),
92 in_next_solution(_blockinfo.currDimensions),
93 in_best_solution(_blockinfo.currDimensions)
94 {
95 getObstaclesFromDB(db, _obstacleinfo);
96 _obstacleFrame[0] = db->getObstacleFrame()[0];
97 _obstacleFrame[1] = db->getObstacleFrame()[1];
98 in_curr_solution.addObstacles(_obstacleinfo, _obstacleFrame);
99 in_next_solution.addObstacles(_obstacleinfo, _obstacleFrame);
100 in_best_solution.addObstacles(_obstacleinfo, _obstacleFrame);
101 // NOTE: must construct slackEval after trees have been filled with
102 // obstacles, or btreeslackeval won't get obstacles
103 _slackEval = new BTreeSlackEval(in_curr_solution);
104 constructor_core();
105 }
106 // --------------------------------------------------------
BTreeAreaWireAnnealer(const Command_Line * const params,DB * const db)107 BTreeAreaWireAnnealer::BTreeAreaWireAnnealer(const Command_Line* const params,
108 DB* const db)
109 : BaseAnnealer(params, db),
110 _blockinfo_cleaner(
111 static_cast<MixedBlockInfoType*>(new MixedBlockInfoTypeFromDB(*db))),
112 _blockinfo(*_blockinfo_cleaner),
113 blockinfo(_blockinfo),
114 in_curr_solution(_blockinfo.currDimensions),
115 in_next_solution(_blockinfo.currDimensions),
116 in_best_solution(_blockinfo.currDimensions)
117 {
118 getObstaclesFromDB(db, _obstacleinfo);
119 _obstacleFrame[0] = db->getObstacleFrame()[0];
120 _obstacleFrame[1] = db->getObstacleFrame()[1];
121 in_curr_solution.addObstacles(_obstacleinfo, _obstacleFrame);
122 in_next_solution.addObstacles(_obstacleinfo, _obstacleFrame);
123 in_best_solution.addObstacles(_obstacleinfo, _obstacleFrame);
124 // NOTE: must construct slackEval after trees have been filled with
125 // obstacles or btreeslackeval won't get obstacles
126 _slackEval = new BTreeSlackEval(in_curr_solution);
127 constructor_core();
128 }
129 // --------------------------------------------------------
constructor_core()130 void BTreeAreaWireAnnealer::constructor_core()
131 {
132 // mgwoo: -noRotation bug fixed here
133 Nodes* theNodes = _db->getNodes();
134 unsigned numNodes = _db->getNumNodes();
135 for (unsigned i = 0; i < numNodes; ++i) {
136 Node& node = theNodes->getNode(i);
137 if (_params->noRotation
138 || (!node.isOrientFixed() && node.isHard()
139 && equalFloat(node.getminAR(), 1.f) && node.allPinsAtCenter)) {
140 node.putIsOrientFixed(true);
141 }
142 }
143 // initialize the orientation map
144 _physicalOrient.resize(in_curr_solution.NUM_BLOCKS);
145 for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++) {
146 _physicalOrient[i].resize(blockinfo.Orient_Num);
147 for (int theta = 0; theta < blockinfo.Orient_Num; theta++) {
148 parquetfp::Node& currBlock = _db->getNodes()->getNode(i);
149 if (currBlock.isOrientFixed()) {
150 _physicalOrient[i][theta] = parquetfp::N;
151 } else {
152 _physicalOrient[i][theta] = parquetfp::ORIENT(theta);
153 // _physicalOrient[i][theta] = parquetfp::N;
154 // cout << "currentOrient: " << _physicalOrient[i][theta] <<
155 // endl;
156 }
157 }
158 }
159
160 // initialize the dimensions of soft blocks
161 for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++)
162 if (blockinfo.blockARinfo[i].isSoft) {
163 float blockAR = max(blockinfo.blockARinfo[i].minAR[0],
164 min(blockinfo.blockARinfo[i].maxAR[0],
165 float(1.0))); // minAR <= AR <= maxAR
166 float blockWidth = sqrt(blockinfo.blockARinfo[i].area * blockAR);
167 float blockHeight = sqrt(blockinfo.blockARinfo[i].area / blockAR);
168
169 _blockinfo.setBlockDimensions(i, blockWidth, blockHeight, 0);
170 }
171
172 // generate an initial solution
173 GenerateRandomSoln(in_curr_solution, blockinfo.currDimensions.blocknum());
174 in_best_solution = in_curr_solution;
175 in_next_solution = in_curr_solution;
176
177 // initialize the orientations of nodes in *_db if necessary
178 for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++) {
179 int initOrient = int(in_curr_solution.tree[i].orient);
180 initOrient = _physicalOrient[i][initOrient];
181
182 float initWidth = in_curr_solution.width(i);
183 float initHeight = in_curr_solution.height(i);
184
185 _db->getNodes()->changeOrient(
186 i, parquetfp::ORIENT(initOrient), *(_db->getNets()));
187 _db->getNodes()->putNodeWidth(i, initWidth);
188 _db->getNodes()->putNodeHeight(i, initHeight);
189 }
190
191 // -----debug messages-----
192 for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++) {
193 for (int thetaIt = 0; thetaIt < blockinfo.Orient_Num; thetaIt++)
194 if ((_db->getNodes()->getNode(i)).isOrientFixed()
195 && int(in_curr_solution.tree[i].orient) != 0) {
196 cout << "ctor: orient of block[" << i << "] should be \"n\"" << endl;
197 printf("in_curr_solution:orient %d\n",
198 int(in_curr_solution.tree[i].orient));
199 cin.get();
200 }
201
202 if (_params->minWL
203 && (int(in_curr_solution.tree[i].orient)
204 != int(_db->getNodes()->getNode(i).getOrient()))) {
205 cout << "ctor: orient of block[" << i << "] is not consistent" << endl;
206 printf("in_curr_solution:orient %d vs. _db->orient: %d\n",
207 int(in_curr_solution.tree[i].orient),
208 int(_db->getNodes()->getNode(i).getOrient()));
209 cin.get();
210 }
211
212 int theta = in_curr_solution.tree[i].orient;
213 if (std::abs(in_curr_solution.width(i)
214 - blockinfo.currDimensions[i].width[theta])
215 > 1e-6) {
216 printf(
217 "ctor: width of block[%d] is not consistent. in_curr_soln: %.2f vs. "
218 "blockinfo: %.2f\n",
219 i,
220 in_curr_solution.width(i),
221 blockinfo.currDimensions[i].width[theta]);
222 cin.get();
223 }
224
225 if (std::abs(in_curr_solution.height(i)
226 - blockinfo.currDimensions[i].height[theta])
227 > 1e-6) {
228 printf(
229 "ctor: height of block[%d] is not consistent. in_curr_soln: %.2f "
230 "vs. blockinfo: %.2f\n",
231 i,
232 in_curr_solution.height(i),
233 blockinfo.currDimensions[i].height[theta]);
234 cin.get();
235 }
236
237 if (_params->minWL
238 && std::abs(in_curr_solution.width(i)
239 - _db->getNodes()->getNodeWidth(i))
240 > 1e-6) {
241 printf(
242 "ctor: width of block[%d] is not consistent. in_curr_solution: %.2f "
243 "vs._db: %.2f\n",
244 i,
245 in_curr_solution.width(i),
246 _db->getNodes()->getNodeWidth(i));
247 cin.get();
248 }
249 }
250 }
251 // --------------------------------------------------------
go()252 bool BTreeAreaWireAnnealer::go()
253 {
254 DBfromSoln(in_curr_solution);
255
256 // turn off rotation for hard square macros
257 // with pins in the center
258 Nodes* theNodes = _db->getNodes();
259 unsigned numNodes = _db->getNumNodes();
260 for (unsigned i = 0; i < numNodes; ++i) {
261 Node& node = theNodes->getNode(i);
262 if (_params->noRotation
263 || (!node.isOrientFixed() && node.isHard()
264 && equalFloat(node.getminAR(), 1.f) && node.allPinsAtCenter)) {
265 node.putIsOrientFixed(true);
266 }
267 }
268 // DEBUG::
269 // for(int i=0; i<numNodes; i++) {
270 // Node &node = theNodes->getNode(i);
271 // cout << "i: " << node.isOrientFixed() << endl;
272 // cout << node.getName() << " " << node.getWidth() << " " <<
273 // node.getHeight () << endl;
274 // }
275
276 bool success = false;
277 if (in_curr_solution.NUM_BLOCKS > 1)
278 success = anneal();
279 else
280 success = packOneBlock();
281
282 // cout << "before DB from soln" << endl;
283 // update *_db for locs, dimensions and slacks
284 DBfromSoln(in_curr_solution);
285 // cout << "after DB from soln" << endl;
286
287 // for(int i=0; i<in_curr_solution.xloc().size(); i++) {
288 // cout << i << " " << in_curr_solution.xloc()[i] << " " <<
289 // in_curr_solution.yloc()[i] << endl;
290 // }
291
292 in_best_solution = in_curr_solution;
293
294 // print solutions
295 SolutionInfo currSoln;
296 currSoln.area = in_curr_solution.totalArea();
297 currSoln.width = in_curr_solution.totalWidth();
298 currSoln.height = in_curr_solution.totalHeight();
299 bool useWts = true;
300 #ifdef USEFLUTE
301 currSoln.HPWL
302 = _db->evalHPWL(useWts, _params->scaleTerms, _params->useSteiner);
303 #else
304 currSoln.HPWL = _db->evalHPWL(useWts, _params->scaleTerms);
305 #endif
306 printResults(currSoln);
307
308 return success;
309 }
310 // --------------------------------------------------------
DBfromSoln(const BTree & soln)311 void BTreeAreaWireAnnealer::DBfromSoln(const BTree& soln)
312 {
313 _db->updatePlacement(const_cast<vector<float>&>(soln.xloc()),
314 const_cast<vector<float>&>(soln.yloc()));
315 for (int i = 0; i < soln.NUM_BLOCKS; i++) {
316 parquetfp::ORIENT newOrient = parquetfp::ORIENT(soln.tree[i].orient);
317 _db->getNodes()->changeOrient(i, newOrient, *(_db->getNets()));
318 _db->getNodes()->putNodeWidth(i, soln.width(i));
319 _db->getNodes()->putNodeHeight(i, soln.height(i));
320 }
321
322 // cout << "Before evaluate Slacks: " << endl;
323 // for(int i=0; i<soln.xloc().size(); i++) {
324 // cout << i << " " << soln.xloc()[i] << " " << soln.yloc()[i] << endl;
325 // }
326
327 _slackEval->evaluateSlacks(soln);
328
329 // cout << "After evaluate Slacks: " << endl;
330 // for(int i=0; i<soln.xloc().size(); i++) {
331 // cout << i << " " << soln.xloc()[i] << " " << soln.yloc()[i] << endl;
332 // }
333
334 int blocknum = soln.NUM_BLOCKS;
335 vector<float> xSlacks(blocknum); // % x-slacks
336 vector<float> ySlacks(blocknum); // % y-slacks
337 float totalWidth = soln.totalWidth();
338 float totalHeight = soln.totalHeight();
339 for (int i = 0; i < blocknum; i++) {
340 xSlacks[i] = (_slackEval->xSlack()[i] / totalWidth) * 100;
341 ySlacks[i] = (_slackEval->ySlack()[i] / totalHeight) * 100;
342 }
343 _db->updateSlacks(xSlacks, ySlacks);
344
345 #ifdef PARQUET_DEBUG_HAYWARD_ASSERT_BTREEANNEAL
346 for (int i = 0; i < blocknum; i++) {
347 int theta = soln.tree[i].orient;
348 if (theta != _physicalOrient[i][theta]) {
349 printf("block: %d theta: %d physicalOrient: %d\n",
350 i,
351 theta,
352 _physicalOrient[i][theta]);
353 cin.get();
354 }
355 }
356 #endif
357 }
358 // --------------------------------------------------------
packOneBlock()359 bool BTreeAreaWireAnnealer::packOneBlock()
360 {
361 const float blocksArea = in_curr_solution.blockArea();
362 const float reqdAR = _params->reqdAR;
363 const float reqdArea = blocksArea * (1 + (_params->maxWS / 100.0));
364 const float reqdWidth = sqrt(reqdArea * reqdAR);
365 const float reqdHeight = reqdWidth / reqdAR;
366
367 const vector<float> defaultXloc(1, 0); // 1 copy of "0"
368 const vector<float> defaultYloc(1, 0);
369 const int defaultOrient = 0;
370
371 if (_params->verb > 0)
372 cout << "Only one block is detected, deterministic algo used." << endl;
373
374 if (_params->reqdAR != FREE_OUTLINE && _params->verb > 0)
375 cout << "outline width: " << reqdWidth << " outline height: " << reqdHeight
376 << endl;
377
378 int bestOrient = defaultOrient;
379
380 float bestHPWL = basepacking_h::Dimension::Infty;
381 bool success = false;
382 for (int theta = 0; theta < basepacking_h::Dimension::Orient_Num; theta++) {
383 if (_db->getNodes()->getNode(0).isOrientFixed() && theta > 0)
384 break;
385
386 in_curr_solution.rotate(0, theta);
387
388 float blockWidth = in_curr_solution.width(0);
389 float blockHeight = in_curr_solution.height(0);
390 bool fitsInside
391 = ((_params->reqdAR == FREE_OUTLINE)
392 || ((blockWidth <= reqdWidth) && (blockHeight <= reqdHeight)));
393
394 if (_params->verb > 0)
395 cout << "orient: " << theta << " width: " << blockWidth
396 << " height: " << blockHeight
397 << " inside: " << ((fitsInside) ? "T" : "F");
398
399 success = success || fitsInside;
400 if (fitsInside && _params->minWL) {
401 DBfromSoln(in_curr_solution);
402 bool useWts = true;
403 #ifdef USEFLUTE
404 float currHPWL
405 = _db->evalHPWL(useWts, _params->scaleTerms, _params->useSteiner);
406 #else
407 float currHPWL = _db->evalHPWL(useWts, _params->scaleTerms);
408 #endif
409
410 if (_params->verb > 0)
411 cout << " HPWL: " << currHPWL;
412 if (currHPWL < bestHPWL) {
413 bestOrient = theta;
414 bestHPWL = currHPWL;
415 }
416 } else if (fitsInside)
417 bestOrient = theta;
418
419 if (_params->verb > 0)
420 cout << endl;
421 }
422
423 in_curr_solution.rotate(0, bestOrient);
424 DBfromSoln(in_curr_solution);
425
426 return success;
427 }
428 // ---------------------------------------------------------
429
anneal()430 bool BTreeAreaWireAnnealer::anneal()
431 {
432 // options
433 const bool budgetTime = _params->budgetTime;
434 float seconds = _params->seconds;
435 const bool minWL = _params->minWL;
436
437 // input params
438 const float wireWeight = _params->wireWeight;
439 const float areaWeight = _params->areaWeight;
440 const float ARWeight = max(1 - areaWeight - wireWeight, float(0.0));
441
442 // input params
443 const float blocksArea = _db->getNodesArea();
444 const float size = in_curr_solution.NUM_BLOCKS;
445
446 float currTime = _params->startTime;
447
448 // if any constraint is imposed
449 const float reqdAR = _params->reqdAR;
450 // const float reqdArea = blocksArea * (1+((_params->maxWS-1)/100.0));
451 // const float reqdWidth = sqrt(reqdArea*reqdAR);
452 // const float reqdHeight = reqdWidth/reqdAR;
453
454 // const float real_reqdAR = _params->reqdAR;
455 const float real_reqdArea = blocksArea * (1 + (_params->maxWS / 100.0));
456 const float real_reqdWidth = sqrt(real_reqdArea * reqdAR);
457 const float real_reqdHeight = real_reqdWidth / reqdAR;
458 // const float maxDist = sqrt(real_reqdWidth * real_reqdWidth *
459 // real_reqdHeight * real_reqdHeight);
460
461 // save attributes of the best solution
462 // float bestArea = FLT_MAX;
463 // float bestHPWL = FLT_MAX;
464
465 // global counters and book-keepers
466 int move = UNINITIALIZED;
467 int count = 0;
468 int prev_move = UNINITIALIZED;
469
470 unsigned int timeChangeCtr = 0;
471 unsigned int moveSelect = UNSIGNED_UNINITIALIZED;
472 unsigned int iter = UNSIGNED_UNINITIALIZED;
473 unsigned int masterMoveSel = 0;
474
475 bool moveAccepted = false;
476 bool brokeFromLoop = false;
477
478 float total = seconds, percent = 1;
479 unsigned int moves = 1000;
480
481 // Added by DAP to support terminate on
482 // acceptence ratio less than 0.5%
483 // unsigned accept_ct = 0;
484 bool saved_best = false;
485
486 _db->updatePlacement(const_cast<vector<float>&>(in_curr_solution.xloc()),
487 const_cast<vector<float>&>(in_curr_solution.yloc()));
488 bool useWts = true;
489 #ifdef USEFLUTE
490 float currHPWL
491 = _db->evalHPWL(useWts, _params->scaleTerms, _params->useSteiner);
492 #else
493 float currHPWL = _db->evalHPWL(useWts, _params->scaleTerms);
494 #endif
495
496 // float currDist = in_curr_solution.getDistance(real_reqdWidth,
497 // real_reqdHeight);
498
499 SkylineContour mapY(in_curr_solution, true);
500 float currWastedArea = in_curr_solution.totalContourArea()
501 + mapY.GetContourArea()
502 - 2.0 * in_curr_solution.blockArea();
503
504 // calculate wastedArea
505 // SkylineContour mapX(in_curr_solution), mapY(in_curr_solution, true);
506 // float currWastedContArea
507 // = mapX.GetContourArea()
508 // + mapY.GetContourArea()
509 // - 2.0 * in_curr_solution.blockArea();
510
511 float bestHPWL = currHPWL;
512 float bestArea = std::numeric_limits<float>::max();
513 // float bestDist = std::numeric_limits<float>::min();
514 float bestWastedArea = std::numeric_limits<float>::max();
515
516 while (currTime > _params->timeCool || budgetTime) {
517 brokeFromLoop = false;
518 iter = 0;
519
520 // ----------------------------------------
521 // an iteration under the same termperature
522 // ----------------------------------------
523 do {
524 // -----------------------
525 // select and apply a move
526 // -----------------------
527
528 // current solution, "currHPWL" updated only when necessary
529 // "currWastedArea" also updated only when necessary
530 float currArea = in_curr_solution.totalArea();
531 float currHeight = in_curr_solution.totalHeight();
532 float currWidth = in_curr_solution.totalWidth();
533 float currAR = currWidth / currHeight;
534
535 ++count;
536 ++iter;
537 prev_move = move;
538
539 // -----select the types of moves here-----
540 if (_params->softBlocks && currTime < 50)
541 masterMoveSel = rand() % 1000;
542 moveSelect = rand() % 1000;
543
544 // -----take action-----
545 int indexOrient = UNSIGNED_UNINITIALIZED;
546 parquetfp::ORIENT newOrient = parquetfp::N;
547 parquetfp::ORIENT oldOrient = parquetfp::N;
548
549 int index = UNINITIALIZED;
550 float newWidth = UNINITIALIZED;
551 float newHeight = UNINITIALIZED;
552
553 // float deadspacePercent = (currArea / blocksArea - 1) * 100;
554 if (_params->softBlocks &&
555 // deadspacePercent < _params->startSoftMovePercent &&
556 masterMoveSel == 1)
557 move = packSoftBlocks(2); // needs its return-value (-1)!!!
558
559 else if (_params->softBlocks &&
560 // deadspacePercent <
561 // _params->startSoftMovePercent &&
562 masterMoveSel > 950)
563 move = makeSoftBlMove(index, newWidth, newHeight);
564
565 else if (((reqdAR - currAR) / reqdAR > 0.00005
566 || (currAR - reqdAR) / reqdAR > 0.00005)
567 && (timeChangeCtr % 4) == 0 && reqdAR != FREE_OUTLINE) {
568 // move = makeMove(indexOrient, newOrient, oldOrient);
569 move = makeARMove();
570 }
571
572 else if (/*false && !minWL &&*/
573 currTime < 30 && (timeChangeCtr % 5) == 0) {
574 // move = compactBlocks();
575 }
576
577 else if (moveSelect < 150) {
578 if (reqdAR != FREE_OUTLINE)
579 move = makeARMove();
580 else
581 move = makeMove(indexOrient, newOrient, oldOrient);
582 }
583
584 else if (moveSelect < 300 && minWL) {
585 if (reqdAR != FREE_OUTLINE)
586 move = makeARWLMove();
587 else
588 move = makeHPWLMove();
589 }
590
591 else
592 move = makeMove(indexOrient, newOrient, oldOrient);
593
594 // -----additional book-keeping for special moves-----
595 // for orientation moves
596 if (move == REP_SPEC_ORIENT || move == ORIENT) {
597 // temp values
598 if (minWL) {
599 _db->getNodes()->changeOrient(
600 indexOrient, newOrient, *(_db->getNets()));
601 }
602 }
603
604 // for soft-block moves
605 if (move == SOFT_BL) {
606 int indexTheta = in_curr_solution.tree[index].orient;
607 _blockinfo.setBlockDimensions(index, newWidth, newHeight, indexTheta);
608 // cout << "Next Solution Evaluate" << endl;
609 in_next_solution.evaluate(in_curr_solution.tree);
610
611 if (minWL) {
612 _db->getNodes()->putNodeWidth(index, newWidth);
613 _db->getNodes()->putNodeHeight(index, newHeight);
614 }
615 }
616
617 // attributes of "in_next_solution"
618 float tempHeight = in_next_solution.totalHeight();
619 float tempWidth = in_next_solution.totalWidth();
620 float tempArea = in_next_solution.totalArea();
621 float tempAR = tempWidth / tempHeight;
622 float tempHPWL = UNINITIALIZED;
623 // float tempDist = in_next_solution.getDistance( real_reqdWidth,
624 // real_reqdHeight);
625
626 SkylineContour mapY(in_next_solution, true);
627
628 float tempWastedArea = in_next_solution.totalContourArea()
629 + mapY.GetContourArea()
630 - 2.0 * in_next_solution.blockArea();
631
632 // -----------------------------------------------------
633 // evaulate the temporary solution and calculate "delta"
634 // -----------------------------------------------------
635
636 float deltaArea = 0;
637 float deltaHPWL = 0;
638 float deltaAR = UNINITIALIZED;
639 float delta = UNINITIALIZED;
640 // float deltaDist = UNINITIALIZED;
641 float deltaWastedArea = UNINITIALIZED;
642
643 /* area objective */
644 if (currTime > 30)
645 deltaArea
646 = ((tempArea - currArea) * 1.2 * _params->timeInit) / blocksArea;
647 else
648 deltaArea
649 = ((tempArea - currArea) * 1.5 * _params->timeInit) / blocksArea;
650
651 /* area objective */
652 if (currTime > 30)
653 deltaWastedArea
654 = ((tempWastedArea - currWastedArea) * 1.2 * _params->timeInit)
655 / blocksArea;
656 else
657 deltaWastedArea
658 = ((tempWastedArea - currWastedArea) * 1.5 * _params->timeInit)
659 / blocksArea;
660
661 // deltaDist = -1 * ((tempDist-currDist) * _params->timeInit) /
662 // maxDist;
663
664 /* HPWL objective if applicable */
665 if (minWL) {
666 _db->updatePlacement(
667 const_cast<vector<float>&>(in_next_solution.xloc()),
668 const_cast<vector<float>&>(in_next_solution.yloc()));
669 // cout << "placement Info Updated! curr" << endl;
670 // for(int i=0; i<in_curr_solution.xloc().size(); i++) {
671 // cout << i << " " << in_curr_solution.xloc(i) << " " <<
672 // in_curr_solution.yloc(i) << endl;
673 // }
674 // cout << "placement Info Updated! next" << endl;
675 // for(int i=0; i<in_next_solution.xloc().size(); i++) {
676 // cout << i << " " << in_next_solution.xloc(i) << " " <<
677 // in_next_solution.yloc(i) << endl;
678 // }
679
680 #ifdef USEFLUTE
681 tempHPWL
682 = _db->evalHPWL(useWts, _params->scaleTerms, _params->useSteiner);
683 #else
684 tempHPWL = _db->evalHPWL(useWts, _params->scaleTerms);
685 #endif
686 if (currHPWL == 0)
687 deltaHPWL = 0;
688 else {
689 if (currTime > 30)
690 deltaHPWL = ((tempHPWL - currHPWL) * 1.2 * _params->timeInit)
691 / currHPWL; // 1.2
692 else
693 deltaHPWL = ((tempHPWL - currHPWL) * 1.5 * _params->timeInit)
694 / currHPWL; // 1.5
695 }
696 }
697
698 // if (_isFixedOutline)
699 // {
700 // /* max(x-viol, y-viol) objective */
701 // if((tempHeight-currHeight) > (tempWidth-currWidth))
702 // deltaArea=((tempHeight-currHeight)*1.3*_params->timeInit)/(real_reqdHeight);
703 // else
704 // deltaArea=((tempWidth-currWidth)*1.3*_params->timeInit)/(real_reqdWidth);
705
706 // // /* x-viol + y-viol objective */
707 // // deltaArea=0.5*1.3*_params->timeInit*
708 // // (abs(tempHeight-currHeight) / (reqdHeight) +
709 // // abs(tempWidth-currWidth) / (reqdWidth));
710 // }
711
712 // if (_isFixedOutline && getNumObstacles())
713 //{ // XXX <aaronnn> compute cost using outline violations, rather than AR
714 // // when obstacles are present (because AR is meaningless when there
715 // are obstacles)
716 // // max(x-viol, y-viol) objective
717
718 // float deltaHeight =
719 // ((tempHeight-currHeight)*1.3*_params->timeInit)/(real_reqdHeight);
720 // float deltaWidth =
721 // ((tempWidth-currWidth)*1.3*_params->timeInit)/(real_reqdWidth);
722
723 // if (deltaHeight > 0 && deltaWidth > 0)
724 // deltaArea = deltaHeight + deltaWidth;
725 // else if (deltaHeight > 0)
726 // deltaArea = deltaHeight;
727 // else if (deltaWidth > 0)
728 // deltaArea = deltaWidth;
729 // else
730 // deltaArea = deltaHeight + deltaWidth;
731 //}
732
733 /* AR and overall objective */
734 delta = deltaArea;
735 if (reqdAR != FREE_OUTLINE) {
736 deltaAR = ((tempAR - reqdAR) * (tempAR - reqdAR)
737 - (currAR - reqdAR) * (currAR - reqdAR))
738 * 20 * _params->timeInit; // 10 // 1.2
739
740 // This Function !!!
741 if (minWL) {
742 // delta = (areaWeight * deltaArea +
743 // wireWeight * deltaHPWL +
744 // ARWeight * deltaAR);
745 // delta = 0.2 * deltaHPWL +
746 // 0.6 * deltaWastedContArea;
747 // delta = 0.2 * deltaHPWL + 0.4 * deltaAR + 0.4 * deltaDist;
748 delta = 0.2 * deltaHPWL + 0.4 * deltaAR + 0.4 * deltaWastedArea;
749 // delta = 0.4 * deltaAR + 0.8 * deltaWastedArea;
750 // cout << "c: " << count << " dHpwl: " << deltaHPWL
751 // << " dAR:" << deltaAR << " dWArea:" << deltaWastedArea<<
752 // endl;
753
754 } else
755 delta = ((areaWeight + wireWeight / 2.0) * deltaArea
756 + (ARWeight + wireWeight / 2.0) * deltaAR);
757
758 } else if (minWL) {
759 delta = ((areaWeight + ARWeight / 2.0) * deltaArea
760 + (wireWeight + ARWeight / 2.0) * deltaHPWL);
761 } else
762 delta = deltaArea;
763 // finish calculating "delta"
764
765 // --------------------------------------------------
766 // decide whether a move is accepted based on "delta"
767 // --------------------------------------------------
768
769 // cout << "Iter: " << iter << " Delta: " << delta << endl;
770
771 if (delta < 0 || move == MISC)
772 moveAccepted = true;
773 else if (currTime > _params->timeCool)
774 // become greedy below time > timeCool
775 {
776 float ran = rand() % 10000;
777 float r = float(ran) / 9999;
778 if (r < exp(-1 * delta / currTime))
779 moveAccepted = true;
780 else
781 moveAccepted = false;
782 } else
783 moveAccepted = false;
784
785 // -----update current solution if accept-----
786 if (moveAccepted && move != MISC) {
787 // cout << "Move Accepted!!" << endl;
788 in_curr_solution = in_next_solution;
789 currHPWL = tempHPWL;
790 // currDist = tempDist;
791 currWastedArea = tempWastedArea;
792 }
793
794 // -----additional book-keeping for special moves-----
795 if (move == REP_SPEC_ORIENT || move == ORIENT) {
796 // if move not accepted, then put back "oldOrient"
797 parquetfp::ORIENT actualOrient
798 = parquetfp::ORIENT(in_curr_solution.tree[indexOrient].orient);
799
800 if (minWL) {
801 _db->getNodes()->changeOrient(
802 indexOrient, actualOrient, *(_db->getNets()));
803 // cout << "After Changing Orient" << endl;
804 // cout << ""
805 }
806 }
807
808 if (move == SOFT_BL) {
809 // if move not accepted, then put back "oldWidth/Height"
810 float actualWidth = in_curr_solution.width(index);
811 float actualHeight = in_curr_solution.height(index);
812 int actualTheta = in_curr_solution.tree[index].orient;
813 _blockinfo.setBlockDimensions(
814 index, actualWidth, actualHeight, actualTheta);
815
816 if (minWL) {
817 _db->getNodes()->putNodeWidth(index, actualWidth);
818 _db->getNodes()->putNodeHeight(index, actualHeight);
819 }
820 }
821
822 // check the best updates
823 bool updateBest = false;
824 if (_params->reqdAR != FREE_OUTLINE) {
825 if (minWL) {
826 updateBest
827 = (currWidth <= real_reqdWidth && currHeight <= real_reqdHeight
828 && currHPWL < bestHPWL && currWastedArea < bestWastedArea);
829 // currDist > bestDist);
830 // cout << "HPWL: " << currHPWL << " " << bestHPWL << endl;
831 } else {
832 updateBest
833 = (currWidth <= real_reqdWidth && currHeight <= real_reqdHeight
834 && currArea < bestArea);
835 }
836 } else if (minWL) {
837 float currCost = areaWeight * currArea + wireWeight * currHPWL;
838 float bestCost = areaWeight * bestArea + wireWeight * bestHPWL;
839
840 updateBest = (currCost < bestCost);
841 } else
842 updateBest = (currArea < bestArea);
843
844 if (updateBest) {
845 saved_best = true;
846 bestHPWL = currHPWL;
847 bestArea = currArea;
848 // bestDist = currDist;
849 bestWastedArea = currWastedArea;
850 in_best_solution = in_curr_solution;
851 }
852 //}
853
854 // ------------------------------
855 // special terminating conditions
856 // ------------------------------
857
858 // Final Termination!!
859 if (minWL /* && _params->startTime > 100*/) // for lowT anneal don't have
860 // this condition
861 {
862 // hhchan TODO: clean-up this code mess
863 if (currArea <= real_reqdArea && currHeight <= real_reqdHeight
864 && currWidth <= real_reqdWidth && reqdAR != FREE_OUTLINE
865 && currTime < 5) {
866 // cout << "case1 !!!" << endl;
867 return true;
868 }
869
870 if (reqdAR != FREE_OUTLINE && currTime < 5 && _params->dontClusterMacros
871 && _params->solveTop) {
872 float widthWMacroOnly = _db->getXSizeWMacroOnly();
873 float heightWMacroOnly = _db->getYSizeWMacroOnly();
874
875 if (widthWMacroOnly <= real_reqdWidth
876 && heightWMacroOnly <= real_reqdHeight) {
877 // cout << "case2 !!!" << endl;
878 return true;
879 }
880 }
881 } else {
882 if (currArea <= real_reqdArea && currHeight <= real_reqdHeight
883 && currWidth <= real_reqdWidth && reqdAR != FREE_OUTLINE) {
884 // cout << "case3 !!!" << endl;
885 return true;
886 }
887 }
888
889 // Hard limit for moves
890 if (iter >= moves)
891 break;
892
893 #ifdef PARQUET_DEBUG_HAYWARD_ASSERT_BTREEANNEAL
894 // -----debugging messages-----
895 for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++) {
896 if (minWL
897 && (int(in_curr_solution.tree[i].orient)
898 != int(_db->getNodes()->getNode(i).getOrient()))) {
899 cout << "round [" << count << "]: orient of block[" << i
900 << "] is not consistent" << endl;
901 printf("in_curr_solution:orient %d vs. _db->orient: %d, move: %d",
902 int(in_curr_solution.tree[i].orient),
903 int(_db->getNodes()->getNode(i).getOrient()),
904 move);
905 cin.get();
906 }
907
908 int theta = in_curr_solution.tree[i].orient;
909 if (theta != int(_physicalOrient[i][theta])) {
910 printf(
911 "round[%d]: orient of block[%d] is not consistent, in_curr_soln: "
912 "%d vs phyOrient: %d move: %d\n",
913 count,
914 i,
915 theta,
916 _physicalOrient[i][theta],
917 move);
918 cin.get();
919 }
920
921 if (std::abs(in_curr_solution.width(i)
922 - blockinfo.currDimensions[i].width[theta])
923 > 1e-6) {
924 printf(
925 "round[%d]: width of block[%d] is not consistent. in_curr_soln: "
926 "%.2f vs. blockinfo: %.2f move: %d prevMove: %d\n",
927 count,
928 i,
929 in_curr_solution.width(i),
930 blockinfo.currDimensions[i].width[theta],
931 move,
932 prev_move);
933 printf(
934 "round[%d]: oldWidth: %.2f oldHeight: %.2f newWidth: %.2f "
935 "newHeight: %.2f moveAccepted: %s\n",
936 count,
937 -1.0,
938 -1.0,
939 newWidth,
940 newHeight,
941 (moveAccepted) ? "T" : "F");
942 cin.get();
943 }
944
945 if (std::abs(in_curr_solution.height(i)
946 - blockinfo.currDimensions[i].height[theta])
947 > 1e-6) {
948 printf(
949 "round[%d]: height of block[%d] is not consistent. "
950 "in_curr_soln: %.2f vs. blockinfo: %.2f move: %d prevMove: %d\n",
951 count,
952 i,
953 in_curr_solution.height(i),
954 blockinfo.currDimensions[i].height[theta],
955 move,
956 prev_move);
957 printf(
958 "round[%d]: oldWidth: %.2f oldHeight: %.2f newWidth: %.2f "
959 "newHeight: %.2f moveAccepted: %s\n",
960 count,
961 -1.0,
962 -1.0,
963 newWidth,
964 newHeight,
965 (moveAccepted) ? "T" : "F");
966 cin.get();
967 }
968
969 if (minWL
970 && std::abs(in_curr_solution.width(i)
971 - _db->getNodes()->getNodeWidth(i))
972 > 1e-6) {
973 printf(
974 "round[%d]: width of block[%d] is not consistent. "
975 "in_curr_solution: %.2f vs._db: %.2f move: %d\n",
976 count,
977 i,
978 in_curr_solution.width(i),
979 _db->getNodes()->getNodeWidth(i),
980 move);
981 cin.get();
982 }
983
984 if (in_curr_solution.width(i) < 1e-10
985 || in_curr_solution.height(i) < 1e-10) {
986 printf("round[%d]: width of block[%d]: %f height: %f move: %d\n",
987 count,
988 i,
989 in_curr_solution.width(i),
990 in_curr_solution.height(i),
991 move);
992 cin.get();
993 }
994 }
995 // -----end of debugging messages-----
996 #endif
997 // cout << "iter: " << iter << " size: " << 4*size << " bTime: " <<
998 // budgetTime << endl;
999 }
1000 // while (iter < 4*size || budgetTime);
1001 while (iter < 10 * size || budgetTime);
1002
1003 // cout << "whileBreak Iter: " << iter << endl;
1004 // finish the loop under constant temperature
1005
1006 // -----------------------------
1007 // update temperature "currTime"
1008 // -----------------------------
1009
1010 float alpha = UNINITIALIZED;
1011 ++timeChangeCtr;
1012 if (budgetTime) {
1013 percent = seconds / total;
1014
1015 if (percent < 0.66666 && percent > 0.33333)
1016 alpha = 0.9f;
1017 else if (percent < 0.33333 && percent > 0.16666)
1018 alpha = 0.95f;
1019 else if (percent < 0.16666 && percent > 0.06666)
1020 alpha = 0.96f;
1021 else if (percent < .06666 && percent > .00333)
1022 alpha = 0.8f;
1023 else if (percent < .00333 && percent > .00003)
1024 alpha = 0.98f;
1025 else
1026 alpha = 0.85f;
1027 } else {
1028 if (currTime < 2000 && currTime > 1000)
1029 alpha = 0.9f;
1030 else if (currTime < 1000 && currTime > 500)
1031 alpha = 0.95f;
1032 else if (currTime < 500 && currTime > 200)
1033 alpha = 0.96f;
1034 else if (currTime < 200 && currTime > 10)
1035 alpha = 0.96f;
1036 else if (currTime < 15 && currTime > 0.1)
1037 alpha = 0.98f;
1038 else
1039 alpha = 0.85f;
1040 }
1041 // cout << "currTime: " << currTime << " -> ";
1042 currTime *= alpha;
1043 // cout << currTime << endl;
1044 if (brokeFromLoop)
1045 break;
1046 }
1047 if (saved_best)
1048 in_curr_solution = in_best_solution;
1049 // if(_params->verb.getForActions() > 0)
1050 // cout << "NumMoves attempted: " << count << endl;
1051 if (reqdAR != FREE_OUTLINE)
1052 return false;
1053 else
1054 return true;
1055 }
1056
1057 // --------------------------------------------------------
takePlfromDB()1058 void BTreeAreaWireAnnealer::takePlfromDB()
1059 {
1060 Pl2BTree converter(_db->getXLocs(),
1061 _db->getYLocs(),
1062 _db->getNodeWidths(),
1063 _db->getNodeHeights(),
1064 Pl2BTree::TCG);
1065 in_curr_solution.evaluate(converter.btree());
1066 in_next_solution = in_curr_solution;
1067 }
1068 // --------------------------------------------------------
compactSoln(bool minWL,bool fixedOutline,float reqdH,float reqdW)1069 void BTreeAreaWireAnnealer::compactSoln(bool minWL,
1070 bool fixedOutline,
1071 float reqdH,
1072 float reqdW)
1073 {
1074 // TO DO: have this function check for WL and fixedOutline
1075 BTreeCompactor compactor(in_curr_solution);
1076
1077 int round = 0;
1078 int numBlkChange = compactor.compact();
1079 float lastArea = in_curr_solution.totalArea();
1080 float currArea = compactor.totalArea();
1081 while (numBlkChange > 0) {
1082 if (_params->verb)
1083 printf("round[%d] %d blks moved, area: %.2f -> %.2f\n",
1084 round,
1085 numBlkChange,
1086 lastArea,
1087 currArea);
1088
1089 numBlkChange = compactor.compact();
1090 round++;
1091 lastArea = currArea;
1092 currArea = compactor.totalArea();
1093 }
1094 if (_params->verb > 0)
1095 printf("round[%d] %d blks moved, area: %.2f -> %.2f\n",
1096 round,
1097 numBlkChange,
1098 lastArea,
1099 currArea);
1100
1101 in_curr_solution = compactor;
1102 DBfromSoln(in_curr_solution);
1103 }
1104 // --------------------------------------------------------
makeMove(int & indexOrient,parquetfp::ORIENT & newOrient,parquetfp::ORIENT & oldOrient)1105 int BTreeAreaWireAnnealer::makeMove(int& indexOrient,
1106 parquetfp::ORIENT& newOrient,
1107 parquetfp::ORIENT& oldOrient)
1108 {
1109 BTree::MoveType move = get_move();
1110 indexOrient = UNSIGNED_UNINITIALIZED;
1111 newOrient = parquetfp::N;
1112 oldOrient = parquetfp::N;
1113 switch (move) {
1114 case BTree::SWAP:
1115 // cout << "makeMoveSwap" << endl;
1116 perform_swap();
1117 return 1;
1118
1119 case BTree::ROTATE:
1120 // cout << "makeMoveRotate" << endl;
1121 perform_rotate(indexOrient, newOrient, oldOrient);
1122 return int(REP_SPEC_ORIENT);
1123
1124 case BTree::MOVE:
1125 // cout << "makeMoveSimple" << endl;
1126 perform_move();
1127 return 3;
1128
1129 default:
1130 cout << "ERROR: invalid move specified in makeMove()" << endl;
1131 exit(1);
1132 }
1133 return MISC;
1134 }
1135 // --------------------------------------------------------
makeMoveSlacks()1136 int BTreeAreaWireAnnealer::makeMoveSlacks()
1137 {
1138 // cout << "makeMoveSlacks" << endl;
1139 int movedir = rand() % 100;
1140 int threshold = 50;
1141 bool horizontal = (movedir < threshold);
1142
1143 makeMoveSlacksCore(horizontal);
1144
1145 static int total = 0;
1146 static int numHoriz = 0;
1147
1148 total++;
1149 numHoriz += ((horizontal) ? 1 : 0);
1150
1151 if (total % 1000 == 0 && _params->verb > 0)
1152 cout << "total: " << total << "horiz: " << numHoriz << endl;
1153 return SLACKS_MOVE;
1154 }
1155 // --------------------------------------------------------
makeARMove()1156 int BTreeAreaWireAnnealer::makeARMove()
1157 {
1158 // cout << "makeARMove" << endl;
1159 float currWidth = in_curr_solution.totalWidth();
1160 float currHeight = in_curr_solution.totalHeight();
1161 float currAR = currWidth / currHeight;
1162
1163 const float reqdAR = _params->reqdAR;
1164 bool horizontal = currAR > reqdAR;
1165
1166 makeMoveSlacksCore(horizontal);
1167 return AR_MOVE;
1168 }
1169 // --------------------------------------------------------
makeMoveSlacksCore(bool horizontal)1170 void BTreeAreaWireAnnealer::makeMoveSlacksCore(bool horizontal)
1171 {
1172 // cout << "makeMoveSlacksCore" << endl;
1173 _slackEval->evaluateSlacks(in_curr_solution);
1174 // cout << "End SlackEval!!" << endl;
1175
1176 vector<int> indices_sorted;
1177 const vector<float>& slacks
1178 = (horizontal) ? _slackEval->xSlack() : _slackEval->ySlack();
1179
1180 sort_slacks(slacks, indices_sorted);
1181
1182 int blocknum = in_curr_solution.NUM_BLOCKS;
1183 int range = int(ceil(blocknum / 5.0));
1184
1185 int operand_ptr = rand() % range;
1186 int operand = indices_sorted[operand_ptr];
1187 while (operand_ptr > 0 && slacks[operand] > 0) {
1188 operand_ptr--;
1189 operand = indices_sorted[operand_ptr];
1190 }
1191
1192 int target_ptr = blocknum - 1 - (rand() % range);
1193 int target = indices_sorted[target_ptr];
1194 while (target_ptr < (blocknum - 1) && slacks[target] <= 0) {
1195 target_ptr++;
1196 target = indices_sorted[target_ptr];
1197 }
1198
1199 if (target == operand || slacks[operand] < 0 || slacks[target] < 0)
1200 return;
1201
1202 in_next_solution = in_curr_solution;
1203 in_next_solution.move(operand, target, horizontal);
1204 }
1205 // --------------------------------------------------------
makeHPWLMove()1206 int BTreeAreaWireAnnealer::makeHPWLMove()
1207 {
1208 // cout << "makeHPWLMove" << endl;
1209 int size = in_curr_solution.NUM_BLOCKS;
1210 int operand = rand() % size;
1211 int target = UNSIGNED_UNINITIALIZED;
1212
1213 vector<int> searchBlocks;
1214 locateSearchBlocks(operand, searchBlocks);
1215
1216 if (searchBlocks.size() > 0) {
1217 int temp = rand() % searchBlocks.size();
1218 target = searchBlocks[temp];
1219 } else {
1220 do
1221 target = rand() % size;
1222 while (target == operand);
1223 }
1224
1225 bool leftChild = bool(rand() % 2);
1226 in_next_solution = in_curr_solution;
1227 in_next_solution.move(operand, target, leftChild);
1228 return HPWL;
1229 }
1230 // --------------------------------------------------------
makeARWLMove()1231 int BTreeAreaWireAnnealer::makeARWLMove()
1232 {
1233 // cout << "makeARWLMove" << endl;
1234 // cout << "before EvalSlack xloc yloc" << endl;
1235 // for(int i=0; i<in_curr_solution.NUM_BLOCKS; i++) {
1236 // cout << i << " " << in_curr_solution.xloc(i) << " " <<
1237 // in_curr_solution.yloc(i) << endl;
1238 // }
1239 _slackEval->evaluateSlacks(in_curr_solution);
1240
1241 // cout << "End SlackEval!!" << endl;
1242 // for(int i=0; i<in_curr_solution.NUM_BLOCKS; i++) {
1243 // cout << i << " " << in_curr_solution.xloc(i) << " " <<
1244 // in_curr_solution.yloc(i) << endl;
1245 // }
1246
1247 const float reqdAR = _params->reqdAR;
1248 const float currAR
1249 = in_curr_solution.totalWidth() / in_curr_solution.totalHeight();
1250 const bool horizontal = currAR > reqdAR;
1251 const vector<float>& slacks
1252 = (horizontal) ? _slackEval->xSlack() : _slackEval->ySlack();
1253
1254 vector<int> indices_sorted;
1255 sort_slacks(slacks, indices_sorted);
1256
1257 int blocknum = in_curr_solution.NUM_BLOCKS;
1258 int range = int(ceil(blocknum / 5.0));
1259
1260 int operand_ptr = rand() % range;
1261 int operand = indices_sorted[operand_ptr];
1262 while (operand_ptr > 0 && slacks[operand] > 0) {
1263 operand_ptr--;
1264 operand = indices_sorted[operand_ptr];
1265 }
1266
1267 vector<int> searchBlocks;
1268 locateSearchBlocks(operand, searchBlocks);
1269
1270 int target = UNSIGNED_UNINITIALIZED;
1271 float maxSlack = -1;
1272 if (searchBlocks.size() == 0) {
1273 do
1274 target = rand() % blocknum;
1275 while (target == operand);
1276 } else {
1277 for (unsigned int i = 0; i < searchBlocks.size(); i++) {
1278 int thisBlk = searchBlocks[i];
1279 if (slacks[thisBlk] > maxSlack) {
1280 maxSlack = slacks[thisBlk];
1281 target = thisBlk;
1282 }
1283 }
1284 }
1285
1286 if (target == operand || slacks[operand] < 0 || maxSlack < 0) {
1287 // <aaronnn> couldn't lock on a target; let's not make any risky moves
1288 // TODO: don't waste this move - pick something reasonable to move
1289 return ARWL;
1290 }
1291
1292 // cout << "REVERT!!! xloc yloc" << endl;
1293 // for(int i=0; i<in_curr_solution.NUM_BLOCKS; i++) {
1294 // cout << i << " " << in_curr_solution.xloc(i) << " " <<
1295 // in_curr_solution.yloc(i) << endl;
1296 // }
1297 in_next_solution = in_curr_solution;
1298 // cout << "next solution move!!!" << endl;
1299 // in_curr_solution.move(operand, target, horizontal);
1300 in_next_solution.move(operand, target, horizontal);
1301 return ARWL;
1302 }
1303 // --------------------------------------------------------
makeSoftBlMove(int & index,float & newWidth,float & newHeight)1304 int BTreeAreaWireAnnealer::makeSoftBlMove(int& index,
1305 float& newWidth,
1306 float& newHeight)
1307 {
1308 _slackEval->evaluateSlacks(in_curr_solution);
1309
1310 int moveDir = rand() % 2;
1311 bool horizontal = (moveDir % 2 == 0);
1312 index = getSoftBlIndex(horizontal);
1313
1314 if (index == NOT_FOUND)
1315 index = getSoftBlIndex(!horizontal);
1316
1317 if (index != NOT_FOUND) {
1318 return getSoftBlNewDimensions(index, newWidth, newHeight);
1319 } else {
1320 newWidth = NOT_FOUND;
1321 newHeight = NOT_FOUND;
1322 return MISC;
1323 }
1324 }
1325 // --------------------------------------------------------
getSoftBlIndex(bool horizontal) const1326 int BTreeAreaWireAnnealer::getSoftBlIndex(bool horizontal) const
1327 {
1328 const int blocknum = in_curr_solution.NUM_BLOCKS;
1329 const vector<float>& slacks
1330 = (horizontal) ? _slackEval->xSlack() : _slackEval->ySlack();
1331
1332 const vector<float>& orth_slacks
1333 = (horizontal) ? _slackEval->ySlack() : _slackEval->xSlack();
1334
1335 vector<int> indices_sorted;
1336 sort_slacks(slacks, indices_sorted);
1337
1338 int operand = NOT_FOUND; // "-1" stands for not found
1339 for (int i = 0; (i < blocknum) && (operand == NOT_FOUND); i++) {
1340 int index = indices_sorted[i];
1341 if (slacks[index] < 0 || orth_slacks[index] < 0) {
1342 // <aaronnn> skip these blocks affected by obstacles
1343 continue;
1344 }
1345
1346 if (blockinfo.blockARinfo[index].isSoft) {
1347 int theta = in_curr_solution.tree[index].orient;
1348 float minAR = blockinfo.blockARinfo[index].minAR[theta];
1349 float maxAR = blockinfo.blockARinfo[index].maxAR[theta];
1350
1351 float currWidth = in_curr_solution.width(index);
1352 float currHeight = in_curr_solution.height(index);
1353 float currAR = currWidth / currHeight;
1354
1355 bool adjustable = (horizontal) ? (currAR > minAR) : (currAR < maxAR);
1356
1357 float reqdLength = (horizontal) ? _outlineHeight : _outlineWidth;
1358 float currLength = (horizontal) ? currHeight : currWidth;
1359 float slackAdjustment
1360 = ((_isFixedOutline) ? currLength - reqdLength : 0.0);
1361 float normalizedSlack = orth_slacks[index] - slackAdjustment;
1362 if (normalizedSlack > 0 && adjustable)
1363 operand = index;
1364 }
1365 }
1366 return operand;
1367 }
1368 // --------------------------------------------------------
getSoftBlNewDimensions(int index,float & newWidth,float & newHeight) const1369 int BTreeAreaWireAnnealer::getSoftBlNewDimensions(int index,
1370 float& newWidth,
1371 float& newHeight) const
1372 {
1373 if (_slackEval->xSlack()[index] < 0 || _slackEval->ySlack()[index] < 0) {
1374 // don't touch nodes around obstacles
1375 return NOOP;
1376 }
1377
1378 if (blockinfo.blockARinfo[index].isSoft) {
1379 float origWidth = in_curr_solution.width(index);
1380 float origHeight = in_curr_solution.height(index);
1381 float indexArea = blockinfo.blockARinfo[index].area;
1382
1383 int theta = in_curr_solution.tree[index].orient;
1384 float minAR = blockinfo.blockARinfo[index].minAR[theta];
1385 float maxAR = blockinfo.blockARinfo[index].maxAR[theta];
1386 if (_isFixedOutline) {
1387 const bool agressiveAR = false;
1388 // ((in_curr_solution.totalArea() / _outlineArea - 1)
1389 // < _params->startSoftMovePercent / 100.0);
1390 minAR = (agressiveAR) ? minAR : max(minAR, float(1.0 / 3.0));
1391 maxAR = (agressiveAR) ? maxAR : min(maxAR, float(3.0));
1392 }
1393
1394 float maxWidth = sqrt(indexArea * maxAR);
1395 float minWidth = sqrt(indexArea * minAR);
1396
1397 float maxHeight = sqrt(indexArea / minAR);
1398 float minHeight = sqrt(indexArea / maxAR);
1399
1400 float indexSlackX = _slackEval->xSlack()[index];
1401 float indexSlackY = _slackEval->ySlack()[index];
1402
1403 // adjustment <= 0.75 * actual slack
1404 float slackAdjustmentX
1405 = (_isFixedOutline) ? (in_curr_solution.totalWidth() - _outlineWidth)
1406 : 0.0;
1407 // slackAdjustmentX = max(slackAdjustmentX, 0.0);
1408 // slackAdjustmentX = min(slackAdjustmentX, 0.75 * indexSlackX);
1409
1410 float slackAdjustmentY
1411 = (_isFixedOutline) ? (in_curr_solution.totalHeight() - _outlineHeight)
1412 : 0.0;
1413 // slackAdjustmentY = max(slackAdjustmentY, 0.0);
1414 // slackAdjustmentY = min(slackAdjustmentY, 0.75 * indexSlackY);
1415
1416 float normalizedSlackX = indexSlackX - slackAdjustmentX;
1417 float normalizedSlackY = indexSlackY - slackAdjustmentY;
1418 if (normalizedSlackX > normalizedSlackY) {
1419 newWidth = min(origWidth + normalizedSlackX, maxWidth);
1420 newWidth = max(newWidth, minWidth);
1421
1422 newHeight = indexArea / newWidth;
1423 } else {
1424 newHeight = min(origHeight + normalizedSlackY, maxHeight);
1425 newHeight = max(newHeight, minHeight);
1426
1427 newWidth = indexArea / newHeight;
1428 }
1429 return SOFT_BL;
1430 } else
1431 return NOOP;
1432 }
1433 // --------------------------------------------------------
packSoftBlocks(int numIter)1434 int BTreeAreaWireAnnealer::packSoftBlocks(int numIter)
1435 {
1436 const int NUM_BLOCKS = in_curr_solution.NUM_BLOCKS;
1437 for (int iter = 0; iter < numIter; iter++) {
1438 bool horizontal = (iter % 2 == 0);
1439 _slackEval->evaluateSlacks(in_curr_solution);
1440
1441 const vector<float>& slacks
1442 = (horizontal) ? _slackEval->xSlack() : _slackEval->ySlack();
1443
1444 vector<int> indices_sorted;
1445 sort_slacks(slacks, indices_sorted);
1446 for (int i = 0; i < NUM_BLOCKS; i++) {
1447 int index = indices_sorted[i];
1448 if (slacks[index] < 0) {
1449 // <aaronnn> skip these blocks affected by obstacles
1450 continue;
1451 }
1452
1453 float origWidth = in_curr_solution.width(index);
1454 float origHeight = in_curr_solution.height(index);
1455
1456 float newWidth, newHeight;
1457 int softDecision = makeIndexSoftBlMove(index, newWidth, newHeight);
1458
1459 if (softDecision == SOFT_BL) {
1460 // change dimensions only when needed
1461 int theta = in_curr_solution.tree[index].orient;
1462 _blockinfo.setBlockDimensions(index, newWidth, newHeight, theta);
1463
1464 in_next_solution.evaluate(in_curr_solution.tree);
1465
1466 float origTotalArea = in_curr_solution.totalArea();
1467 float newTotalArea = in_next_solution.totalArea();
1468 if (newTotalArea < origTotalArea) {
1469 in_curr_solution = in_next_solution;
1470 if (_params->minWL) {
1471 _db->getNodes()->putNodeWidth(index, newWidth);
1472 _db->getNodes()->putNodeHeight(index, newHeight);
1473 }
1474 } else {
1475 _blockinfo.setBlockDimensions(index, origWidth, origHeight, theta);
1476 }
1477 }
1478 }
1479 }
1480 return MISC;
1481 }
1482 // --------------------------------------------------------
locateSearchBlocks(int operand,vector<int> & searchBlocks)1483 void BTreeAreaWireAnnealer::locateSearchBlocks(int operand,
1484 vector<int>& searchBlocks)
1485 {
1486 int size = in_curr_solution.NUM_BLOCKS;
1487 vector<bool> seenBlocks(size, false);
1488 seenBlocks[operand] = true;
1489 float unitRadiusSize
1490 = max(in_curr_solution.totalWidth(), in_curr_solution.totalHeight());
1491 unitRadiusSize /= sqrt(float(size));
1492
1493 vector<float>& xloc = const_cast<vector<float>&>(in_curr_solution.xloc());
1494 vector<float>& yloc = const_cast<vector<float>&>(in_curr_solution.yloc());
1495 parquetfp::Point idealLoc(_analSolve->getOptLoc(operand, xloc, yloc));
1496 // get optimum location of "operand"
1497
1498 int searchRadiusNum = int(ceil(size / 5.0));
1499 float searchRadius = 0;
1500 for (int i = 0; ((i < searchRadiusNum)
1501 && (searchBlocks.size() < unsigned(searchRadiusNum)));
1502 ++i) {
1503 searchRadius += unitRadiusSize;
1504 for (int j = 0;
1505 ((j < size) && (searchBlocks.size() < unsigned(searchRadiusNum)));
1506 ++j) {
1507 if (!seenBlocks[j]) {
1508 float xDist = xloc[j] - idealLoc.x;
1509 float yDist = yloc[j] - idealLoc.y;
1510 float distance = sqrt(xDist * xDist + yDist * yDist);
1511 if (distance < searchRadius) {
1512 seenBlocks[j] = true;
1513 searchBlocks.push_back(j);
1514 }
1515 }
1516 }
1517 }
1518 }
1519 // --------------------------------------------------------
GenerateRandomSoln(BTree & soln,int blocknum)1520 void BTreeAreaWireAnnealer::GenerateRandomSoln(BTree& soln, int blocknum)
1521 {
1522 vector<int> tree_bits;
1523 int balance = 0;
1524 int num_zeros = 0;
1525 for (int i = 0; i < 2 * blocknum; i++) {
1526 float rand_num = float(rand()) / (RAND_MAX + 1.0);
1527 float threshold;
1528
1529 if (balance == 0)
1530 threshold = 1; // push_back "0" for sure
1531 else if (num_zeros == blocknum)
1532 threshold = 0; // push_back "1" for sure
1533 else
1534 threshold = 1; // (rand_num * (balance - rand_num));
1535
1536 if (rand_num >= threshold) {
1537 tree_bits.push_back(1);
1538 balance--;
1539 } else {
1540 tree_bits.push_back(0);
1541 balance++;
1542 num_zeros++;
1543 }
1544 }
1545
1546 vector<int> tree_perm;
1547 tree_perm.resize(blocknum);
1548 for (int i = 0; i < blocknum; i++)
1549 tree_perm[i] = i;
1550 std::shuffle(tree_perm.begin(), tree_perm.end(), _random_gen);
1551
1552 vector<int> tree_perm_inverse(blocknum);
1553 for (int i = 0; i < blocknum; i++)
1554 tree_perm_inverse[tree_perm[i]] = i;
1555
1556 vector<int> tree_orient(blocknum);
1557 for (int i = 0; i < blocknum; i++) {
1558 int rand_num = int(8 * (float(rand()) / (RAND_MAX + 1.0)));
1559 rand_num = _physicalOrient[i][rand_num];
1560
1561 tree_orient[tree_perm_inverse[i]] = rand_num;
1562 }
1563
1564 soln.evaluate(tree_bits, tree_perm, tree_orient);
1565 }
1566 // --------------------------------------------------------
getObstaclesFromDB(DB * const db,BasePacking & out)1567 void getObstaclesFromDB(DB* const db, BasePacking& out)
1568 // <aaronnn> massage db obstacles from Node into BlockPacking
1569 {
1570 out.xloc.clear();
1571 out.yloc.clear();
1572 out.width.clear();
1573 out.height.clear();
1574
1575 Nodes* nodes = db->getObstacles();
1576 // Node tmp1("obs1", 400*300, 400/300, 400/300, 0, false);
1577 // tmp1.putX( 200 );
1578 // tmp1.putY( 200 );
1579 // tmp1.putWidth( 100 );
1580 // tmp1.putHeight( 100 );
1581 //
1582 // nodes->putNewNode(tmp1 );
1583 //
1584 // Node tmp2("obs2", 50*50, 50/50, 50/50, 0, false);
1585 // tmp2.putX( 100 );
1586 // tmp2.putY( 100 );
1587 // tmp2.putWidth( 50 );
1588 // tmp2.putHeight( 50 );
1589 //
1590 // nodes->putNewNode(tmp2 );
1591
1592 for (unsigned i = 0; i < nodes->getNumNodes(); ++i) {
1593 Node& node = nodes->getNode(i);
1594
1595 out.xloc.push_back(node.getX());
1596 out.yloc.push_back(node.getY());
1597 out.width.push_back(node.getWidth());
1598 out.height.push_back(node.getHeight());
1599 }
1600 // out.xloc.push_back(0);
1601 // out.yloc.push_back(0);
1602 // out.width.push_back(200);
1603 // out.height.push_back(50);
1604
1605 // out.xloc.push_back(100);
1606 // out.yloc.push_back(50);
1607 // out.width.push_back(50);
1608 // out.height.push_back(50);
1609 }
1610 // --------------------------------------------------------
1611
1612 } // namespace parquetfp
1613