1 ///////////////////////////////////////////////////////////////////////////////
2 // BSD 3-Clause License
3 //
4 // Copyright (c) 2018-2020, The Regents of the University of California
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright notice, this
11 // list of conditions and the following disclaimer.
12 //
13 // * Redistributions in binary form must reproduce the above copyright notice,
14 // this list of conditions and the following disclaimer in the documentation
15 // and/or other materials provided with the distribution.
16 //
17 // * Neither the name of the copyright holder nor the names of its
18 // contributors may be used to endorse or promote products derived from
19 // this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 // ARE
25 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
26 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
28 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ///////////////////////////////////////////////////////////////////////////////
33
34 #include "opendb/db.h"
35
36 #include "nesterovBase.h"
37 #include "placerBase.h"
38 #include "fft.h"
39 #include "utl/Logger.h"
40
41 #include <iostream>
42 #include <random>
43 #include <algorithm>
44
45
46 #define REPLACE_SQRT2 1.414213562373095048801L
47
48 namespace gpl {
49
50 using utl::GPL;
51
52 using namespace std;
53 using namespace odb;
54
55 static int
56 fastModulo(const int input, const int ceil);
57
58 static int64_t
59 getOverlapArea(const Bin* bin, const Instance* inst);
60
61 // Note that
62 // int64_t is ideal in the following function, but
63 // runtime is doubled compared with float.
64 //
65 // Choose to use "float" only in the following functions
66 static float
67 getOverlapDensityArea(const Bin* bin, const GCell* cell);
68
69 static float
70 fastExp(float exp);
71
72
73 ////////////////////////////////////////////////
74 // GCell
75
GCell()76 GCell::GCell()
77 : lx_(0), ly_(0), ux_(0), uy_(0),
78 dLx_(0), dLy_(0), dUx_(0), dUy_(0),
79 densityScale_(0),
80 gradientX_(0), gradientY_(0) {}
81
82
GCell(Instance * inst)83 GCell::GCell(Instance* inst)
84 : GCell() {
85 setInstance(inst);
86 }
87
GCell(const std::vector<Instance * > & insts)88 GCell::GCell(const std::vector<Instance*>& insts)
89 : GCell() {
90 setClusteredInstance(insts);
91 }
92
GCell(int cx,int cy,int dx,int dy)93 GCell::GCell(int cx, int cy, int dx, int dy)
94 : GCell() {
95 dLx_ = lx_ = cx - dx/2;
96 dLy_ = ly_ = cy - dy/2;
97 dUx_ = ux_ = cx + dx/2;
98 dUy_ = uy_ = cy + dy/2;
99 setFiller();
100 }
101
~GCell()102 GCell::~GCell() {
103 insts_.clear();
104 }
105
106 void
setInstance(Instance * inst)107 GCell::setInstance(Instance* inst) {
108 insts_.push_back(inst);
109 // density coordi has the same center points.
110 dLx_ = lx_ = inst->lx();
111 dLy_ = ly_ = inst->ly();
112 dUx_ = ux_ = inst->ux();
113 dUy_ = uy_ = inst->uy();
114 }
115
116 Instance*
instance() const117 GCell::instance() const {
118 return *insts_.begin();
119 }
120
121 void
addGPin(GPin * gPin)122 GCell::addGPin(GPin* gPin) {
123 gPins_.push_back(gPin);
124 }
125
126
127 // do nothing
128 void
setFiller()129 GCell::setFiller() {
130 }
131
132 void
setClusteredInstance(const std::vector<Instance * > & insts)133 GCell::setClusteredInstance(const std::vector<Instance*>& insts) {
134 insts_ = insts;
135 }
136
137 void
setMacroInstance()138 GCell::setMacroInstance() {
139 isMacroInstance_ = true;
140 }
141
142 void
setStdInstance()143 GCell::setStdInstance() {
144 isMacroInstance_ = false;
145 }
146
147 void
setLocation(int lx,int ly)148 GCell::setLocation(int lx, int ly) {
149 ux_ = lx + (ux_ - lx_);
150 uy_ = ly + (uy_ - ly_);
151 lx = lx_;
152 ly = ly_;
153
154 for(auto& gPin: gPins_) {
155 gPin->updateLocation(this);
156 }
157 }
158
159 void
setCenterLocation(int cx,int cy)160 GCell::setCenterLocation(int cx, int cy) {
161 const int halfDx = dx()/2;
162 const int halfDy = dy()/2;
163
164 lx_ = cx - halfDx;
165 ly_ = cy - halfDy;
166 ux_ = cx + halfDx;
167 uy_ = cy + halfDy;
168
169 for(auto& gPin: gPins_) {
170 gPin->updateLocation(this);
171 }
172 }
173
174 // changing size and preserve center coordinates
175 void
setSize(int dx,int dy)176 GCell::setSize(int dx, int dy) {
177 const int centerX = cx();
178 const int centerY = cy();
179
180 lx_ = centerX - dx/2;
181 ly_ = centerY - dy/2;
182 ux_ = centerX + dx/2;
183 uy_ = centerY + dy/2;
184 }
185
186 void
setDensityLocation(int dLx,int dLy)187 GCell::setDensityLocation(int dLx, int dLy) {
188 dUx_ = dLx + (dUx_ - dLx_);
189 dUy_ = dLy + (dUy_ - dLy_);
190 dLx_ = dLx;
191 dLy_ = dLy;
192
193 // assume that density Center change the gPin coordi
194 for(auto& gPin: gPins_) {
195 gPin->updateDensityLocation(this);
196 }
197 }
198
199 void
setDensityCenterLocation(int dCx,int dCy)200 GCell::setDensityCenterLocation(int dCx, int dCy) {
201 const int halfDDx = dDx()/2;
202 const int halfDDy = dDy()/2;
203
204 dLx_ = dCx - halfDDx;
205 dLy_ = dCy - halfDDy;
206 dUx_ = dCx + halfDDx;
207 dUy_ = dCy + halfDDy;
208
209
210 // assume that density Center change the gPin coordi
211 for(auto& gPin: gPins_) {
212 gPin->updateDensityLocation(this);
213 }
214 }
215
216 // changing size and preserve center coordinates
217 void
setDensitySize(int dDx,int dDy)218 GCell::setDensitySize(int dDx, int dDy) {
219 const int dCenterX = dCx();
220 const int dCenterY = dCy();
221
222 dLx_ = dCenterX - dDx/2;
223 dLy_ = dCenterY - dDy/2;
224 dUx_ = dCenterX + dDx/2;
225 dUy_ = dCenterY + dDy/2;
226 }
227
228 void
setDensityScale(float densityScale)229 GCell::setDensityScale(float densityScale) {
230 densityScale_ = densityScale;
231 }
232
233 void
setGradientX(float gradientX)234 GCell::setGradientX(float gradientX) {
235 gradientX_ = gradientX;
236 }
237
238 void
setGradientY(float gradientY)239 GCell::setGradientY(float gradientY) {
240 gradientY_ = gradientY;
241 }
242
243 bool
isInstance() const244 GCell::isInstance() const {
245 return (insts_.size() == 1);
246 }
247
248 bool
isClusteredInstance() const249 GCell::isClusteredInstance() const {
250 return (insts_.size() > 0);
251 }
252
253 bool
isFiller() const254 GCell::isFiller() const {
255 return (insts_.size() == 0);
256 }
257
258 bool
isMacroInstance() const259 GCell::isMacroInstance() const {
260 if( !isInstance() ) {
261 return false;
262 }
263 return isMacroInstance_;
264 }
265
266 bool
isStdInstance() const267 GCell::isStdInstance() const {
268 if( !isInstance() ) {
269 return false;
270 }
271 return !isMacroInstance_;
272 }
273
274 ////////////////////////////////////////////////
275 // GNet
276
GNet()277 GNet::GNet()
278 : lx_(0), ly_(0), ux_(0), uy_(0),
279 timingWeight_(1), customWeight_(1),
280 waExpMinSumX_(0), waXExpMinSumX_(0),
281 waExpMaxSumX_(0), waXExpMaxSumX_(0),
282 waExpMinSumY_(0), waYExpMinSumY_(0),
283 waExpMaxSumY_(0), waYExpMaxSumY_(0),
284 isDontCare_(0) {}
285
GNet(Net * net)286 GNet::GNet(Net* net) : GNet() {
287 nets_.push_back(net);
288 }
289
GNet(const std::vector<Net * > & nets)290 GNet::GNet(const std::vector<Net*>& nets) : GNet() {
291 nets_ = nets;
292 }
293
~GNet()294 GNet::~GNet() {
295 gPins_.clear();
296 nets_.clear();
297 }
298
299 Net*
net() const300 GNet::net() const {
301 return *nets_.begin();
302 }
303
304 void
setTimingWeight(float timingWeight)305 GNet::setTimingWeight(float timingWeight) {
306 timingWeight_ = timingWeight;
307 }
308
309 void
setCustomWeight(float customWeight)310 GNet::setCustomWeight(float customWeight) {
311 customWeight_ = customWeight;
312 }
313
314 void
addGPin(GPin * gPin)315 GNet::addGPin(GPin* gPin) {
316 gPins_.push_back(gPin);
317 }
318
319 void
updateBox()320 GNet::updateBox() {
321 lx_ = ly_ = INT_MAX;
322 ux_ = uy_ = INT_MIN;
323
324 for(auto& gPin : gPins_) {
325 lx_ = std::min(gPin->cx(), lx_);
326 ly_ = std::min(gPin->cy(), ly_);
327 ux_ = std::max(gPin->cx(), ux_);
328 uy_ = std::max(gPin->cy(), uy_);
329 }
330 }
331
332 int64_t
hpwl() const333 GNet::hpwl() const {
334 return static_cast<int64_t>((ux_ - lx_) + (uy_ - ly_));
335 }
336
337 void
clearWaVars()338 GNet::clearWaVars() {
339 waExpMinSumX_ = 0;
340 waXExpMinSumX_ = 0;
341
342 waExpMaxSumX_ = 0;
343 waXExpMaxSumX_ = 0;
344
345 waExpMinSumY_ = 0;
346 waYExpMinSumY_ = 0;
347
348 waExpMaxSumY_ = 0;
349 waYExpMaxSumY_ = 0;
350 }
351
352
353 void
setDontCare()354 GNet::setDontCare() {
355 isDontCare_ = 1;
356 }
357
358 bool
isDontCare() const359 GNet::isDontCare() const {
360 return (gPins_.size() == 0) || (isDontCare_ == 1);
361 }
362
363 ////////////////////////////////////////////////
364 // GPin
365
GPin()366 GPin::GPin()
367 : gCell_(nullptr), gNet_(nullptr),
368 offsetCx_(0), offsetCy_(0),
369 cx_(0), cy_(0),
370 maxExpSumX_(0), maxExpSumY_(0),
371 minExpSumX_(0), minExpSumY_(0),
372 hasMaxExpSumX_(0), hasMaxExpSumY_(0),
373 hasMinExpSumX_(0), hasMinExpSumY_(0) {}
374
GPin(Pin * pin)375 GPin::GPin(Pin* pin)
376 : GPin() {
377 pins_.push_back(pin);
378 cx_ = pin->cx();
379 cy_ = pin->cy();
380 offsetCx_ = pin->offsetCx();
381 offsetCy_ = pin->offsetCy();
382 }
383
GPin(const std::vector<Pin * > & pins)384 GPin::GPin(const std::vector<Pin*> & pins) {
385 pins_ = pins;
386 }
387
~GPin()388 GPin::~GPin() {
389 gCell_ = nullptr;
390 gNet_ = nullptr;
391 pins_.clear();
392 }
393
394 Pin*
pin() const395 GPin::pin() const {
396 return *pins_.begin();
397 }
398
399 void
setGCell(GCell * gCell)400 GPin::setGCell(GCell* gCell) {
401 gCell_ = gCell;
402 }
403
404 void
setGNet(GNet * gNet)405 GPin::setGNet(GNet* gNet) {
406 gNet_ = gNet;
407 }
408
409 void
setCenterLocation(int cx,int cy)410 GPin::setCenterLocation(int cx, int cy) {
411 cx_ = cx;
412 cy_ = cy;
413 }
414
415 void
clearWaVars()416 GPin::clearWaVars() {
417 hasMaxExpSumX_ = 0;
418 hasMaxExpSumY_ = 0;
419 hasMinExpSumX_ = 0;
420 hasMinExpSumY_ = 0;
421
422 maxExpSumX_ = maxExpSumY_ = 0;
423 minExpSumX_ = minExpSumY_ = 0;
424 }
425
426 void
setMaxExpSumX(float maxExpSumX)427 GPin::setMaxExpSumX(float maxExpSumX) {
428 hasMaxExpSumX_ = 1;
429 maxExpSumX_ = maxExpSumX;
430 }
431
432 void
setMaxExpSumY(float maxExpSumY)433 GPin::setMaxExpSumY(float maxExpSumY) {
434 hasMaxExpSumY_ = 1;
435 maxExpSumY_ = maxExpSumY;
436 }
437
438 void
setMinExpSumX(float minExpSumX)439 GPin::setMinExpSumX(float minExpSumX) {
440 hasMinExpSumX_ = 1;
441 minExpSumX_ = minExpSumX;
442 }
443
444 void
setMinExpSumY(float minExpSumY)445 GPin::setMinExpSumY(float minExpSumY) {
446 hasMinExpSumY_ = 1;
447 minExpSumY_ = minExpSumY;
448 }
449
450
451 void
updateLocation(const GCell * gCell)452 GPin::updateLocation(const GCell* gCell) {
453 cx_ = gCell->cx() + offsetCx_;
454 cy_ = gCell->cy() + offsetCy_;
455 }
456
457 void
updateDensityLocation(const GCell * gCell)458 GPin::updateDensityLocation(const GCell* gCell) {
459 cx_ = gCell->dCx() + offsetCx_;
460 cy_ = gCell->dCy() + offsetCy_;
461 }
462
463 ////////////////////////////////////////////////////////
464 // Bin
465
Bin()466 Bin::Bin()
467 : x_(0), y_(0), lx_(0), ly_(0),
468 ux_(0), uy_(0),
469 nonPlaceArea_(0), instPlacedArea_(0),
470 fillerArea_(0),
471 density_ (0),
472 targetDensity_(0),
473 electroPhi_(0),
474 electroForceX_(0), electroForceY_(0) {}
475
Bin(int x,int y,int lx,int ly,int ux,int uy,float targetDensity)476 Bin::Bin(int x, int y, int lx, int ly, int ux, int uy, float targetDensity)
477 : Bin() {
478 x_ = x;
479 y_ = y;
480 lx_ = lx;
481 ly_ = ly;
482 ux_ = ux;
483 uy_ = uy;
484 targetDensity_ = targetDensity;
485 }
486
~Bin()487 Bin::~Bin() {
488 x_ = y_ = 0;
489 lx_ = ly_ = ux_ = uy_ = 0;
490 nonPlaceArea_ = instPlacedArea_ = fillerArea_ = 0;
491 electroPhi_ = electroForceX_ = electroForceY_ = 0;
492 density_ = targetDensity_ = 0;
493 }
494
495
496 const int64_t
binArea() const497 Bin::binArea() const {
498 return static_cast<int64_t>( dx() )
499 * static_cast<int64_t>( dy() );
500 }
501
502 float
density() const503 Bin::density() const {
504 return density_;
505 }
506
507 float
targetDensity() const508 Bin::targetDensity() const {
509 return targetDensity_;
510 }
511
512 float
electroForceX() const513 Bin::electroForceX() const {
514 return electroForceX_;
515 }
516
517 float
electroForceY() const518 Bin::electroForceY() const {
519 return electroForceY_;
520 }
521
522 float
electroPhi() const523 Bin::electroPhi() const {
524 return electroPhi_;
525 }
526
527 void
setDensity(float density)528 Bin::setDensity(float density) {
529 density_ = density;
530 }
531
532 void
setTargetDensity(float density)533 Bin::setTargetDensity(float density) {
534 targetDensity_ = density;
535 }
536
537 void
setElectroForce(float electroForceX,float electroForceY)538 Bin::setElectroForce(float electroForceX, float electroForceY) {
539 electroForceX_ = electroForceX;
540 electroForceY_ = electroForceY;
541 }
542
543 void
setElectroPhi(float phi)544 Bin::setElectroPhi(float phi) {
545 electroPhi_ = phi;
546 }
547
548 ////////////////////////////////////////////////
549 // BinGrid
550
BinGrid()551 BinGrid::BinGrid()
552 : lx_(0), ly_(0), ux_(0), uy_(0),
553 binCntX_(0), binCntY_(0),
554 binSizeX_(0), binSizeY_(0),
555 targetDensity_(0),
556 overflowArea_(0),
557 isSetBinCntX_(0), isSetBinCntY_(0) {}
558
BinGrid(Die * die)559 BinGrid::BinGrid(Die* die) : BinGrid() {
560 setCorePoints(die);
561 }
562
~BinGrid()563 BinGrid::~BinGrid() {
564 binStor_.clear();
565 bins_.clear();
566 binCntX_ = binCntY_ = 0;
567 binSizeX_ = binSizeY_ = 0;
568 isSetBinCntX_ = isSetBinCntY_ = 0;
569 overflowArea_ = 0;
570 }
571
572 void
setCorePoints(const Die * die)573 BinGrid::setCorePoints(const Die* die) {
574 lx_ = die->coreLx();
575 ly_ = die->coreLy();
576 ux_ = die->coreUx();
577 uy_ = die->coreUy();
578 }
579
580 void
setPlacerBase(const std::shared_ptr<PlacerBase> pb)581 BinGrid::setPlacerBase(const std::shared_ptr<PlacerBase> pb) {
582 pb_ = pb;
583 }
584
585 void
setLogger(utl::Logger * log)586 BinGrid::setLogger(utl::Logger* log) {
587 log_ = log;
588 }
589
590 void
setTargetDensity(float density)591 BinGrid::setTargetDensity(float density) {
592 targetDensity_ = density;
593 }
594
595 void
setBinCnt(int binCntX,int binCntY)596 BinGrid::setBinCnt(int binCntX, int binCntY) {
597 setBinCntX(binCntX);
598 setBinCntY(binCntY);
599 }
600
601 void
setBinCntX(int binCntX)602 BinGrid::setBinCntX(int binCntX) {
603 isSetBinCntX_ = 1;
604 binCntX_ = binCntX;
605 }
606
607 void
setBinCntY(int binCntY)608 BinGrid::setBinCntY(int binCntY) {
609 isSetBinCntY_ = 1;
610 binCntY_ = binCntY;
611 }
612
613 int
lx() const614 BinGrid::lx() const {
615 return lx_;
616 }
617 int
ly() const618 BinGrid::ly() const {
619 return ly_;
620 }
621
622 int
ux() const623 BinGrid::ux() const {
624 return ux_;
625 }
626
627 int
uy() const628 BinGrid::uy() const {
629 return uy_;
630 }
631
632 int
cx() const633 BinGrid::cx() const {
634 return (ux_ + lx_)/2;
635 }
636
637 int
cy() const638 BinGrid::cy() const {
639 return (uy_ + ly_)/2;
640 }
641
642 int
dx() const643 BinGrid::dx() const {
644 return (ux_ - lx_);
645 }
646 int
dy() const647 BinGrid::dy() const {
648 return (uy_ - ly_);
649 }
650 int
binCntX() const651 BinGrid::binCntX() const {
652 return binCntX_;
653 }
654
655 int
binCntY() const656 BinGrid::binCntY() const {
657 return binCntY_;
658 }
659
660 int
binSizeX() const661 BinGrid::binSizeX() const {
662 return binSizeX_;
663 }
664
665 int
binSizeY() const666 BinGrid::binSizeY() const {
667 return binSizeY_;
668 }
669
670 int64_t
overflowArea() const671 BinGrid::overflowArea() const {
672 return overflowArea_;
673 }
674
675
676
677 void
initBins()678 BinGrid::initBins() {
679
680 int64_t totalBinArea
681 = static_cast<int64_t>(ux_ - lx_)
682 * static_cast<int64_t>(uy_ - ly_);
683
684 int64_t averagePlaceInstArea
685 = pb_->placeInstsArea() / pb_->placeInsts().size();
686
687 int64_t idealBinArea =
688 std::round(static_cast<float>(averagePlaceInstArea) / targetDensity_);
689 int idealBinCnt = totalBinArea / idealBinArea;
690 if (idealBinCnt < 4) { // the smallest we allow is 2x2 bins
691 idealBinCnt = 4;
692 }
693
694 log_->info(GPL, 23, "TargetDensity: {:.2f}", targetDensity_);
695 log_->info(GPL, 24, "AveragePlaceInstArea: {}", averagePlaceInstArea);
696 log_->info(GPL, 25, "IdealBinArea: {}", idealBinArea);
697 log_->info(GPL, 26, "IdealBinCnt: {}", idealBinCnt);
698 log_->info(GPL, 27, "TotalBinArea: {}", totalBinArea);
699
700 int foundBinCnt = 2;
701 // find binCnt: 2, 4, 8, 16, 32, 64, ...
702 // s.t. binCnt^2 <= idealBinCnt <= (binCnt*2)^2.
703 for(foundBinCnt = 2; foundBinCnt <= 1024; foundBinCnt *= 2) {
704 if( foundBinCnt * foundBinCnt <= idealBinCnt
705 && 4 * foundBinCnt * foundBinCnt > idealBinCnt ) {
706 break;
707 }
708 }
709
710 // setBinCntX_;
711 if( !isSetBinCntX_ ) {
712 binCntX_ = foundBinCnt;
713 }
714
715 // setBinCntY_;
716 if( !isSetBinCntY_ ) {
717 binCntY_ = foundBinCnt;
718 }
719
720
721 log_->info(GPL, 28, "BinCnt: {} {}", binCntX_, binCntY_ );
722
723 binSizeX_ = ceil(
724 static_cast<float>((ux_ - lx_))/binCntX_);
725 binSizeY_ = ceil(
726 static_cast<float>((uy_ - ly_))/binCntY_);
727
728 log_->info(GPL, 29, "BinSize: {} {}", binSizeX_, binSizeY_);
729
730 // initialize binStor_, bins_ vector
731 binStor_.resize(binCntX_ * binCntY_);
732 bins_.reserve(binCntX_ * binCntY_);
733 int x = lx_, y = ly_;
734 int idxX = 0, idxY = 0;
735 for(auto& bin : binStor_) {
736
737 int sizeX = (x + binSizeX_ > ux_)?
738 ux_ - x : binSizeX_;
739 int sizeY = (y + binSizeY_ > uy_)?
740 uy_ - y : binSizeY_;
741
742 //cout << "idxX: " << idxX << " idxY: " << idxY
743 // << " x:" << x << " y:" << y
744 // << " " << x+sizeX << " " << y+sizeY << endl;
745 bin = Bin(idxX, idxY, x, y, x+sizeX, y+sizeY, targetDensity_);
746
747 // move x, y coordinates.
748 x += binSizeX_;
749 idxX += 1;
750
751 if( x >= ux_ ) {
752 y += binSizeY_;
753 x = lx_;
754
755 idxY ++;
756 idxX = 0;
757 }
758
759 bins_.push_back( &bin );
760 }
761
762 log_->info(GPL, 30, "NumBins: {}", bins_.size());
763
764 // only initialized once
765 updateBinsNonPlaceArea();
766 }
767
768 void
updateBinsNonPlaceArea()769 BinGrid::updateBinsNonPlaceArea() {
770 for(auto& bin : bins_) {
771 bin->setNonPlaceArea(0);
772 }
773
774 for(auto& inst : pb_->nonPlaceInsts()) {
775 std::pair<int, int> pairX = getMinMaxIdxX(inst);
776 std::pair<int, int> pairY = getMinMaxIdxY(inst);
777 for(int i = pairX.first; i < pairX.second; i++) {
778 for(int j = pairY.first; j < pairY.second; j++) {
779 Bin* bin = bins_[ j * binCntX_ + i ];
780
781 // Note that nonPlaceArea should have scale-down with
782 // target density.
783 // See MS-replace paper
784 //
785 bin->addNonPlaceArea( getOverlapArea(bin, inst)
786 * bin->targetDensity() );
787 }
788 }
789 }
790 }
791
792
793 // Core Part
794 void
updateBinsGCellDensityArea(const std::vector<GCell * > & cells)795 BinGrid::updateBinsGCellDensityArea(
796 const std::vector<GCell*>& cells) {
797 // clear the Bin-area info
798 for(auto& bin : bins_) {
799 bin->setInstPlacedArea(0);
800 bin->setFillerArea(0);
801 }
802
803 for(auto& cell : cells) {
804 std::pair<int, int> pairX
805 = getDensityMinMaxIdxX(cell);
806 std::pair<int, int> pairY
807 = getDensityMinMaxIdxY(cell);
808
809 // The following function is critical runtime hotspot
810 // for global placer.
811 //
812 if( cell->isInstance() ) {
813 // macro should have
814 // scale-down with target-density
815 if( cell->isMacroInstance() ) {
816 for(int i = pairX.first; i < pairX.second; i++) {
817 for(int j = pairY.first; j < pairY.second; j++) {
818 Bin* bin = bins_[ j * binCntX_ + i ];
819 bin->addInstPlacedArea(
820 getOverlapDensityArea(bin, cell)
821 * cell->densityScale() * bin->targetDensity() );
822 }
823 }
824 }
825 // normal cells
826 else if( cell->isStdInstance() ) {
827 for(int i = pairX.first; i < pairX.second; i++) {
828 for(int j = pairY.first; j < pairY.second; j++) {
829 Bin* bin = bins_[ j * binCntX_ + i ];
830 bin->addInstPlacedArea(
831 getOverlapDensityArea(bin, cell)
832 * cell->densityScale() );
833 }
834 }
835 }
836 }
837 else if( cell->isFiller() ) {
838 for(int i = pairX.first; i < pairX.second; i++) {
839 for(int j = pairY.first; j < pairY.second; j++) {
840 Bin* bin = bins_[ j * binCntX_ + i ];
841 bin->addFillerArea(
842 getOverlapDensityArea(bin, cell)
843 * cell->densityScale() );
844 }
845 }
846 }
847 }
848
849 overflowArea_ = 0;
850
851 // update density and overflowArea
852 // for nesterov use and FFT library
853 for(auto& bin : bins_) {
854 int64_t binArea = bin->binArea();
855 bin->setDensity(
856 ( static_cast<float> (bin->instPlacedArea())
857 + static_cast<float> (bin->fillerArea())
858 + static_cast<float> (bin->nonPlaceArea()) )
859 / static_cast<float>(binArea * bin->targetDensity()));
860
861 overflowArea_
862 += std::max(0.0f,
863 static_cast<float>(bin->instPlacedArea())
864 + static_cast<float>(bin->nonPlaceArea())
865 - (binArea * bin->targetDensity()));
866
867 }
868 }
869
870
871 std::pair<int, int>
getDensityMinMaxIdxX(const GCell * gcell) const872 BinGrid::getDensityMinMaxIdxX(const GCell* gcell) const {
873 int lowerIdx = (gcell->dLx() - lx())/binSizeX_;
874 int upperIdx =
875 ( fastModulo((gcell->dUx() - lx()), binSizeX_) == 0)?
876 (gcell->dUx() - lx()) / binSizeX_
877 : (gcell->dUx() - lx()) / binSizeX_ + 1;
878 return std::make_pair(lowerIdx, upperIdx);
879 }
880
881 std::pair<int, int>
getDensityMinMaxIdxY(const GCell * gcell) const882 BinGrid::getDensityMinMaxIdxY(const GCell* gcell) const {
883 int lowerIdx = (gcell->dLy() - ly())/binSizeY_;
884 int upperIdx =
885 ( fastModulo((gcell->dUy() - ly()), binSizeY_) == 0)?
886 (gcell->dUy() - ly()) / binSizeY_
887 : (gcell->dUy() - ly()) / binSizeY_ + 1;
888
889 return std::make_pair(lowerIdx, upperIdx);
890 }
891
892
893 std::pair<int, int>
getMinMaxIdxX(const Instance * inst) const894 BinGrid::getMinMaxIdxX(const Instance* inst) const {
895 int lowerIdx = (inst->lx() - lx()) / binSizeX_;
896 int upperIdx =
897 ( fastModulo((inst->ux() - lx()), binSizeX_) == 0)?
898 (inst->ux() - lx()) / binSizeX_
899 : (inst->ux() - lx()) / binSizeX_ + 1;
900
901 return std::make_pair(
902 std::max(lowerIdx, 0),
903 std::min(upperIdx, binCntX_));
904 }
905
906 std::pair<int, int>
getMinMaxIdxY(const Instance * inst) const907 BinGrid::getMinMaxIdxY(const Instance* inst) const {
908 int lowerIdx = (inst->ly() - ly()) / binSizeY_;
909 int upperIdx =
910 ( fastModulo((inst->uy() - ly()), binSizeY_) == 0)?
911 (inst->uy() - ly()) / binSizeY_
912 : (inst->uy() - ly()) / binSizeY_ + 1;
913
914 return std::make_pair(
915 std::max(lowerIdx, 0),
916 std::min(upperIdx, binCntY_));
917 }
918
919
920
921
922 ////////////////////////////////////////////////
923 // NesterovBaseVars
NesterovBaseVars()924 NesterovBaseVars::NesterovBaseVars()
925 {
926 reset();
927 }
928
929
930
931 void
reset()932 NesterovBaseVars::reset() {
933 targetDensity = 1.0;
934 binCntX = binCntY = 0;
935 minWireLengthForceBar = -300;
936 isSetBinCntX = isSetBinCntY = 0;
937 useUniformTargetDensity = 0;
938 }
939
940
941 ////////////////////////////////////////////////
942 // NesterovBase
943
NesterovBase()944 NesterovBase::NesterovBase()
945 : pb_(nullptr), log_(nullptr),
946 fillerDx_(0), fillerDy_(0),
947 whiteSpaceArea_(0),
948 movableArea_(0), totalFillerArea_(0),
949 stdInstsArea_(0), macroInstsArea_(0),
950 sumPhi_(0), targetDensity_(0),
951 uniformTargetDensity_(0) {}
952
NesterovBase(NesterovBaseVars nbVars,std::shared_ptr<PlacerBase> pb,utl::Logger * log)953 NesterovBase::NesterovBase(
954 NesterovBaseVars nbVars,
955 std::shared_ptr<PlacerBase> pb,
956 utl::Logger* log)
957 : NesterovBase() {
958 nbVars_ = nbVars;
959 pb_ = pb;
960 log_ = log;
961 init();
962 }
963
~NesterovBase()964 NesterovBase::~NesterovBase() {
965 reset();
966 }
967
968 void
reset()969 NesterovBase::reset() {
970 nbVars_.reset();
971 pb_ = nullptr;
972 log_ = nullptr;
973
974 fillerDx_ = fillerDy_ = 0;
975 whiteSpaceArea_ = movableArea_ = 0;
976 totalFillerArea_ = 0;
977
978 stdInstsArea_ = macroInstsArea_ = 0;
979
980 gCellStor_.clear();
981 gNetStor_.clear();
982 gPinStor_.clear();
983
984 gCells_.clear();
985 gCellInsts_.clear();
986 gCellFillers_.clear();
987
988 gNets_.clear();
989 gPins_.clear();
990
991 gCellMap_.clear();
992 gPinMap_.clear();
993 gNetMap_.clear();
994
995 gCellStor_.shrink_to_fit();
996 gNetStor_.shrink_to_fit();
997 gPinStor_.shrink_to_fit();
998
999 gCells_.shrink_to_fit();
1000 gCellInsts_.shrink_to_fit();
1001 gCellFillers_.shrink_to_fit();
1002
1003 gNets_.shrink_to_fit();
1004 gPins_.shrink_to_fit();
1005
1006 sumPhi_ = 0;
1007 targetDensity_ = 0;
1008 uniformTargetDensity_ = 0;
1009 }
1010
1011
1012 void
init()1013 NesterovBase::init() {
1014
1015 // area update from pb
1016 stdInstsArea_ = pb_->stdInstsArea();
1017 macroInstsArea_ = pb_->macroInstsArea();
1018
1019 // gCellStor init
1020 gCellStor_.reserve(pb_->placeInsts().size());
1021 for(auto& inst: pb_->placeInsts()) {
1022 GCell myGCell(inst);
1023 // Check whether the given instance is
1024 // macro or not
1025 if( inst->dy() > pb_->siteSizeY() * 6 ) {
1026 myGCell.setMacroInstance();
1027 }
1028 else {
1029 myGCell.setStdInstance();
1030 }
1031 gCellStor_.push_back(myGCell);
1032 }
1033
1034 // TODO:
1035 // at this moment, GNet and GPin is equal to
1036 // Net and Pin
1037
1038 // gPinStor init
1039 gPinStor_.reserve(pb_->pins().size());
1040 for(auto& pin : pb_->pins()) {
1041 GPin myGPin(pin);
1042 gPinStor_.push_back(myGPin);
1043 }
1044
1045 // gNetStor init
1046 gNetStor_.reserve(pb_->nets().size());
1047 for(auto& net : pb_->nets()) {
1048 GNet myGNet(net);
1049 gNetStor_.push_back(myGNet);
1050 }
1051
1052 // update gFillerCells
1053 initFillerGCells();
1054
1055 // gCell ptr init
1056 gCells_.reserve(gCellStor_.size());
1057 for(auto& gCell : gCellStor_) {
1058 gCells_.push_back(&gCell);
1059 if( gCell.isInstance() ) {
1060 gCellMap_[gCell.instance()] = &gCell;
1061 gCellInsts_.push_back(&gCell);
1062 }
1063 else if( gCell.isFiller() ) {
1064 gCellFillers_.push_back(&gCell);
1065 }
1066 }
1067
1068 // gPin ptr init
1069 gPins_.reserve(gPinStor_.size());
1070 for(auto& gPin : gPinStor_) {
1071 gPins_.push_back(&gPin);
1072 gPinMap_[gPin.pin()] = &gPin;
1073 }
1074
1075 // gNet ptr init
1076 gNets_.reserve(gNetStor_.size());
1077 for(auto& gNet : gNetStor_) {
1078 gNets_.push_back(&gNet);
1079 gNetMap_[gNet.net()] = &gNet;
1080 }
1081
1082 // gCellStor_'s pins_ fill
1083 for(auto& gCell : gCellStor_) {
1084 if( gCell.isFiller()) {
1085 continue;
1086 }
1087
1088 for( auto& pin : gCell.instance()->pins() ) {
1089 gCell.addGPin( pbToNb(pin) );
1090 }
1091 }
1092
1093 // gPinStor_' GNet and GCell fill
1094 for(auto& gPin : gPinStor_) {
1095 gPin.setGCell(
1096 pbToNb(gPin.pin()->instance()));
1097 gPin.setGNet(
1098 pbToNb(gPin.pin()->net()));
1099 }
1100
1101 // gNetStor_'s GPin fill
1102 for(auto& gNet : gNetStor_) {
1103 for(auto& pin : gNet.net()->pins()) {
1104 gNet.addGPin( pbToNb(pin) );
1105 }
1106 }
1107
1108
1109 log_->info(GPL, 31, "FillerInit: NumGCells: {}", gCells_.size());
1110 log_->info(GPL, 32, "FillerInit: NumGNets: {}", gNets_.size());
1111 log_->info(GPL, 33, "FillerInit: NumGPins: {}", gPins_.size());
1112
1113 // initialize bin grid structure
1114 // send param into binGrid structure
1115 if( nbVars_.isSetBinCntX ) {
1116 bg_.setBinCntX(nbVars_.binCntX);
1117 }
1118
1119 if( nbVars_.isSetBinCntY ) {
1120 bg_.setBinCntY(nbVars_.binCntY);
1121 }
1122
1123 bg_.setPlacerBase(pb_);
1124 bg_.setLogger(log_);
1125 bg_.setCorePoints(&(pb_->die()));
1126 bg_.setTargetDensity(targetDensity_);
1127
1128 // update binGrid info
1129 bg_.initBins();
1130
1131 // initialize fft structrue based on bins
1132 std::unique_ptr<FFT> fft(
1133 new FFT(bg_.binCntX(), bg_.binCntY(),
1134 bg_.binSizeX(), bg_.binSizeY()));
1135
1136 fft_ = std::move(fft);
1137
1138 // update densitySize and densityScale in each gCell
1139 updateDensitySize();
1140 }
1141
1142
1143 // virtual filler GCells
1144 void
initFillerGCells()1145 NesterovBase::initFillerGCells() {
1146 // extract average dx/dy in range (10%, 90%)
1147 vector<int> dxStor;
1148 vector<int> dyStor;
1149
1150 dxStor.reserve(pb_->placeInsts().size());
1151 dyStor.reserve(pb_->placeInsts().size());
1152 for(auto& placeInst : pb_->placeInsts()) {
1153 dxStor.push_back(placeInst->dx());
1154 dyStor.push_back(placeInst->dy());
1155 }
1156
1157 // sort
1158 std::sort(dxStor.begin(), dxStor.end());
1159 std::sort(dyStor.begin(), dyStor.end());
1160
1161 // average from (10 - 90%) .
1162 int64_t dxSum = 0, dySum = 0;
1163
1164 int minIdx = dxStor.size()*0.05;
1165 int maxIdx = dxStor.size()*0.95;
1166
1167 // when #instances are too small,
1168 // extracts average values in whole ranges.
1169 if( minIdx == maxIdx ) {
1170 minIdx = 0;
1171 maxIdx = dxStor.size();
1172 }
1173
1174 for(int i=minIdx; i<maxIdx; i++) {
1175 dxSum += dxStor[i];
1176 dySum += dyStor[i];
1177 }
1178
1179 // the avgDx and avgDy will be used as filler cells'
1180 // width and height
1181 fillerDx_ = static_cast<int>(dxSum / (maxIdx - minIdx));
1182 fillerDy_ = static_cast<int>(dySum / (maxIdx - minIdx));
1183
1184 int64_t coreArea = pb_->die().coreArea();
1185
1186 // nonPlaceInstsArea should not have density downscaling!!!
1187 whiteSpaceArea_ = coreArea -
1188 static_cast<int64_t>(pb_->nonPlaceInstsArea());
1189
1190 // targetDensity initialize
1191 if( nbVars_.useUniformTargetDensity ) {
1192 targetDensity_ = static_cast<float>(stdInstsArea_)/static_cast<float>(whiteSpaceArea_ - macroInstsArea_) + 0.01;
1193 }
1194 else {
1195 targetDensity_ = nbVars_.targetDensity;
1196 }
1197
1198 // TODO density screening
1199 movableArea_ = whiteSpaceArea_ * targetDensity_;
1200
1201 totalFillerArea_ = movableArea_ - nesterovInstsArea();
1202 uniformTargetDensity_
1203 = static_cast<float>(nesterovInstsArea()) / static_cast<float>(whiteSpaceArea_);
1204 if( totalFillerArea_ < 0 ) {
1205 log_->error(GPL, 302,
1206 "Use a higher -density or "
1207 "re-floorplan with a larger core area.\n"
1208 "Given target density: {:.2f}\n"
1209 "Suggested target density: {:.2f}",
1210 targetDensity_,
1211 uniformTargetDensity_);
1212 }
1213
1214 int fillerCnt =
1215 static_cast<int>(totalFillerArea_
1216 / static_cast<int64_t>(fillerDx_ * fillerDy_));
1217
1218 debugPrint(log_, GPL, "replace", 3, "FillerInit: CoreArea {}", coreArea);
1219 debugPrint(log_, GPL, "replace", 3, "FillerInit: WhiteSpaceArea {}", whiteSpaceArea_);
1220 debugPrint(log_, GPL, "replace", 3, "FillerInit: MovableArea {}", movableArea_);
1221 debugPrint(log_, GPL, "replace", 3, "FillerInit: TotalFillerArea {}", totalFillerArea_);
1222 debugPrint(log_, GPL, "replace", 3, "FillerInit: NumFillerCells {}", fillerCnt);
1223 debugPrint(log_, GPL, "replace", 3, "FillerInit: FillerCellArea {}", fillerCellArea());
1224 debugPrint(log_, GPL, "replace", 3, "FillerInit: FillerCellSize {} {}", fillerDx_, fillerDy_);
1225
1226 //
1227 // mt19937 supports huge range of random values.
1228 // rand()'s RAND_MAX is only 32767.
1229 //
1230 mt19937 randVal(0);
1231 for(int i=0; i<fillerCnt; i++) {
1232
1233 // instability problem between g++ and clang++!
1234 auto randX = randVal();
1235 auto randY = randVal();
1236
1237 // place filler cells on random coordi and
1238 // set size as avgDx and avgDy
1239 GCell myGCell(
1240 randX % pb_->die().coreDx() + pb_->die().coreLx(),
1241 randY % pb_->die().coreDy() + pb_->die().coreLy(),
1242 fillerDx_, fillerDy_);
1243
1244 gCellStor_.push_back(myGCell);
1245 }
1246 }
1247
1248 GCell*
pbToNb(Instance * inst) const1249 NesterovBase::pbToNb(Instance* inst) const {
1250 auto gcPtr = gCellMap_.find(inst);
1251 return (gcPtr == gCellMap_.end())?
1252 nullptr : gcPtr->second;
1253 }
1254
1255 GPin*
pbToNb(Pin * pin) const1256 NesterovBase::pbToNb(Pin* pin) const {
1257 auto gpPtr = gPinMap_.find(pin);
1258 return (gpPtr == gPinMap_.end())?
1259 nullptr : gpPtr->second;
1260 }
1261
1262 GNet*
pbToNb(Net * net) const1263 NesterovBase::pbToNb(Net* net) const {
1264 auto gnPtr = gNetMap_.find(net);
1265 return (gnPtr == gNetMap_.end())?
1266 nullptr : gnPtr->second;
1267 }
1268
1269
1270 GCell*
dbToNb(odb::dbInst * inst) const1271 NesterovBase::dbToNb(odb::dbInst* inst) const {
1272 Instance* pbInst = pb_->dbToPb(inst);
1273 return pbToNb(pbInst);
1274 }
1275
1276 GPin*
dbToNb(odb::dbITerm * pin) const1277 NesterovBase::dbToNb(odb::dbITerm* pin) const {
1278 Pin* pbPin = pb_->dbToPb(pin);
1279 return pbToNb(pbPin);
1280 }
1281
1282 GPin*
dbToNb(odb::dbBTerm * pin) const1283 NesterovBase::dbToNb(odb::dbBTerm* pin) const {
1284 Pin* pbPin = pb_->dbToPb(pin);
1285 return pbToNb(pbPin);
1286 }
1287
1288 GNet*
dbToNb(odb::dbNet * net) const1289 NesterovBase::dbToNb(odb::dbNet* net) const {
1290 Net* pbNet = pb_->dbToPb(net);
1291 return pbToNb(pbNet);
1292 }
1293
1294 // gcell update
1295 void
updateGCellLocation(const std::vector<FloatPoint> & coordis)1296 NesterovBase::updateGCellLocation(
1297 const std::vector<FloatPoint>& coordis) {
1298 for(auto& coordi : coordis) {
1299 int idx = &coordi - &coordis[0];
1300 gCells_[idx]->setLocation( coordi.x, coordi.y );
1301 }
1302 }
1303
1304 // gcell update
1305 void
updateGCellCenterLocation(const std::vector<FloatPoint> & coordis)1306 NesterovBase::updateGCellCenterLocation(
1307 const std::vector<FloatPoint>& coordis) {
1308 for(auto& coordi : coordis) {
1309 int idx = &coordi - &coordis[0];
1310 gCells_[idx]->setCenterLocation( coordi.x, coordi.y );
1311 }
1312 }
1313
1314 void
updateGCellDensityCenterLocation(const std::vector<FloatPoint> & coordis)1315 NesterovBase::updateGCellDensityCenterLocation(
1316 const std::vector<FloatPoint>& coordis) {
1317 for(auto& coordi : coordis) {
1318 int idx = &coordi - &coordis[0];
1319 gCells_[idx]->setDensityCenterLocation(
1320 coordi.x, coordi.y );
1321 }
1322 bg_.updateBinsGCellDensityArea( gCells_ );
1323 }
1324
1325 void
setTargetDensity(float density)1326 NesterovBase::setTargetDensity(float density) {
1327 targetDensity_ = density;
1328 bg_.setTargetDensity(density);
1329 for(auto& bin : bins()) {
1330 bin->setTargetDensity(density);
1331 }
1332 // update nonPlaceArea's target denstiy
1333 bg_.updateBinsNonPlaceArea();
1334 }
1335
1336 int
binCntX() const1337 NesterovBase::binCntX() const {
1338 return bg_.binCntX();
1339 }
1340
1341 int
binCntY() const1342 NesterovBase::binCntY() const {
1343 return bg_.binCntY();
1344 }
1345
1346 int
binSizeX() const1347 NesterovBase::binSizeX() const {
1348 return bg_.binSizeX();
1349 }
1350
1351 int
binSizeY() const1352 NesterovBase::binSizeY() const {
1353 return bg_.binSizeY();
1354 }
1355
1356
1357 int64_t
overflowArea() const1358 NesterovBase::overflowArea() const {
1359 return bg_.overflowArea();
1360 }
1361
1362 int
fillerDx() const1363 NesterovBase::fillerDx() const {
1364 return fillerDx_;
1365 }
1366
1367 int
fillerDy() const1368 NesterovBase::fillerDy() const {
1369 return fillerDy_;
1370 }
1371
1372 int
fillerCnt() const1373 NesterovBase::fillerCnt() const {
1374 return static_cast<int>(gCellFillers_.size());
1375 }
1376
1377 int64_t
fillerCellArea() const1378 NesterovBase::fillerCellArea() const {
1379 return static_cast<int64_t>(fillerDx_)
1380 * static_cast<int64_t>(fillerDy_);
1381 }
1382
1383 int64_t
whiteSpaceArea() const1384 NesterovBase::whiteSpaceArea() const {
1385 return whiteSpaceArea_;
1386 }
1387
1388 int64_t
movableArea() const1389 NesterovBase::movableArea() const {
1390 return movableArea_;
1391 }
1392
1393 int64_t
totalFillerArea() const1394 NesterovBase::totalFillerArea() const {
1395 return totalFillerArea_;
1396 }
1397
1398
1399 int64_t
nesterovInstsArea() const1400 NesterovBase::nesterovInstsArea() const {
1401 return stdInstsArea_
1402 + static_cast<int64_t>(round(macroInstsArea_ * targetDensity_));
1403 }
1404
1405 float
sumPhi() const1406 NesterovBase::sumPhi() const {
1407 return sumPhi_;
1408 }
1409
1410 float
uniformTargetDensity() const1411 NesterovBase::uniformTargetDensity() const {
1412 return uniformTargetDensity_;
1413 }
1414
1415 float
initTargetDensity() const1416 NesterovBase::initTargetDensity() const {
1417 return nbVars_.targetDensity;
1418 }
1419
1420 float
targetDensity() const1421 NesterovBase::targetDensity() const {
1422 return targetDensity_;
1423 }
1424
1425 // update densitySize and densityScale in each gCell
1426 void
updateDensitySize()1427 NesterovBase::updateDensitySize() {
1428 for(auto& gCell : gCells_) {
1429 float scaleX = 0, scaleY = 0;
1430 float densitySizeX = 0, densitySizeY = 0;
1431 if( gCell->dx() < REPLACE_SQRT2 * bg_.binSizeX() ) {
1432 scaleX = static_cast<float>(gCell->dx())
1433 / static_cast<float>( REPLACE_SQRT2 * bg_.binSizeX());
1434 densitySizeX = REPLACE_SQRT2
1435 * static_cast<float>(bg_.binSizeX());
1436 }
1437 else {
1438 scaleX = 1.0;
1439 densitySizeX = gCell->dx();
1440 }
1441
1442 if( gCell->dy() < REPLACE_SQRT2 * bg_.binSizeY() ) {
1443 scaleY = static_cast<float>(gCell->dy())
1444 / static_cast<float>( REPLACE_SQRT2 * bg_.binSizeY());
1445 densitySizeY = REPLACE_SQRT2
1446 * static_cast<float>(bg_.binSizeY());
1447 }
1448 else {
1449 scaleY = 1.0;
1450 densitySizeY = gCell->dy();
1451 }
1452
1453 gCell->setDensitySize(densitySizeX, densitySizeY);
1454 gCell->setDensityScale(scaleX * scaleY);
1455 }
1456 }
1457
1458 void
updateAreas()1459 NesterovBase::updateAreas() {
1460 // bloating can change the following :
1461 // stdInstsArea and macroInstsArea
1462 stdInstsArea_ = macroInstsArea_ = 0;
1463 for( auto& gCell : gCells_) {
1464 if( gCell->isMacroInstance() ) {
1465 macroInstsArea_
1466 += static_cast<int64_t>(gCell->dx())
1467 * static_cast<int64_t>(gCell->dy());
1468 }
1469 else if( gCell->isStdInstance() ) {
1470 stdInstsArea_
1471 += static_cast<int64_t>(gCell->dx())
1472 * static_cast<int64_t>(gCell->dy());
1473 }
1474 }
1475
1476 int64_t coreArea = pb_->die().coreArea();
1477
1478 // nonPlaceInstsArea should not have density downscaling!!!
1479 whiteSpaceArea_ = coreArea -
1480 static_cast<int64_t>(pb_->nonPlaceInstsArea());
1481
1482 // TODO density screening
1483 movableArea_ = whiteSpaceArea_ * targetDensity_;
1484
1485 totalFillerArea_ = movableArea_ - nesterovInstsArea();
1486 uniformTargetDensity_ =
1487 static_cast<float>(nesterovInstsArea()) / static_cast<float>(whiteSpaceArea_);
1488
1489 if( totalFillerArea_ < 0 ) {
1490 log_->error(GPL, 303,
1491 "Use a higher -density or "
1492 "re-floorplan with a larger core area.\n"
1493 "Given target density: {:.2f}\n"
1494 "Suggested target density: {:.2f}",
1495 targetDensity_,
1496 uniformTargetDensity_);
1497 }
1498 }
1499
1500 // cut the filler cells
1501 void
cutFillerCells(int64_t targetFillerArea)1502 NesterovBase::cutFillerCells(int64_t targetFillerArea) {
1503 std::vector<GCell*> newGCells = gCellInsts_;
1504 std::vector<GCell*> newGCellFillers;
1505
1506 int64_t curFillerArea = 0;
1507 log_->info(GPL, 34, "gCellFiller: {}", gCellFillers_.size());
1508
1509 for(auto& gCellFiller : gCellFillers_ ) {
1510 curFillerArea +=
1511 static_cast<int64_t>(gCellFiller->dx())
1512 * static_cast<int64_t>(gCellFiller->dy());
1513
1514 if( curFillerArea >= targetFillerArea ) {
1515 curFillerArea -=
1516 static_cast<int64_t>(gCellFiller->dx())
1517 * static_cast<int64_t>(gCellFiller->dy());
1518 break;
1519 }
1520
1521 newGCells.push_back(gCellFiller);
1522 newGCellFillers.push_back(gCellFiller);
1523 }
1524
1525 // update totalFillerArea_
1526 totalFillerArea_ = curFillerArea;
1527 log_->info(GPL, 35, "NewTotalFillerArea: {}", totalFillerArea_);
1528
1529 gCells_.swap(newGCells);
1530 gCellFillers_.swap(newGCellFillers);
1531 }
1532
1533 void
updateDensityCoordiLayoutInside(GCell * gCell)1534 NesterovBase::updateDensityCoordiLayoutInside(
1535 GCell* gCell) {
1536
1537 float targetLx = gCell->dLx();
1538 float targetLy = gCell->dLy();
1539
1540 if( targetLx < bg_.lx() ) {
1541 targetLx = bg_.lx();
1542 }
1543
1544 if( targetLy < bg_.ly() ) {
1545 targetLy = bg_.ly();
1546 }
1547
1548 if( targetLx + gCell->dDx() > bg_.ux() ) {
1549 targetLx = bg_.ux() - gCell->dDx();
1550 }
1551
1552 if( targetLy + gCell->dDy() > bg_.uy() ) {
1553 targetLy = bg_.uy() - gCell->dDy();
1554 }
1555 gCell->setDensityLocation(targetLx, targetLy);
1556 }
1557
1558 float
getDensityCoordiLayoutInsideX(const GCell * gCell,float cx) const1559 NesterovBase::getDensityCoordiLayoutInsideX(const GCell* gCell, float cx) const {
1560 float adjVal = cx;
1561 //TODO will change base on each assigned binGrids.
1562 //
1563 if( cx - gCell->dDx()/2 < bg_.lx() ) {
1564 adjVal = bg_.lx() + gCell->dDx()/2;
1565 }
1566 if( cx + gCell->dDx()/2 > bg_.ux() ) {
1567 adjVal = bg_.ux() - gCell->dDx()/2;
1568 }
1569 return adjVal;
1570 }
1571
1572 float
getDensityCoordiLayoutInsideY(const GCell * gCell,float cy) const1573 NesterovBase::getDensityCoordiLayoutInsideY(const GCell* gCell, float cy) const {
1574 float adjVal = cy;
1575 //TODO will change base on each assigned binGrids.
1576 //
1577 if( cy - gCell->dDy()/2 < bg_.ly() ) {
1578 adjVal = bg_.ly() + gCell->dDy()/2;
1579 }
1580 if( cy + gCell->dDy()/2 > bg_.uy() ) {
1581 adjVal = bg_.uy() - gCell->dDy()/2;
1582 }
1583
1584 return adjVal;
1585 }
1586
1587 //
1588 // WA force cals - wlCoeffX / wlCoeffY
1589 //
1590 // * Note that wlCoeffX and wlCoeffY is 1/gamma
1591 // in ePlace paper.
1592 void
updateWireLengthForceWA(float wlCoeffX,float wlCoeffY)1593 NesterovBase::updateWireLengthForceWA(
1594 float wlCoeffX, float wlCoeffY) {
1595
1596 // clear all WA variables.
1597 for(auto& gNet : gNets_) {
1598 gNet->clearWaVars();
1599 }
1600 for(auto& gPin : gPins_) {
1601 gPin->clearWaVars();
1602 }
1603
1604 for(auto& gNet : gNets_) {
1605 gNet->updateBox();
1606
1607 for(auto& gPin : gNet->gPins()) {
1608 // The WA terms are shift invariant:
1609 //
1610 // Sum(x_i * exp(x_i)) Sum(x_i * exp(x_i - C))
1611 // ----------------- = -----------------
1612 // Sum(exp(x_i)) Sum(exp(x_i - C))
1613 //
1614 // So we shift to keep the exponential from overflowing
1615 float expMinX = (gNet->lx() - gPin->cx()) * wlCoeffX;
1616 float expMaxX = (gPin->cx() - gNet->ux()) * wlCoeffX;
1617 float expMinY = (gNet->ly() - gPin->cy()) * wlCoeffY;
1618 float expMaxY = (gPin->cy() - gNet->uy()) * wlCoeffY;
1619
1620 // min x
1621 if(expMinX > nbVars_.minWireLengthForceBar) {
1622 gPin->setMinExpSumX( fastExp(expMinX) );
1623 gNet->addWaExpMinSumX( gPin->minExpSumX() );
1624 gNet->addWaXExpMinSumX( gPin->cx()
1625 * gPin->minExpSumX() );
1626 }
1627
1628 // max x
1629 if(expMaxX > nbVars_.minWireLengthForceBar) {
1630 gPin->setMaxExpSumX( fastExp(expMaxX) );
1631 gNet->addWaExpMaxSumX( gPin->maxExpSumX() );
1632 gNet->addWaXExpMaxSumX( gPin->cx()
1633 * gPin->maxExpSumX() );
1634 }
1635
1636 // min y
1637 if(expMinY > nbVars_.minWireLengthForceBar) {
1638 gPin->setMinExpSumY( fastExp(expMinY) );
1639 gNet->addWaExpMinSumY( gPin->minExpSumY() );
1640 gNet->addWaYExpMinSumY( gPin->cy()
1641 * gPin->minExpSumY() );
1642 }
1643
1644 // max y
1645 if(expMaxY > nbVars_.minWireLengthForceBar) {
1646 gPin->setMaxExpSumY( fastExp(expMaxY) );
1647 gNet->addWaExpMaxSumY( gPin->maxExpSumY() );
1648 gNet->addWaYExpMaxSumY( gPin->cy()
1649 * gPin->maxExpSumY() );
1650 }
1651 }
1652 //cout << gNet->lx() << " " << gNet->ly() << " "
1653 // << gNet->ux() << " " << gNet->uy() << endl;
1654 }
1655 }
1656
1657 // get x,y WA Gradient values with given GCell
1658 FloatPoint
getWireLengthGradientWA(const GCell * gCell,float wlCoeffX,float wlCoeffY) const1659 NesterovBase::getWireLengthGradientWA(const GCell* gCell, float wlCoeffX, float wlCoeffY) const {
1660 FloatPoint gradientPair;
1661
1662 for(auto& gPin : gCell->gPins()) {
1663 auto tmpPair = getWireLengthGradientPinWA(gPin, wlCoeffX, wlCoeffY);
1664
1665 // apply timing/custom net weight
1666 tmpPair.x *= gPin->gNet()->totalWeight();
1667 tmpPair.y *= gPin->gNet()->totalWeight();
1668
1669 gradientPair.x += tmpPair.x;
1670 gradientPair.y += tmpPair.y;
1671 }
1672
1673 // return sum
1674 return gradientPair;
1675 }
1676
1677 // get x,y WA Gradient values from GPin
1678 // Please check the JingWei's Ph.D. thesis full paper,
1679 // Equation (4.13)
1680 //
1681 // You can't understand the following function
1682 // unless you read the (4.13) formula
1683 FloatPoint
getWireLengthGradientPinWA(const GPin * gPin,float wlCoeffX,float wlCoeffY) const1684 NesterovBase::getWireLengthGradientPinWA(const GPin* gPin, float wlCoeffX, float wlCoeffY) const {
1685
1686 float gradientMinX = 0, gradientMinY = 0;
1687 float gradientMaxX = 0, gradientMaxY = 0;
1688
1689 // min x
1690 if( gPin->hasMinExpSumX() ) {
1691 // from Net.
1692 float waExpMinSumX = gPin->gNet()->waExpMinSumX();
1693 float waXExpMinSumX = gPin->gNet()->waXExpMinSumX();
1694
1695 gradientMinX =
1696 ( waExpMinSumX * ( gPin->minExpSumX() * ( 1.0 - wlCoeffX * gPin->cx()) )
1697 + wlCoeffX * gPin->minExpSumX() * waXExpMinSumX )
1698 / ( waExpMinSumX * waExpMinSumX );
1699 }
1700
1701 // max x
1702 if( gPin->hasMaxExpSumX() ) {
1703
1704 float waExpMaxSumX = gPin->gNet()->waExpMaxSumX();
1705 float waXExpMaxSumX = gPin->gNet()->waXExpMaxSumX();
1706
1707 gradientMaxX =
1708 ( waExpMaxSumX * ( gPin->maxExpSumX() * ( 1.0 + wlCoeffX * gPin->cx()) )
1709 - wlCoeffX * gPin->maxExpSumX() * waXExpMaxSumX )
1710 / ( waExpMaxSumX * waExpMaxSumX );
1711
1712 }
1713
1714 // min y
1715 if( gPin->hasMinExpSumY() ) {
1716
1717 float waExpMinSumY = gPin->gNet()->waExpMinSumY();
1718 float waYExpMinSumY = gPin->gNet()->waYExpMinSumY();
1719
1720 gradientMinY =
1721 ( waExpMinSumY * ( gPin->minExpSumY() * ( 1.0 - wlCoeffY * gPin->cy()) )
1722 + wlCoeffY * gPin->minExpSumY() * waYExpMinSumY )
1723 / ( waExpMinSumY * waExpMinSumY );
1724 }
1725
1726 // max y
1727 if( gPin->hasMaxExpSumY() ) {
1728
1729 float waExpMaxSumY = gPin->gNet()->waExpMaxSumY();
1730 float waYExpMaxSumY = gPin->gNet()->waYExpMaxSumY();
1731
1732 gradientMaxY =
1733 ( waExpMaxSumY * ( gPin->maxExpSumY() * ( 1.0 + wlCoeffY * gPin->cy()) )
1734 - wlCoeffY * gPin->maxExpSumY() * waYExpMaxSumY )
1735 / ( waExpMaxSumY * waExpMaxSumY );
1736 }
1737
1738 return FloatPoint(gradientMinX - gradientMaxX,
1739 gradientMinY - gradientMaxY);
1740 }
1741
1742 FloatPoint
getWireLengthPreconditioner(const GCell * gCell) const1743 NesterovBase::getWireLengthPreconditioner(const GCell* gCell) const {
1744 return FloatPoint( gCell->gPins().size(),
1745 gCell->gPins().size() );
1746 }
1747
1748 FloatPoint
getDensityPreconditioner(const GCell * gCell) const1749 NesterovBase::getDensityPreconditioner(const GCell* gCell) const {
1750 float areaVal = static_cast<float>(gCell->dx())
1751 * static_cast<float>(gCell->dy());
1752
1753 return FloatPoint(areaVal, areaVal);
1754 }
1755
1756 // get GCells' electroForcePair
1757 // i.e. get DensityGradient with given GCell
1758 FloatPoint
getDensityGradient(const GCell * gCell) const1759 NesterovBase::getDensityGradient(const GCell* gCell) const {
1760 std::pair<int, int> pairX
1761 = bg_.getDensityMinMaxIdxX(gCell);
1762 std::pair<int, int> pairY
1763 = bg_.getDensityMinMaxIdxY(gCell);
1764
1765 FloatPoint electroForce;
1766
1767 for(int i = pairX.first; i < pairX.second; i++) {
1768 for(int j = pairY.first; j < pairY.second; j++) {
1769 Bin* bin = bg_.bins()[ j * binCntX() + i ];
1770 float overlapArea
1771 = getOverlapDensityArea(bin, gCell) * gCell->densityScale();
1772
1773 electroForce.x += overlapArea * bin->electroForceX();
1774 electroForce.y += overlapArea * bin->electroForceY();
1775 }
1776 }
1777 return electroForce;
1778 }
1779
1780 // Density force cals
1781 void
updateDensityForceBin()1782 NesterovBase::updateDensityForceBin() {
1783 // copy density to utilize FFT
1784 for(auto& bin : bg_.bins()) {
1785 fft_->updateDensity(bin->x(), bin->y(),
1786 bin->density());
1787 }
1788
1789 // do FFT
1790 fft_->doFFT();
1791
1792 // update electroPhi and electroForce
1793 // update sumPhi_ for nesterov loop
1794 sumPhi_ = 0;
1795 for(auto& bin : bg_.bins()) {
1796 auto eForcePair = fft_->getElectroForce(bin->x(), bin->y());
1797 bin->setElectroForce(eForcePair.first, eForcePair.second);
1798
1799 float electroPhi = fft_->getElectroPhi(bin->x(), bin->y());
1800 bin->setElectroPhi(electroPhi);
1801
1802 sumPhi_ += electroPhi
1803 * static_cast<float>(bin->nonPlaceArea()
1804 + bin->instPlacedArea() + bin->fillerArea());
1805 }
1806 }
1807
1808 void
updateDbGCells()1809 NesterovBase::updateDbGCells() {
1810 for(auto& gCell : gCells()) {
1811 if( gCell->isInstance() ) {
1812 odb::dbInst* inst = gCell->instance()->dbInst();
1813 inst->setPlacementStatus(odb::dbPlacementStatus::PLACED);
1814
1815 Instance* replInst = gCell->instance();
1816 // pad awareness on X coordinates
1817 inst->setLocation(
1818 gCell->dCx()-replInst->dx()/2
1819 + pb_->siteSizeX() * pb_->padLeft(),
1820 gCell->dCy()-replInst->dy()/2 );
1821 }
1822 }
1823 }
1824
1825 int64_t
getHpwl()1826 NesterovBase::getHpwl() {
1827 int64_t hpwl = 0;
1828 for(auto& gNet : gNets_) {
1829 gNet->updateBox();
1830 hpwl += gNet->hpwl();
1831 }
1832 return hpwl;
1833 }
1834
1835
1836
1837 // https://stackoverflow.com/questions/33333363/built-in-mod-vs-custom-mod-function-improve-the-performance-of-modulus-op
1838 static int
fastModulo(const int input,const int ceil)1839 fastModulo(const int input, const int ceil) {
1840 return input >= ceil? input % ceil : input;
1841 }
1842
1843 // int64_t is recommended, but float is 2x fast
1844 static float
getOverlapDensityArea(const Bin * bin,const GCell * cell)1845 getOverlapDensityArea(const Bin* bin, const GCell* cell) {
1846 int rectLx = max(bin->lx(), cell->dLx()),
1847 rectLy = max(bin->ly(), cell->dLy()),
1848 rectUx = min(bin->ux(), cell->dUx()),
1849 rectUy = min(bin->uy(), cell->dUy());
1850
1851 if( rectLx >= rectUx || rectLy >= rectUy ) {
1852 return 0;
1853 }
1854 else {
1855 return static_cast<float>(rectUx - rectLx)
1856 * static_cast<float>(rectUy - rectLy);
1857 }
1858 }
1859
1860
1861 static int64_t
getOverlapArea(const Bin * bin,const Instance * inst)1862 getOverlapArea(const Bin* bin, const Instance* inst) {
1863 int rectLx = max(bin->lx(), inst->lx()),
1864 rectLy = max(bin->ly(), inst->ly()),
1865 rectUx = min(bin->ux(), inst->ux()),
1866 rectUy = min(bin->uy(), inst->uy());
1867
1868 if( rectLx >= rectUx || rectLy >= rectUy ) {
1869 return 0;
1870 }
1871 else {
1872 return static_cast<int64_t>(rectUx - rectLx)
1873 * static_cast<int64_t>(rectUy - rectLy);
1874 }
1875 }
1876
1877 //
1878 // https://codingforspeed.com/using-faster-exponential-approximation/
1879 static float
fastExp(float a)1880 fastExp(float a) {
1881 a = 1.0f + a / 1024.0f;
1882 a *= a;
1883 a *= a;
1884 a *= a;
1885 a *= a;
1886 a *= a;
1887 a *= a;
1888 a *= a;
1889 a *= a;
1890 a *= a;
1891 a *= a;
1892 return a;
1893 }
1894
1895
1896
1897 }
1898