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