1 //////////////////////////////////////////////////////////////////////////////// 2 // Authors: Vitor Bandeira, Eder Matheus Monteiro e Isadora Oliveira 3 // (Advisor: Ricardo Reis) 4 // 5 // BSD 3-Clause License 6 // 7 // Copyright (c) 2019, Federal University of Rio Grande do Sul (UFRGS) 8 // All rights reserved. 9 // 10 // Redistribution and use in source and binary forms, with or without 11 // modification, are permitted provided that the following conditions are met: 12 // 13 // * Redistributions of source code must retain the above copyright notice, this 14 // list of conditions and the following disclaimer. 15 // 16 // * Redistributions in binary form must reproduce the above copyright notice, 17 // this list of conditions and the following disclaimer in the documentation 18 // and/or other materials provided with the distribution. 19 // 20 // * Neither the name of the copyright holder nor the names of its 21 // contributors may be used to endorse or promote products derived from 22 // this software without specific prior written permission. 23 // 24 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 25 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 28 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 29 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 30 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 31 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 32 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 33 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 // POSSIBILITY OF SUCH DAMAGE. 35 //////////////////////////////////////////////////////////////////////////////// 36 37 #pragma once 38 39 #include <map> 40 #include <string> 41 #include <vector> 42 43 #include "grt/GRoute.h" 44 #include "DataType.h" 45 #include "flute.h" 46 #include "boost/multi_array.hpp" 47 48 namespace utl { 49 class Logger; 50 } 51 52 namespace odb{ 53 class dbDatabase; 54 } 55 56 using boost::multi_array; 57 58 namespace grt { 59 60 class FastRouteCore 61 { 62 public: 63 FastRouteCore(odb::dbDatabase* db, utl::Logger* log); 64 ~FastRouteCore(); 65 66 void deleteComponents(); 67 void clear(); 68 void setGridsAndLayers(int x, int y, int nLayers); 69 void addVCapacity(short verticalCapacity, int layer); 70 void addHCapacity(short horizontalCapacity, int layer); 71 void addMinWidth(int width, int layer); 72 void addMinSpacing(int spacing, int layer); 73 void addViaSpacing(int spacing, int layer); 74 void setNumberNets(int nNets); 75 void setLowerLeft(int x, int y); 76 void setTileSize(int width, int height); 77 void setLayerOrientation(int x); 78 void addPin(int netID, int x, int y, int layer); 79 int addNet(odb::dbNet* db_net, 80 int num_pins, 81 float alpha, 82 bool is_clock, 83 int driver_idx, 84 int cost, 85 std::vector<int> edge_cost_per_layer); 86 void initEdges(); 87 void setNumAdjustments(int nAdjustements); 88 void addAdjustment(long x1, 89 long y1, 90 int l1, 91 long x2, 92 long y2, 93 int l2, 94 int reducedCap, 95 bool isReduce); 96 void initAuxVar(); 97 NetRouteMap run(); 98 void updateDbCongestion(); 99 100 int getEdgeCapacity(long x1, long y1, int l1, long x2, long y2, int l2); 101 int getEdgeCurrentResource(long x1, 102 long y1, 103 int l1, 104 long x2, 105 long y2, 106 int l2); 107 int getEdgeCurrentUsage(long x1, long y1, int l1, long x2, long y2, int l2); 108 void setEdgeUsage(long x1, 109 long y1, 110 int l1, 111 long x2, 112 long y2, 113 int l2, 114 int newUsage); 115 void setEdgeCapacity(long x1, 116 long y1, 117 int l1, 118 long x2, 119 long y2, 120 int l2, 121 int newCap); 122 void setMaxNetDegree(int); 123 void setVerbose(int v); 124 void setOverflowIterations(int iterations); 125 void setAllowOverflow(bool allow); 126 void computeCongestionInformation(); 127 std::vector<int> getOriginalResources(); getTotalCapacityPerLayer()128 const std::vector<int>& getTotalCapacityPerLayer() { return cap_per_layer_; } getTotalUsagePerLayer()129 const std::vector<int>& getTotalUsagePerLayer() { return usage_per_layer_; } getTotalOverflowPerLayer()130 const std::vector<int>& getTotalOverflowPerLayer() { return overflow_per_layer_; } getMaxHorizontalOverflows()131 const std::vector<int>& getMaxHorizontalOverflows() { return max_h_overflow_; } getMaxVerticalOverflows()132 const std::vector<int>& getMaxVerticalOverflows() { return max_v_overflow_; } 133 134 private: 135 NetRouteMap getRoutes(); 136 void init_usage(); 137 138 // maze functions 139 // Maze-routing in different orders 140 void mazeRouteMSMD(int iter, 141 int expand, 142 float height, 143 int ripup_threshold, 144 int mazeedgeThreshold, 145 bool ordering, 146 int cost_type, 147 float LOGIS_COF, 148 int VIA, 149 int slope, 150 int L); 151 void convertToMazeroute(); 152 void updateCongestionHistory(int round, int upType, bool stopDEC, int &max_adj); 153 int getOverflow2D(int* maxOverflow); 154 int getOverflow2Dmaze(int* maxOverflow, int* tUsage); 155 int getOverflow3D(void); 156 void str_accu(int rnd); 157 void InitLastUsage(int upType); 158 void InitEstUsage(); 159 void convertToMazerouteNet(int netID); 160 void setupHeap(int netID, 161 int edgeID, 162 int* heapLen1, 163 int* heapLen2, 164 int regionX1, 165 int regionX2, 166 int regionY1, 167 int regionY2); 168 int copyGrids(TreeNode* treenodes, 169 int n1, 170 int n2, 171 TreeEdge* treeedges, 172 int edge_n1n2, 173 std::vector<int>& gridsX_n1n2, 174 std::vector<int>& gridsY_n1n2); 175 void updateRouteType1(TreeNode* treenodes, 176 int n1, 177 int A1, 178 int A2, 179 int E1x, 180 int E1y, 181 TreeEdge* treeedges, 182 int edge_n1A1, 183 int edge_n1A2); 184 void updateRouteType2(TreeNode* treenodes, 185 int n1, 186 int A1, 187 int A2, 188 int C1, 189 int C2, 190 int E1x, 191 int E1y, 192 TreeEdge* treeedges, 193 int edge_n1A1, 194 int edge_n1A2, 195 int edge_C1C2); 196 void reInitTree(int netID); 197 198 // maze3D functions 199 void mazeRouteMSMDOrder3D(int expand, int ripupTHlb, int ripupTHub, int layerOrientation); 200 void setupHeap3D(int netID, 201 int edgeID, 202 int* heapLen1, 203 int* heapLen2, 204 int regionX1, 205 int regionX2, 206 int regionY1, 207 int regionY2); 208 void newUpdateNodeLayers(TreeNode* treenodes, int edgeID, int n1, int lastL); 209 int copyGrids3D(TreeNode* treenodes, 210 int n1, 211 int n2, 212 TreeEdge* treeedges, 213 int edge_n1n2, 214 int gridsX_n1n2[], 215 int gridsY_n1n2[], 216 int gridsL_n1n2[]); 217 void updateRouteType13D(int netID, 218 TreeNode* treenodes, 219 int n1, 220 int A1, 221 int A2, 222 int E1x, 223 int E1y, 224 TreeEdge* treeedges, 225 int edge_n1A1, 226 int edge_n1A2); 227 void updateRouteType23D(int netID, 228 TreeNode* treenodes, 229 int n1, 230 int A1, 231 int A2, 232 int C1, 233 int C2, 234 int E1x, 235 int E1y, 236 TreeEdge* treeedges, 237 int edge_n1A1, 238 int edge_n1A2, 239 int edge_C1C2); 240 241 // rsmt functions 242 void copyStTree(int ind, Tree rsmt); 243 void gen_brk_RSMT(bool congestionDriven, 244 bool reRoute, 245 bool genTree, 246 bool newType, 247 bool noADJ); 248 void fluteNormal(int netID, 249 int d, 250 DTYPE x[], 251 DTYPE y[], 252 int acc, 253 float coeffV, 254 Tree* t); 255 void fluteCongest(int netID, 256 int d, 257 DTYPE x[], 258 DTYPE y[], 259 int acc, 260 float coeffV, 261 Tree* t); 262 float coeffADJ(int netID); 263 bool HTreeSuite(int netID); 264 bool VTreeSuite(int netID); 265 bool netCongestion(int netID); 266 267 // route functions 268 // old functions for segment list data structure 269 void routeSegL(Segment* seg); 270 void routeLAll(bool firstTime); 271 // new functions for tree data structure 272 void newrouteL(int netID, RouteType ripuptype, bool viaGuided); 273 void newrouteZ(int netID, int threshold); 274 void newrouteZ_edge(int netID, int edgeID); 275 void newrouteLAll(bool firstTime, bool viaGuided); 276 void newrouteZAll(int threshold); 277 void routeMonotonicAll(int threshold); 278 void routeMonotonic(int netID, int edgeID, int threshold); 279 void routeLVAll(int threshold, int expand, float logis_cof); 280 void spiralRouteAll(); 281 void newrouteLInMaze(int netID); 282 void estimateOneSeg(Segment* seg); 283 void routeSegV(Segment* seg); 284 void routeSegH(Segment* seg); 285 void routeSegLFirstTime(Segment* seg); 286 void spiralRoute(int netID, int edgeID); 287 void routeLVEnew(int netID, int edgeID, int threshold, int enlarge); 288 289 // ripup functions 290 void ripupSegL(Segment* seg); 291 void ripupSegZ(Segment* seg); 292 void newRipup(TreeEdge* treeedge, 293 TreeNode* treenodes, 294 int x1, 295 int y1, 296 int x2, 297 int y2, 298 int netID); 299 bool newRipupCheck(TreeEdge* treeedge, 300 int x1, 301 int y1, 302 int x2, 303 int y2, 304 int ripup_threshold, 305 int netID, 306 int edgeID); 307 308 bool newRipupType2(TreeEdge* treeedge, 309 TreeNode* treenodes, 310 int x1, 311 int y1, 312 int x2, 313 int y2, 314 int deg, 315 int netID); 316 bool newRipup3DType3(int netID, int edgeID); 317 void newRipupNet(int netID); 318 319 // utility functions 320 void printEdge(int netID, int edgeID); 321 void ConvertToFull3DType2(); 322 void fillVIA(); 323 int threeDVIA(); 324 void assignEdge(int netID, int edgeID, bool processDIR); 325 void recoverEdge(int netID, int edgeID); 326 void newLayerAssignmentV4(); 327 void netpinOrderInc(); 328 void checkRoute3D(); 329 void StNetOrder(); 330 bool checkRoute2DTree(int netID); 331 void checkUsage(); 332 void netedgeOrderDec(int netID); 333 void printTree2D(int netID); 334 void printEdge2D(int netID, int edgeID); 335 void printEdge3D(int netID, int edgeID); 336 void printTree3D(int netID); 337 void check2DEdgesUsage(); 338 void newLA(); 339 void copyBR(void); 340 void copyRS(void); 341 void freeRR(void); 342 Tree fluteToTree(stt::Tree fluteTree); 343 stt::Tree treeToFlute(Tree tree); 344 int edgeShift(Tree* t, int net); 345 int edgeShiftNew(Tree* t, int net); 346 347 static const int MAXLEN = 20000; 348 static const int BIG_INT = 1e7; // big integer used as infinity 349 static const int HCOST = 5000; 350 351 int max_degree_; 352 std::vector<int> cap_per_layer_; 353 std::vector<int> usage_per_layer_; 354 std::vector<int> overflow_per_layer_; 355 std::vector<int> max_h_overflow_; 356 std::vector<int> max_v_overflow_; 357 odb::dbDatabase* db_; 358 bool allow_overflow_; 359 int overflow_iterations_; 360 int num_nets_; 361 int layer_orientation_; 362 int x_range_; 363 int y_range_; 364 365 int new_net_id_; 366 int seg_count_; 367 int pin_ind_; 368 int num_adjust_; 369 int v_capacity_; 370 int h_capacity_; 371 int x_grid_; 372 int y_grid_; 373 int x_corner_; 374 int y_corner_; 375 int w_tile_; 376 int h_tile_; 377 int enlarge_; 378 int costheight_; 379 int ahth_; 380 int num_valid_nets_; // # nets need to be routed (having pins in different grids) 381 int num_layers_; 382 int total_overflow_; // total # overflow 383 int grid_hv_; 384 int grid_h_; 385 int grid_v_; 386 int verbose_; 387 int via_cost_; 388 int mazeedge_threshold_; 389 float v_capacity_lb_; 390 float h_capacity_lb_; 391 392 std::vector<short> v_capacity_3D_; 393 std::vector<short> h_capacity_3D_; 394 std::vector<float> cost_hvh_; // Horizontal first Z 395 std::vector<float> cost_vhv_; // Vertical first Z 396 std::vector<float> cost_h_; // Horizontal segment cost 397 std::vector<float> cost_v_; // Vertical segment cost 398 std::vector<float> cost_lr_; // Left and right boundary cost 399 std::vector<float> cost_tb_; // Top and bottom boundary cost 400 std::vector<float> cost_hvh_test_; // Vertical first Z 401 std::vector<float> cost_v_test_; // Vertical segment cost 402 std::vector<float> cost_tb_test_; // Top and bottom boundary cost 403 std::vector<float> h_cost_table_; 404 std::vector<float> v_cost_table_; 405 std::vector<int> xcor_; 406 std::vector<int> ycor_; 407 std::vector<int> dcor_; 408 std::vector<int> seglist_index_; // the index for the segments for each net 409 std::vector<int> seglist_cnt_; // the number of segements for each net 410 std::vector<int> grid_hs_; 411 std::vector<int> grid_vs_; 412 std::vector<bool> pop_heap2_; 413 414 std::vector<FrNet*> nets_; 415 std::vector<Edge> h_edges_; 416 std::vector<Edge> v_edges_; 417 std::vector<OrderNetEdge> net_eo_; 418 std::vector<std::vector<DTYPE>> gxs_; // the copy of xs for nets, used for second FLUTE 419 std::vector<std::vector<DTYPE>> gys_; // the copy of xs for nets, used for second FLUTE 420 std::vector<std::vector<DTYPE>> gs_; // the copy of vertical sequence for nets, used for second FLUTE 421 std::vector<Edge3D> h_edges_3D_; 422 std::vector<Edge3D> v_edges_3D_; 423 std::vector<Segment> seglist_; 424 std::vector<OrderNetPin> tree_order_pv_; 425 std::vector<OrderTree> tree_order_cong_; 426 427 multi_array<dirctionT, 3> directions_3D_; 428 multi_array<parent3D, 3> pr_3D_; 429 multi_array<int, 3> corr_edge_3D_; 430 multi_array<int, 2> corr_edge_; 431 multi_array<int, 2> layer_grid_; 432 multi_array<int, 2> via_link_; 433 multi_array<int, 3> d1_3D_; 434 multi_array<short, 3> d2_3D_; 435 multi_array<short, 2> parent_x1_; 436 multi_array<short, 2> parent_y1_; 437 multi_array<short, 2> parent_x3_; 438 multi_array<short, 2> parent_y3_; 439 multi_array<float, 2> d1_; 440 multi_array<float, 2> d2_; 441 multi_array<bool, 2> hv_; 442 multi_array<bool, 2> hyper_v_; 443 multi_array<bool, 2> hyper_h_; 444 multi_array<bool, 2> in_region_; 445 446 StTree* sttrees_; // the Steiner trees 447 StTree* sttrees_bk_; 448 449 int** heap1_3D_; 450 short** heap2_3D_; 451 452 float **heap2_; 453 float **heap1_; 454 455 utl::Logger* logger_; 456 }; 457 458 } // namespace grt 459