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