1 /* Authors: Lutong Wang and Bangqi Xu */
2 /*
3  * Copyright (c) 2019, The Regents of the University of California
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *     * Redistributions of source code must retain the above copyright
9  *       notice, this list of conditions and the following disclaimer.
10  *     * Redistributions in binary form must reproduce the above copyright
11  *       notice, this list of conditions and the following disclaimer in the
12  *       documentation and/or other materials provided with the distribution.
13  *     * Neither the name of the University nor the
14  *       names of its contributors may be used to endorse or promote products
15  *       derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS BE LIABLE FOR ANY DIRECT,
21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #include "dr/FlexGridGraph.h"
30 
31 #include <fstream>
32 #include <iostream>
33 #include <map>
34 
35 #include "dr/FlexDR.h"
36 
37 using namespace std;
38 using namespace fr;
39 
initGrids(const map<frCoord,map<frLayerNum,frTrackPattern * >> & xMap,const map<frCoord,map<frLayerNum,frTrackPattern * >> & yMap,const map<frLayerNum,frPrefRoutingDirEnum> & zMap,bool followGuide)40 void FlexGridGraph::initGrids(
41     const map<frCoord, map<frLayerNum, frTrackPattern*>>& xMap,
42     const map<frCoord, map<frLayerNum, frTrackPattern*>>& yMap,
43     const map<frLayerNum, frPrefRoutingDirEnum>& zMap,
44     bool followGuide)
45 {
46   // initialize coord vectors
47   xCoords_.clear();
48   yCoords_.clear();
49   zCoords_.clear();
50   zHeights_.clear();
51   zDirs_.clear();
52   for (auto& [k, v] : xMap) {
53     xCoords_.push_back(k);
54   }
55   for (auto& [k, v] : yMap) {
56     yCoords_.push_back(k);
57   }
58   frCoord zHeight = 0;
59   // vector<frCoord> via2viaMinLenTmp(4, 0);
60   for (auto& [k, v] : zMap) {
61     zCoords_.push_back(k);
62     zHeight += getTech()->getLayer(k)->getPitch() * VIACOST;
63     zHeights_.push_back(zHeight);
64     zDirs_.push_back((v == frPrefRoutingDirEnum::frcHorzPrefRoutingDir));
65   }
66   // initialize all grids
67   frMIdx xDim, yDim, zDim;
68   getDim(xDim, yDim, zDim);
69   nodes_.clear();
70   nodes_.resize(xDim * yDim * zDim, Node());
71   // new
72   prevDirs_.clear();
73   srcs_.clear();
74   dsts_.clear();
75   prevDirs_.resize(xDim * yDim * zDim * 3, 0);
76   srcs_.resize(xDim * yDim * zDim, 0);
77   dsts_.resize(xDim * yDim * zDim, 0);
78   guides_.clear();
79   if (followGuide) {
80     guides_.resize(xDim * yDim * zDim, 0);
81   } else {
82     guides_.resize(xDim * yDim * zDim, 1);
83   }
84 }
85 
outOfDieVia(frMIdx x,frMIdx y,frMIdx z,const frBox & dieBox)86 bool FlexGridGraph::outOfDieVia(frMIdx x,
87                                 frMIdx y,
88                                 frMIdx z,
89                                 const frBox& dieBox)
90 {
91   frViaDef* via = getTech()->getLayer(getLayerNum(z) + 1)->getDefaultViaDef();
92   frBox viaBox(via->getLayer1ShapeBox());
93   viaBox.merge(via->getLayer2ShapeBox());
94   viaBox.shift(xCoords_[x], yCoords_[y]);
95   return !dieBox.contains(viaBox);
96 }
97 
isWorkerBorder(frMIdx v,bool isVert)98 bool FlexGridGraph::isWorkerBorder(frMIdx v, bool isVert)
99 {
100   if (isVert)
101     return xCoords_[v] == drWorker_->getRouteBox().left()
102            || xCoords_[v] == drWorker_->getRouteBox().right();
103   return yCoords_[v] == drWorker_->getRouteBox().bottom()
104          || yCoords_[v] == drWorker_->getRouteBox().top();
105 }
106 
initEdges(const frDesign * design,const map<frCoord,map<frLayerNum,frTrackPattern * >> & xMap,const map<frCoord,map<frLayerNum,frTrackPattern * >> & yMap,const map<frLayerNum,frPrefRoutingDirEnum> & zMap,const frBox & bbox,bool initDR)107 void FlexGridGraph::initEdges(
108     const frDesign* design,
109     const map<frCoord, map<frLayerNum, frTrackPattern*>>& xMap,
110     const map<frCoord, map<frLayerNum, frTrackPattern*>>& yMap,
111     const map<frLayerNum, frPrefRoutingDirEnum>& zMap,
112     const frBox& bbox,
113     bool initDR)
114 {
115   frMIdx xDim, yDim, zDim;
116   getDim(xDim, yDim, zDim);
117   // initialize grid graph
118   frMIdx xIdx = 0, yIdx = 0, zIdx = 0;
119   design->getTopBlock()->getDieBox(dieBox_);
120   for (const auto& [layerNum, dir] : zMap) {
121     frLayerNum nonPrefLayerNum;
122     const auto layer = getTech()->getLayer(layerNum);
123     if (layerNum + 2 <= getTech()->getTopLayerNum()) {
124       nonPrefLayerNum = layerNum + 2;
125     } else if (layerNum - 2 >= getTech()->getBottomLayerNum()) {
126       nonPrefLayerNum = layerNum - 2;
127     } else {
128       nonPrefLayerNum = layerNum;
129     }
130 
131     const auto nonPrefLayer = getTech()->getLayer(nonPrefLayerNum);
132     yIdx = 0;
133     for (auto& [yCoord, ySubMap] : yMap) {
134       auto yIt = ySubMap.find(layerNum);
135       auto yIt2 = ySubMap.find(layerNum + 2);
136       auto yIt3 = ySubMap.find(nonPrefLayerNum);
137       bool yFound = (yIt != ySubMap.end());
138       bool yFound2 = (yIt2 != ySubMap.end());
139       bool yFound3 = (yIt3 != ySubMap.end());
140       xIdx = 0;
141       for (auto& [xCoord, xSubMap] : xMap) {
142         auto xIt = xSubMap.find(layerNum);
143         auto xIt2 = xSubMap.find(layerNum + 2);
144         auto xIt3 = xSubMap.find(nonPrefLayerNum);
145         bool xFound = (xIt != xSubMap.end());
146         bool xFound2 = (xIt2 != xSubMap.end());
147         bool xFound3 = (xIt3 != xSubMap.end());
148         // add cost to out-of-die edge
149         bool outOfDiePlanar = false;
150         // add edge for preferred direction
151         if (dir == frcHorzPrefRoutingDir && yFound) {
152           if (layerNum >= BOTTOM_ROUTING_LAYER
153               && layerNum <= TOP_ROUTING_LAYER) {
154             if (layer->getLef58RightWayOnGridOnlyConstraint() == nullptr
155                 || yIt->second != nullptr) {
156               addEdge(xIdx, yIdx, zIdx, frDirEnum::E, bbox, initDR);
157               if (yIt->second == nullptr || outOfDiePlanar
158                   || isWorkerBorder(yIdx, false)) {
159                 setGridCostE(xIdx, yIdx, zIdx);
160               }
161             }
162           }
163           // via to upper layer
164           if (xFound2) {
165             if ((layer->getLef58RightWayOnGridOnlyConstraint() != nullptr
166                  && yIt->second == nullptr)
167                 || (nonPrefLayer->getLef58RightWayOnGridOnlyConstraint()
168                         != nullptr
169                     && xIt2->second == nullptr)) {
170               ;
171             } else if (!outOfDieVia(xIdx, yIdx, zIdx, dieBox_)) {
172               addEdge(xIdx, yIdx, zIdx, frDirEnum::U, bbox, initDR);
173               bool condition
174                   = (yIt->second == nullptr || xIt2->second == nullptr);
175               if (condition) {
176                 setGridCostU(xIdx, yIdx, zIdx);
177               }
178             }
179           }
180         } else if (dir == frcVertPrefRoutingDir && xFound) {
181           if (layerNum >= BOTTOM_ROUTING_LAYER
182               && layerNum <= TOP_ROUTING_LAYER) {
183             if (layer->getLef58RightWayOnGridOnlyConstraint() == nullptr
184                 || xIt->second != nullptr) {
185               addEdge(xIdx, yIdx, zIdx, frDirEnum::N, bbox, initDR);
186               if (xIt->second == nullptr || outOfDiePlanar
187                   || isWorkerBorder(xIdx, true)) {
188                 setGridCostN(xIdx, yIdx, zIdx);
189               }
190             }
191           }
192           // via to upper layer
193           if (yFound2) {
194             if ((layer->getLef58RightWayOnGridOnlyConstraint() != nullptr
195                  && xIt->second == nullptr)
196                 || (nonPrefLayer->getLef58RightWayOnGridOnlyConstraint()
197                         != nullptr
198                     && yIt2->second == nullptr)) {
199               ;
200             } else if (!outOfDieVia(xIdx, yIdx, zIdx, dieBox_)) {
201               addEdge(xIdx, yIdx, zIdx, frDirEnum::U, bbox, initDR);
202               bool condition
203                   = (yIt2->second == nullptr || xIt->second == nullptr);
204               if (condition) {
205                 setGridCostU(xIdx, yIdx, zIdx);
206               }
207             }
208           }
209         }
210         // get non pref track layer --> use upper layer pref dir track if
211         // possible
212         if (USENONPREFTRACKS && !layer->isUnidirectional()) {
213           // add edge for non-preferred direction
214           // vertical non-pref track
215           if (dir == frcHorzPrefRoutingDir && xFound3) {
216             if (layerNum >= BOTTOM_ROUTING_LAYER
217                 && layerNum <= TOP_ROUTING_LAYER) {
218               addEdge(xIdx, yIdx, zIdx, frDirEnum::N, bbox, initDR);
219               setGridCostN(xIdx, yIdx, zIdx);
220             }
221             // horizontal non-pref track
222           } else if (dir == frcVertPrefRoutingDir && yFound3) {
223             if (layerNum >= BOTTOM_ROUTING_LAYER
224                 && layerNum <= TOP_ROUTING_LAYER) {
225               addEdge(xIdx, yIdx, zIdx, frDirEnum::E, bbox, initDR);
226               setGridCostE(xIdx, yIdx, zIdx);
227             }
228           }
229         }
230         ++xIdx;
231       }
232       ++yIdx;
233     }
234     ++zIdx;
235   }
236 }
237 
238 // initialization: update grid graph topology, does not assign edge cost
init(const frDesign * design,const frBox & routeBBox,const frBox & extBBox,map<frCoord,map<frLayerNum,frTrackPattern * >> & xMap,map<frCoord,map<frLayerNum,frTrackPattern * >> & yMap,bool initDR,bool followGuide)239 void FlexGridGraph::init(const frDesign* design,
240                          const frBox& routeBBox,
241                          const frBox& extBBox,
242                          map<frCoord, map<frLayerNum, frTrackPattern*>>& xMap,
243                          map<frCoord, map<frLayerNum, frTrackPattern*>>& yMap,
244                          bool initDR,
245                          bool followGuide)
246 {
247   auto* via_data = getDRWorker()->getViaData();
248   halfViaEncArea_ = &via_data->halfViaEncArea;
249   via2viaMinLen_ = &via_data->via2viaMinLen;
250   via2turnMinLen_ = &via_data->via2turnMinLen;
251   via2viaMinLenNew_ = &via_data->via2viaMinLenNew;
252 
253   // get tracks intersecting with the Maze bbox
254   map<frLayerNum, frPrefRoutingDirEnum> zMap;
255   initTracks(design, xMap, yMap, zMap, extBBox);
256   initGrids(xMap, yMap, zMap, followGuide);  // buildGridGraph
257   initEdges(
258       design, xMap, yMap, zMap, routeBBox, initDR);  // add edges and edgeCost
259 }
260 
261 // initialization helpers
262 // get all tracks intersecting with the Maze bbox, left/bottom are inclusive
initTracks(const frDesign * design,map<frCoord,map<frLayerNum,frTrackPattern * >> & xMap,map<frCoord,map<frLayerNum,frTrackPattern * >> & yMap,map<frLayerNum,frPrefRoutingDirEnum> & zMap,const frBox & bbox)263 void FlexGridGraph::initTracks(
264     const frDesign* design,
265     map<frCoord, map<frLayerNum, frTrackPattern*>>& xMap,
266     map<frCoord, map<frLayerNum, frTrackPattern*>>& yMap,
267     map<frLayerNum, frPrefRoutingDirEnum>& zMap,
268     const frBox& bbox)
269 {
270   for (auto& layer : getTech()->getLayers()) {
271     if (layer->getType() != frLayerTypeEnum::ROUTING) {
272       continue;
273     }
274     frLayerNum currLayerNum = layer->getLayerNum();
275     frPrefRoutingDirEnum currPrefRouteDir = layer->getDir();
276     for (auto& tp : design->getTopBlock()->getTrackPatterns(currLayerNum)) {
277       // allow wrongway if global varialble and design rule allow
278       bool flag = (USENONPREFTRACKS && !layer->isUnidirectional())
279                       ? (tp->isHorizontal()
280                          && currPrefRouteDir == frcVertPrefRoutingDir)
281                             || (!tp->isHorizontal()
282                                 && currPrefRouteDir == frcHorzPrefRoutingDir)
283                       : true;
284       if (flag) {
285         int trackNum = ((tp->isHorizontal() ? bbox.left() : bbox.bottom())
286                         - tp->getStartCoord())
287                        / (int) tp->getTrackSpacing();
288         if (trackNum < 0) {
289           trackNum = 0;
290         }
291         if (trackNum * (int) tp->getTrackSpacing() + tp->getStartCoord()
292             < (tp->isHorizontal() ? bbox.left() : bbox.bottom())) {
293           ++trackNum;
294         }
295         for (; trackNum < (int) tp->getNumTracks()
296                && trackNum * (int) tp->getTrackSpacing() + tp->getStartCoord()
297                       < (tp->isHorizontal() ? bbox.right() : bbox.top());
298              ++trackNum) {
299           frCoord trackLoc
300               = trackNum * tp->getTrackSpacing() + tp->getStartCoord();
301           if (tp->isHorizontal()) {
302             xMap[trackLoc][currLayerNum] = tp.get();
303           } else {
304             yMap[trackLoc][currLayerNum] = tp.get();
305           }
306         }
307       }
308     }
309     zMap[currLayerNum] = currPrefRouteDir;
310   }
311 }
312 
resetStatus()313 void FlexGridGraph::resetStatus()
314 {
315   resetSrc();
316   resetDst();
317   resetPrevNodeDir();
318 }
319 
resetSrc()320 void FlexGridGraph::resetSrc()
321 {
322   srcs_.assign(srcs_.size(), 0);
323 }
324 
resetDst()325 void FlexGridGraph::resetDst()
326 {
327   dsts_.assign(dsts_.size(), 0);
328 }
329 
resetPrevNodeDir()330 void FlexGridGraph::resetPrevNodeDir()
331 {
332   prevDirs_.assign(prevDirs_.size(), 0);
333 }
334 
335 // print the grid graph with edge and vertex for debug purpose
print() const336 void FlexGridGraph::print() const
337 {
338   ofstream mazeLog(OUT_MAZE_FILE.c_str());
339   if (mazeLog.is_open()) {
340     // print edges
341     frBox gridBBox;
342     getBBox(gridBBox);
343     mazeLog << "printing Maze grid (" << gridBBox.left() << ", "
344             << gridBBox.bottom() << ") -- (" << gridBBox.right() << ", "
345             << gridBBox.top() << ")\n";
346     frMIdx xDim, yDim, zDim;
347     getDim(xDim, yDim, zDim);
348 
349     if (xDim == 0 || yDim == 0 || zDim == 0) {
350       cout << "Error: dimension == 0\n";
351       return;
352     } else {
353       cout << "extBBox (xDim, yDim, zDim) = (" << xDim << ", " << yDim << ", "
354            << zDim << ")\n";
355     }
356 
357     frPoint p;
358     for (frMIdx xIdx = 0; xIdx < xDim; ++xIdx) {
359       for (frMIdx yIdx = 0; yIdx < yDim; ++yIdx) {
360         for (frMIdx zIdx = 0; zIdx < zDim; ++zIdx) {
361           if (hasEdge(xIdx, yIdx, zIdx, frDirEnum::N)) {
362             if (yIdx + 1 >= yDim) {
363               cout << "Error: no edge (" << xIdx << ", " << yIdx << ", " << zIdx
364                    << ", N) " << yDim << endl;
365               continue;
366             }
367             mazeLog << "Edge: " << getPoint(p, xIdx, yIdx).x() << " "
368                     << getPoint(p, xIdx, yIdx).y() << " " << zIdx << " "
369                     << getPoint(p, xIdx, yIdx + 1).x() << " "
370                     << getPoint(p, xIdx, yIdx + 1).y() << " " << zIdx << "\n";
371           }
372           if (hasEdge(xIdx, yIdx, zIdx, frDirEnum::E)) {
373             if (xIdx + 1 >= xDim) {
374               cout << "Error: no edge (" << xIdx << ", " << yIdx << ", " << zIdx
375                    << ", E) " << xDim << endl;
376               continue;
377             }
378             mazeLog << "Edge: " << getPoint(p, xIdx, yIdx).x() << " "
379                     << getPoint(p, xIdx, yIdx).y() << " " << zIdx << " "
380                     << getPoint(p, xIdx + 1, yIdx).x() << " "
381                     << getPoint(p, xIdx + 1, yIdx).y() << " " << zIdx << "\n";
382           }
383           if (hasEdge(xIdx, yIdx, zIdx, frDirEnum::U)) {
384             if (zIdx + 1 >= zDim) {
385               cout << "Error: no edge (" << xIdx << ", " << yIdx << ", " << zIdx
386                    << ", U) " << zDim << endl;
387               continue;
388             }
389             mazeLog << "Edge: " << getPoint(p, xIdx, yIdx).x() << " "
390                     << getPoint(p, xIdx, yIdx).y() << " " << zIdx << " "
391                     << getPoint(p, xIdx, yIdx).x() << " "
392                     << getPoint(p, xIdx, yIdx).y() << " " << zIdx + 1 << "\n";
393           }
394         }
395       }
396     }
397   } else {
398     cout << "Error: Fail to open maze log\n";
399   }
400 }
401