AMF-Placer  2.0
An Open-Source Timing-driven Analytical Mixed-size FPGA Placer
ParallelCLBPacker.cc
Go to the documentation of this file.
1 
26 #include "ParallelCLBPacker.h"
27 #define TIMINGDP
28 
29 void ParallelCLBPacker::prePackLegalizedMacros(PlacementInfo::PlacementMacro *tmpMacro)
30 {
31  std::map<PlacementInfo::PlacementUnit *, std::vector<DeviceInfo::DeviceSite *>> &PULegalSite =
32  placementInfo->getPULegalSite();
33  if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_CARRY)
34  {
35  assert(PULegalSite.find(tmpMacro) != PULegalSite.end());
36  std::vector<DeviceInfo::DeviceSite *> &legalSites = PULegalSite[tmpMacro];
37  for (unsigned int i = 0; i < legalSites.size(); i++)
38  {
39  deviceSite2PackingSite[legalSites[i]]->mapCarryRelatedCellsToSlots(tmpMacro, i);
40  deviceSite2PackingSite[legalSites[i]]->addCarry();
41  placementInfo->addPUIntoClockColumn(tmpMacro, legalSites[i]);
42  }
43  }
44  else if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_MCLB)
45  {
46  assert(PULegalSite.find(tmpMacro) != PULegalSite.end());
47  std::vector<DeviceInfo::DeviceSite *> &legalSites = PULegalSite[tmpMacro];
48  for (unsigned int i = 0; i < legalSites.size(); i++)
49  {
50  deviceSite2PackingSite[legalSites[i]]->mapLUTRAMRelatedCellsToSlots(tmpMacro);
51  deviceSite2PackingSite[legalSites[i]]->addLUTRAMMacro();
52  placementInfo->addPUIntoClockColumn(tmpMacro, legalSites[i]);
53  }
54  }
55 }
56 
57 ParallelCLBPacker::ParallelCLBPacker(DesignInfo *designInfo, DeviceInfo *deviceInfo, PlacementInfo *placementInfo,
58  std::map<std::string, std::string> &JSONCfg, int unchangedIterationThr,
59  int numNeighbor, float deltaD, float curD, float maxD, int PQSize,
60  float HPWLWeight, std::string packerName,
61  PlacementTimingOptimizer *timingOptimizer, WirelengthOptimizer *WLOptimizer)
62  : designInfo(designInfo), deviceInfo(deviceInfo), placementInfo(placementInfo), JSONCfg(JSONCfg),
63  unchangedIterationThr(unchangedIterationThr), numNeighbor(numNeighbor), deltaD(deltaD), curD(curD), maxD(maxD),
64  PQSize(PQSize), HPWLWeight(HPWLWeight), packerName(packerName), timingOptimizer(timingOptimizer),
65  WLOptimizer(WLOptimizer), PUId2PackingCLBSite(placementInfo->getPlacementUnits().size(), nullptr),
66  PUId2PackingCLBSiteCandidate(placementInfo->getPlacementUnits().size(), nullptr),
67  placementUnits(placementInfo->getPlacementUnits()),
68  placementUnpackedCells(placementInfo->getPlacementUnpackedCells()),
69  placementMacros(placementInfo->getPlacementMacros()), cellInMacros(placementInfo->getCellInMacros()),
70  cellId2PlacementUnit(placementInfo->getCellId2PlacementUnit())
71 {
72  if (JSONCfg.find("y2xRatio") != JSONCfg.end())
73  {
74  y2xRatio = std::stof(JSONCfg["y2xRatio"]);
75  }
76  // PlacementInfo *placementInfo, DeviceInfo::DeviceSite *CLBSite, int unchangedIterationThr,
77  // int numNeighbor, float deltaD, float curD, float maxD, int PQSize, float y2xRatio,
78  // std::vector<PackingCLBSite *> &PUId2PackingCLBSite
79 
80  int numClockCols = placementInfo->getDeviceInfo()->getClockColumns().size();
81  clockColumns2PackingSites =
82  std::vector<std::vector<PackingCLBSite *>>(numClockCols, std::vector<PackingCLBSite *>());
83 
84  std::string targetSiteType = "SLICEL";
85  deviceSite2PackingSite.clear();
86  for (auto curSite : deviceInfo->getSitesInType(targetSiteType))
87  {
88  if (curSite->isOccupied())
89  continue;
90  PackingCLBSite *tmpPackingSite =
91  new PackingCLBSite(placementInfo, curSite, unchangedIterationThr, numNeighbor, deltaD, curD, maxD, PQSize,
92  y2xRatio, HPWLWeight, PUId2PackingCLBSite);
93  deviceSite2PackingSite[curSite] = tmpPackingSite;
94  packingSites.push_back(tmpPackingSite);
95  clockColumns2PackingSites[curSite->getClockHalfColumn()->getId()].push_back(tmpPackingSite);
96  }
97  targetSiteType = "SLICEM";
98  for (auto curSite : deviceInfo->getSitesInType(targetSiteType))
99  {
100  if (curSite->isOccupied())
101  continue;
102  PackingCLBSite *tmpPackingSite =
103  new PackingCLBSite(placementInfo, curSite, unchangedIterationThr, numNeighbor, deltaD, curD, maxD, PQSize,
104  y2xRatio, HPWLWeight, PUId2PackingCLBSite);
105  deviceSite2PackingSite[curSite] = tmpPackingSite;
106  packingSites.push_back(tmpPackingSite);
107  clockColumns2PackingSites[curSite->getClockHalfColumn()->getId()].push_back(tmpPackingSite);
108  }
109 
110  for (auto tmpMacro : placementMacros)
111  {
112  prePackLegalizedMacros(tmpMacro);
113  }
114 
115  print_status("ParallelCLBPacker: CARRY macros are mapped to sites.");
116 
117  int numPackingSites = packingSites.size();
118  for (int i = 0; i < numPackingSites; i++)
119  {
120  auto tmpPackingSite = packingSites[i];
121  if (tmpPackingSite->getDeterminedClusterInSite())
122  {
123  assert(tmpPackingSite->checkIsPrePackedSite());
124  }
125  }
126  print_status("ParallelCLBPacker: initialized.");
127 }
128 
129 void ParallelCLBPacker::packCLBsIteration(bool initial, bool debug)
130 {
131  int numClockCols = clockColumns2PackingSites.size();
132 #pragma omp parallel for schedule(dynamic, 16)
133  for (int i = 0; i < numClockCols; i++)
134  {
135  for (unsigned int j = 0; j < clockColumns2PackingSites[i].size(); j++)
136  {
137  auto tmpPackingSite = clockColumns2PackingSites[i][j];
138  tmpPackingSite->updateStep(initial, debug);
139  }
140  }
141 
142  // int numPackingSites = packingSites.size();
143  // #pragma omp parallel for schedule(dynamic, 16)
144  // for (int i = 0; i < numPackingSites; i++)
145  // {
146  // auto tmpPackingSite = packingSites[i];
147  // tmpPackingSite->updateStep(initial, debug);
148  // }
149 
150  // update PU's selection of packing site
151  PUId2PackingCLBSite.clear();
152  PUId2PackingCLBSite.resize(placementInfo->getPlacementUnits().size(), nullptr);
153 
154  for (auto packingSite : packingSites)
155  {
156  if (packingSite)
157  {
158  if (packingSite->getDeterminedClusterInSite())
159  {
160  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
161  {
162  assert(!PUId2PackingCLBSite[tmpPU->getId()]);
163  // if (!placementInfo->checkClockColumnLegalization(tmpPU, packingSite->getCLBSite()))
164  // {
165  // placementInfo->printOutClockColumnLegalization(tmpPU, packingSite->getCLBSite());
166  // }
167  // assert(placementInfo->checkClockColumnLegalization(tmpPU, packingSite->getCLBSite()));
168  PUId2PackingCLBSite[tmpPU->getId()] = packingSite;
169  placementInfo->addPUIntoClockColumn(tmpPU, packingSite->getCLBSite());
170  }
171  }
172  }
173  }
174 
175  PUId2PackingCLBSiteCandidate.clear();
176  PUId2PackingCLBSiteCandidate.resize(placementInfo->getPlacementUnits().size(), nullptr);
177  for (auto tmpPackingSite : packingSites)
178  {
179  if (tmpPackingSite->hasValidPQTop())
180  {
181  const ParallelCLBPacker::PackingCLBSite::PackingCLBCluster *tmpTop = tmpPackingSite->getPriorityQueueTop();
182  for (auto tmpPU : tmpTop->getPUs())
183  {
184  if (!PUId2PackingCLBSite[tmpPU->getId()])
185  {
186 
187  if (!placementInfo->checkClockColumnLegalization(tmpPU, tmpPackingSite->getCLBSite()))
188  continue;
189 
190  if (!PUId2PackingCLBSiteCandidate[tmpPU->getId()])
191  {
192  PUId2PackingCLBSiteCandidate[tmpPU->getId()] = tmpPackingSite;
193  // if (tmpPU->getId() == 117104)
194  // {
195  // std::ofstream debugFile;
196  // debugFile.open("OpenPitonSLICE_SLICE_X38Y213", std::ios_base::app);
197  // assert(debugFile.is_open() && debugFile.good() &&
198  // "The path for placement Tcl dumping does not exist and please check your path "
199  // "settings");
200 
201  // debugFile << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<First Choice >>>>>>>>>>>>>>>\n";
202  // debugFile << PUId2PackingCLBSiteCandidate[117104]->getCLBSite()->getName() << "\n";
203  // debugFile << PUId2PackingCLBSiteCandidate[117104]->getPriorityQueueTop();
204  // debugFile << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>\n";
205  // debugFile.close();
206  // }
207  // if (tmpPU->getId() == 116959)
208  // {
209  // std::ofstream debugFile;
210  // debugFile.open("OpenPitonSLICE_SLICE_X38Y213", std::ios_base::app);
211  // assert(debugFile.is_open() && debugFile.good() &&
212  // "The path for placement Tcl dumping does not exist and please check your path "
213  // "settings");
214 
215  // debugFile << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<First Choice >>>>>>>>>>>>>>>\n";
216  // debugFile << PUId2PackingCLBSiteCandidate[116959]->getCLBSite()->getName() << "\n";
217  // debugFile << PUId2PackingCLBSiteCandidate[116959]->getPriorityQueueTop();
218  // debugFile << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>\n";
219  // debugFile.close();
220  // }
221  }
222  else
223  {
224  float oriDeltaScore =
225  PUId2PackingCLBSiteCandidate[tmpPU->getId()]->getPriorityQueueTop()->getScoreInSite() -
226  PUId2PackingCLBSiteCandidate[tmpPU->getId()]->getDetScore();
227  float newDeltaScore =
228  tmpPackingSite->getPriorityQueueTop()->getScoreInSite() - tmpPackingSite->getDetScore();
229  if (newDeltaScore > oriDeltaScore)
230  {
231  PUId2PackingCLBSiteCandidate[tmpPU->getId()] = tmpPackingSite;
232  // if (tmpPU->getId() == 117104)
233  // {
234  // std::ofstream debugFile;
235  // debugFile.open("OpenPitonSLICE_SLICE_X38Y213", std::ios_base::app);
236  // assert(debugFile.is_open() && debugFile.good() &&
237  // "The path for placement Tcl dumping does not exist and please check your path
238  // " "settings");
239 
240  // debugFile
241  // << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<Second Choice >>>>>>>>>>>>>>> :
242  // newDeltaScore"
243  // << newDeltaScore << " oriDeltaScore:" << oriDeltaScore << "\n";
244  // debugFile << PUId2PackingCLBSiteCandidate[117104]->getCLBSite()->getName() << "\n";
245  // debugFile << PUId2PackingCLBSiteCandidate[117104]->getPriorityQueueTop();
246  // debugFile << "-----------------------------------------------------------------\n";
247  // if (PUId2PackingCLBSiteCandidate[117104]->getDeterminedClusterInSite())
248  // debugFile << PUId2PackingCLBSiteCandidate[117104]->getDeterminedClusterInSite();
249  // debugFile << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>\n";
250  // debugFile.close();
251  // }
252  // if (tmpPU->getId() == 116959)
253  // {
254  // std::ofstream debugFile;
255  // debugFile.open("OpenPitonSLICE_SLICE_X38Y213", std::ios_base::app);
256  // assert(debugFile.is_open() && debugFile.good() &&
257  // "The path for placement Tcl dumping does not exist and please check your path
258  // " "settings");
259 
260  // debugFile
261  // << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<Second Choice >>>>>>>>>>>>>>> :
262  // newDeltaScore"
263  // << newDeltaScore << " oriDeltaScore:" << oriDeltaScore << "\n";
264  // debugFile << PUId2PackingCLBSiteCandidate[116959]->getCLBSite()->getName() << "\n";
265  // debugFile << PUId2PackingCLBSiteCandidate[116959]->getPriorityQueueTop();
266  // debugFile << "-----------------------------------------------------------------\n";
267  // if (PUId2PackingCLBSiteCandidate[116959]->getDeterminedClusterInSite())
268  // debugFile << PUId2PackingCLBSiteCandidate[116959]->getDeterminedClusterInSite();
269  // debugFile << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>\n";
270  // debugFile.close();
271  // }
272  }
273  }
274  }
275  }
276  }
277  }
278 
279  for (unsigned int i = 0; i < PUId2PackingCLBSite.size(); i++)
280  {
281  if (!PUId2PackingCLBSite[i] && PUId2PackingCLBSiteCandidate[i])
282  {
283  PUId2PackingCLBSite[i] = PUId2PackingCLBSiteCandidate[i];
284  }
285  }
286 }
287 
288 void ParallelCLBPacker::packCLBs(int packIterNum, bool doExceptionHandling, bool debug)
289 {
290  placementInfo->updateB2BAndGetTotalHPWL();
291  placementInfo->updateElementBinGrid(); // we don't need utilization information here, we can update LUT/FF
292  // utilization when needed.
293  int iterCnt = 0;
294  std::ofstream debugFile;
295  debugFile.open("OpenPitonSLICE_SLICE_X38Y213");
296  debugFile.close();
297 
298  packCLBsIteration(true, debug);
299  print_status("ParallelCLBPacker: initial packCLBsIteration done.");
300  while (true)
301  {
302  bool noValidPQTop = true;
303  for (auto tmpPackingSite : packingSites)
304  {
305  if (tmpPackingSite->hasValidPQTop())
306  {
307  noValidPQTop = false;
308  }
309  }
310  if (noValidPQTop)
311  {
312  break;
313  }
314 
315  int mappedPUCnt = 0;
316  for (auto packingSite : PUId2PackingCLBSite)
317  {
318  if (packingSite)
319  mappedPUCnt++;
320  }
321 
322  print_status("ParallelCLBPacker: iter#" + std::to_string(iterCnt) +
323  " #Mapped PU=" + std::to_string(mappedPUCnt));
324 
325  int deteminedCnt = 0;
326  std::map<int, int> sliceSize2SliceCnt;
327  sliceSize2SliceCnt.clear();
328  for (auto packingSite : packingSites)
329  {
330  if (packingSite)
331  {
332  if (packingSite->getDeterminedClusterInSite())
333  {
334  if (packingSite->getDeterminedClusterInSite()->getPUs().size())
335  {
336  deteminedCnt++;
337  int tmpSize = 0;
338  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
339  {
340  if (tmpPU->getType() == PlacementInfo::PlacementUnitType_Macro)
341  {
342  if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(tmpPU))
343  {
344  tmpSize += tmpPU->getWeight();
345  assert((unsigned int)tmpPU->getWeight() >= curMacro->getCells().size());
346  }
347 
348  // tmpSize += tmpPU->getWeight();
349  }
350  else
351  tmpSize += 1;
352  }
353  if (sliceSize2SliceCnt.find(tmpSize) == sliceSize2SliceCnt.end())
354  {
355  sliceSize2SliceCnt[tmpSize] = 1;
356  }
357  else
358  {
359  sliceSize2SliceCnt[tmpSize]++;
360  }
361  }
362  }
363  }
364  }
365  setPULocationToPackedSite();
366  int numFixed = 0;
367  for (auto PU : placementInfo->getPlacementUnits())
368  if (PU->isFixed())
369  numFixed++;
370 
371  float fixedRatio = (float)numFixed / (float)placementInfo->getPlacementUnits().size();
372  if (fixedRatio > 0.25 && WLOptimizer && iterCnt < 32)
373  {
374  placementInfo->updateElementBinGrid();
375  timingOptimizer->pauseCounter();
376  timingOptimizer->conductStaticTimingAnalysis();
377  placementInfo->getPU2ClockRegionCenters().clear();
378  print_status("ParallelCLBPacker: Move unfixed elements with WLOptimizer");
379  WLOptimizer->GlobalPlacementQPSolve(placementInfo->getPseudoNetWeight() * 2 * (1 + fixedRatio), true, true,
380  true, true, false, 1, timingOptimizer);
381  dumpAllCellsCoordinate();
382  }
383 
384  print_status("ParallelCLBPacker: current HPWL=" + std::to_string(placementInfo->updateB2BAndGetTotalHPWL()));
385  print_status("ParallelCLBPacker: iter#" + std::to_string(iterCnt) +
386  " #determined Slice=" + std::to_string(deteminedCnt));
387 
388  std::string distibution = "";
389  for (auto tmpPair : sliceSize2SliceCnt)
390  {
391  distibution += ("(" + std::to_string(tmpPair.first) + "," + std::to_string(tmpPair.second) + "), ");
392  }
393  print_status("ParallelCLBPacker: iter#" + std::to_string(iterCnt) + " Distribution: " + distibution);
394 
395  if (iterCnt > packIterNum)
396  {
397  break;
398  }
399  iterCnt++;
400 
401  // setPULocationToPackedSite();
402  // placementInfo->updateB2BAndGetTotalHPWL();
403 
404  packCLBsIteration(false, debug);
405 
406  for (auto packingSite : packingSites)
407  {
408  if (packingSite)
409  {
410  if (packingSite->getDeterminedClusterInSite())
411  {
412  assert(packingSite->getDeterminedClusterInSite()->areAllPUsValidForThisSite(PUId2PackingCLBSite,
413  packingSite));
414  }
415  }
416  }
417  // dumpCLBPacking();
418  }
419  print_status("ParallelCLBPacker: finish iterative packing");
420  if (doExceptionHandling)
421  {
422  // assert(!incrementalPacking && "for incremental packing, it is not worthy to do exception handling");
423  placementInfo->updateElementBinGrid();
424  timingOptimizer->conductStaticTimingAnalysis();
425  exceptionHandling(true);
426  placementInfo->updateElementBinGrid();
427  timingOptimizer->conductStaticTimingAnalysis();
428  int packNum = packingSites.size();
429  addNonCLBPackingSites();
430  int replaceCnt = 1000;
431 
432 #ifdef TIMINGDP
433  for (int i = 0; (i < 120 || replaceCnt > 60) && i < 150; i++)
434  {
435  cellId2PackingSite = std::vector<PackingCLBSite *>(placementInfo->getCells().size(), nullptr);
436  PUId2PackingCLBSite.clear();
437  PUId2PackingCLBSite.resize(placementInfo->getPlacementUnits().size(), nullptr);
438  for (auto packingSite : packingSites)
439  {
440  if (packingSite)
441  {
442  if (packingSite->getDeterminedClusterInSite())
443  {
444  auto cellSet = packingSite->getDeterminedClusterInSite()->getCellSet();
445  for (auto cell : cellSet)
446  {
447  cellId2PackingSite[cell->getCellId()] = packingSite;
448  auto curPU = placementInfo->getPlacementUnitByCellId(cell->getCellId());
449  PUId2PackingCLBSite[curPU->getId()] = packingSite;
450  }
451  }
452  else if (packingSite->checkIsNonCLBSite())
453  {
454  cellId2PackingSite[packingSite->getNonCLBCell()->getCellId()] = packingSite;
455  auto curPU = placementInfo->getPlacementUnitByCellId(packingSite->getNonCLBCell()->getCellId());
456  PUId2PackingCLBSite[curPU->getId()] = packingSite;
457  }
458  }
459  }
460  i++;
461  if (i >= 100)
462  replaceCnt = timingDrivenDetailedPlacement_shortestPath(i, 1.0 - 100.0 / 105.0);
463  else
464  replaceCnt = timingDrivenDetailedPlacement_shortestPath(i, 1.0 - i / 105.0);
465 
466  setPULocationToPackedSite();
467  timingOptimizer->conductStaticTimingAnalysis();
468  }
469 
470  replaceCnt = 1000;
471  for (int i = 0; i < 40 && replaceCnt > 5; i++)
472  {
473  cellId2PackingSite = std::vector<PackingCLBSite *>(placementInfo->getCells().size(), nullptr);
474  PUId2PackingCLBSite.clear();
475  PUId2PackingCLBSite.resize(placementInfo->getPlacementUnits().size(), nullptr);
476  for (auto packingSite : packingSites)
477  {
478  if (packingSite)
479  {
480  if (packingSite->getDeterminedClusterInSite())
481  {
482  auto cellSet = packingSite->getDeterminedClusterInSite()->getCellSet();
483  for (auto cell : cellSet)
484  {
485  cellId2PackingSite[cell->getCellId()] = packingSite;
486  auto curPU = placementInfo->getPlacementUnitByCellId(cell->getCellId());
487  PUId2PackingCLBSite[curPU->getId()] = packingSite;
488  }
489  }
490  else if (packingSite->checkIsNonCLBSite())
491  {
492  cellId2PackingSite[packingSite->getNonCLBCell()->getCellId()] = packingSite;
493  auto curPU = placementInfo->getPlacementUnitByCellId(packingSite->getNonCLBCell()->getCellId());
494  PUId2PackingCLBSite[curPU->getId()] = packingSite;
495  }
496  }
497  }
498  replaceCnt = timingDrivenDetailedPlacement_swap(i);
499  setPULocationToPackedSite();
500  timingOptimizer->conductStaticTimingAnalysis();
501  }
502 #endif
503 #pragma omp parallel for schedule(dynamic)
504  for (int i = 0; i < packNum; i++)
505  packingSites[i]->finalMapToSlots();
506 #ifdef TIMINGDP
507  timingDrivenDetailedPlacement_LUTFFPairReloacationAfterSlotMapping();
508 #endif
509  }
510 
511  // ensure the packing is legal
512  for (auto packingSite : packingSites)
513  {
514  if (packingSite)
515  {
516  if (packingSite->getDeterminedClusterInSite())
517  {
518  assert(packingSite->getDeterminedClusterInSite()->checkCellCorrectness(nullptr, true));
519  }
520  }
521  }
522  dumpFinalPacking();
523 }
524 
525 inline float getAngle(float v1x, float v1y, float v2x, float v2y)
526 {
527  float angle = atan2(v2y, v2x) - atan2(v1y, v1x);
528  if (angle > M_PI)
529  {
530  angle -= 2 * M_PI;
531  }
532  else if (angle <= -M_PI)
533  {
534  angle += 2 * M_PI;
535  }
536  return angle;
537 }
538 
539 int ParallelCLBPacker::timingDrivenDetailedPlacement_shortestPath(int iterId, float displacementRatio)
540 {
541  print_status("ParallelCLBPacker: conducting timing-driven detailed placement based on shortest path.");
542  auto oriCellIdsInCriticalPaths = timingOptimizer->findCriticalPaths(0.9);
543  std::set<PlacementInfo::PlacementUnit *> PUsTouched;
544  PUsTouched.clear();
545  std::ofstream outfileTcl("./DetailedPlacementRecord");
546  int replaceCnt = 0;
547  for (auto oriCellIdsInCriticalPath : oriCellIdsInCriticalPaths)
548  {
549  std::map<int, std::vector<PackingCLBSite *>> cellId2CandidateSites;
550  std::set<PackingCLBSite *> sitesCandidates;
551  std::map<PackingCLBSite *, PackingCLBSite::PackingCLBCluster *> site2TrialCluster;
552  cellId2CandidateSites.clear();
553 
554  std::vector<int> cellIdsInCriticalPath;
555  PlacementInfo::PlacementUnit *lastPU = nullptr;
556  std::set<PlacementInfo::PlacementUnit *> PUsInCriticalPathSet;
557  for (auto cellId : oriCellIdsInCriticalPath)
558  {
559  if (PUsInCriticalPathSet.find(placementInfo->getPlacementUnitByCellId(cellId)) ==
560  PUsInCriticalPathSet.end())
561  {
562  PUsInCriticalPathSet.insert(placementInfo->getPlacementUnitByCellId(cellId));
563  cellIdsInCriticalPath.push_back(cellId);
564  }
565  }
566  // std::cout << "processing endpoint [" << designInfo->getCells()[cellIdsInCriticalPath[0]] << "] with "
567  // << cellIdsInCriticalPath.size() << " nodes in path.\n";
568 
569  bool CellUnmapped = false;
570  for (auto cellId : cellIdsInCriticalPath)
571  {
572  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
573  auto curPackingSite = cellId2PackingSite[cellId];
574  auto curCell = designInfo->getCells()[cellId];
575  if (!curPackingSite)
576  {
577  CellUnmapped = true;
578  // std::cout << "a cell of the PU does not map to sites: " << curCell << "\n";
579  break;
580  }
581  assert(curPackingSite);
582  cellId2CandidateSites[cellId] = std::vector<PackingCLBSite *>(1, curPackingSite);
583  sitesCandidates.insert(curPackingSite);
584  if (!curPackingSite->checkIsNonCLBSite())
585  site2TrialCluster[curPackingSite] =
586  new PackingCLBSite::PackingCLBCluster(curPackingSite->getDeterminedClusterInSite());
587  }
588  if (CellUnmapped)
589  continue;
590  // find candidate sites for each possible PU
591 
592  for (int siteCandidateLimit = 1; siteCandidateLimit <= 10; siteCandidateLimit++)
593  {
594  float displacementThr = 5.0 * displacementRatio;
595  if (displacementThr < 1)
596  displacementThr = 1;
597  for (int orderI = cellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
598  {
599  auto cellId = cellIdsInCriticalPath[orderI];
600  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
601  if (PUsTouched.find(curPU) != PUsTouched.end())
602  {
603  continue;
604  }
605  auto curCell = designInfo->getCells()[cellId];
606  // std::cout << curCell << " has following candidates: \n";
607  if (!curPU->isLocked() && !curPU->checkHasCARRY() && !curPU->checkHasLUTRAM() &&
608  !curPU->checkHasBRAM() && !curPU->checkHasDSP())
609  {
610  float v1x = 0, v1y = 0, v2x = 0, v2y = 0;
611  if (orderI > 0 && orderI < cellIdsInCriticalPath.size() - 1)
612  {
613  auto predSite = cellId2PackingSite[cellIdsInCriticalPath[orderI - 1]];
614  int predSiteOrderId = orderI - 1;
615  auto curSite = cellId2PackingSite[cellId];
616  auto succSite = cellId2PackingSite[cellIdsInCriticalPath[orderI + 1]];
617  int succSiteOrderId = orderI + 1;
618  assert(predSite && curSite && succSite);
619  // while (curSite == predSite && predSiteOrderId - 1 >= 0)
620  // {
621  // predSiteOrderId--;
622  // predSite = cellId2PackingSite[cellIdsInCriticalPath[predSiteOrderId]];
623  // }
624  // while (curSite == succSite && succSiteOrderId + 1 <= cellIdsInCriticalPath.size() - 1)
625  // {
626  // succSiteOrderId++;
627  // succSite = cellId2PackingSite[cellIdsInCriticalPath[succSiteOrderId]];
628  // }
629  v1x = predSite->getCLBSite()->X() - curSite->getCLBSite()->X();
630  v1y = predSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
631  v2x = succSite->getCLBSite()->X() - curSite->getCLBSite()->X();
632  v2y = succSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
633  }
634  else if (orderI == 0)
635  {
636  auto curSite = cellId2PackingSite[cellId];
637  auto succSite = cellId2PackingSite[cellIdsInCriticalPath[orderI + 1]];
638  assert(curSite && succSite);
639  int succSiteOrderId = orderI + 1;
640  while (curSite == succSite && succSiteOrderId + 1 <= cellIdsInCriticalPath.size() - 1)
641  {
642  succSiteOrderId++;
643  succSite = cellId2PackingSite[cellIdsInCriticalPath[succSiteOrderId]];
644  }
645  v1x = v2x = succSite->getCLBSite()->X() - curSite->getCLBSite()->X();
646  v1y = v2y = succSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
647  }
648  else
649  {
650  auto predSite = cellId2PackingSite[cellIdsInCriticalPath[orderI - 1]];
651  auto curSite = cellId2PackingSite[cellId];
652  assert(predSite && curSite);
653  int predSiteOrderId = orderI - 1;
654  while (curSite == predSite && predSiteOrderId - 1 >= 0)
655  {
656  predSiteOrderId--;
657  predSite = cellId2PackingSite[cellIdsInCriticalPath[predSiteOrderId]];
658  }
659  v1x = v2x = predSite->getCLBSite()->X() - curSite->getCLBSite()->X();
660  v1y = v2y = predSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
661  }
662  if (std::fabs(v1x) + std::fabs(v1y) + std::fabs(v2x) + std::fabs(v2y) < 0.1)
663  continue;
664  if (std::fabs(getAngle(v1x, v1y, v2x, v2y)) < M_PI / 2)
665  {
666  assert(PUId2PackingCLBSite[curPU->getId()]);
667  auto candidateSitesToPlaceTheCell_cone = findNeiborSitesFromBinGrid(
668  DesignInfo::CellType_LUT4, PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X(),
669  PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y(), 0, displacementThr, y2xRatio, false,
670  v1x, v1y, v2x, v2y, 20);
671 
672  for (auto curDeviceSite : *candidateSitesToPlaceTheCell_cone)
673  {
674  if (deviceSite2PackingSite.find(curDeviceSite) == deviceSite2PackingSite.end())
675  continue;
676  PackingCLBSite *candidatePackingSite = deviceSite2PackingSite[curDeviceSite];
677  if (cellId2CandidateSites[cellId].size() >= siteCandidateLimit)
678  break;
679  bool duplicate = false;
680  for (auto existCandidate : cellId2CandidateSites[cellId])
681  {
682  if (existCandidate == candidatePackingSite)
683  duplicate = true;
684  }
685  if (duplicate)
686  continue;
687  PackingCLBSite::PackingCLBCluster *trialCluster = nullptr;
688  if (sitesCandidates.find(candidatePackingSite) == sitesCandidates.end())
689  {
690  if (!candidatePackingSite->getDeterminedClusterInSite())
691  {
692  auto determinedClusterInSite =
693  new PackingCLBSite::PackingCLBCluster(candidatePackingSite);
694  candidatePackingSite->setDeterminedClusterInSite(determinedClusterInSite);
695  }
696  trialCluster = new PackingCLBSite::PackingCLBCluster(
697  candidatePackingSite->getDeterminedClusterInSite());
698  site2TrialCluster[candidatePackingSite] = trialCluster;
699  }
700  else
701  {
702  trialCluster = site2TrialCluster[candidatePackingSite];
703  }
704 
705  if (trialCluster->checkAddPU(curPU))
706  {
707  assert(trialCluster->addPU(curPU));
708  cellId2CandidateSites[cellId].push_back(candidatePackingSite);
709  sitesCandidates.insert(candidatePackingSite);
710  }
711 
712  // }
713  }
714 
715  delete candidateSitesToPlaceTheCell_cone;
716  }
717  }
718  }
719 
720  for (int orderI = cellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
721  {
722  auto cellId = cellIdsInCriticalPath[orderI];
723  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
724  auto curCell = designInfo->getCells()[cellId];
725  if (PUsTouched.find(curPU) != PUsTouched.end())
726  {
727  continue;
728  }
729  // std::cout << curCell << " has following candidates: \n";
730  if (!curPU->isLocked() && !curPU->checkHasCARRY() && !curPU->checkHasLUTRAM() &&
731  !curPU->checkHasBRAM() && !curPU->checkHasDSP())
732  {
733  std::vector<DeviceInfo::DeviceSite *> *candidateSitesToPlaceTheCell = findNeiborSitesFromBinGrid(
734  DesignInfo::CellType_LUT4, PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X(),
735  PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y(), 0, 0.8 + displacementRatio, y2xRatio,
736  false);
737  if (cellId2CandidateSites[cellId].size() >= siteCandidateLimit + 1)
738  break;
739  // std::cout << curCell << " has " << candidateSitesToPlaceTheCell->size()
740  // << " neighbors and candidates are:\n";
741  for (auto curDeviceSite : *candidateSitesToPlaceTheCell)
742  {
743  if (deviceSite2PackingSite.find(curDeviceSite) == deviceSite2PackingSite.end())
744  continue;
745  PackingCLBSite *candidatePackingSite = deviceSite2PackingSite[curDeviceSite];
746  bool duplicate = false;
747  for (auto existCandidate : cellId2CandidateSites[cellId])
748  {
749  if (existCandidate == candidatePackingSite)
750  duplicate = true;
751  }
752  if (duplicate)
753  continue;
754  PackingCLBSite::PackingCLBCluster *trialCluster = nullptr;
755  if (sitesCandidates.find(candidatePackingSite) == sitesCandidates.end())
756  {
757  if (!candidatePackingSite->getDeterminedClusterInSite())
758  {
759  auto determinedClusterInSite =
760  new PackingCLBSite::PackingCLBCluster(candidatePackingSite);
761  candidatePackingSite->setDeterminedClusterInSite(determinedClusterInSite);
762  }
763  trialCluster = new PackingCLBSite::PackingCLBCluster(
764  candidatePackingSite->getDeterminedClusterInSite());
765  site2TrialCluster[candidatePackingSite] = trialCluster;
766  }
767  else
768  {
769  trialCluster = site2TrialCluster[candidatePackingSite];
770  }
771 
772  if (trialCluster->checkAddPU(curPU))
773  {
774  assert(trialCluster->addPU(curPU));
775  cellId2CandidateSites[cellId].push_back(candidatePackingSite);
776  sitesCandidates.insert(candidatePackingSite);
777  }
778  }
779 
780  delete candidateSitesToPlaceTheCell;
781  }
782 
783  // for (auto packingSite : cellId2CandidateSites[cellId])
784  // {
785  // std::cout << " " << packingSite->getCLBSite()->getName() << "\n";
786  // }
787  }
788  }
789 
790  // calculate the shortest paths
791  std::vector<std::vector<float>> shortestPath_LayerSite;
792  std::vector<std::vector<int>> shortestPath_LayerSite_backtrace;
793  shortestPath_LayerSite.push_back(
794  std::vector<float>(cellId2CandidateSites[cellIdsInCriticalPath[0]].size(), 0.0));
795  shortestPath_LayerSite_backtrace.push_back(
796  std::vector<int>(cellId2CandidateSites[cellIdsInCriticalPath[0]].size(), -1));
797 
798  if (iterId > 100)
799  {
800  outfileTcl << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>\nCellsCandidate:\n";
801  for (int i = 0; i < cellIdsInCriticalPath.size(); i++)
802  {
803  auto curCellId = cellIdsInCriticalPath[i];
804  auto curCell = designInfo->getCells()[curCellId];
805  auto &curCandidates = cellId2CandidateSites[curCellId];
806  outfileTcl << "cell: " << curCell << "\n";
807  for (int k = 0; k < curCandidates.size(); k++)
808  {
809  outfileTcl << " " << cellId2CandidateSites[curCellId][k]->getCLBSite()->getName() << "\n";
810  }
811  }
812  }
813 
814  int bestEndChoice = -1;
815  float bestChoiceDelay = 100000;
816  for (int i = 1; i < cellIdsInCriticalPath.size(); i++)
817  {
818  auto predCell = cellIdsInCriticalPath[i - 1];
819  auto curCell = cellIdsInCriticalPath[i];
820  auto &predCandidates = cellId2CandidateSites[predCell];
821  auto &curCandidates = cellId2CandidateSites[curCell];
822  shortestPath_LayerSite.push_back(std::vector<float>(cellId2CandidateSites[curCell].size(), 100000.0));
823  shortestPath_LayerSite_backtrace.push_back(std::vector<int>(cellId2CandidateSites[curCell].size(), -1));
824 
825  for (int j = 0; j < predCandidates.size(); j++)
826  {
827  for (int k = 0; k < curCandidates.size(); k++)
828  {
829  float delay = timingOptimizer->getDelayByModel(
830  predCandidates[j]->getCLBSite()->X(), predCandidates[j]->getCLBSite()->Y(),
831  curCandidates[k]->getCLBSite()->X(), curCandidates[k]->getCLBSite()->Y());
832 
833  if (shortestPath_LayerSite[i][k] > shortestPath_LayerSite[i - 1][j] + delay)
834  {
835  shortestPath_LayerSite[i][k] = shortestPath_LayerSite[i - 1][j] + delay;
836  shortestPath_LayerSite_backtrace[i][k] = j;
837 
838  if (i == cellIdsInCriticalPath.size() - 1)
839  {
840  if (shortestPath_LayerSite[i][k] < bestChoiceDelay)
841  {
842  bestChoiceDelay = shortestPath_LayerSite[i][k];
843  bestEndChoice = k;
844  }
845  }
846  }
847  }
848  }
849  }
850 
851  for (int i = shortestPath_LayerSite.size() - 1; i >= 0; i--)
852  {
853  assert(bestEndChoice >= 0);
854  if (bestEndChoice > 0)
855  {
856  auto curCellId = cellIdsInCriticalPath[i];
857  auto curPU = placementInfo->getPlacementUnitByCellId(curCellId);
858 
859  auto &curCandidates = cellId2CandidateSites[curCellId];
860 
861  auto targetPackingSite = cellId2CandidateSites[curCellId][bestEndChoice];
862  if (!targetPackingSite->getDeterminedClusterInSite()->checkAddPU(curPU))
863  {
864  bestEndChoice = shortestPath_LayerSite_backtrace[i][bestEndChoice];
865  continue;
866  }
867 
868  cellId2CandidateSites[curCellId][0]->getDeterminedClusterInSite()->removePUToConstructDetCluster(curPU);
869 
870  assert(bestEndChoice < cellId2CandidateSites[curCellId].size());
871  assert(targetPackingSite->getDeterminedClusterInSite()->addPU(curPU));
872  PUId2PackingCLBSite[curPU->getId()] = targetPackingSite;
873  placementInfo->addPUIntoClockColumn(curPU, targetPackingSite->getCLBSite());
874  auto cellSet = targetPackingSite->getDeterminedClusterInSite()->getCellSet();
875  for (auto cell : cellSet)
876  {
877  cellId2PackingSite[cell->getCellId()] = targetPackingSite;
878  }
879  replaceCnt++;
880  }
881  bestEndChoice = shortestPath_LayerSite_backtrace[i][bestEndChoice];
882  }
883 
884  for (int i = 0; i < shortestPath_LayerSite.size() - 1; i++)
885  {
886  auto curCellId = cellIdsInCriticalPath[i];
887  auto curPU = placementInfo->getPlacementUnitByCellId(curCellId);
888  auto nextCellId = cellIdsInCriticalPath[i + 1];
889  auto nextPU = placementInfo->getPlacementUnitByCellId(nextCellId);
890  if (curPU->checkHasCARRY() || curPU->checkHasLUTRAM() || curPU->checkHasBRAM() || curPU->checkHasDSP() ||
891  nextPU->checkHasCARRY() || nextPU->checkHasLUTRAM() || nextPU->checkHasBRAM() ||
892  nextPU->checkHasDSP() || PUsTouched.find(curPU) != PUsTouched.end() ||
893  PUsTouched.find(nextPU) != PUsTouched.end() || curPU == nextPU || curPU->isLocked() ||
894  nextPU->isLocked())
895  {
896  continue;
897  }
898  if (PUId2PackingCLBSite[curPU->getId()] == PUId2PackingCLBSite[nextPU->getId()])
899  continue;
900 
901  float oriDis = 0;
902  float newDis = 0;
903  auto curPackingSite = PUId2PackingCLBSite[curPU->getId()];
904  auto nextPackingSite = PUId2PackingCLBSite[nextPU->getId()];
905  float curX = PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X();
906  float curY = PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y();
907  float nextX = PUId2PackingCLBSite[nextPU->getId()]->getCLBSite()->X();
908  float nextY = PUId2PackingCLBSite[nextPU->getId()]->getCLBSite()->Y();
909 
910  if (timingOptimizer->getDelayByModel(nextX, nextY, curX, curY) > 0.5)
911  continue;
912 
913  if (i > 0)
914  {
915  auto prevCellId = cellIdsInCriticalPath[i - 1];
916  assert(cellId2PackingSite[prevCellId]);
917  float headX = cellId2PackingSite[prevCellId]->getCLBSite()->X();
918  float headY = cellId2PackingSite[prevCellId]->getCLBSite()->Y();
919  oriDis += timingOptimizer->getDelayByModel(headX, headY, curX, curY);
920  newDis += timingOptimizer->getDelayByModel(headX, headY, nextX, nextY);
921  }
922 
923  if (i < shortestPath_LayerSite.size() - 1)
924  {
925  auto succCellId = cellIdsInCriticalPath[i + 1];
926  assert(cellId2PackingSite[succCellId]);
927  float tailX = cellId2PackingSite[succCellId]->getCLBSite()->X();
928  float tailY = cellId2PackingSite[succCellId]->getCLBSite()->Y();
929  newDis += timingOptimizer->getDelayByModel(tailX, tailY, curX, curY);
930  oriDis += timingOptimizer->getDelayByModel(tailX, tailY, nextX, nextY);
931  }
932 
933  if (newDis < oriDis)
934  {
935  auto trialClusterWithCurPU =
936  new PackingCLBSite::PackingCLBCluster(curPackingSite->getDeterminedClusterInSite());
937  auto trialClusterWithNextPU =
938  new PackingCLBSite::PackingCLBCluster(nextPackingSite->getDeterminedClusterInSite());
939  assert(trialClusterWithCurPU->contains(curPU));
940  trialClusterWithCurPU->removePUToConstructDetCluster(curPU);
941  assert(trialClusterWithNextPU->contains(nextPU));
942  trialClusterWithNextPU->removePUToConstructDetCluster(nextPU);
943  if (trialClusterWithCurPU->addPU(nextPU))
944  {
945  if (trialClusterWithNextPU->addPU(curPU))
946  {
947  curPackingSite->getDeterminedClusterInSite()->removePUToConstructDetCluster(curPU);
948  assert(curPackingSite->getDeterminedClusterInSite()->addPU(nextPU));
949  nextPackingSite->getDeterminedClusterInSite()->removePUToConstructDetCluster(nextPU);
950  assert(nextPackingSite->getDeterminedClusterInSite()->addPU(curPU));
951 
952  PUId2PackingCLBSite[curPU->getId()] = nextPackingSite;
953  placementInfo->addPUIntoClockColumn(curPU, nextPackingSite->getCLBSite());
954  auto cellSet = nextPackingSite->getDeterminedClusterInSite()->getCellSet();
955  for (auto cell : cellSet)
956  {
957  cellId2PackingSite[cell->getCellId()] = nextPackingSite;
958  }
959 
960  PUId2PackingCLBSite[nextPU->getId()] = curPackingSite;
961  placementInfo->addPUIntoClockColumn(nextPU, curPackingSite->getCLBSite());
962  cellSet = curPackingSite->getDeterminedClusterInSite()->getCellSet();
963  for (auto cell : cellSet)
964  {
965  cellId2PackingSite[cell->getCellId()] = curPackingSite;
966  }
967  }
968  }
969 
970  delete trialClusterWithCurPU;
971  delete trialClusterWithNextPU;
972  }
973  }
974 
975  for (int orderI = cellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
976  {
977  auto cellId = cellIdsInCriticalPath[orderI];
978  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
979  PUsTouched.insert(curPU);
980  }
981  for (auto pair : site2TrialCluster)
982  {
983  delete pair.second;
984  }
985  }
986 
987  print_status("ParallelCLBPacker: conducted timing-driven detailed placement (shortest path) and " +
988  std::to_string(replaceCnt) + " PlacementUnits are replaced.");
989  outfileTcl.close();
990  return replaceCnt;
991 }
992 
993 int ParallelCLBPacker::timingDrivenDetailedPlacement_LUTFFPairReloacationAfterSlotMapping()
994 {
995  print_status("ParallelCLBPacker: re-place some LUT-FF pairs since they are not connected via internal nets.");
996  auto oriCellIdsInCriticalPaths = timingOptimizer->findCriticalPaths(1, false, 100);
997 
998  // auto &sortedTimingNodes = timingOptimizer->getSortedTimingNodes();
999  // std::vector<bool> FFDirectlyDrivenButNotInOneSlot;
1000  // FFDirectlyDrivenButNotInOneSlot.clear();
1001  // FFDirectlyDrivenButNotInOneSlot.resize(designInfo->getCells().size(), 0);
1002  // for (auto node : sortedTimingNodes)
1003  // {
1004  // int cellId = node->getDesignNode()->getCellId();
1005  // bool shouldRelocateLUTFFPair = false;
1006  // PackingCLBSite *srcSite = nullptr;
1007  // auto LUTFFPair = dynamic_cast<PlacementInfo::PlacementMacro
1008  // *>(placementInfo->getPlacementUnitByCellId(cellId)); DesignInfo::DesignCell *targetLUT = nullptr;
1009  // DesignInfo::DesignCell *targetFF = nullptr;
1010  // if (LUTFFPair)
1011  // {
1012  // if (LUTFFPair->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_LUTFFPair)
1013  // {
1014  // auto curPackingSite = cellId2PackingSite[cellId];
1015  // targetLUT = LUTFFPair->getCells()[0];
1016  // targetFF = LUTFFPair->getCells()[1];
1017  // auto LUTLoc = curPackingSite->getLUTSlot(targetLUT);
1018  // auto FFLoc = curPackingSite->getFFSlot(targetFF);
1019  // shouldRelocateLUTFFPair = !(LUTLoc[0] == FFLoc[0] && LUTLoc[1] == FFLoc[1] && LUTLoc[2] == FFLoc[2]);
1020  // srcSite = curPackingSite;
1021  // }
1022  // FFDirectlyDrivenButNotInOneSlot[cellId] = shouldRelocateLUTFFPair;
1023  // }
1024  // }
1025 
1026  // auto oriCellIdsInCriticalPaths = timingOptimizer->findCriticalPaths(1, FFDirectlyDrivenButNotInOneSlot);
1027  // oriCellIdsInCriticalPaths.resize(200);
1028  std::set<PlacementInfo::PlacementUnit *> PUsTouched;
1029  PUsTouched.clear();
1030  int replaceCnt = 0;
1031  for (auto oriCellIdsInCriticalPath : oriCellIdsInCriticalPaths)
1032  {
1033  std::map<int, std::vector<PackingCLBSite *>> cellId2CandidateSites;
1034  std::set<PackingCLBSite *> sitesCandidates;
1035  std::map<PackingCLBSite *, PackingCLBSite::PackingCLBCluster *> site2TrialCluster;
1036  cellId2CandidateSites.clear();
1037 
1038  std::vector<int> cellIdsInCriticalPath;
1039  PlacementInfo::PlacementUnit *lastPU = nullptr;
1040  std::set<PlacementInfo::PlacementUnit *> PUsInCriticalPathSet;
1041  for (auto cellId : oriCellIdsInCriticalPath)
1042  {
1043  if (PUsInCriticalPathSet.find(placementInfo->getPlacementUnitByCellId(cellId)) ==
1044  PUsInCriticalPathSet.end())
1045  {
1046  PUsInCriticalPathSet.insert(placementInfo->getPlacementUnitByCellId(cellId));
1047  cellIdsInCriticalPath.push_back(cellId);
1048  }
1049  }
1050 
1051  bool shouldRelocateLUTFFPair = false;
1052  PackingCLBSite *srcSite = nullptr;
1053  auto LUTFFPair = dynamic_cast<PlacementInfo::PlacementMacro *>(
1054  placementInfo->getPlacementUnitByCellId(oriCellIdsInCriticalPath[0]));
1055  DesignInfo::DesignCell *targetLUT = nullptr;
1056  DesignInfo::DesignCell *targetFF = nullptr;
1057  if (LUTFFPair)
1058  {
1059  if (LUTFFPair->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_LUTFFPair)
1060  {
1061  auto curPackingSite = cellId2PackingSite[oriCellIdsInCriticalPath[0]];
1062  targetLUT = LUTFFPair->getCells()[0];
1063  targetFF = LUTFFPair->getCells()[1];
1064  auto LUTLoc = curPackingSite->getLUTSlot(targetLUT);
1065  auto FFLoc = curPackingSite->getFFSlot(targetFF);
1066  shouldRelocateLUTFFPair = !(LUTLoc[0] == FFLoc[0] && LUTLoc[1] == FFLoc[1] && LUTLoc[2] == FFLoc[2]);
1067  srcSite = curPackingSite;
1068  }
1069  }
1070 
1071  if (!shouldRelocateLUTFFPair)
1072  continue;
1073 
1074  // std::cout << "handling " << LUTFFPair << "\n";
1075  int siteCandidateLimit = 9;
1076 
1077  float displacementThr = 1.5;
1078  int orderI = 0;
1079  auto cellId = cellIdsInCriticalPath[orderI];
1080  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1081  if (PUsTouched.find(curPU) != PUsTouched.end())
1082  {
1083  continue;
1084  }
1085 
1086  PUsTouched.insert(curPU);
1087  if (!curPU->isLocked() && !curPU->checkHasCARRY() && !curPU->checkHasLUTRAM() && !curPU->checkHasBRAM() &&
1088  !curPU->checkHasDSP())
1089  {
1090  float v1x = 0, v1y = 0, v2x = 0, v2y = 0;
1091 
1092  auto curSite = cellId2PackingSite[cellId];
1093  auto succSite = cellId2PackingSite[cellIdsInCriticalPath[orderI + 1]];
1094  assert(curSite && succSite);
1095  int succSiteOrderId = orderI + 1;
1096  while (curSite == succSite && succSiteOrderId + 1 <= cellIdsInCriticalPath.size() - 1)
1097  {
1098  succSiteOrderId++;
1099  succSite = cellId2PackingSite[cellIdsInCriticalPath[succSiteOrderId]];
1100  }
1101  v1x = v2x = succSite->getCLBSite()->X() - curSite->getCLBSite()->X();
1102  v1y = v2y = succSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
1103 
1104  if (std::fabs(v1x) + std::fabs(v1y) + std::fabs(v2x) + std::fabs(v2y) < 0.1)
1105  continue;
1106  if (std::fabs(getAngle(v1x, v1y, v2x, v2y)) < M_PI / 2)
1107  {
1108  assert(PUId2PackingCLBSite[curPU->getId()]);
1109  auto candidateSitesToPlaceTheCell_cone = findNeiborSitesFromBinGrid(
1110  DesignInfo::CellType_LUT4, PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X(),
1111  PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y(), 0, displacementThr, y2xRatio, false, v1x,
1112  v1y, v2x, v2y, 20);
1113 
1114  for (auto curDeviceSite : *candidateSitesToPlaceTheCell_cone)
1115  {
1116  if (deviceSite2PackingSite.find(curDeviceSite) == deviceSite2PackingSite.end())
1117  continue;
1118  PackingCLBSite *candidatePackingSite = deviceSite2PackingSite[curDeviceSite];
1119  if (cellId2CandidateSites[cellId].size() >= siteCandidateLimit)
1120  break;
1121  bool duplicate = false;
1122  for (auto existCandidate : cellId2CandidateSites[cellId])
1123  {
1124  if (existCandidate == candidatePackingSite)
1125  duplicate = true;
1126  }
1127  if (duplicate)
1128  continue;
1129  PackingCLBSite::PackingCLBCluster *trialCluster = nullptr;
1130  if (sitesCandidates.find(candidatePackingSite) == sitesCandidates.end())
1131  {
1132  if (!candidatePackingSite->getDeterminedClusterInSite())
1133  {
1134  auto determinedClusterInSite = new PackingCLBSite::PackingCLBCluster(candidatePackingSite);
1135  candidatePackingSite->setDeterminedClusterInSite(determinedClusterInSite);
1136  }
1137  trialCluster =
1138  new PackingCLBSite::PackingCLBCluster(candidatePackingSite->getDeterminedClusterInSite());
1139  site2TrialCluster[candidatePackingSite] = trialCluster;
1140  }
1141  else
1142  {
1143  trialCluster = site2TrialCluster[candidatePackingSite];
1144  }
1145 
1146  if (trialCluster->checkAddPU(curPU))
1147  {
1148  assert(trialCluster->addPU(curPU));
1149  cellId2CandidateSites[cellId].push_back(candidatePackingSite);
1150  sitesCandidates.insert(candidatePackingSite);
1151  }
1152 
1153  // }
1154  }
1155  delete candidateSitesToPlaceTheCell_cone;
1156  }
1157  }
1158 
1159  // std::cout << curCell << " has following candidates: \n";
1160  if (!curPU->isLocked() && !curPU->checkHasCARRY() && !curPU->checkHasLUTRAM() && !curPU->checkHasBRAM() &&
1161  !curPU->checkHasDSP())
1162  {
1163  std::vector<DeviceInfo::DeviceSite *> *candidateSitesToPlaceTheCell = findNeiborSitesFromBinGrid(
1164  DesignInfo::CellType_LUT4, PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X(),
1165  PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y(), 0, displacementThr, y2xRatio, false);
1166  if (cellId2CandidateSites[cellId].size() >= siteCandidateLimit + 1)
1167  break;
1168  // std::cout << curCell << " has " << candidateSitesToPlaceTheCell->size()
1169  // << " neighbors and candidates are:\n";
1170  for (auto curDeviceSite : *candidateSitesToPlaceTheCell)
1171  {
1172  if (deviceSite2PackingSite.find(curDeviceSite) == deviceSite2PackingSite.end())
1173  continue;
1174  PackingCLBSite *candidatePackingSite = deviceSite2PackingSite[curDeviceSite];
1175  bool duplicate = false;
1176  for (auto existCandidate : cellId2CandidateSites[cellId])
1177  {
1178  if (existCandidate == candidatePackingSite)
1179  duplicate = true;
1180  }
1181  if (duplicate)
1182  continue;
1183  PackingCLBSite::PackingCLBCluster *trialCluster = nullptr;
1184  if (sitesCandidates.find(candidatePackingSite) == sitesCandidates.end())
1185  {
1186  if (!candidatePackingSite->getDeterminedClusterInSite())
1187  {
1188  auto determinedClusterInSite = new PackingCLBSite::PackingCLBCluster(candidatePackingSite);
1189  candidatePackingSite->setDeterminedClusterInSite(determinedClusterInSite);
1190  }
1191  trialCluster =
1192  new PackingCLBSite::PackingCLBCluster(candidatePackingSite->getDeterminedClusterInSite());
1193  site2TrialCluster[candidatePackingSite] = trialCluster;
1194  }
1195  else
1196  {
1197  trialCluster = site2TrialCluster[candidatePackingSite];
1198  }
1199 
1200  if (trialCluster->checkAddPU(curPU))
1201  {
1202  assert(trialCluster->addPU(curPU));
1203  cellId2CandidateSites[cellId].push_back(candidatePackingSite);
1204  sitesCandidates.insert(candidatePackingSite);
1205  }
1206  }
1207 
1208  delete candidateSitesToPlaceTheCell;
1209  }
1210 
1211  // calculate the shortest paths
1212  int bestEndChoice = -1;
1213  float bestChoiceDelay = 100000;
1214 
1215  int predCell = cellIdsInCriticalPath[1];
1216  auto &curCandidates = cellId2CandidateSites[cellId];
1217  auto predCandidate = cellId2PackingSite[predCell];
1218 
1219  for (int k = 0; k < curCandidates.size(); k++)
1220  {
1221  // std::cout << "considering " << curCandidates[k]->getCLBSite()->getName() << "\n";
1222  if (curCandidates[k] == srcSite)
1223  continue;
1224  float delay = timingOptimizer->getDelayByModel(
1225  predCandidate->getCLBSite()->X(), predCandidate->getCLBSite()->Y(), curCandidates[k]->getCLBSite()->X(),
1226  curCandidates[k]->getCLBSite()->Y());
1227 
1228  if (bestChoiceDelay > delay)
1229  {
1230  // std::cout << " better delay\n";
1231  if (curCandidates[k]->getSlotMapping().canDirectConnectInSlot(targetLUT, targetFF))
1232  {
1233  bestChoiceDelay = delay;
1234  bestEndChoice = k;
1235  // std::cout << " has direct connect\n";
1236  }
1237  }
1238  }
1239 
1240  if (bestEndChoice > 0)
1241  {
1242  srcSite->getDeterminedClusterInSite()->removePUToConstructDetCluster(LUTFFPair);
1243  srcSite->getSlotMappingRef().removeLUTFFPair(targetLUT, targetFF);
1244  assert(curCandidates[bestEndChoice]->getDeterminedClusterInSite()->addPU(LUTFFPair));
1245  curCandidates[bestEndChoice]->getSlotMappingRef().addLUTFFPair(targetLUT, targetFF);
1246  PUId2PackingCLBSite[LUTFFPair->getId()] = curCandidates[bestEndChoice];
1247  placementInfo->addPUIntoClockColumn(LUTFFPair, curCandidates[bestEndChoice]->getCLBSite());
1248  replaceCnt++;
1249  }
1250 
1251  for (auto pair : site2TrialCluster)
1252  {
1253  delete pair.second;
1254  }
1255  }
1256 
1257  print_status("ParallelCLBPacker: conducted timing-driven detailed placement (LUT-FF pairs) and " +
1258  std::to_string(replaceCnt) + " PlacementUnits are replaced.");
1259 
1260  return replaceCnt;
1261 }
1262 
1263 int ParallelCLBPacker::timingDrivenDetailedPlacement_shortestPath_intermediate()
1264 {
1265  print_status("ParallelCLBPacker: conducting timing-driven detailed placement based on shortest path.");
1266  auto oriCellIdsInCriticalPaths = timingOptimizer->findCriticalPaths(1);
1267  std::set<PlacementInfo::PlacementUnit *> PUsTouched;
1268  PUsTouched.clear();
1269  std::vector<PlacementInfo::Location> &cellLoc = placementInfo->getCellId2location();
1270 
1271  int replaceCnt = 0;
1272  for (auto oriCellIdsInCriticalPath : oriCellIdsInCriticalPaths)
1273  {
1274  std::map<int, std::vector<PlacementInfo::Location>> cellId2CandidateLocation;
1275  cellId2CandidateLocation.clear();
1276 
1277  std::vector<int> cellIdsInCriticalPath;
1278  PlacementInfo::PlacementUnit *lastPU = nullptr;
1279  std::set<PlacementInfo::PlacementUnit *> PUsInCriticalPathSet;
1280  for (auto cellId : oriCellIdsInCriticalPath)
1281  {
1282  if (PUsInCriticalPathSet.find(placementInfo->getPlacementUnitByCellId(cellId)) ==
1283  PUsInCriticalPathSet.end())
1284  {
1285  PUsInCriticalPathSet.insert(placementInfo->getPlacementUnitByCellId(cellId));
1286  cellIdsInCriticalPath.push_back(cellId);
1287  }
1288  }
1289 
1290  bool CellUnmapped = false;
1291  for (auto cellId : cellIdsInCriticalPath)
1292  {
1293  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1294  auto curPackingSite = cellId2PackingSite[cellId];
1295  auto curCell = designInfo->getCells()[cellId];
1296 
1297  cellId2CandidateLocation[cellId] = std::vector<PlacementInfo::Location>(1, cellLoc[cellId]);
1298  }
1299 
1300  for (int orderI = cellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
1301  {
1302  auto cellId = cellIdsInCriticalPath[orderI];
1303  auto curPackingSite = cellId2PackingSite[cellId];
1304  if (curPackingSite)
1305  continue;
1306  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1307  auto curCell = designInfo->getCells()[cellId];
1308  if (PUsTouched.find(curPU) != PUsTouched.end())
1309  {
1310  continue;
1311  }
1312  // std::cout << curCell << " has following candidates: \n";
1313  if (!curPU->isLocked() && !curPU->isFixed() && !curPU->checkHasCARRY() && !curPU->checkHasLUTRAM() &&
1314  !curPU->checkHasBRAM() && !curPU->checkHasDSP())
1315  {
1316  auto curX = cellLoc[cellId].X;
1317  auto curY = cellLoc[cellId].Y;
1318  for (float cX = curX - 1.0; cX < curX + 1.1; cX += 0.5)
1319  {
1320  for (float cY = curY - 1.0; cY < curY + 1.1; cY += 0.5)
1321  {
1322  if (std::fabs(cX - curX) + std::fabs(cY - curY) < 0.1)
1323  continue;
1324  PlacementInfo::Location newLoc;
1325  newLoc.X = cX;
1326  newLoc.Y = cY;
1327  cellId2CandidateLocation[cellId].push_back(newLoc);
1328  }
1329  }
1330  }
1331  }
1332  for (int orderI = cellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
1333  {
1334  auto cellId = cellIdsInCriticalPath[orderI];
1335  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1336  PUsTouched.insert(curPU);
1337  }
1338  // calculate the shortest paths
1339  std::vector<std::vector<float>> shortestPath_LayerSite;
1340  std::vector<std::vector<int>> shortestPath_LayerSite_backtrace;
1341  shortestPath_LayerSite.push_back(
1342  std::vector<float>(cellId2CandidateLocation[cellIdsInCriticalPath[0]].size(), 0.0));
1343  shortestPath_LayerSite_backtrace.push_back(
1344  std::vector<int>(cellId2CandidateLocation[cellIdsInCriticalPath[0]].size(), -1));
1345 
1346  int bestEndChoice = -1;
1347  float bestChoiceDelay = 100000;
1348 
1349  for (int i = 1; i < cellIdsInCriticalPath.size(); i++)
1350  {
1351  auto predCell = cellIdsInCriticalPath[i - 1];
1352  auto curCell = cellIdsInCriticalPath[i];
1353  auto &predCandidates = cellId2CandidateLocation[predCell];
1354  auto &curCandidates = cellId2CandidateLocation[curCell];
1355  shortestPath_LayerSite.push_back(std::vector<float>(cellId2CandidateLocation[curCell].size(), 100000.0));
1356  shortestPath_LayerSite_backtrace.push_back(std::vector<int>(cellId2CandidateLocation[curCell].size(), -1));
1357 
1358  for (int j = 0; j < predCandidates.size(); j++)
1359  {
1360  for (int k = 0; k < curCandidates.size(); k++)
1361  {
1362  float predX = predCandidates[j].X, predY = predCandidates[j].Y;
1363  float curX = curCandidates[k].X, curY = curCandidates[k].Y;
1364 
1365  float delay = timingOptimizer->getDelayByModel(predX, predY, curX, curY);
1366 
1367  if (shortestPath_LayerSite[i][k] > shortestPath_LayerSite[i - 1][j] + delay)
1368  {
1369  shortestPath_LayerSite[i][k] = shortestPath_LayerSite[i - 1][j] + delay;
1370  shortestPath_LayerSite_backtrace[i][k] = j;
1371 
1372  if (i == cellIdsInCriticalPath.size() - 1)
1373  {
1374  if (shortestPath_LayerSite[i][k] < bestChoiceDelay)
1375  {
1376  bestChoiceDelay = shortestPath_LayerSite[i][k];
1377  bestEndChoice = k;
1378  }
1379  }
1380  }
1381  }
1382  }
1383  }
1384 
1385  for (int i = shortestPath_LayerSite.size() - 1; i >= 0; i--)
1386  {
1387  if (bestEndChoice)
1388  {
1389  auto curCellId = cellIdsInCriticalPath[i];
1390  auto curPU = placementInfo->getPlacementUnitByCellId(curCellId);
1391 
1392  auto &curCandidates = cellId2CandidateLocation[curCellId];
1393  if (!curPU->isLocked() && !curPU->isFixed() && !curPU->checkHasCARRY() && !curPU->checkHasLUTRAM() &&
1394  !curPU->checkHasBRAM() && !curPU->checkHasDSP())
1395  {
1396  curPU->setAnchorLocationAndForgetTheOriginalOne(curCandidates[bestEndChoice].X,
1397  curCandidates[bestEndChoice].Y);
1398  replaceCnt++;
1399  }
1400  }
1401  bestEndChoice = shortestPath_LayerSite_backtrace[i][bestEndChoice];
1402  }
1403  }
1404 
1405  print_status("ParallelCLBPacker: conducted timing-driven detailed placement (shortest path) and " +
1406  std::to_string(replaceCnt) + " PlacementUnits are replaced.");
1407  return replaceCnt;
1408 }
1409 
1410 int ParallelCLBPacker::timingDrivenDetailedPlacement_swap(int iterId)
1411 {
1412  print_status("ParallelCLBPacker: conducting timing-driven detailed placement based on swaping.");
1413  auto oriCellIdsInCriticalPaths = timingOptimizer->findCriticalPaths(0.9);
1414  std::set<PlacementInfo::PlacementUnit *> PUsTouched;
1415  std::set<PlacementInfo::PlacementUnit *> PUsDontTouch;
1416  PUsTouched.clear();
1417  PUsDontTouch.clear();
1418  for (auto oriCellIdsInCriticalPath : oriCellIdsInCriticalPaths)
1419  {
1420  for (int orderI = oriCellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
1421  {
1422  auto cellId = oriCellIdsInCriticalPath[orderI];
1423  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1424  PUsDontTouch.insert(curPU);
1425  }
1426  }
1427 
1428  int replaceCnt = 0;
1429  for (auto oriCellIdsInCriticalPath : oriCellIdsInCriticalPaths)
1430  {
1431  std::map<int, std::vector<PackingCLBSite *>> cellId2CandidateSites;
1432  std::set<PackingCLBSite *> sitesCandidates;
1433  std::map<PackingCLBSite *, PackingCLBSite::PackingCLBCluster *> site2TrialCluster;
1434  cellId2CandidateSites.clear();
1435 
1436  std::vector<int> cellIdsInCriticalPath;
1437  PlacementInfo::PlacementUnit *lastPU = nullptr;
1438  std::set<PlacementInfo::PlacementUnit *> PUsInCriticalPathSet;
1439  for (auto cellId : oriCellIdsInCriticalPath)
1440  {
1441  if (PUsInCriticalPathSet.find(placementInfo->getPlacementUnitByCellId(cellId)) ==
1442  PUsInCriticalPathSet.end())
1443  {
1444  PUsInCriticalPathSet.insert(placementInfo->getPlacementUnitByCellId(cellId));
1445  cellIdsInCriticalPath.push_back(cellId);
1446  }
1447  }
1448 
1449  bool CellUnmapped = false;
1450  for (auto cellId : cellIdsInCriticalPath)
1451  {
1452  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1453  auto curPackingSite = cellId2PackingSite[cellId];
1454  if (!curPackingSite)
1455  {
1456  CellUnmapped = true;
1457  break;
1458  }
1459  assert(curPackingSite);
1460  }
1461  if (CellUnmapped)
1462  continue;
1463 
1464  // std::cout << "processing endpoint [" << designInfo->getCells()[cellIdsInCriticalPath[0]] << "] with "
1465  // << cellIdsInCriticalPath.size() << " nodes in path.\n";
1466 
1467  // find candidate sites for each possible PU
1468  for (int orderI = 1; orderI <= cellIdsInCriticalPath.size() - 2; orderI++)
1469  {
1470  auto cellId = cellIdsInCriticalPath[orderI];
1471  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1472  auto curCell = designInfo->getCells()[cellId];
1473  // std::cout << "------ " << curPU << " \n"
1474  // << " cell: " << curCell << "\n";
1475  if (curPU->getType() == PlacementInfo::PlacementUnitType_Macro)
1476  continue;
1477  if (PUsTouched.find(curPU) != PUsTouched.end())
1478  {
1479  // std::cout << "bypassing touched\n";
1480  continue;
1481  }
1482  if (curCell->isLUT())
1483  {
1484  float v1x = 0, v1y = 0, v2x = 0, v2y = 0;
1485 
1486  auto predSite = cellId2PackingSite[cellIdsInCriticalPath[orderI - 1]];
1487  int predSiteOrderId = orderI - 1;
1488  auto curSite = cellId2PackingSite[cellId];
1489  auto succSite = cellId2PackingSite[cellIdsInCriticalPath[orderI + 1]];
1490  int succSiteOrderId = orderI + 1;
1491  assert(predSite && curSite && succSite);
1492 
1493  float oriDelay =
1494  timingOptimizer->getDelayByModel(curSite->getCLBSite()->X(), curSite->getCLBSite()->Y(),
1495  predSite->getCLBSite()->X(), predSite->getCLBSite()->Y()) +
1496  timingOptimizer->getDelayByModel(curSite->getCLBSite()->X(), curSite->getCLBSite()->Y(),
1497  succSite->getCLBSite()->X(), succSite->getCLBSite()->Y());
1498 
1499  if (oriDelay < 0.3)
1500  continue;
1501 
1502  v1x = predSite->getCLBSite()->X() - curSite->getCLBSite()->X();
1503  v1y = predSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
1504  v2x = succSite->getCLBSite()->X() - curSite->getCLBSite()->X();
1505  v2y = succSite->getCLBSite()->Y() - curSite->getCLBSite()->Y();
1506 
1507  // std::cout << curCell << " oriDelay=" << oriDelay << " has following candidates: \n";
1508 
1509  if (std::fabs(v1x) + std::fabs(v1y) < 0.1 || std::fabs(v2x) + std::fabs(v2y) < 0.1)
1510  continue;
1511 
1512  assert(PUId2PackingCLBSite[curPU->getId()]);
1513  auto candidateSitesToPlaceTheCell_cone = findNeiborSitesFromBinGrid(
1514  DesignInfo::CellType_LUT4, PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X(),
1515  PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y(), 0, 1.1, y2xRatio, false);
1516  PackingCLBSite *bestCandidatePackingSite = nullptr;
1517  PlacementInfo::PlacementUnit *bestSwapCandidatePU = nullptr;
1518  float bestOverheadSlack = -1000000;
1519  float oriOverhead = timingOptimizer->getWorstSlackOfCell(curCell);
1520  // std::cout << curCell << " oriOverhead=" << oriOverhead << " has following candidates: \n";
1521  for (auto curDeviceSite : *candidateSitesToPlaceTheCell_cone)
1522  {
1523  if (deviceSite2PackingSite.find(curDeviceSite) == deviceSite2PackingSite.end())
1524  continue;
1525  PackingCLBSite *candidatePackingSite = deviceSite2PackingSite[curDeviceSite];
1526  if (curSite == candidatePackingSite)
1527  continue;
1528 
1529  if (!candidatePackingSite->getDeterminedClusterInSite())
1530  {
1531  continue;
1532  }
1533 
1534  float newDelay =
1535  timingOptimizer->getDelayByModel(candidatePackingSite->getCLBSite()->X(),
1536  candidatePackingSite->getCLBSite()->Y(),
1537  predSite->getCLBSite()->X(), predSite->getCLBSite()->Y()) +
1538  timingOptimizer->getDelayByModel(candidatePackingSite->getCLBSite()->X(),
1539  candidatePackingSite->getCLBSite()->Y(),
1540  succSite->getCLBSite()->X(), succSite->getCLBSite()->Y());
1541 
1542  // std::cout << " " << candidatePackingSite->getCLBSite()->getName() << " newDelay=" <<
1543  // newDelay
1544  // << "\n";
1545  if (newDelay > oriDelay - 0.05)
1546  continue;
1547 
1548  // find lowest slack LUT
1549  for (auto tmpPU : candidatePackingSite->getDeterminedClusterInSite()->getPUs())
1550  {
1551  if (tmpPU->isLocked() || PUsDontTouch.find(tmpPU) != PUsDontTouch.end())
1552  continue;
1553  if (auto unpackedCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(tmpPU))
1554  {
1555  auto targetCell = unpackedCell->getCell();
1556 
1557  // try to swap LUTs
1558  if (targetCell->isLUT())
1559  {
1560  auto trialTargetCluster = new PackingCLBSite::PackingCLBCluster(
1561  candidatePackingSite->getDeterminedClusterInSite());
1562  trialTargetCluster->removePUToConstructDetCluster(tmpPU);
1563  if (trialTargetCluster->addPU(curPU))
1564  {
1565  auto trialCurrentCluster = new PackingCLBSite::PackingCLBCluster(
1566  PUId2PackingCLBSite[curPU->getId()]->getDeterminedClusterInSite());
1567  trialCurrentCluster->removePUToConstructDetCluster(curPU);
1568  if (trialCurrentCluster->addPU(tmpPU))
1569  {
1570  // std::cout << " " << tmpPU
1571  // << " worstSlack=" <<
1572  // timingOptimizer->getWorstSlackOfCell(targetCell)
1573  // << "\n";
1574  float overhead = timingOptimizer->getWorstSlackOfCell(targetCell);
1575  if (overhead > oriOverhead + 0.2)
1576  {
1577  if (overhead > bestOverheadSlack)
1578  {
1579  bestOverheadSlack = overhead;
1580  bestCandidatePackingSite = candidatePackingSite;
1581  bestSwapCandidatePU = tmpPU;
1582  }
1583  }
1584  }
1585  delete trialCurrentCluster;
1586  }
1587  delete trialTargetCluster;
1588  }
1589  }
1590  }
1591  }
1592 
1593  if (bestCandidatePackingSite)
1594  {
1595  auto trialTargetCluster = bestCandidatePackingSite->getDeterminedClusterInSite();
1596  trialTargetCluster->removePUToConstructDetCluster(bestSwapCandidatePU);
1597  assert(trialTargetCluster->addPU(curPU));
1598  auto trialCurrentCluster = PUId2PackingCLBSite[curPU->getId()]->getDeterminedClusterInSite();
1599  trialCurrentCluster->removePUToConstructDetCluster(curPU);
1600  assert(trialCurrentCluster->addPU(bestSwapCandidatePU));
1601  auto unpackedCell_curPU = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(curPU);
1602  auto unpackedCell_bestSwapCandidatePU =
1603  dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(bestSwapCandidatePU);
1604  cellId2PackingSite[unpackedCell_curPU->getCell()->getCellId()] = bestCandidatePackingSite;
1605  cellId2PackingSite[unpackedCell_bestSwapCandidatePU->getCell()->getCellId()] =
1606  PUId2PackingCLBSite[curPU->getId()];
1607 
1608  auto tmpSwapPackingSite = PUId2PackingCLBSite[bestSwapCandidatePU->getId()];
1609  PUId2PackingCLBSite[bestSwapCandidatePU->getId()] = PUId2PackingCLBSite[curPU->getId()];
1610  PUId2PackingCLBSite[curPU->getId()] = tmpSwapPackingSite;
1611  replaceCnt++;
1612  }
1613  delete candidateSitesToPlaceTheCell_cone;
1614  }
1615  }
1616 
1617  for (int i = 0; i < cellIdsInCriticalPath.size() - 1; i++)
1618  {
1619  auto curCellId = cellIdsInCriticalPath[i];
1620  auto curPU = placementInfo->getPlacementUnitByCellId(curCellId);
1621  auto nextCellId = cellIdsInCriticalPath[i + 1];
1622  auto nextPU = placementInfo->getPlacementUnitByCellId(nextCellId);
1623  if (curPU->checkHasCARRY() || curPU->checkHasLUTRAM() || curPU->checkHasBRAM() || curPU->checkHasDSP() ||
1624  nextPU->checkHasCARRY() || nextPU->checkHasLUTRAM() || nextPU->checkHasBRAM() ||
1625  nextPU->checkHasDSP() || PUsTouched.find(curPU) != PUsTouched.end() ||
1626  PUsTouched.find(nextPU) != PUsTouched.end() || curPU == nextPU || curPU->isLocked() ||
1627  nextPU->isLocked())
1628  {
1629  continue;
1630  }
1631  if (PUId2PackingCLBSite[curPU->getId()] == PUId2PackingCLBSite[nextPU->getId()])
1632  continue;
1633 
1634  float oriDis = 0;
1635  float newDis = 0;
1636  auto curPackingSite = PUId2PackingCLBSite[curPU->getId()];
1637  auto nextPackingSite = PUId2PackingCLBSite[nextPU->getId()];
1638  float curX = PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->X();
1639  float curY = PUId2PackingCLBSite[curPU->getId()]->getCLBSite()->Y();
1640  float nextX = PUId2PackingCLBSite[nextPU->getId()]->getCLBSite()->X();
1641  float nextY = PUId2PackingCLBSite[nextPU->getId()]->getCLBSite()->Y();
1642 
1643  if (timingOptimizer->getDelayByModel(nextX, nextY, curX, curY) > 0.5)
1644  continue;
1645 
1646  if (i > 0)
1647  {
1648  auto prevCellId = cellIdsInCriticalPath[i - 1];
1649  assert(cellId2PackingSite[prevCellId]);
1650  float headX = cellId2PackingSite[prevCellId]->getCLBSite()->X();
1651  float headY = cellId2PackingSite[prevCellId]->getCLBSite()->Y();
1652  oriDis += timingOptimizer->getDelayByModel(headX, headY, curX, curY);
1653  newDis += timingOptimizer->getDelayByModel(headX, headY, nextX, nextY);
1654  }
1655 
1656  if (i < cellIdsInCriticalPath.size() - 1)
1657  {
1658  auto succCellId = cellIdsInCriticalPath[i + 1];
1659  assert(cellId2PackingSite[succCellId]);
1660  float tailX = cellId2PackingSite[succCellId]->getCLBSite()->X();
1661  float tailY = cellId2PackingSite[succCellId]->getCLBSite()->Y();
1662  newDis += timingOptimizer->getDelayByModel(tailX, tailY, curX, curY);
1663  oriDis += timingOptimizer->getDelayByModel(tailX, tailY, nextX, nextY);
1664  }
1665 
1666  if (newDis < oriDis)
1667  {
1668  auto trialClusterWithCurPU =
1669  new PackingCLBSite::PackingCLBCluster(curPackingSite->getDeterminedClusterInSite());
1670  auto trialClusterWithNextPU =
1671  new PackingCLBSite::PackingCLBCluster(nextPackingSite->getDeterminedClusterInSite());
1672  assert(trialClusterWithCurPU->contains(curPU));
1673  trialClusterWithCurPU->removePUToConstructDetCluster(curPU);
1674 
1675  assert(trialClusterWithNextPU->contains(nextPU));
1676  trialClusterWithNextPU->removePUToConstructDetCluster(nextPU);
1677  if (trialClusterWithCurPU->addPU(nextPU))
1678  {
1679  if (trialClusterWithNextPU->addPU(curPU))
1680  {
1681  curPackingSite->getDeterminedClusterInSite()->removePUToConstructDetCluster(curPU);
1682  assert(curPackingSite->getDeterminedClusterInSite()->addPU(nextPU));
1683  nextPackingSite->getDeterminedClusterInSite()->removePUToConstructDetCluster(nextPU);
1684  assert(nextPackingSite->getDeterminedClusterInSite()->addPU(curPU));
1685 
1686  PUId2PackingCLBSite[curPU->getId()] = nextPackingSite;
1687  placementInfo->addPUIntoClockColumn(curPU, nextPackingSite->getCLBSite());
1688  auto cellSet = nextPackingSite->getDeterminedClusterInSite()->getCellSet();
1689  for (auto cell : cellSet)
1690  {
1691  cellId2PackingSite[cell->getCellId()] = nextPackingSite;
1692  }
1693 
1694  PUId2PackingCLBSite[nextPU->getId()] = curPackingSite;
1695  placementInfo->addPUIntoClockColumn(nextPU, curPackingSite->getCLBSite());
1696  cellSet = curPackingSite->getDeterminedClusterInSite()->getCellSet();
1697  for (auto cell : cellSet)
1698  {
1699  cellId2PackingSite[cell->getCellId()] = curPackingSite;
1700  }
1701  }
1702  }
1703 
1704  delete trialClusterWithCurPU;
1705  delete trialClusterWithNextPU;
1706  }
1707  }
1708 
1709  for (int orderI = cellIdsInCriticalPath.size() - 1; orderI >= 0; orderI--)
1710  {
1711  auto cellId = cellIdsInCriticalPath[orderI];
1712  auto curPU = placementInfo->getPlacementUnitByCellId(cellId);
1713  PUsTouched.insert(curPU);
1714  }
1715  }
1716 
1717  print_status("ParallelCLBPacker: conducted timing-driven detailed placement (swaping) and " +
1718  std::to_string(replaceCnt) + " PlacementUnits are replaced.");
1719  return replaceCnt;
1720 }
1721 
1722 void ParallelCLBPacker::checkPackedPUsAndUnpackedPUs()
1723 {
1724  packedPUs.clear();
1725  for (auto packingSite : packingSites)
1726  {
1727  if (packingSite)
1728  {
1729  if (packingSite->getDeterminedClusterInSite())
1730  {
1731  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
1732  {
1733  assert(packedPUs.find(tmpPU) == packedPUs.end());
1734  packedPUs.insert(tmpPU);
1735  }
1736  }
1737  }
1738  }
1739 
1740  unpackedPUs.clear();
1741  unpackedPUsVec.clear();
1742  for (auto tmpCell : placementInfo->getCells())
1743  {
1744  if (tmpCell->isLUT() || tmpCell->isFF())
1745  {
1746  auto tmpPU = placementInfo->getPlacementUnitByCell(tmpCell);
1747  if (packedPUs.find(tmpPU) != packedPUs.end())
1748  continue;
1749  if (auto tmpMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(tmpPU))
1750  {
1751  if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_CARRY ||
1752  tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_MCLB)
1753  {
1754  continue;
1755  }
1756  }
1757  if (unpackedPUs.find(tmpPU) == unpackedPUs.end())
1758  {
1759  unpackedPUs.insert(tmpPU);
1760  unpackedPUsVec.push_back(tmpPU);
1761  }
1762  }
1763  }
1764 }
1765 
1766 void ParallelCLBPacker::exceptionHandling(bool verbose)
1767 {
1768  checkPackedPUsAndUnpackedPUs();
1769  print_status("ParallelCLBPacker: start exceptionHandling.");
1770 
1771  std::vector<bool> isLegalizedPU(placementUnits.size(), false);
1772 
1773  float Dc = maxD * 0.5;
1774 
1775  auto inputUnpackedPUsVec = unpackedPUsVec;
1776 
1777  std::set<PlacementInfo::PlacementUnit *, Packing_PUcompare> processedPUs;
1778  processedPUs.clear();
1779 
1780  PUPoints.clear();
1781  for (auto PU : inputUnpackedPUsVec)
1782  {
1783  if (!PU->isLocked())
1784  PUPoints.emplace_back(PU);
1785  }
1786 
1787  while (PUPoints.size())
1788  {
1789  timingOptimizer->getPUId2Slack(true); // update PU slack information
1790  // build k-d tree
1791  kdt::KDTree<PULocation> kdtree(PUPoints, y2xRatio);
1792  processedPUs.clear();
1793  print_status("ParallelCLBPacker: starting parallel ripping up for " + std::to_string(PUPoints.size()) +
1794  " PUs and current displacement threshold for ripping up is " + std::to_string(Dc));
1795  // loop until there is no unprocessed PU
1796  while (processedPUs.size() < PUPoints.size())
1797  {
1798  std::vector<PlacementInfo::PlacementUnit *> noRipUpOverlapPUs;
1799  std::set<PlacementInfo::PlacementUnit *, Packing_PUcompare> coveredPUs;
1800  noRipUpOverlapPUs.clear();
1801  coveredPUs.clear();
1802 
1803  // find unprocessed PUs and try to rip up them with Dc
1804  for (auto &tmpPUPoint : PUPoints)
1805  {
1806  // avoid that the potential ripup site cause conflict so the PUs to be processed should far enough
1807  // between each othters.
1808  if (coveredPUs.find(tmpPUPoint.getPU()) != coveredPUs.end())
1809  continue;
1810  if (processedPUs.find(tmpPUPoint.getPU()) != processedPUs.end())
1811  continue;
1812  if (isLegalizedPU[tmpPUPoint.getPU()->getId()])
1813  continue;
1814  noRipUpOverlapPUs.push_back(tmpPUPoint.getPU());
1815  coveredPUs.insert(tmpPUPoint.getPU());
1816  processedPUs.insert(tmpPUPoint.getPU());
1817  std::vector<int> indices = kdtree.radiusSearch(tmpPUPoint, 4 * Dc + 2);
1818  for (auto tmpInd : indices)
1819  {
1820  assert(std::fabs(PUPoints[tmpInd].getPU()->X() - tmpPUPoint.getPU()->X()) +
1821  y2xRatio * std::fabs(PUPoints[tmpInd].getPU()->Y() - tmpPUPoint.getPU()->Y()) <=
1822  4 * Dc + 2);
1823  coveredPUs.insert(PUPoints[tmpInd].getPU());
1824  }
1825  }
1826 
1827  // print_status("ParallelCLBPacker: find " + std::to_string(noRipUpOverlapPUs.size()) +
1828  // " relatively independent PUs from " + std::to_string(PUPoints.size()) + " PUs. Total " +
1829  // std::to_string(processedPUs.size()) + " have been tried.");
1830 
1831  unsigned int numNoRipUpOverlapPUs = noRipUpOverlapPUs.size();
1832  // involvedPackingSite2PU.clear();
1833 
1834 #pragma omp parallel for schedule(dynamic)
1835  for (unsigned int i = 0; i < numNoRipUpOverlapPUs; i++)
1836  {
1837  isLegalizedPU[noRipUpOverlapPUs[i]->getId()] = exceptionPULegalize(noRipUpOverlapPUs[i], Dc, verbose);
1838  }
1839 
1840  int successCnt = 0;
1841  for (unsigned int i = 0; i < numNoRipUpOverlapPUs; i++)
1842  {
1843  successCnt += isLegalizedPU[noRipUpOverlapPUs[i]->getId()];
1844  }
1845  // print_status("ParallelCLBPacker: successfully rip up " + std::to_string(successCnt) + " PUs of the " +
1846  // std::to_string(noRipUpOverlapPUs.size()) + " PUs.");
1847  }
1848  // remove those successfully ripup PU from PUPoints
1849  int unprocessedCnt = 0;
1850  for (unsigned int i = 0; i < PUPoints.size(); i++)
1851  {
1852  if (!isLegalizedPU[PUPoints[i].getPU()->getId()])
1853  {
1854  PUPoints[unprocessedCnt] = PUPoints[i];
1855  unprocessedCnt++;
1856  }
1857  }
1858  PUPoints.resize(unprocessedCnt);
1859  Dc += 0.3 * maxD;
1860 
1861  if (placementInfo->isDensePlacement())
1862  clockRegionAware = false;
1863 
1864  if (Dc > 300)
1865  {
1866  Dc = maxD * 0.5 - 1;
1867  for (unsigned int i = 0; i < PUPoints.size(); i++)
1868  {
1869  std::cout << PUPoints[i].getPU() << "\n=================================================\n";
1870  }
1871  assert("fail to handle exceptions" && false);
1872  break;
1873  }
1874  if (Dc < 1)
1875  Dc = 1;
1876  print_status("ParallelCLBPacker: there are " + std::to_string(unprocessedCnt) +
1877  " PUs left to be legalized and current displacement threshold for ripping up is " +
1878  std::to_string(Dc));
1879  int tmpFFCnt = 0, tmpLUTCnt = 0;
1880  float avgFFWeight = 0, avgLUTWeight = 0;
1881  for (unsigned int i = 0; i < PUPoints.size(); i++)
1882  {
1883  auto tmpPU = PUPoints[i].getPU();
1884  if (auto unpackCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(tmpPU))
1885  {
1886  if (unpackCell->getCell()->isFF())
1887  {
1888  tmpFFCnt++;
1889  avgFFWeight += placementInfo->getActualOccupation(unpackCell->getCell());
1890  }
1891  else if (unpackCell->getCell()->isLUT())
1892  {
1893  tmpLUTCnt++;
1894  avgLUTWeight += placementInfo->getActualOccupation(unpackCell->getCell());
1895  }
1896  }
1897  else if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(tmpPU))
1898  {
1899  assert(curMacro->getMacroType() != PlacementInfo::PlacementMacro::PlacementMacroType_CARRY &&
1900  curMacro->getMacroType() != PlacementInfo::PlacementMacro::PlacementMacroType_MCLB);
1901  assert(!curMacro->isPacked());
1902  for (auto tmpCell : curMacro->getCells())
1903  {
1904  if (tmpCell->isFF())
1905  {
1906  tmpFFCnt++;
1907  avgFFWeight += placementInfo->getActualOccupation(tmpCell);
1908  }
1909  else if (tmpCell->isLUT())
1910  {
1911  tmpLUTCnt++;
1912  avgLUTWeight += placementInfo->getActualOccupation(tmpCell);
1913  }
1914  }
1915  }
1916  }
1917  avgFFWeight /= tmpFFCnt;
1918  avgLUTWeight /= tmpLUTCnt;
1919  print_info("there are " + std::to_string(tmpFFCnt) + " FFs(avgW=" + std::to_string(avgFFWeight) + ") and " +
1920  std::to_string(tmpLUTCnt) + " LUTs(avgW=" + std::to_string(avgLUTWeight) + ") ");
1921  placementInfo->updateElementBinGrid();
1922  timingOptimizer->conductStaticTimingAnalysis();
1923  }
1924 
1925  if (verbose)
1926  {
1927  print_status("ParallelCLBPacker::exceptionHandling done!");
1928  }
1929 }
1930 
1931 bool ParallelCLBPacker::exceptionPULegalize(PlacementInfo::PlacementUnit *curPU, float displacementThreshold,
1932  bool verbose)
1933 {
1934 
1935  std::vector<DeviceInfo::DeviceSite *> *candidateSitesToPlaceThePU = nullptr;
1936  if (displacementThreshold < 4)
1937  candidateSitesToPlaceThePU = findNeiborSitesFromBinGrid(DesignInfo::CellType_LUT4, curPU->X(), curPU->Y(), 0,
1938  displacementThreshold, y2xRatio, clockRegionAware);
1939  else
1940  candidateSitesToPlaceThePU =
1941  findNeiborSitesFromBinGrid(DesignInfo::CellType_LUT4, curPU->X(), curPU->Y(), displacementThreshold - 3,
1942  displacementThreshold, y2xRatio, clockRegionAware);
1943  std::vector<siteWithScore> sitesToRipUp;
1944  sitesToRipUp.clear();
1945  for (auto tmpSite : *candidateSitesToPlaceThePU)
1946  {
1947  float lambda1 = 0.02;
1948  float lambda2 = 1.0;
1949  float lambda3 = 4.0;
1950  assert(deviceSite2PackingSite.find(tmpSite) != deviceSite2PackingSite.end());
1951  PackingCLBSite *packingSite = deviceSite2PackingSite[tmpSite];
1952 
1953  // if (involvedPackingSite2PU.find(packingSite) != involvedPackingSite2PU.end())
1954  // {
1955  // if (involvedPackingSite2PU[packingSite] != curPU)
1956  // {
1957  // std::cout << "displacementThr: " << displacementThreshold << "\n";
1958  // std::cout << "curPU: " << curPU << "\n";
1959  // std::cout << "prevPU: " << involvedPackingSite2PU[packingSite] << "\n";
1960  // std::cout << " packingSite: " << packingSite->getCLBSite()->getName()
1961  // << " X:" << packingSite->getCLBSite()->X() << " Y:" << packingSite->getCLBSite()->Y() <<
1962  // "\n";
1963  // assert(false);
1964  // }
1965  // }
1966 
1967  // involvedPackingSite2PU[packingSite] = curPU;
1968 
1969  float changeHPWL = 0;
1970  for (auto tmpNet : *(curPU->getNetsSetPtr()))
1971  {
1972  if (tmpNet->getUnits().size() > 64) // ignore large net
1973  continue;
1974  changeHPWL += tmpNet->getNewHPWLByTrying(curPU, tmpSite->X(), tmpSite->Y(), y2xRatio);
1975  changeHPWL -= tmpNet->getHPWL(y2xRatio);
1976  assert(!std::isnan(changeHPWL));
1977  }
1978 
1979  float packedScore = 0;
1980  float score = -lambda1 * changeHPWL;
1981  // std::cout << "site: " << packingSite->getCLBSite()->getName() << " changeHPWL:" << changeHPWL << "\n";
1982  if (packingSite->getDeterminedClusterInSite())
1983  {
1984  packingSite->getDeterminedClusterInSite()->updateScoreInSite();
1985  packedScore = packingSite->getDeterminedClusterInSite()->getScoreInSite();
1986  score += -lambda2 * packedScore - lambda3 * packingSite->getDeterminedClusterInSite()->getTotalCellWeight();
1987  // std::cout << "packedScore: " << packedScore << "\n"
1988  // << " CellWeight:" << packingSite->getDeterminedClusterInSite()->getTotalCellWeight() << "\n"
1989  // << "DeterminedClusterInSite: " << packingSite->getDeterminedClusterInSite() << "\n";
1990  }
1991 
1992  sitesToRipUp.emplace_back(packingSite, score);
1993  }
1994  std::sort(sitesToRipUp.begin(), sitesToRipUp.end(), [](const siteWithScore &a, const siteWithScore &b) -> bool {
1995  return a.score == b.score
1996  ? (a.site->getCLBSite()->getElementIdInParent() > b.site->getCLBSite()->getElementIdInParent())
1997  : (a.score > b.score);
1998  });
1999 
2000  // if (verbose)
2001  // {
2002  // for (auto pair : sitesToRipUp)
2003  // {
2004  // std::cout << "site: " << pair.site->getCLBSite()->getName() << " X:" << pair.site->getCLBSite()->X()
2005  // << " Y:" << pair.site->getCLBSite()->Y() << " score:" << pair.score << "\n";
2006  // }
2007  // std::cout << "\n";
2008  // std::cout.flush();
2009  // }
2010  delete candidateSitesToPlaceThePU;
2011 
2012  // std::cout << "start check sites\n";
2013  std::cout.flush();
2014  for (auto pair : sitesToRipUp)
2015  {
2016 
2017  PackingCLBSite *packingSite = pair.site;
2018  std::map<PackingCLBSite *, PackingCLBSite::PackingCLBCluster *> packingSite2DeterminedCluster;
2019  packingSite2DeterminedCluster.clear(); // record the original determined cluster for rolling back
2020 
2021  // std::cout << "start check sites: ripUpAndLegalizae\n";
2022  if (ripUpAndLegalizae(packingSite, curPU, displacementThreshold, packingSite2DeterminedCluster, verbose))
2023  {
2024  return true;
2025  }
2026  else
2027  {
2028  assert(packingSite->getDeterminedClusterInSite());
2029  for (auto pair : packingSite2DeterminedCluster)
2030  {
2031  if (pair.first->getDeterminedClusterInSite())
2032  delete pair.first->getDeterminedClusterInSite();
2033  pair.first->setDeterminedClusterInSite(pair.second);
2034  }
2035  }
2036  }
2037  return false;
2038  // std::cout << "handled unpacked PU: " << curPU << "\n candidateSites:\n";
2039  // for (auto pair : sitesToRipUp)
2040  // {
2041  // std::cout << "site: " << pair.site->getName() << " X:" << pair.site->X() << " Y:" << pair.site->Y()
2042  // << " score:" << pair.score << "\n";
2043  // }
2044 
2045  // std::cout << "\n";
2046  // std::cout.flush();
2047  // assert(false);
2048 }
2049 
2050 bool ParallelCLBPacker::ripUpAndLegalizae(
2051  PackingCLBSite *curTargetPackingSite, PlacementInfo::PlacementUnit *curPU, float displacementThreshold,
2052  std::map<PackingCLBSite *, PackingCLBSite::PackingCLBCluster *> &packingSite2DeterminedCluster, bool verbose)
2053 {
2054  PackingCLBSite::PackingCLBCluster *backup_determinedCluster = nullptr;
2055 
2056  if (curTargetPackingSite->getDeterminedClusterInSite())
2057  {
2058 
2059  backup_determinedCluster =
2060  new PackingCLBSite::PackingCLBCluster(curTargetPackingSite->getDeterminedClusterInSite());
2061 
2062  // if (verbose)
2063  // {
2064  // std::cout << "ripUpAndLegalizae target site: " << curTargetPackingSite->getCLBSite()->getName()
2065  // << " X:" << curTargetPackingSite->getCLBSite()->X()
2066  // << " Y:" << curTargetPackingSite->getCLBSite()->Y() << "\n";
2067  // std::cout << "and its determined cluster is :\n" << backup_determinedCluster << "\n";
2068  // std::cout.flush();
2069  // }
2070  delete curTargetPackingSite->getDeterminedClusterInSite();
2071  }
2072 
2073  packingSite2DeterminedCluster[curTargetPackingSite] = backup_determinedCluster;
2074  curTargetPackingSite->setDeterminedClusterInSite(nullptr);
2075 
2076  if (curTargetPackingSite->checkIsCarrySite())
2077  {
2078  curTargetPackingSite->addCarry();
2079  }
2080  else if (curTargetPackingSite->checkIsLUTRAMSite())
2081  {
2082  curTargetPackingSite->addLUTRAMMacro();
2083  }
2084  else
2085  {
2086  curTargetPackingSite->setDeterminedClusterInSite(new PackingCLBSite::PackingCLBCluster(curTargetPackingSite));
2087  }
2088 
2089  // if (verbose)
2090  // {
2091  // std::cout << "start ripUpAndLegalizae\n";
2092  // std::cout.flush();
2093  // }
2094 
2095  assert(curTargetPackingSite->getDeterminedClusterInSite());
2096  assert(curTargetPackingSite->getDeterminedClusterInSite()->getPUs().size() == 0);
2097  if (curTargetPackingSite->getDeterminedClusterInSite()->addPU(curPU))
2098  {
2099  // if (verbose)
2100  // {
2101  // std::cout << "successfully curTargetPackingSite->getDeterminedClusterInSite()->addPU(curPU)\n";
2102  // std::cout.flush();
2103  // }
2104 
2105  if (backup_determinedCluster)
2106  {
2107 
2108  std::set<PlacementInfo::PlacementUnit *, Packing_PUcompare> evictedPUs = backup_determinedCluster->getPUs();
2109  std::set<PlacementInfo::PlacementUnit *, Packing_PUcompare> notEvictedPUs;
2110  notEvictedPUs.clear();
2111 
2112  auto &PUId2Slack = timingOptimizer->getPUId2Slack();
2113  std::vector<PUWithScore> PUsWithSlack;
2114  PUsWithSlack.clear();
2115  for (auto evictedPU : evictedPUs)
2116  {
2117  PUsWithSlack.emplace_back(evictedPU, PUId2Slack[evictedPU->getId()]);
2118  }
2119  std::sort(PUsWithSlack.begin(), PUsWithSlack.end(), [](const PUWithScore &a, const PUWithScore &b) -> bool {
2120  return a.score == b.score ? (a.PU->getId() > b.PU->getId()) : (a.score < b.score);
2121  });
2122 
2123  for (auto evictedPU_scorePair : PUsWithSlack)
2124  {
2125  auto evictedPU = evictedPU_scorePair.PU;
2126  assert(curTargetPackingSite->getDeterminedClusterInSite()->getPUs().find(evictedPU) ==
2127  curTargetPackingSite->getDeterminedClusterInSite()->getPUs().end());
2128  // if (verbose)
2129  // {
2130  // std::cout << " curTargetPackingSite->getDeterminedClusterInSite()->tryAddPU(evictedPU)\n";
2131  // std::cout.flush();
2132  // }
2133  assert(notEvictedPUs.find(evictedPU) == notEvictedPUs.end());
2134  if (curTargetPackingSite->getDeterminedClusterInSite()->tryAddPU(evictedPU))
2135  {
2136  // if (verbose)
2137  // {
2138  // std::cout << " before
2139  // curTargetPackingSite->getDeterminedClusterInSite()->addPU(evictedPU)\n"; std::cout.flush();
2140  // }
2141  // if (!curTargetPackingSite->getDeterminedClusterInSite()->addPU(evictedPU))
2142  // {
2143  // std::cout << "cluster:\n" << curTargetPackingSite->getDeterminedClusterInSite() << "\n";
2144  // curTargetPackingSite->getDeterminedClusterInSite()->addPUFailReason(evictedPU);
2145  // assert(false);
2146  // }
2147  curTargetPackingSite->getDeterminedClusterInSite()->incrementalUpdateScoreInSite(evictedPU);
2148  curTargetPackingSite->getDeterminedClusterInSite()->getHash();
2149  notEvictedPUs.insert(evictedPU);
2150 
2151  // if (verbose)
2152  // {
2153  // std::cout
2154  // << " successfully
2155  // curTargetPackingSite->getDeterminedClusterInSite()->addPU(evictedPU)\n";
2156  // std::cout.flush();
2157  // }
2158  }
2159  }
2160 
2161  for (auto evictedPU : evictedPUs)
2162  {
2163  if (notEvictedPUs.find(evictedPU) != notEvictedPUs.end())
2164  continue;
2165  // std::cout << "rip up the evicted PU\n";
2166  std::vector<DeviceInfo::DeviceSite *> *candidateSitesToPlaceThePU = nullptr;
2167  if (displacementThreshold < 4)
2168  candidateSitesToPlaceThePU = findNeiborSitesFromBinGrid(
2169  DesignInfo::CellType_LUT4, curTargetPackingSite->getCLBSite()->X(),
2170  curTargetPackingSite->getCLBSite()->Y(), 0, displacementThreshold, y2xRatio, clockRegionAware);
2171  else
2172  candidateSitesToPlaceThePU =
2173  findNeiborSitesFromBinGrid(DesignInfo::CellType_LUT4, curTargetPackingSite->getCLBSite()->X(),
2174  curTargetPackingSite->getCLBSite()->Y(), displacementThreshold - 3,
2175  displacementThreshold, y2xRatio, clockRegionAware);
2176 
2177  float highestScoreIncrease = -1e5;
2178  PackingCLBSite::PackingCLBCluster *bestClusterToPack = nullptr;
2179  for (auto tmpSite : *candidateSitesToPlaceThePU)
2180  {
2181  assert(deviceSite2PackingSite.find(tmpSite) != deviceSite2PackingSite.end());
2182  PackingCLBSite *tmpPackingSiteForEvictim = deviceSite2PackingSite[tmpSite];
2183 
2184  // if (involvedPackingSite2PU.find(tmpPackingSiteForEvictim) != involvedPackingSite2PU.end())
2185  // {
2186  // if (involvedPackingSite2PU[tmpPackingSiteForEvictim] != curPU)
2187  // {
2188  // std::cout << "displacementThr: " << displacementThreshold << "\n";
2189  // std::cout << "curPU: " << curPU << "\n";
2190  // std::cout << "prevPU: " << involvedPackingSite2PU[tmpPackingSiteForEvictim] << "\n";
2191  // std::cout << " tmpPackingSiteForEvictim: "
2192  // << tmpPackingSiteForEvictim->getCLBSite()->getName()
2193  // << " X:" << tmpPackingSiteForEvictim->getCLBSite()->X()
2194  // << " Y:" << tmpPackingSiteForEvictim->getCLBSite()->Y() << "\n";
2195  // assert(false);
2196  // }
2197  // }
2198  // involvedPackingSite2PU[tmpPackingSiteForEvictim] = curPU;
2199 
2200  PackingCLBSite::PackingCLBCluster *tmpCluster = nullptr;
2201  if (tmpPackingSiteForEvictim->getDeterminedClusterInSite())
2202  {
2203  tmpCluster = new PackingCLBSite::PackingCLBCluster(
2204  tmpPackingSiteForEvictim->getDeterminedClusterInSite());
2205  }
2206  else
2207  {
2208  tmpCluster = new PackingCLBSite::PackingCLBCluster(tmpPackingSiteForEvictim);
2209  }
2210 
2211  tmpCluster->updateScoreInSite();
2212  float oriScore = tmpCluster->getScoreInSite();
2213  // std::cout << "adding into tmpCluster \n";
2214  if (tmpCluster->addPU(evictedPU))
2215  {
2216 
2217  tmpCluster->incrementalUpdateScoreInSite(evictedPU);
2218  tmpCluster->getHash();
2219  float newScore = tmpCluster->getScoreInSite();
2220  // std::cout << "successfully and oriScore=" << oriScore << " newScore=" << newScore << "\n";
2221  if (!bestClusterToPack)
2222  {
2223  bestClusterToPack = tmpCluster;
2224  highestScoreIncrease = newScore - oriScore;
2225  // std::cout << "the cluster is better. Update bestClusterToPack\n";
2226  }
2227  else
2228  {
2229  if (highestScoreIncrease < newScore - oriScore)
2230  {
2231  delete bestClusterToPack;
2232  bestClusterToPack = tmpCluster;
2233  highestScoreIncrease = newScore - oriScore;
2234  // std::cout << "the cluster is better. Update bestClusterToPack\n";
2235  }
2236  else
2237  {
2238  delete tmpCluster;
2239  // std::cout << "the cluster is not good enough.\n";
2240  }
2241  }
2242  }
2243  else
2244  {
2245  // std::cout << "failed\n";
2246  delete tmpCluster;
2247  }
2248  }
2249  delete candidateSitesToPlaceThePU;
2250  if (bestClusterToPack)
2251  {
2252  PackingCLBSite *evictPUToPackingSite = bestClusterToPack->getParentPackingCLB();
2253  if (packingSite2DeterminedCluster.find(evictPUToPackingSite) ==
2254  packingSite2DeterminedCluster.end()) // if the determined cluster has no backup yet, backup
2255  // the determined cluster of the site might be changed by multiple PU but we only record the most
2256  // original determined cluster
2257  {
2258  if (evictPUToPackingSite->getDeterminedClusterInSite())
2259  {
2260  auto backUp = new PackingCLBSite::PackingCLBCluster(
2261  evictPUToPackingSite->getDeterminedClusterInSite());
2262  packingSite2DeterminedCluster[evictPUToPackingSite] =
2263  backUp; // back up for later rolling back.
2264  }
2265  else
2266  {
2267  // if the site has no determined cluster, it must be not site for CLB with CARRY
2268  assert(!evictPUToPackingSite->checkIsPrePackedSite());
2269  packingSite2DeterminedCluster[evictPUToPackingSite] =
2270  nullptr; // back up for later rolling back.
2271  }
2272  }
2273  if (evictPUToPackingSite->getDeterminedClusterInSite())
2274  delete evictPUToPackingSite->getDeterminedClusterInSite();
2275  evictPUToPackingSite->setDeterminedClusterInSite(bestClusterToPack);
2276  }
2277  else
2278  {
2279  // std::cout << "failed to ripUpAndLegalizae target site: "
2280  // << curTargetPackingSite->getCLBSite()->getName()
2281  // << " X:" << curTargetPackingSite->getCLBSite()->X()
2282  // << " Y:" << curTargetPackingSite->getCLBSite()->Y() << "because evictedPU: " <<
2283  // evictedPU
2284  // << "\n cannot be added into it\n";
2285  return false;
2286  }
2287  }
2288  }
2289  }
2290  else
2291  {
2292  // std::cout << "failed to ripUpAndLegalizae target site: " << curTargetPackingSite->getCLBSite()->getName()
2293  // << " X:" << curTargetPackingSite->getCLBSite()->X()
2294  // << " Y:" << curTargetPackingSite->getCLBSite()->Y() << "because curPU cannot be added into it\n";
2295  return false;
2296  }
2297  // std::cout << "successfully ripUpAndLegalizae target site: " << curTargetPackingSite->getCLBSite()->getName()
2298  // << " X:" << curTargetPackingSite->getCLBSite()->X() << " Y:" << curTargetPackingSite->getCLBSite()->Y()
2299  // << "\n";
2300  return true;
2301 }
2302 
2303 std::vector<DeviceInfo::DeviceSite *> *
2304 ParallelCLBPacker::findNeiborSitesFromBinGrid(DesignInfo::DesignCellType curCellType, float targetX, float targetY,
2305  float displacementLowerbound, float displacementUpperbound,
2306  float y2xRatio, bool clockRegionAware, float v1x, float v1y, float v2x,
2307  float v2y, int numLimit)
2308 {
2309  assert(displacementLowerbound < displacementUpperbound);
2310  // please note that the input DesignCell is only used to find the corresponding binGrid for site search.
2311  std::vector<DeviceInfo::DeviceSite *> *res = new std::vector<DeviceInfo::DeviceSite *>();
2312  res->clear();
2313 
2314  int binIdX, binIdY;
2315  placementInfo->getGridXY(targetX, targetY, binIdX, binIdY);
2316 
2317  auto sharedTypeIds = placementInfo->getPotentialBELTypeIDs(curCellType);
2318 
2319  int clockRegionX, clockRegionY;
2320  placementInfo->getDeviceInfo()->getClockRegionByLocation(targetX, targetY, clockRegionX, clockRegionY);
2321 
2322  float vxCom, vyCom;
2323  vxCom = v1x + v2x;
2324  vyCom = v1y + v2y;
2325 
2326  for (auto sharedTypeId : sharedTypeIds)
2327  {
2328  std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &curBinGrid =
2329  placementInfo->getBinGrid(sharedTypeId);
2330  assert(binIdY >= 0);
2331  assert((unsigned int)binIdY < curBinGrid.size());
2332  assert(binIdX >= 0);
2333  assert((unsigned int)binIdX < curBinGrid[binIdY].size());
2334 
2335  std::queue<std::pair<int, int>> binXYqueue;
2336  std::set<std::pair<int, int>> reachedBinXYs;
2337  binXYqueue.emplace(binIdX, binIdY);
2338  reachedBinXYs.emplace(binIdX, binIdY);
2339 
2340  while (binXYqueue.size() > 0)
2341  {
2342  std::pair<int, int> curXY = binXYqueue.front();
2343  binXYqueue.pop();
2344  int curbinIdX = curXY.first, curbinIdY = curXY.second;
2345 
2346  PlacementInfo::PlacementBinInfo *curBin = curBinGrid[curbinIdY][curbinIdX];
2347  float bin2TargetXYDistance = curBin->getManhattanDistanceTo(targetX, targetY);
2348  if (bin2TargetXYDistance > displacementUpperbound)
2349  continue;
2350  for (auto tmpSite : curBin->getCorrespondingSites())
2351  {
2352  float vx = tmpSite->X() - targetX;
2353  float vy = tmpSite->Y() - targetY;
2354  float tmpPUDis = fabs(vx) + y2xRatio * fabs(vy);
2355  if (tmpPUDis > displacementLowerbound && tmpPUDis <= displacementUpperbound &&
2356  std::fabs(getAngle(vx, vy, vxCom, vyCom)) < 0.42 * M_PI)
2357  {
2358  int siteClockRegionX, siteClockRegionY;
2359  placementInfo->getDeviceInfo()->getClockRegionByLocation(tmpSite->X(), targetY, siteClockRegionX,
2360  siteClockRegionY);
2361  if (siteClockRegionX != clockRegionX && clockRegionAware)
2362  continue;
2363 
2364  res->push_back(tmpSite);
2365  }
2366  }
2367 
2368  if (res->size() > numLimit)
2369  break;
2370 
2371  for (int nextY = curbinIdY - 1; nextY <= curbinIdY + 1; nextY++)
2372  {
2373  for (int nextX = curbinIdX - 1; nextX <= curbinIdX + 1; nextX++)
2374  {
2375  if (!(nextY >= 0))
2376  continue;
2377  if (!((unsigned int)nextY < curBinGrid.size()))
2378  continue;
2379  if (!(nextX >= 0))
2380  continue;
2381  if (!((unsigned int)nextX < curBinGrid[binIdY].size()))
2382  continue;
2383 
2384  PlacementInfo::PlacementBinInfo *nextBin = curBinGrid[nextY][nextX];
2385  float nextBin2TargetXYDistance = nextBin->getManhattanDistanceTo(targetX, targetY);
2386  if (nextBin2TargetXYDistance > displacementUpperbound)
2387  continue;
2388 
2389  std::pair<int, int> nextXY(nextX, nextY);
2390  if (reachedBinXYs.find(nextXY) != reachedBinXYs.end())
2391  {
2392  continue;
2393  }
2394 
2395  std::vector<float> binXB;
2396  binXB.push_back(nextBin->left());
2397  binXB.push_back(nextBin->right());
2398 
2399  std::vector<float> binYB;
2400  binYB.push_back(nextBin->top());
2401  binYB.push_back(nextBin->bottom());
2402 
2403  bool overlap = false;
2404  for (auto bX : binXB)
2405  {
2406  for (auto bY : binYB)
2407  {
2408  float vx = bX - targetX;
2409  float vy = bY - targetY;
2410  if (std::fabs(getAngle(vx, vy, vxCom, vyCom)) < 0.42 * M_PI)
2411  {
2412  overlap = true;
2413  }
2414  }
2415  }
2416 
2417  if (reachedBinXYs.find(nextXY) == reachedBinXYs.end())
2418  {
2419  reachedBinXYs.insert(nextXY);
2420  if (overlap)
2421  binXYqueue.push(nextXY);
2422  }
2423  }
2424  }
2425  }
2426  }
2427 
2428  return res;
2429 }
2430 
2431 std::vector<DeviceInfo::DeviceSite *> *
2432 ParallelCLBPacker::findNeiborSitesFromBinGrid(DesignInfo::DesignCellType curCellType, float targetX, float targetY,
2433  float displacementLowerbound, float displacementUpperbound,
2434  float y2xRatio, bool clockRegionAware)
2435 {
2436  assert(displacementLowerbound < displacementUpperbound);
2437  // please note that the input DesignCell is only used to find the corresponding binGrid for site search.
2438  std::vector<DeviceInfo::DeviceSite *> *res = new std::vector<DeviceInfo::DeviceSite *>();
2439  res->clear();
2440 
2441  int binIdX, binIdY;
2442  placementInfo->getGridXY(targetX, targetY, binIdX, binIdY);
2443 
2444  auto sharedTypeIds = placementInfo->getPotentialBELTypeIDs(curCellType);
2445 
2446  int clockRegionX, clockRegionY;
2447  placementInfo->getDeviceInfo()->getClockRegionByLocation(targetX, targetY, clockRegionX, clockRegionY);
2448 
2449  for (auto sharedTypeId : sharedTypeIds)
2450  {
2451  std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &curBinGrid =
2452  placementInfo->getBinGrid(sharedTypeId);
2453  assert(binIdY >= 0);
2454  assert((unsigned int)binIdY < curBinGrid.size());
2455  assert(binIdX >= 0);
2456  assert((unsigned int)binIdX < curBinGrid[binIdY].size());
2457 
2458  std::queue<std::pair<int, int>> binXYqueue;
2459  std::set<std::pair<int, int>> reachedBinXYs;
2460  binXYqueue.emplace(binIdX, binIdY);
2461  reachedBinXYs.emplace(binIdX, binIdY);
2462 
2463  while (binXYqueue.size() > 0)
2464  {
2465  std::pair<int, int> curXY = binXYqueue.front();
2466  binXYqueue.pop();
2467  int curbinIdX = curXY.first, curbinIdY = curXY.second;
2468 
2469  PlacementInfo::PlacementBinInfo *curBin = curBinGrid[curbinIdY][curbinIdX];
2470  float bin2TargetXYDistance = curBin->getManhattanDistanceTo(targetX, targetY);
2471  if (bin2TargetXYDistance > displacementUpperbound)
2472  continue;
2473  for (auto tmpSite : curBin->getCorrespondingSites())
2474  {
2475  float tmpPUDis = fabs(targetX - tmpSite->X()) + y2xRatio * fabs(targetY - tmpSite->Y());
2476  if (tmpPUDis > displacementLowerbound && tmpPUDis <= displacementUpperbound)
2477  {
2478  int siteClockRegionX, siteClockRegionY;
2479  placementInfo->getDeviceInfo()->getClockRegionByLocation(tmpSite->X(), targetY, siteClockRegionX,
2480  siteClockRegionY);
2481  if (siteClockRegionX != clockRegionX && clockRegionAware)
2482  continue;
2483 
2484  res->push_back(tmpSite);
2485  }
2486  }
2487 
2488  for (int nextY = curbinIdY - 1; nextY <= curbinIdY + 1; nextY++)
2489  {
2490  for (int nextX = curbinIdX - 1; nextX <= curbinIdX + 1; nextX++)
2491  {
2492  if (!(nextY >= 0))
2493  continue;
2494  if (!((unsigned int)nextY < curBinGrid.size()))
2495  continue;
2496  if (!(nextX >= 0))
2497  continue;
2498  if (!((unsigned int)nextX < curBinGrid[binIdY].size()))
2499  continue;
2500  PlacementInfo::PlacementBinInfo *nextBin = curBinGrid[nextY][nextX];
2501  float nextBin2TargetXYDistance = nextBin->getManhattanDistanceTo(targetX, targetY);
2502  if (nextBin2TargetXYDistance > displacementUpperbound)
2503  continue;
2504  std::pair<int, int> nextXY(nextX, nextY);
2505  if (reachedBinXYs.find(nextXY) == reachedBinXYs.end())
2506  {
2507  reachedBinXYs.insert(nextXY);
2508  binXYqueue.push(nextXY);
2509  }
2510  }
2511  }
2512  }
2513  }
2514 
2515  return res;
2516 }
2517 
2518 void ParallelCLBPacker::setPULocationToPackedSite()
2519 {
2520  for (auto packingSite : packingSites)
2521  {
2522  if (packingSite)
2523  {
2524  if (packingSite->getDeterminedClusterInSite())
2525  {
2526  if (packingSite->getDeterminedClusterInSite()->getPUs().size())
2527  {
2528  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
2529  {
2530  tmpPU->setAnchorLocationAndForgetTheOriginalOne(packingSite->getCLBSite()->X(),
2531  packingSite->getCLBSite()->Y());
2532  tmpPU->setFixed();
2533  }
2534  }
2535  }
2536  }
2537  }
2538  placementInfo->updateElementBinGrid();
2539  placementInfo->updateB2BAndGetTotalHPWL();
2540 }
2541 
2542 void ParallelCLBPacker::setPUsToBePacked()
2543 {
2544  for (auto packingSite : packingSites)
2545  {
2546  if (packingSite)
2547  {
2548  if (packingSite->getDeterminedClusterInSite())
2549  {
2550  if (packingSite->getDeterminedClusterInSite()->getPUs().size())
2551  {
2552  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
2553  {
2554  tmpPU->setPacked();
2555  }
2556  }
2557  }
2558  }
2559  }
2560 }
2561 
2562 void ParallelCLBPacker::updatePackedMacro(bool setPUPseudoNetToCLBSite, bool setCLBFixed)
2563 {
2564  std::vector<PlacementInfo::PlacementUnit *> packedPUs;
2565  std::vector<PlacementInfo::Location> &cellLoc = placementInfo->getCellId2location();
2566  std::map<PlacementInfo::PlacementUnit *, float> PU2X, PU2Y;
2567  std::map<PlacementInfo::PlacementUnit *, std::vector<DeviceInfo::DeviceSite *>> PU2Sites;
2568  PU2Sites.clear();
2569  PU2X.clear();
2570  PU2Y.clear();
2571  for (auto packingSite : packingSites)
2572  {
2573  if (packingSite)
2574  {
2575  if (packingSite->getDeterminedClusterInSite())
2576  {
2577  if (packingSite->getDeterminedClusterInSite()->getPUs().size() >= 1)
2578  {
2579  std::vector<DesignInfo::DesignCellType> cellsToAdd_cellType(0);
2580  std::vector<DesignInfo::DesignCell *> cellsToAdd(0);
2581  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
2582  {
2583  if (auto unpackCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(tmpPU))
2584  {
2585  cellsToAdd.push_back(unpackCell->getCell());
2586  cellsToAdd_cellType.push_back(unpackCell->getCell()->getCellType());
2587  }
2588  else if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(tmpPU))
2589  {
2590  assert(curMacro->getMacroType() !=
2591  PlacementInfo::PlacementMacro::PlacementMacroType_CARRY &&
2592  curMacro->getMacroType() != PlacementInfo::PlacementMacro::PlacementMacroType_MCLB);
2593  assert(!curMacro->isPacked());
2594  int cellIdInMacro = 0;
2595  for (auto tmpCell : curMacro->getCells())
2596  {
2597  cellsToAdd.push_back(tmpCell);
2598  cellsToAdd_cellType.push_back(curMacro->getVirtualCellType(cellIdInMacro));
2599  cellIdInMacro++;
2600  }
2601  }
2602  placementUnits[tmpPU->getId()] = nullptr;
2603  placementInfo->deleteLegalizationInfoFor(tmpPU);
2604  delete tmpPU;
2605  }
2606  assert(cellsToAdd.size() >= 1);
2607  PlacementInfo::PlacementMacro *curMacro = new PlacementInfo::PlacementMacro(
2608  cellsToAdd[0]->getName(), -1, PlacementInfo::PlacementMacro::PlacementMacroType_LCLB);
2609  curMacro->setAnchorLocationAndForgetTheOriginalOne(packingSite->getCLBSite()->X(),
2610  packingSite->getCLBSite()->Y());
2611  int totalWeight = 0;
2612  for (unsigned int tmpId = 0; tmpId < cellsToAdd.size(); tmpId++)
2613  {
2614  curMacro->addCell(cellsToAdd[tmpId], cellsToAdd_cellType[tmpId], 0, 0.0);
2615  cellLoc[cellsToAdd[tmpId]->getCellId()].X = packingSite->getCLBSite()->X();
2616  cellLoc[cellsToAdd[tmpId]->getCellId()].Y = packingSite->getCLBSite()->Y();
2617 
2618  cellId2PlacementUnit[cellsToAdd[tmpId]->getCellId()] = curMacro;
2619  cellInMacros.insert(cellsToAdd[tmpId]);
2620  totalWeight += placementInfo->getCompatiblePlacementTable()
2621  ->cellType2sharedBELTypeOccupation[cellsToAdd_cellType[tmpId]];
2622  }
2623  curMacro->setWeight(totalWeight);
2624  curMacro->setPacked();
2625  if (setCLBFixed)
2626  curMacro->setFixed();
2627  assert((unsigned int)curMacro->getWeight() >= curMacro->getCells().size());
2628  curMacro->addOccupiedSite(0.0, 1);
2629  packedPUs.push_back(curMacro);
2630  placementUnits.push_back(curMacro);
2631  if (setPUPseudoNetToCLBSite)
2632  {
2633  PU2X[curMacro] = packingSite->getCLBSite()->X();
2634  PU2Y[curMacro] = packingSite->getCLBSite()->Y();
2635  PU2Sites[curMacro] = std::vector<DeviceInfo::DeviceSite *>();
2636  PU2Sites[curMacro].push_back(packingSite->getCLBSite());
2637  }
2638 
2639  for (auto LUTPair : packingSite->getDeterminedClusterInSite()->getPairedLUTs())
2640  {
2641  placementInfo->setDeterminedOccupation(LUTPair.first->getCellId(), 1);
2642  placementInfo->setDeterminedOccupation(LUTPair.second->getCellId(), 1);
2643  }
2644 
2645  if (cellsToAdd.size() > 8)
2646  {
2647  for (auto &tmpControlSet : packingSite->getDeterminedClusterInSite()->getFFControlSets())
2648  {
2649  float estimatedFFUtil = 4.0 / (float)tmpControlSet.getSize();
2650 
2651  for (auto tmpFF : tmpControlSet.getFFs())
2652  {
2653  placementInfo->setDeterminedOccupation(tmpFF->getCellId(), estimatedFFUtil);
2654  }
2655  }
2656  }
2657  }
2658  }
2659  }
2660  }
2661  unsigned int validCnt = 0;
2662  placementMacros.clear();
2663  placementUnpackedCells.clear();
2664  for (unsigned int tmpPUId = 0; tmpPUId < placementUnits.size(); tmpPUId++)
2665  {
2666  if (placementUnits[tmpPUId])
2667  {
2668  placementUnits[validCnt] = placementUnits[tmpPUId];
2669  placementUnits[validCnt]->renewId(validCnt);
2670  if (auto unpackCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(placementUnits[validCnt]))
2671  {
2672  placementUnpackedCells.push_back(unpackCell);
2673  }
2674  else if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(placementUnits[validCnt]))
2675  {
2676  placementMacros.push_back(curMacro);
2677  assert((unsigned int)curMacro->getWeight() >= curMacro->getCells().size());
2678  }
2679  validCnt++;
2680  }
2681  }
2682  placementUnits.resize(validCnt);
2683 
2684  print_status("ParallelCLBPacker Updating Cell-PlacementUnit Mapping");
2685  placementInfo->updateCells2PlacementUnits();
2686 
2687  // since new placement units might be generated, we need to update the net information
2688  print_status("ParallelCLBPacker Loading Nets");
2689  placementInfo->reloadNets();
2690 
2691  // ensure that each cell is only assigned into one placementUnit.
2692  std::map<DesignInfo::DesignCell *, PlacementInfo::PlacementUnit *> cell2PUMap;
2693 
2694  cell2PUMap.clear();
2695  for (auto unpackedCell : placementUnpackedCells)
2696  {
2697  DesignInfo::DesignCell *curCell = unpackedCell->getCell();
2698  assert(cell2PUMap.find(curCell) == cell2PUMap.end());
2699  cell2PUMap[curCell] = unpackedCell;
2700  }
2701 
2702  for (auto curMacro : placementMacros)
2703  {
2704  for (auto curCell : curMacro->getCells())
2705  {
2706  if (cell2PUMap.find(curCell) != cell2PUMap.end())
2707  {
2708  std::cout << "recorded PU:" << cell2PUMap[curCell] << "\n";
2709  std::cout << "another PU:" << curMacro << "\n";
2710  std::cout.flush();
2711  }
2712  assert(cell2PUMap.find(curCell) == cell2PUMap.end());
2713  cell2PUMap[curCell] = curMacro;
2714  }
2715  }
2716 
2717  placementInfo->setPULegalSite(PU2Sites);
2718  placementInfo->setPULegalXY(PU2X, PU2Y);
2719  placementInfo->updateB2BAndGetTotalHPWL();
2720 }
2721 
2722 bool hasLUT62(ParallelCLBPacker::PackingCLBSite::SiteBELMapping &slots)
2723 {
2724  for (int i = 0; i < 2; i++)
2725  {
2726  for (int k = 0; k < 4; k++)
2727  {
2728  for (int j = 0; j < 2; j++)
2729  {
2730  if (slots.LUTs[i][j][k])
2731  {
2732  if (slots.LUTs[i][j][k]->isVirtualCell())
2733  continue;
2734  if (slots.LUTs[i][j][k]->getOriCellType() == DesignInfo::CellType_LUT6_2)
2735  return true;
2736  }
2737  }
2738  }
2739  }
2740  return false;
2741 }
2742 
2743 void ParallelCLBPacker::addNonCLBPackingSites()
2744 {
2745  for (auto &DSPBRAM_LegalSitePair : placementInfo->getPULegalSite())
2746  {
2747  if (auto tmpMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(DSPBRAM_LegalSitePair.first))
2748  {
2749  if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_BRAM)
2750  {
2751  assert(tmpMacro->getCells().size() == DSPBRAM_LegalSitePair.second.size());
2752  for (unsigned int i = 0; i < tmpMacro->getCells().size(); i++)
2753  {
2754  auto curCell = tmpMacro->getCells()[i];
2755  auto targetSite = DSPBRAM_LegalSitePair.second[i];
2756  if (!curCell->isVirtualCell())
2757  {
2758  if (curCell->getOriCellType() == DesignInfo::CellType_RAMB36E2 ||
2759  curCell->getOriCellType() == DesignInfo::CellType_FIFO36E2)
2760  {
2761  assert(targetSite->getSiteY() % 2 == 0);
2762  PackingCLBSite *tmpPackingSite = new PackingCLBSite(
2763  placementInfo, targetSite, unchangedIterationThr, numNeighbor, deltaD, curD, maxD,
2764  PQSize, y2xRatio, HPWLWeight, PUId2PackingCLBSite);
2765  tmpPackingSite->setNonCLBCell(curCell);
2766  deviceSite2PackingSite[targetSite] = tmpPackingSite;
2767  packingSites.push_back(tmpPackingSite);
2768  }
2769  else if (curCell->getOriCellType() == DesignInfo::CellType_RAMB18E2 ||
2770  curCell->getOriCellType() == DesignInfo::CellType_FIFO18E2)
2771  {
2772  PackingCLBSite *tmpPackingSite = new PackingCLBSite(
2773  placementInfo, targetSite, unchangedIterationThr, numNeighbor, deltaD, curD, maxD,
2774  PQSize, y2xRatio, HPWLWeight, PUId2PackingCLBSite);
2775  tmpPackingSite->setNonCLBCell(curCell);
2776  deviceSite2PackingSite[targetSite] = tmpPackingSite;
2777  packingSites.push_back(tmpPackingSite);
2778  }
2779  else
2780  {
2781  assert(false && "undefined situtation");
2782  }
2783  }
2784  else
2785  {
2786  assert(targetSite->getSiteY() % 2 == 1);
2787  }
2788  }
2789  }
2790  else if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_DSP)
2791  {
2792  assert(tmpMacro->getCells().size() == DSPBRAM_LegalSitePair.second.size());
2793  for (unsigned int i = 0; i < tmpMacro->getCells().size(); i++)
2794  {
2795  auto curCell = tmpMacro->getCells()[i];
2796  auto targetSite = DSPBRAM_LegalSitePair.second[i];
2797  if (!curCell->isVirtualCell())
2798  {
2799  PackingCLBSite *tmpPackingSite =
2800  new PackingCLBSite(placementInfo, targetSite, unchangedIterationThr, numNeighbor, deltaD,
2801  curD, maxD, PQSize, y2xRatio, HPWLWeight, PUId2PackingCLBSite);
2802  tmpPackingSite->setNonCLBCell(curCell);
2803  deviceSite2PackingSite[targetSite] = tmpPackingSite;
2804  packingSites.push_back(tmpPackingSite);
2805  }
2806  else
2807  {
2808  assert(false && "there should be no virtual DSP");
2809  }
2810  }
2811  }
2812  else
2813  {
2814  // assert(false && "undefined situtation");
2815  }
2816  }
2817  else if (auto tmpUnppackedCell =
2818  dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(DSPBRAM_LegalSitePair.first))
2819  {
2820  assert(1 == DSPBRAM_LegalSitePair.second.size());
2821  auto curCell = tmpUnppackedCell->getCell();
2822  auto targetSite = DSPBRAM_LegalSitePair.second[0];
2823  if (curCell->getOriCellType() == DesignInfo::CellType_RAMB18E2)
2824  {
2825  PackingCLBSite *tmpPackingSite =
2826  new PackingCLBSite(placementInfo, targetSite, unchangedIterationThr, numNeighbor, deltaD, curD,
2827  maxD, PQSize, y2xRatio, HPWLWeight, PUId2PackingCLBSite);
2828  tmpPackingSite->setNonCLBCell(curCell);
2829  deviceSite2PackingSite[targetSite] = tmpPackingSite;
2830  packingSites.push_back(tmpPackingSite);
2831  }
2832  else if (curCell->getOriCellType() == DesignInfo::CellType_DSP48E2)
2833  {
2834  PackingCLBSite *tmpPackingSite =
2835  new PackingCLBSite(placementInfo, targetSite, unchangedIterationThr, numNeighbor, deltaD, curD,
2836  maxD, PQSize, y2xRatio, HPWLWeight, PUId2PackingCLBSite);
2837  tmpPackingSite->setNonCLBCell(curCell);
2838  deviceSite2PackingSite[targetSite] = tmpPackingSite;
2839  packingSites.push_back(tmpPackingSite);
2840  }
2841  else
2842  {
2843  // assert(false && "undefined situtation");
2844  }
2845  }
2846  }
2847 
2848  for (auto unpackedCell : placementInfo->getPlacementUnpackedCells())
2849  {
2850  auto curCell = unpackedCell->getCell();
2851  if (curCell->isIO() && unpackedCell->isLocked())
2852  {
2853  auto lockedSite = unpackedCell->getLockedSite();
2854  assert(lockedSite);
2855  PackingCLBSite *tmpPackingSite =
2856  new PackingCLBSite(placementInfo, lockedSite, unchangedIterationThr, numNeighbor, deltaD, curD, maxD,
2857  PQSize, y2xRatio, HPWLWeight, PUId2PackingCLBSite);
2858  tmpPackingSite->setNonCLBCell(curCell);
2859  deviceSite2PackingSite[lockedSite] = tmpPackingSite;
2860  packingSites.push_back(tmpPackingSite);
2861  }
2862  }
2863 }
2864 
2865 void ParallelCLBPacker::dumpDSPBRAMPlacementTcl(std::ofstream &outfileTcl)
2866 {
2867  for (auto &DSPBRAM_LegalSitePair : placementInfo->getPULegalSite())
2868  {
2869  std::string placementStr = "";
2870  if (auto tmpMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(DSPBRAM_LegalSitePair.first))
2871  {
2872  if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_BRAM)
2873  {
2874  assert(tmpMacro->getCells().size() == DSPBRAM_LegalSitePair.second.size());
2875  for (unsigned int i = 0; i < tmpMacro->getCells().size(); i++)
2876  {
2877  auto curCell = tmpMacro->getCells()[i];
2878  auto targetSite = DSPBRAM_LegalSitePair.second[i];
2879  if (!curCell->isVirtualCell())
2880  {
2881  if (curCell->getOriCellType() == DesignInfo::CellType_RAMB36E2 ||
2882  curCell->getOriCellType() == DesignInfo::CellType_FIFO36E2)
2883  {
2884  assert(targetSite->getSiteY() % 2 == 0);
2885  placementStr += " " + curCell->getName() + " RAMB36_X" +
2886  std::to_string(targetSite->getSiteX()) + "Y" +
2887  std::to_string(targetSite->getSiteY() / 2) + "\n";
2888  }
2889  else if (curCell->getOriCellType() == DesignInfo::CellType_RAMB18E2 ||
2890  curCell->getOriCellType() == DesignInfo::CellType_FIFO18E2)
2891  {
2892  if (targetSite->getSiteY() % 2)
2893  {
2894  placementStr +=
2895  " " + curCell->getName() + " " + targetSite->getName() + "/RAMB18E2_U" + "\n";
2896  }
2897  else
2898  {
2899  placementStr +=
2900  " " + curCell->getName() + " " + targetSite->getName() + "/RAMB18E2_L" + "\n";
2901  }
2902  }
2903  else
2904  {
2905  assert(false && "undefined situtation");
2906  }
2907  }
2908  else
2909  {
2910  assert(targetSite->getSiteY() % 2 == 1);
2911  }
2912  }
2913  }
2914  else if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_DSP)
2915  {
2916  assert(tmpMacro->getCells().size() == DSPBRAM_LegalSitePair.second.size());
2917  for (unsigned int i = 0; i < tmpMacro->getCells().size(); i++)
2918  {
2919  auto curCell = tmpMacro->getCells()[i];
2920  auto targetSite = DSPBRAM_LegalSitePair.second[i];
2921  if (!curCell->isVirtualCell())
2922  {
2923  placementStr += " " + curCell->getName() + " " + targetSite->getName() + "/DSP_ALU" + "\n";
2924  }
2925  else
2926  {
2927  assert(false && "there should be no virtual DSP");
2928  }
2929  }
2930  }
2931  else
2932  {
2933  // assert(false && "undefined situtation");
2934  }
2935  }
2936  else if (auto tmpUnppackedCell =
2937  dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(DSPBRAM_LegalSitePair.first))
2938  {
2939  assert(1 == DSPBRAM_LegalSitePair.second.size());
2940  auto curCell = tmpUnppackedCell->getCell();
2941  auto targetSite = DSPBRAM_LegalSitePair.second[0];
2942  if (curCell->getOriCellType() == DesignInfo::CellType_RAMB18E2)
2943  {
2944  if (targetSite->getSiteY() % 2)
2945  {
2946  placementStr += " " + curCell->getName() + " " + targetSite->getName() + "/RAMB18E2_U" + "\n";
2947  }
2948  else
2949  {
2950  placementStr += " " + curCell->getName() + " " + targetSite->getName() + "/RAMB18E2_L" + "\n";
2951  }
2952  }
2953  else if (curCell->getOriCellType() == DesignInfo::CellType_DSP48E2)
2954  {
2955  placementStr += " " + curCell->getName() + " " + targetSite->getName() + "/DSP_ALU" + "\n";
2956  }
2957  else
2958  {
2959  // assert(false && "undefined situtation");
2960  }
2961  }
2962  if (placementStr != "")
2963  {
2964  std::string oriBrace = "[";
2965  std::string newBrace = "\\[";
2966  outfileTcl << "set result "
2967  << "[catch {place_cell {" << placementStr << "}}]\n"
2968  << "if {$result} {\n incr errorNum \n";
2969  std::vector<std::string> splitItems;
2970  splitItems.clear();
2971  strSplit(placementStr, splitItems, "\n");
2972  for (auto item : splitItems)
2973  {
2974  replaceAll(item, oriBrace, newBrace);
2975  outfileTcl << "puts $fo \"" << item << " \"\n";
2976  }
2977  outfileTcl << "\n}\n";
2978  placementStr = "";
2979  }
2980  }
2981 }
2982 
2983 bool containLUTRAMCells(PlacementInfo::PlacementUnit *curPU)
2984 {
2985  if (auto unpackedCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(curPU))
2986  {
2987  return unpackedCell->getCell()->originallyIsLUTRAM();
2988  }
2989  else if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(curPU))
2990  {
2991  for (auto tmpCell : curMacro->getCells())
2992  {
2993  if (tmpCell->originallyIsLUTRAM())
2994  {
2995  return true;
2996  }
2997  }
2998  return false;
2999  }
3000  return false;
3001 }
3002 
3003 void ParallelCLBPacker::dumpCLBPlacementTcl(std::ofstream &outfileTcl, bool packingRelatedToLUT6_2)
3004 {
3005  std::string placementStr = "";
3006  int cnt = 0;
3007  for (auto tmpPackingSite : packingSites)
3008  {
3009  auto slotMapping = tmpPackingSite->getSlotMapping();
3010  auto CLBSite = tmpPackingSite->getCLBSite();
3011  if ((packingRelatedToLUT6_2 && !hasLUT62(slotMapping)) || (!packingRelatedToLUT6_2 && hasLUT62(slotMapping)))
3012  continue;
3013 
3014  if (tmpPackingSite->getDeterminedClusterInSite())
3015  {
3016 
3017  if (tmpPackingSite->checkIsCarrySite())
3018  {
3019  cnt++;
3020  placementStr += slotMapping.Carry->getName() + " " + CLBSite->getName() + "/CARRY8 \n";
3021  }
3022  else if (tmpPackingSite->checkIsMuxSite())
3023  {
3024  for (int i = 0; i < 2; i++)
3025  {
3026  if (slotMapping.MuxF8[i])
3027  {
3028  if (slotMapping.MuxF8[i]->isVirtualCell())
3029  continue;
3030  assert(slotMapping.MuxF8[i]->getOriCellType() == DesignInfo::CellType_MUXF8);
3031  cnt++;
3032  placementStr += " " + slotMapping.MuxF8[i]->getName() + " " + CLBSite->getName() + "/" +
3033  slotMapping.MuxF8SlotNames[i] + " \n";
3034  }
3035  for (int j = 0; j < 2; j++)
3036  {
3037  if (slotMapping.MuxF7[i][j])
3038  {
3039  if (slotMapping.MuxF7[i][j]->isVirtualCell())
3040  continue;
3041  cnt++;
3042  placementStr += " " + slotMapping.MuxF7[i][j]->getName() + " " + CLBSite->getName() +
3043  "/" + slotMapping.MuxF7SlotNames[i][j] + " \n";
3044  }
3045  }
3046  }
3047  }
3048  else if (tmpPackingSite->checkIsLUTRAMSite())
3049  {
3050  auto tmpMacro = tmpPackingSite->getLUTRAMMacro();
3051  if (containLUTRAMCells(tmpMacro))
3052  {
3053  if (tmpMacro->getFixedCellInfoVec().size() % 2 ==
3054  0) // if the number of fixed cells is odd and >1, there might be weird errors from Vivado.
3055  {
3056  if (tmpMacro->getFixedCellInfoVec().size() > 0)
3057  {
3058  for (unsigned int i = 0; i < tmpMacro->getFixedCellInfoVec().size(); i++)
3059  {
3060  DesignInfo::DesignCell *curCell = tmpMacro->getFixedCellInfoVec()[i].cell;
3061  placementStr += " " + curCell->getName() + " " + CLBSite->getName() + "/" +
3062  tmpMacro->getFixedCellInfoVec()[i].BELName + " \n";
3063  }
3064  }
3065  else
3066  {
3067  placementStr += " " + tmpMacro->getName() + " " + CLBSite->getName() + "/H6LUT \n";
3068  }
3069  }
3070  else
3071  {
3072  if (tmpMacro->getFixedCellInfoVec().size() == 1)
3073  {
3074  placementStr += " " + tmpMacro->getName() + " " + CLBSite->getName() + "/H6LUT \n";
3075  }
3076  }
3077  }
3078  }
3079 
3080  for (int i = 0; i < 2; i++)
3081  {
3082  for (int k = 0; k < 4; k++)
3083  {
3084  for (int j = 0; j < 2; j++)
3085  {
3086  if (slotMapping.LUTs[i][j][k])
3087  {
3088  if (slotMapping.LUTs[i][j][k]->isVirtualCell())
3089  continue;
3090  assert(slotMapping.LUTs[i][j][k]->isLUT());
3091  char LUTCode = (i * 4 + k) + 'A';
3092  if (j == 0)
3093  {
3094  std::string LUTSiteName = std::string(1, LUTCode) + "6LUT";
3095  cnt++;
3096  placementStr += " " + slotMapping.LUTs[i][j][k]->getName() + " " + CLBSite->getName() +
3097  "/" + LUTSiteName + "\n";
3098  }
3099  else
3100  {
3101  if (slotMapping.LUTs[i][j][k]->getOriCellType() == DesignInfo::CellType_LUT6_2)
3102  continue;
3103 
3104  std::string LUTSiteName = std::string(1, LUTCode) + "5LUT";
3105  cnt++;
3106  placementStr += " " + slotMapping.LUTs[i][j][k]->getName() + " " + CLBSite->getName() +
3107  "/" + LUTSiteName + "\n";
3108  }
3109  }
3110  }
3111  }
3112  }
3113  for (int i = 0; i < 2; i++)
3114  {
3115  for (int k = 0; k < 4; k++)
3116  {
3117  for (int j = 0; j < 2; j++)
3118  {
3119  if (slotMapping.FFs[i][j][k])
3120  {
3121  if (slotMapping.FFs[i][j][k]->isVirtualCell())
3122  continue;
3123  assert(slotMapping.FFs[i][j][k]->isFF());
3124  auto PU = placementInfo->getPlacementUnitByCell(slotMapping.FFs[i][j][k]);
3125  if (auto tmpMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(PU))
3126  {
3127  if (tmpMacro->getMacroType() ==
3128  PlacementInfo::PlacementMacro::
3129  PlacementMacroType_LCLB) // currently we failed to predict the LCLB macros, so
3130  // leave it to Vivado placement.
3131  continue;
3132  }
3133  char FFCode = (i * 4 + k) + 'A';
3134  if (j == 0)
3135  {
3136  std::string FFSiteName = std::string(1, FFCode) + "FF";
3137  cnt++;
3138  placementStr += " " + slotMapping.FFs[i][j][k]->getName() + " " + CLBSite->getName() +
3139  "/" + FFSiteName + "\n";
3140  }
3141  else
3142  {
3143  std::string FFSiteName = std::string(1, FFCode) + "FF2";
3144  cnt++;
3145  placementStr += " " + slotMapping.FFs[i][j][k]->getName() + " " + CLBSite->getName() +
3146  "/" + FFSiteName + "\n";
3147  }
3148  }
3149  }
3150  }
3151  }
3152  }
3153  if (cnt > 100)
3154  {
3155  if (placementStr != "")
3156  {
3157  std::string oriBrace = "[";
3158  std::string newBrace = "\\[";
3159  outfileTcl << "set result "
3160  << "[catch {place_cell {" << placementStr << "}}]\n"
3161  << "if {$result} {\n incr errorNum \n";
3162  std::vector<std::string> splitItems;
3163  splitItems.clear();
3164  strSplit(placementStr, splitItems, "\n");
3165  for (auto item : splitItems)
3166  {
3167  replaceAll(item, oriBrace, newBrace);
3168  outfileTcl << "puts $fo \"" << item << " \"\n";
3169  }
3170  outfileTcl << "\n}\n";
3171  placementStr = "";
3172  }
3173  cnt = 0;
3174  }
3175  }
3176  if (placementStr != "")
3177  {
3178  outfileTcl << "set result "
3179  << "[catch {place_cell {" << placementStr << "}}]\n"
3180  << "if {$result} {\n incr errorNum \nputs $fo \"" << placementStr << "\"\n}\n";
3181  }
3182 }
3183 
3184 void ParallelCLBPacker::dumpPlacementTcl(std::string dumpTclFile)
3185 {
3186  std::ofstream outfileTcl(dumpTclFile);
3187  assert(outfileTcl.is_open() && outfileTcl.good() &&
3188  "The path for placement Tcl dumping does not exist and please check your path settings");
3189  outfileTcl << "set script_path [ file dirname [ file normalize [ info script ] ] ]\n";
3190  outfileTcl
3191  << "set fo [open \"${script_path}/initialPlacementError\" \"w\"]\nplace_design -unplace\nset errorNum 0\n";
3192  dumpDSPBRAMPlacementTcl(outfileTcl);
3193  dumpCLBPlacementTcl(outfileTcl, true);
3194  // Except LUT6_2 cells, remove the packing information in Vivado and use our packing
3195  outfileTcl << "set_property HLUTNM {} [get_cells -hierarchical *]\n";
3196  outfileTcl << "set_property SOFT_HLUTNM {} [get_cells -hierarchical *]\n";
3197  dumpCLBPlacementTcl(outfileTcl, false);
3198  // outfileTcl << "place_design\n";
3199  outfileTcl << "$errorNum\n";
3200  outfileTcl << "close $fo \n"
3201  "set a [open \"${script_path}/initialPlacementError\"]\n"
3202  "set lines [split [read $a] \"\\n\"]\n"
3203  "close $a;\n"
3204  "exec rm \"${script_path}/initialPlacementError\"\n"
3205  "set b [open \"${script_path}/placementError\" \"w\"]\n"
3206  "set lineCnt 0\n"
3207  "set placeBatch {}\n"
3208  "foreach line $lines {\n"
3209  " incr lineCnt\n"
3210  " set placeBatch [concat $placeBatch $line]\n"
3211  " if {$lineCnt == 2 } {\n"
3212  " set result [catch {place_cell $placeBatch }]\n"
3213  " if {$result} {\n"
3214  " puts $b $placeBatch\n"
3215  " }\n"
3216  " set lineCnt 0\n"
3217  " set placeBatch \"\"\n"
3218  " }\n"
3219  "}\n"
3220  "close $b\n";
3221  outfileTcl << "place_design\nroute_design\n";
3222  outfileTcl.close();
3223 }
3224 
3225 void ParallelCLBPacker::dumpFinalPacking()
3226 {
3227  if (JSONCfg.find("DumpCLBPacking") != JSONCfg.end())
3228  {
3229  std::string dumpTclFile =
3230  JSONCfg["DumpCLBPacking"] + "-" + packerName + "-" + std::to_string(DumpCLBPackingCnt) + ".tcl";
3231  std::string dumpFile =
3232  JSONCfg["DumpCLBPacking"] + "-" + packerName + "-" + std::to_string(DumpCLBPackingCnt) + ".gz";
3233 
3234  print_status("ParallelCLBPacker: dumping CLBPacking archieve to: " + dumpFile);
3235 
3236  std::stringstream outfile0;
3237 
3238  for (auto tmpPackingSite : packingSites)
3239  {
3240  if (tmpPackingSite->getDeterminedClusterInSite())
3241  {
3242  outfile0 << tmpPackingSite->getDeterminedClusterInSite() << "\n";
3243  if (tmpPackingSite->checkIsCarrySite())
3244  {
3245  outfile0 << "LUTSlots:\n";
3246  for (int i = 0; i < 2; i++)
3247  {
3248  for (int k = 0; k < 4; k++)
3249  {
3250  for (int j = 0; j < 2; j++)
3251  {
3252  if (tmpPackingSite->getSlotMapping().LUTs[i][j][k])
3253  {
3254  outfile0 << "i,j,k:" << i << "," << j << "," << k << " "
3255  << tmpPackingSite->getSlotMapping().LUTs[i][j][k] << "\n";
3256  }
3257  }
3258  }
3259  }
3260  }
3261  if (tmpPackingSite->checkIsCarrySite())
3262  {
3263  outfile0 << "FFSlots:\n";
3264  for (int i = 0; i < 2; i++)
3265  {
3266  for (int k = 0; k < 4; k++)
3267  {
3268  for (int j = 0; j < 2; j++)
3269  {
3270  if (tmpPackingSite->getSlotMapping().FFs[i][j][k])
3271  {
3272  outfile0 << "i,j,k:" << i << "," << j << "," << k << " "
3273  << tmpPackingSite->getSlotMapping().FFs[i][j][k] << "\n";
3274  }
3275  }
3276  }
3277  }
3278  }
3279  }
3280  }
3281 
3282  writeStrToGZip(dumpFile, outfile0);
3283  print_status("ParallelCLBPacker: dumped CLBPacking archieve to: " + dumpFile);
3284 
3285  std::vector<PackingCLBSite *> PUId2PackingCLBSite;
3286  PUId2PackingCLBSite.clear();
3287  PUId2PackingCLBSite.resize(placementInfo->getPlacementUnits().size(), nullptr);
3288 
3289  std::vector<DeviceInfo::DeviceSite *> PUId2NeighborSite(placementInfo->getPlacementUnits().size(), nullptr);
3290  int mappedPUCnt = 0;
3291  for (auto packingSite : packingSites)
3292  {
3293  if (packingSite)
3294  {
3295  if (packingSite->getDeterminedClusterInSite())
3296  {
3297  for (auto tmpPU : packingSite->getDeterminedClusterInSite()->getPUs())
3298  {
3299  assert(!PUId2PackingCLBSite[tmpPU->getId()]);
3300  PUId2PackingCLBSite[tmpPU->getId()] = packingSite;
3301  mappedPUCnt++;
3302  }
3303  }
3304  }
3305  }
3306  for (auto packingSite : packingSites)
3307  {
3308  if (packingSite)
3309  {
3310  for (auto tmpPU : packingSite->getNeighborPUs())
3311  {
3312  if (PUId2PackingCLBSite[tmpPU->getId()])
3313  continue;
3314  if (!PUId2NeighborSite[tmpPU->getId()])
3315  {
3316  PUId2NeighborSite[tmpPU->getId()] = packingSite->getCLBSite();
3317  }
3318  else
3319  {
3320  float oriDis = std::abs(PUId2NeighborSite[tmpPU->getId()]->X() - tmpPU->X()) +
3321  y2xRatio * std::abs(PUId2NeighborSite[tmpPU->getId()]->Y() - tmpPU->Y());
3322  float newDis = std::abs(packingSite->getCLBSite()->X() - tmpPU->X()) +
3323  y2xRatio * std::abs(packingSite->getCLBSite()->Y() - tmpPU->Y());
3324  if (oriDis > newDis)
3325  {
3326  PUId2NeighborSite[tmpPU->getId()] = packingSite->getCLBSite();
3327  }
3328  }
3329  }
3330  }
3331  }
3332 
3333  print_info("#mappedPUCnt = " + std::to_string(mappedPUCnt));
3334 
3335  dumpFile = JSONCfg["DumpCLBPacking"] + "-" + packerName + "-unpackablePUs-" +
3336  std::to_string(DumpCLBPackingCnt) + ".gz";
3337  print_status("ParallelCLBPacker: dumping unpackable PUs archieve to: " + dumpFile);
3338  std::stringstream outfile1;
3339 
3340  int PUNeedMappingCnt = 0;
3341  std::set<PlacementInfo::PlacementUnit *, Packing_PUcompare> dumpedPUs;
3342  dumpedPUs.clear();
3343  for (auto tmpCell : placementInfo->getCells())
3344  {
3345  if (tmpCell->isLUT() || tmpCell->isFF())
3346  {
3347  auto tmpPU = placementInfo->getPlacementUnitByCell(tmpCell);
3348  if (tmpPU->isPacked())
3349  continue;
3350  if (auto tmpMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(tmpPU))
3351  {
3352  if (tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_CARRY ||
3353  tmpMacro->getMacroType() == PlacementInfo::PlacementMacro::PlacementMacroType_MCLB)
3354  {
3355  continue;
3356  }
3357  }
3358  if (dumpedPUs.find(tmpPU) != dumpedPUs.end())
3359  continue;
3360  dumpedPUs.insert(tmpPU);
3361  PUNeedMappingCnt++;
3362  if (PUId2PackingCLBSite[tmpPU->getId()])
3363  continue;
3364  outfile1 << tmpPU;
3365  if (PUId2NeighborSite[tmpPU->getId()])
3366  {
3367  outfile1 << "candidate neighbor site: " << PUId2NeighborSite[tmpPU->getId()]->getName()
3368  << " X:" << PUId2NeighborSite[tmpPU->getId()]->X()
3369  << " Y:" << PUId2NeighborSite[tmpPU->getId()]->Y() << "\n";
3370  outfile1 << tmpCell
3371  << " estimated util:" << placementInfo->getActualOccupationByCellId(tmpCell->getCellId())
3372  << "\n";
3373  }
3374  else
3375  {
3376  std::vector<DeviceInfo::DeviceSite *> *candidateSites =
3377  placementInfo->findNeiborSiteFromBinGrid(tmpCell, tmpPU->X(), tmpPU->Y(), 5.0, 10);
3378  if (candidateSites->size())
3379  {
3380  for (auto tmpSite : *candidateSites)
3381  {
3382  if (!PUId2NeighborSite[tmpPU->getId()])
3383  {
3384  PUId2NeighborSite[tmpPU->getId()] = tmpSite;
3385  }
3386  else
3387  {
3388  float oriDis = std::abs(PUId2NeighborSite[tmpPU->getId()]->X() - tmpPU->X()) +
3389  y2xRatio * std::abs(PUId2NeighborSite[tmpPU->getId()]->Y() - tmpPU->Y());
3390  float newDis = std::abs(tmpSite->X() - tmpPU->X()) +
3391  y2xRatio * std::abs(tmpSite->Y() - tmpPU->Y());
3392  if (oriDis > newDis)
3393  {
3394  PUId2NeighborSite[tmpPU->getId()] = tmpSite;
3395  }
3396  }
3397  }
3398  }
3399  delete candidateSites;
3400  outfile1 << "closed neighbor site: " << PUId2NeighborSite[tmpPU->getId()]->getName()
3401  << " X:" << PUId2NeighborSite[tmpPU->getId()]->X()
3402  << " Y:" << PUId2NeighborSite[tmpPU->getId()]->Y() << "\n";
3403  outfile1 << tmpCell
3404  << " estimated util:" << placementInfo->getActualOccupationByCellId(tmpCell->getCellId())
3405  << "\n";
3406  }
3407  }
3408  }
3409  writeStrToGZip(dumpFile, outfile1);
3410  print_status("ParallelCLBPacker: dumped unpackable PUs archieve to: " + dumpFile);
3411  print_info("#PUNeedMappingCnt = " + std::to_string(PUNeedMappingCnt));
3412 
3413  print_status("ParallelCLBPacker: dumping placementTcl archieve to: " + dumpTclFile);
3414  dumpPlacementTcl(dumpTclFile);
3415  print_status("ParallelCLBPacker: dumped placementTcl archieve to: " + dumpTclFile);
3416  DumpCLBPackingCnt++;
3417  }
3418 }
3419 
3420 void ParallelCLBPacker::dumpAllCellsCoordinate()
3421 {
3422  if (JSONCfg.find("DumpAllCoordTrace") != JSONCfg.end())
3423  {
3424  std::string dumpFile =
3425  JSONCfg["DumpAllCoordTrace"] + "-Packing-" + std::to_string(allCoordinateDumpCnt) + ".gz";
3426  print_status("GlobalPlacer: dumping coordinate archieve to: " + dumpFile);
3427  allCoordinateDumpCnt++;
3428  if (dumpFile != "")
3429  {
3430  std::stringstream outfile0;
3431  for (auto curPU : placementInfo->getPlacementUnits())
3432  {
3433  if (auto curUnpackedCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(curPU))
3434  {
3435  float cellX = curUnpackedCell->X();
3436  float cellY = curUnpackedCell->Y();
3437  DesignInfo::DesignCell *curCell = curUnpackedCell->getCell();
3438  outfile0 << cellX << " " << cellY << " " << curCell->getName() << "\n";
3439  }
3440  else if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(curPU))
3441  {
3442  for (int vId = 0; vId < curMacro->getNumOfCells(); vId++)
3443  {
3444  float offsetX_InMacro, offsetY_InMacro;
3445  DesignInfo::DesignCellType cellType;
3446  curMacro->getVirtualCellInfo(vId, offsetX_InMacro, offsetY_InMacro, cellType);
3447  float cellX = curMacro->X() + offsetX_InMacro;
3448  float cellY = curMacro->Y() + offsetY_InMacro;
3449 
3450  if (curMacro->getCell(vId))
3451  outfile0 << cellX << " " << cellY << " " << curMacro->getCell(vId)->getName() << "\n";
3452  else
3453  outfile0 << cellX << " " << cellY << "\n";
3454  }
3455  }
3456  }
3457  writeStrToGZip(dumpFile, outfile0);
3458  print_status("GlobalPlacer: dumped coordinate archieve to: " + dumpFile);
3459  }
3460  }
3461 }
ParallelCLBPacker::dumpFinalPacking
void dumpFinalPacking()
Definition: ParallelCLBPacker.cc:3225
ParallelCLBPacker::dumpCLBPlacementTcl
void dumpCLBPlacementTcl(std::ofstream &outfileTcl, bool packingRelatedToLUT6_2)
Definition: ParallelCLBPacker.cc:3003
DesignInfo::DesignCell::isVirtualCell
bool isVirtualCell()
Definition: DesignInfo.h:1042
PlacementInfo::Location
Definition: PlacementInfo.h:3595
PlacementInfo::getBinGrid
std::vector< std::vector< PlacementBinInfo * > > & getBinGrid(unsigned int BELTypeId)
Get the Bin Grid object.
Definition: PlacementInfo.h:3099
PlacementInfo::PlacementUnit::getWeight
int getWeight()
Definition: PlacementInfo.h:1201
PlacementInfo::CompatiblePlacementTable::cellType2sharedBELTypeOccupation
std::map< DesignInfo::DesignCellType, int > cellType2sharedBELTypeOccupation
the resource demand of specific types. (cost how many slot/BELs)
Definition: PlacementInfo.h:144
delayVisualization.delay
delay
Definition: delayVisualization.py:55
PlacementTimingOptimizer::getWorstSlackOfCell
float getWorstSlackOfCell(DesignInfo::DesignCell *srcCell)
Definition: PlacementTimingOptimizer.cc:66
containLUTRAMCells
bool containLUTRAMCells(PlacementInfo::PlacementUnit *curPU)
Definition: ParallelCLBPacker.cc:2983
DesignInfo::CellType_LUT6_2
@ CellType_LUT6_2
Definition: DesignInfo.h:80
ParallelCLBPacker::PackingCLBSite::setNonCLBCell
void setNonCLBCell(DesignInfo::DesignCell *_NonCLBCell)
Definition: ParallelCLBPacker.h:2061
ParallelCLBPacker::numNeighbor
int numNeighbor
the threshold number of cells for site
Definition: ParallelCLBPacker.h:2984
PlacementTimingOptimizer::getDelayByModel
float getDelayByModel(PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::TimingNode *node1, PlacementTimingInfo::TimingGraph< DesignInfo::DesignCell >::TimingNode *node2, float X1, float Y1, float X2, float Y2)
Definition: PlacementTimingOptimizer.h:103
ParallelCLBPacker::designInfo
DesignInfo * designInfo
Definition: ParallelCLBPacker.h:2969
paintPlacement.cnt
int cnt
Definition: paintPlacement.py:155
ParallelCLBPacker::exceptionHandling
void exceptionHandling(bool verbose=false)
handle the PlacementUnits that cannot be packed during the parallel procedure
Definition: ParallelCLBPacker.cc:1766
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::getTotalCellWeight
float getTotalCellWeight() const
Get the total weights of cells in the cluster (each cell will have different weight in the placement)
Definition: ParallelCLBPacker.h:1538
ParallelCLBPacker::cellInMacros
std::set< DesignInfo::DesignCell * > & cellInMacros
Definition: ParallelCLBPacker.h:3030
DesignInfo::CellType_RAMB36E2
@ CellType_RAMB36E2
Definition: DesignInfo.h:111
PlacementInfo::getPlacementUnits
std::vector< PlacementUnit * > & getPlacementUnits()
Definition: PlacementInfo.h:2810
ParallelCLBPacker::ParallelCLBPacker
ParallelCLBPacker(DesignInfo *designInfo, DeviceInfo *deviceInfo, PlacementInfo *placementInfo, std::map< std::string, std::string > &JSONCfg, int unchangedIterationThr, int numNeighbor, float deltaD, float curD, float maxD, int PQSize, float HPWLWeight, std::string packerName, PlacementTimingOptimizer *timingOptimizer, WirelengthOptimizer *WLOptimizer=nullptr)
Construct a new Parallel CLB Packer object.
Definition: ParallelCLBPacker.cc:57
PlacementInfo::PlacementBinInfo::right
float right()
return the right boundary of the bin
Definition: PlacementInfo.h:703
PlacementInfo::PlacementUnit::setPacked
void setPacked()
Definition: PlacementInfo.h:1369
PlacementInfo::getCells
std::vector< DesignInfo::DesignCell * > & getCells()
Definition: PlacementInfo.h:3898
PlacementInfo::PlacementBinInfo::bottom
float bottom()
return the bottom boundary of the bin
Definition: PlacementInfo.h:723
ParallelCLBPacker::clockColumns2PackingSites
std::vector< std::vector< PackingCLBSite * > > clockColumns2PackingSites
Definition: ParallelCLBPacker.h:3025
ParallelCLBPacker::dumpPlacementTcl
void dumpPlacementTcl(std::string dumpTclFile)
Definition: ParallelCLBPacker.cc:3184
PlacementInfo::getPlacementUnpackedCells
std::vector< PlacementUnpackedCell * > & getPlacementUnpackedCells()
Definition: PlacementInfo.h:2838
PlacementInfo::PlacementBinInfo
BEL bin for global placement for a specific shared BEL type.
Definition: PlacementInfo.h:372
ParallelCLBPacker::dumpAllCellsCoordinate
void dumpAllCellsCoordinate()
Definition: ParallelCLBPacker.cc:3420
ParallelCLBPacker::exceptionPULegalize
bool exceptionPULegalize(PlacementInfo::PlacementUnit *curPU, float displacementThreshold, bool verbose)
try to find a legal location for the given PlacementUnit when most of PlacementUnits are packed into ...
Definition: ParallelCLBPacker.cc:1931
ParallelCLBPacker::WLOptimizer
WirelengthOptimizer * WLOptimizer
Definition: ParallelCLBPacker.h:3018
PlacementInfo::getCompatiblePlacementTable
CompatiblePlacementTable * getCompatiblePlacementTable()
Definition: PlacementInfo.h:2740
PlacementInfo::PlacementMacro
a fixed group of multiple standard cells with constraints of their relative locations
Definition: PlacementInfo.h:1525
PlacementInfo::PlacementUnit::setWeight
void setWeight(int numCell)
Definition: PlacementInfo.h:1196
ParallelCLBPacker::timingDrivenDetailedPlacement_swap
int timingDrivenDetailedPlacement_swap(int iterId)
Definition: ParallelCLBPacker.cc:1410
DesignInfo::DesignCell
a DesignCell in design netlist, DesignPin objects of which might connect to DesignNet objects
Definition: DesignInfo.h:782
DesignInfo::CellType_FIFO18E2
@ CellType_FIFO18E2
Definition: DesignInfo.h:109
PlacementInfo::checkClockColumnLegalization
bool checkClockColumnLegalization(PlacementInfo::PlacementUnit *curPU, DeviceInfo::DeviceSite *curSite)
check whether the given PlacementUnit can be mapped to the site considering the half-column clock leg...
Definition: PlacementInfo.h:4242
ParallelCLBPacker::PUId2PackingCLBSiteCandidate
std::vector< PackingCLBSite * > PUId2PackingCLBSiteCandidate
Definition: ParallelCLBPacker.h:3026
DeviceInfo::getSitesInType
std::vector< DeviceSite * > & getSitesInType(std::string &siteType)
Get sites of a specfic type.
Definition: DeviceInfo.h:1043
ParallelCLBPacker::addNonCLBPackingSites
void addNonCLBPackingSites()
Definition: ParallelCLBPacker.cc:2743
ParallelCLBPacker::ripUpAndLegalizae
bool ripUpAndLegalizae(PackingCLBSite *curTargetPackingSite, PlacementInfo::PlacementUnit *curPU, float displacementThreshold, std::map< PackingCLBSite *, PackingCLBSite::PackingCLBCluster * > &packingSite2DeterminedCluster, bool verbose)
try to rip up the packing for a given CLB site and pack the given PlacementUnit in the site....
Definition: ParallelCLBPacker.cc:2050
PlacementInfo::PlacementMacro::PlacementMacroType_LCLB
@ PlacementMacroType_LCLB
Definition: PlacementInfo.h:1533
ParallelCLBPacker::packedPUs
std::set< PlacementInfo::PlacementUnit *, Packing_PUcompare > packedPUs
Definition: ParallelCLBPacker.h:3034
PlacementInfo::getGridXY
void getGridXY(float cellX, float cellY, int &binIdX, int &binIdY)
Get the Grid row/column based on given location X,Y.
Definition: PlacementInfo.h:3344
PlacementInfo::PlacementUnit::getNetsSetPtr
std::vector< PlacementNet * > * getNetsSetPtr()
Get the Nets Set Ptr object which records the nets connecting to the PlacementUnit.
Definition: PlacementInfo.h:1231
ParallelCLBPacker::dumpDSPBRAMPlacementTcl
void dumpDSPBRAMPlacementTcl(std::ofstream &outfileTcl)
Definition: ParallelCLBPacker.cc:2865
PlacementTimingOptimizer::findCriticalPaths
std::vector< std::vector< int > > findCriticalPaths(float criticalRatio, bool checkOverlap=true, int pathNumThr=1000, int converThr=30)
Definition: PlacementTimingOptimizer.cc:119
ParallelCLBPacker::maxD
float maxD
the maximum constraint of the neighbor search diameter
Definition: ParallelCLBPacker.h:3002
ParallelCLBPacker.h
This header file contains the definitions of ParallelCLBPacker class and its internal modules and API...
PlacementInfo::PlacementMacro::PlacementMacroType_CARRY
@ PlacementMacroType_CARRY
Definition: PlacementInfo.h:1537
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::getScoreInSite
float getScoreInSite() const
Get the score if this cluster is mapped the site.
Definition: ParallelCLBPacker.h:1318
DeviceInfo::getClockColumns
std::vector< ClockColumn * > & getClockColumns()
Definition: DeviceInfo.h:1266
ParallelCLBPacker::PackingCLBSite::setDeterminedClusterInSite
void setDeterminedClusterInSite(PackingCLBCluster *tmpCluster)
Definition: ParallelCLBPacker.h:1938
PlacementInfo::PlacementUnit::Y
float Y()
Definition: PlacementInfo.h:1029
ParallelCLBPacker::DumpCLBPackingCnt
int DumpCLBPackingCnt
Definition: ParallelCLBPacker.h:3020
PlacementInfo::getCellId2location
std::vector< Location > & getCellId2location()
Definition: PlacementInfo.h:3600
DesignInfo::DesignCellType
DesignCellType
design cell types
Definition: DesignInfo.h:73
ParallelCLBPacker::placementUnits
std::vector< PlacementInfo::PlacementUnit * > & placementUnits
Definition: ParallelCLBPacker.h:3027
ParallelCLBPacker::y2xRatio
float y2xRatio
Definition: ParallelCLBPacker.h:3041
DeviceInfo::getClockRegionByLocation
void getClockRegionByLocation(float locX, float locY, int &clockRegionX, int &clockRegionY)
Get the clock region ID (X/Y) by a given location (X/Y)
Definition: DeviceInfo.h:1183
ParallelCLBPacker::prePackLegalizedMacros
void prePackLegalizedMacros(PlacementInfo::PlacementMacro *tmpMacro)
Load the information of some packed macros like LUTRAM/Crossing-Clock-Domain FFs/Carry Chains have be...
Definition: ParallelCLBPacker.cc:29
ParallelCLBPacker::placementInfo
PlacementInfo * placementInfo
Definition: ParallelCLBPacker.h:2971
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::removePUToConstructDetCluster
void removePUToConstructDetCluster(PlacementInfo::PlacementUnit *tmpPU)
remove some PlacementInfo::PlacementUnit from the cluster for later determined cluster construction o...
Definition: ParallelCLBPacker.h:893
PlacementInfo::PlacementUnit::setFixed
void setFixed()
Definition: PlacementInfo.h:1144
PlacementInfo::PlacementMacro::PlacementMacroType_MCLB
@ PlacementMacroType_MCLB
Definition: PlacementInfo.h:1535
ParallelCLBPacker::deviceSite2PackingSite
std::map< DeviceInfo::DeviceSite *, PackingCLBSite * > deviceSite2PackingSite
Definition: ParallelCLBPacker.h:3033
PlacementInfo::deleteLegalizationInfoFor
void deleteLegalizationInfoFor(PlacementInfo::PlacementUnit *curPU)
remove the legalization information of a PlacementUnit object
Definition: PlacementInfo.h:3714
ParallelCLBPacker::PackingCLBSite::checkIsLUTRAMSite
bool checkIsLUTRAMSite()
Definition: ParallelCLBPacker.h:2093
ParallelCLBPacker::findNeiborSitesFromBinGrid
std::vector< DeviceInfo::DeviceSite * > * findNeiborSitesFromBinGrid(DesignInfo::DesignCellType curCellType, float targetX, float targetY, float displacementLowerbound, float displacementUpperbound, float y2xRatio, bool clockRegionAware)
find the neighbors of specific cell type with given coordinate center
Definition: ParallelCLBPacker.cc:2432
PlacementInfo::updateB2BAndGetTotalHPWL
double updateB2BAndGetTotalHPWL()
update the B2B net model for the placement and get the total HPWL of all the nets in the design
Definition: PlacementInfo.h:3913
ParallelCLBPacker::PQSize
int PQSize
the size of priority queue (the low-priority candidates will be removed)
Definition: ParallelCLBPacker.h:3008
PlacementInfo::updateCells2PlacementUnits
void updateCells2PlacementUnits()
update the mapping from Cells to PlacementUnits, since sometime, PlacementUnits might change
Definition: PlacementInfo.cc:1683
PlacementTimingOptimizer
Definition: PlacementTimingOptimizer.h:46
PlacementInfo::PlacementUnit::X
float X()
Definition: PlacementInfo.h:1024
PlacementInfo::getDeviceInfo
DeviceInfo * getDeviceInfo()
Definition: PlacementInfo.h:3308
ParallelCLBPacker::PackingCLBSite::SiteBELMapping::LUTs
DesignInfo::DesignCell * LUTs[2][2][4]
Definition: ParallelCLBPacker.h:2364
ParallelCLBPacker::PackingCLBSite::addCarry
void addCarry()
add CARRY-related PlacementUnit into this CLB site
Definition: ParallelCLBPacker.h:1994
ParallelCLBPacker::PackingCLBSite::SiteBELMapping
SiteBELMapping is a contain recording the mapping between cells and BELs.
Definition: ParallelCLBPacker.h:2184
ParallelCLBPacker::allCoordinateDumpCnt
int allCoordinateDumpCnt
Definition: ParallelCLBPacker.h:3021
ParallelCLBPacker::PackingCLBSite::getDeterminedClusterInSite
PackingCLBCluster * getDeterminedClusterInSite()
Definition: ParallelCLBPacker.h:1933
ParallelCLBPacker::cellId2PlacementUnit
std::map< int, PlacementInfo::PlacementUnit * > & cellId2PlacementUnit
Definition: ParallelCLBPacker.h:3031
PlacementInfo::Location::X
float X
Definition: PlacementInfo.h:3596
PlacementInfo::PlacementUnit::getName
std::string & getName()
Definition: PlacementInfo.h:1186
delayVisualization.X
X
Definition: delayVisualization.py:80
DesignInfo::DesignCell::getOriCellType
DesignCellType getOriCellType()
Get the Original Cell Type object defined in the design netlist.
Definition: DesignInfo.h:1089
PlacementInfo::findNeiborSiteFromBinGrid
std::vector< DeviceInfo::DeviceSite * > * findNeiborSiteFromBinGrid(DesignInfo::DesignCell *curCell, float targetX, float targetY, float displacementThreshold, int siteNumThreshold, bool checkClockRegion=false)
find neibor device sites of a given cell from bin grid
Definition: PlacementInfo.h:3799
PlacementInfo::getActualOccupationByCellId
float getActualOccupationByCellId(int id)
Get the Actual Occupation By Cell Id.
Definition: PlacementInfo.h:2995
PlacementInfo::PlacementMacro::PlacementMacroType_DSP
@ PlacementMacroType_DSP
Definition: PlacementInfo.h:1538
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::updateScoreInSite
void updateScoreInSite()
update the score of this cluster by considering HPWL, interconnection density, timing and etc
Definition: ParallelCLBPacker_PackingCLBCluster.cc:515
ParallelCLBPacker::deltaD
float deltaD
the increase step of the neighbor search diameter
Definition: ParallelCLBPacker.h:2990
PlacementInfo::getPULegalSite
std::map< PlacementInfo::PlacementUnit *, std::vector< DeviceInfo::DeviceSite * > > & getPULegalSite()
get the sites occupied by the legalized PlacementUnit objects
Definition: PlacementInfo.h:3681
PlacementInfo::reloadNets
void reloadNets()
update PlacementNet objects when there are some updates of PlacementUnit objects (e....
Definition: PlacementInfo.cc:507
DesignInfo::CellType_RAMB18E2
@ CellType_RAMB18E2
Definition: DesignInfo.h:110
ParallelCLBPacker::setPUsToBePacked
void setPUsToBePacked()
set the packed attribute for the packed PlacementUnits
Definition: ParallelCLBPacker.cc:2542
PlacementInfo::updateElementBinGrid
void updateElementBinGrid()
map design cells to the bins in the bin grid.
Definition: PlacementInfo.cc:906
DesignInfo::CellType_FIFO36E2
@ CellType_FIFO36E2
Definition: DesignInfo.h:108
ParallelCLBPacker::unchangedIterationThr
int unchangedIterationThr
specify how many iterations a PlacementUnit should stay at the top priority of a site before we final...
Definition: ParallelCLBPacker.h:2978
ParallelCLBPacker::PackingCLBSite::SiteBELMapping::removeLUTFFPair
void removeLUTFFPair(DesignInfo::DesignCell *targetLUT, DesignInfo::DesignCell *targetFF)
Definition: ParallelCLBPacker.h:2338
print_status
void print_status(std::string tmp_string)
Definition: strPrint.cc:44
PlacementInfo::PlacementMacro::PlacementMacroType_LUTFFPair
@ PlacementMacroType_LUTFFPair
Definition: PlacementInfo.h:1529
ParallelCLBPacker::clockRegionAware
bool clockRegionAware
whether make clock region become constraints
Definition: ParallelCLBPacker.h:3047
DesignInfo::DesignElement::getName
const std::string & getName() const
Definition: DesignInfo.h:243
DesignInfo::CellType_LUT4
@ CellType_LUT4
Definition: DesignInfo.h:77
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster
PackingCLBCluster is a container of cells/PlacementUnits which can be packed in the corresponding CLB...
Definition: ParallelCLBPacker.h:453
ParallelCLBPacker::HPWLWeight
float HPWLWeight
the factor of HPWL overhead in packing evaluation for a cell
Definition: ParallelCLBPacker.h:3014
PlacementInfo::isDensePlacement
bool isDensePlacement()
Definition: PlacementInfo.h:4388
ParallelCLBPacker::checkPackedPUsAndUnpackedPUs
void checkPackedPUsAndUnpackedPUs()
check the packing status for all the PlacementUnits
Definition: ParallelCLBPacker.cc:1722
PlacementInfo::setPULegalSite
void setPULegalSite(std::map< PlacementInfo::PlacementUnit *, std::vector< DeviceInfo::DeviceSite * >> &PU2Sites)
set the sites occupied by the PlacementUnit objects
Definition: PlacementInfo.h:3668
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::addPU
bool addPU(PlacementInfo::PlacementUnit *tmpPU, bool allowOverlap=false)
try to add a given PlacementUnit into this cluster
Definition: ParallelCLBPacker_PackingCLBCluster.cc:621
ParallelCLBPacker::_PUWithScore
helper struct for candidate site sorting
Definition: ParallelCLBPacker.h:2796
PlacementInfo::getPlacementUnitByCellId
PlacementUnit * getPlacementUnitByCellId(int cellId)
Definition: PlacementInfo.h:3127
ParallelCLBPacker::timingDrivenDetailedPlacement_shortestPath_intermediate
int timingDrivenDetailedPlacement_shortestPath_intermediate()
Definition: ParallelCLBPacker.cc:1263
PlacementInfo::getPseudoNetWeight
float getPseudoNetWeight()
Get the Pseudo Net Weight object.
Definition: PlacementInfo.h:4026
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::getHash
int getHash()
Get the hash code for this cluster.
Definition: ParallelCLBPacker.h:1426
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::getPUs
const std::set< PlacementInfo::PlacementUnit *, Packing_PUcompare > & getPUs() const
Definition: ParallelCLBPacker.h:1032
ParallelCLBPacker::unpackedPUsVec
std::vector< PlacementInfo::PlacementUnit * > unpackedPUsVec
Definition: ParallelCLBPacker.h:3036
PlacementInfo::setPULegalXY
void setPULegalXY(std::map< PlacementInfo::PlacementUnit *, float > &PU2X, std::map< PlacementInfo::PlacementUnit *, float > &PU2Y)
set the legalization of some PlacementUnit objects
Definition: PlacementInfo.h:3648
PlacementInfo::PlacementUnit
a movement unit in placement with information of location and resource demand
Definition: PlacementInfo.h:1010
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::getParentPackingCLB
PackingCLBSite * getParentPackingCLB() const
Get the Parent Packing CLB site of this cluster (this can be used to get more device information)
Definition: ParallelCLBPacker.h:1342
ParallelCLBPacker::cellId2PackingSite
std::vector< PackingCLBSite * > cellId2PackingSite
Definition: ParallelCLBPacker.h:3039
ParallelCLBPacker::packCLBs
void packCLBs(int packIterNum, bool doExceptionHandling, bool debug=false)
packing the PlacementUnits (which are compatible to CLB sites) into CLB sites
Definition: ParallelCLBPacker.cc:288
PlacementInfo::PlacementBinInfo::getManhattanDistanceTo
float getManhattanDistanceTo(float inX, float inY)
Get the shortest Manhattan distance from the bin to a specific location.
Definition: PlacementInfo.h:413
PlacementTimingOptimizer::pauseCounter
void pauseCounter()
Definition: PlacementTimingOptimizer.h:174
PlacementInfo::PlacementUnit::getId
unsigned int getId()
Definition: PlacementInfo.h:1206
ParallelCLBPacker::updatePackedMacro
void updatePackedMacro(bool setPUPseudoNetToCLBSite=false, bool setCLBFixed=false)
Update the macros in PlacementInfo by regarding those elements in one CLB site as a macro.
Definition: ParallelCLBPacker.cc:2562
writeStrToGZip
void writeStrToGZip(std::string fileName, std::stringstream &data)
Definition: dumpZip.cc:29
hasLUT62
bool hasLUT62(ParallelCLBPacker::PackingCLBSite::SiteBELMapping &slots)
Definition: ParallelCLBPacker.cc:2722
ParallelCLBPacker::PackingCLBSite::checkIsPrePackedSite
bool checkIsPrePackedSite()
Definition: ParallelCLBPacker.h:2069
PlacementInfo::PlacementMacro::addOccupiedSite
void addOccupiedSite(float siteOffset, float occ)
for site-level cell spreading
Definition: PlacementInfo.h:1827
DesignInfo::CellType_MUXF8
@ CellType_MUXF8
Definition: DesignInfo.h:93
ParallelCLBPacker::timingDrivenDetailedPlacement_shortestPath
int timingDrivenDetailedPlacement_shortestPath(int iterId, float displacementRatio)
Definition: ParallelCLBPacker.cc:539
strSplit
void strSplit(const std::string &s, std::vector< std::string > &sv, const char *delim)
Definition: stringCheck.cc:35
DesignInfo::CellType_DSP48E2
@ CellType_DSP48E2
Definition: DesignInfo.h:90
ParallelCLBPacker::JSONCfg
std::map< std::string, std::string > & JSONCfg
Definition: ParallelCLBPacker.h:2972
ParallelCLBPacker::PackingCLBSite::getCLBSite
DeviceInfo::DeviceSite * getCLBSite()
Definition: ParallelCLBPacker.h:1918
ParallelCLBPacker::PackingCLBSite::addLUTRAMMacro
void addLUTRAMMacro()
add LUTRAM-related PlacementUnit into this CLB site
Definition: ParallelCLBPacker.h:2052
PlacementInfo::addPUIntoClockColumn
void addPUIntoClockColumn(PlacementInfo::PlacementUnit *curPU, DeviceInfo::DeviceSite *curSite)
map the given PlacementUnit to the site for later checking of the half-column clock legalization rule...
Definition: PlacementInfo.h:4301
DesignInfo::getCells
std::vector< DesignCell * > & getCells()
Definition: DesignInfo.h:1609
ParallelCLBPacker::packerName
std::string packerName
Definition: ParallelCLBPacker.h:3015
PlacementInfo::PlacementBinInfo::top
float top()
return the top boundary of the bin
Definition: PlacementInfo.h:713
ParallelCLBPacker::unpackedPUs
std::set< PlacementInfo::PlacementUnit *, Packing_PUcompare > unpackedPUs
Definition: ParallelCLBPacker.h:3035
PlacementTimingOptimizer::conductStaticTimingAnalysis
float conductStaticTimingAnalysis(bool enforeOptimisticTiming=false)
Definition: PlacementTimingOptimizer.cc:218
DeviceInfo
Information class related to FPGA device, including the details of BEL/Site/Tile/ClockRegion.
Definition: DeviceInfo.h:43
DeviceInfo::DeviceSite::X
float X()
Definition: DeviceInfo.h:288
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::incrementalUpdateScoreInSite
void incrementalUpdateScoreInSite(PlacementInfo::PlacementUnit *tmpPU)
incrementally update the score of this cluster by considering that only a given PlacementUnit will be...
Definition: ParallelCLBPacker_PackingCLBCluster.cc:568
delayVisualization.Y
Y
Definition: delayVisualization.py:80
WirelengthOptimizer::GlobalPlacementQPSolve
void GlobalPlacementQPSolve(float pesudoNetWeight, bool firstIteration=true, bool forwardSolutionToNextIteration=false, bool enableMacroPseudoNet2Site=false, bool considerNetNum=true, bool enableUserDefinedClusterOpt=false, float displacementLimit=-10, PlacementTimingOptimizer *timingOptimizer=nullptr)
use quadratic model to estimate the HPWL and some timing/user-defined pseudo nets are involved for sp...
Definition: WirelengthOptimizer.cc:100
PlacementInfo::getActualOccupation
float getActualOccupation(DesignInfo::DesignCell *cell)
Get the actual occupation of a specific cell.
Definition: PlacementInfo.h:2957
PlacementInfo::PlacementUnitType_Macro
@ PlacementUnitType_Macro
Definition: PlacementInfo.h:70
PlacementInfo::PlacementMacro::addCell
void addCell(DesignInfo::DesignCell *curCell, DesignInfo::DesignCellType cellType, float x, float y)
add a real cell into the macro with its offsets in the macro
Definition: PlacementInfo.h:1576
PlacementInfo::PlacementUnit::setAnchorLocationAndForgetTheOriginalOne
void setAnchorLocationAndForgetTheOriginalOne(float x, float y)
Definition: PlacementInfo.h:1128
PlacementInfo::PlacementUnpackedCell
the smallest, indivisible, representable component. It will include only one standard cell
Definition: PlacementInfo.h:1447
PlacementTimingOptimizer::getPUId2Slack
std::vector< float > & getPUId2Slack(bool update=false)
Definition: PlacementTimingOptimizer.cc:892
PlacementInfo::PlacementBinInfo::left
float left()
return the left boundary of the bin
Definition: PlacementInfo.h:693
ParallelCLBPacker::PUPoints
std::vector< PULocation > PUPoints
Definition: ParallelCLBPacker.h:3038
print_info
void print_info(std::string tmp_string)
Definition: strPrint.cc:39
ParallelCLBPacker::PackingCLBSite::checkIsCarrySite
bool checkIsCarrySite()
Definition: ParallelCLBPacker.h:2074
PlacementInfo::PlacementMacro::getCells
std::vector< DesignInfo::DesignCell * > & getCells()
Definition: PlacementInfo.h:1724
checkHalfColumn.i
int i
Definition: checkHalfColumn.py:5
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::tryAddPU
bool tryAddPU(PlacementInfo::PlacementUnit *tmpPU)
without modifying the original cluster container, try to add a given PlacementUnit into this cluster
Definition: ParallelCLBPacker.h:979
PlacementInfo::getPlacementUnitByCell
PlacementUnit * getPlacementUnitByCell(DesignInfo::DesignCell *curCell)
Definition: PlacementInfo.h:3120
ParallelCLBPacker::curD
float curD
current neighbor search diameter
Definition: ParallelCLBPacker.h:2996
ParallelCLBPacker::placementUnpackedCells
std::vector< PlacementInfo::PlacementUnpackedCell * > & placementUnpackedCells
Definition: ParallelCLBPacker.h:3028
ParallelCLBPacker::deviceInfo
DeviceInfo * deviceInfo
Definition: ParallelCLBPacker.h:2970
ParallelCLBPacker::packCLBsIteration
void packCLBsIteration(bool initial, bool debug=false)
update the packing cluster candidates for each CLB site and determine some mapping from elements to s...
Definition: ParallelCLBPacker.cc:129
PlacementInfo::getPU2ClockRegionCenters
std::map< PlacementUnit *, std::pair< float, float > > & getPU2ClockRegionCenters()
get the PlacementUnit Mapping to clock region centers for timing optimzation
Definition: PlacementInfo.h:4343
ParallelCLBPacker::setPULocationToPackedSite
void setPULocationToPackedSite()
update the location of PlacementUnits according to the packing result
Definition: ParallelCLBPacker.cc:2518
ParallelCLBPacker::packingSites
std::vector< PackingCLBSite * > packingSites
Definition: ParallelCLBPacker.h:3024
getAngle
float getAngle(float v1x, float v1y, float v2x, float v2y)
Definition: ParallelCLBPacker.cc:525
ParallelCLBPacker::placementMacros
std::vector< PlacementInfo::PlacementMacro * > & placementMacros
Definition: ParallelCLBPacker.h:3029
PlacementInfo::PlacementMacro::PlacementMacroType_BRAM
@ PlacementMacroType_BRAM
Definition: PlacementInfo.h:1539
PlacementInfo::PlacementMacro::getMacroType
PlacementMacroType getMacroType()
Definition: PlacementInfo.h:1841
ParallelCLBPacker::PackingCLBSite::PackingCLBCluster::checkAddPU
bool checkAddPU(PlacementInfo::PlacementUnit *tmpPU)
Definition: ParallelCLBPacker.h:998
ParallelCLBPacker::PUId2PackingCLBSite
std::vector< PackingCLBSite * > PUId2PackingCLBSite
Definition: ParallelCLBPacker.h:3023
ParallelCLBPacker::timingDrivenDetailedPlacement_LUTFFPairReloacationAfterSlotMapping
int timingDrivenDetailedPlacement_LUTFFPairReloacationAfterSlotMapping()
Definition: ParallelCLBPacker.cc:993
ParallelCLBPacker::timingOptimizer
PlacementTimingOptimizer * timingOptimizer
Definition: ParallelCLBPacker.h:3017
replaceAll
void replaceAll(std::string &str, const std::string from, const std::string to)
Definition: stringCheck.cc:50
DesignInfo
Information related to FPGA designs, including design cells and their interconnections.
Definition: DesignInfo.h:51
ParallelCLBPacker::_siteWithScore
helper struct for candidate site sorting
Definition: ParallelCLBPacker.h:2782
PlacementInfo::setDeterminedOccupation
void setDeterminedOccupation(int cellId, int occupation)
Set the Determined Occupation of a specific cell.
Definition: PlacementInfo.h:4112
PlacementInfo::Location::Y
float Y
Definition: PlacementInfo.h:3597
ParallelCLBPacker::PackingCLBSite
PackingCLBSite is a container for the packing information (parameters, candidates and packing status)...
Definition: ParallelCLBPacker.h:400
WirelengthOptimizer
WirelengthOptimizer builds numerical models based on the element locations and calls solvers to find ...
Definition: WirelengthOptimizer.h:54
ParallelCLBPacker::PackingCLBSite::getSlotMappingRef
SiteBELMapping & getSlotMappingRef()
Definition: ParallelCLBPacker.h:2580
PlacementInfo::getPotentialBELTypeIDs
std::vector< int > & getPotentialBELTypeIDs(DesignInfo::DesignCell *cell)
Definition: PlacementInfo.h:2932
PlacementInfo::PlacementBinInfo::getCorrespondingSites
std::vector< DeviceInfo::DeviceSite * > & getCorrespondingSites()
Get the reference of the set of sites in the bin.
Definition: PlacementInfo.h:775
DeviceInfo::DeviceSite::Y
float Y()
Definition: DeviceInfo.h:292
PlacementInfo
Information related to FPGA placement (wirelength optimization, cell spreading, legalization,...
Definition: PlacementInfo.h:59