VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
route_breadth_first.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include "util.h"
3 #include "vpr_types.h"
4 #include "globals.h"
5 #include "route_export.h"
6 #include "route_common.h"
7 #include "route_breadth_first.h"
8 
9 /********************* Subroutines local to this module *********************/
10 
11 static boolean breadth_first_route_net(int inet, float bend_cost);
12 
13 static void breadth_first_expand_trace_segment(struct s_trace *start_ptr,
14  int remaining_connections_to_sink);
15 
16 static void breadth_first_expand_neighbours(int inode, float pcost, int inet,
17  float bend_cost);
18 
19 static void breadth_first_add_source_to_heap(int inet);
20 
21 /************************ Subroutine definitions ****************************/
22 
23 boolean try_breadth_first_route(struct s_router_opts router_opts,
24  t_ivec ** clb_opins_used_locally, int width_fac) {
25 
26  /* Iterated maze router ala Pathfinder Negotiated Congestion algorithm, *
27  * (FPGA 95 p. 111). Returns TRUE if it can route this FPGA, FALSE if *
28  * it can't. */
29 
30  float pres_fac;
31  boolean success, is_routable, rip_up_local_opins;
32  int itry, inet;
33 
34  /* Usually the first iteration uses a very small (or 0) pres_fac to find *
35  * the shortest path and get a congestion map. For fast compiles, I set *
36  * pres_fac high even for the first iteration. */
37 
38  pres_fac = router_opts.first_iter_pres_fac;
39 
40  for (itry = 1; itry <= router_opts.max_router_iterations; itry++) {
41 
42  for (inet = 0; inet < num_nets; inet++) {
43  if (clb_net[inet].is_global == FALSE) { /* Skip global nets. */
44 
45  pathfinder_update_one_cost(trace_head[inet], -1, pres_fac);
46 
47  is_routable = breadth_first_route_net(inet,
48  router_opts.bend_cost);
49 
50  /* Impossible to route? (disconnected rr_graph) */
51 
52  if (!is_routable) {
53  vpr_printf(TIO_MESSAGE_INFO, "Routing failed.\n");
54  return (FALSE);
55  }
56 
57  pathfinder_update_one_cost(trace_head[inet], 1, pres_fac);
58 
59  }
60  }
61 
62  /* Make sure any CLB OPINs used up by subblocks being hooked directly *
63  * to them are reserved for that purpose. */
64 
65  if (itry == 1)
66  rip_up_local_opins = FALSE;
67  else
68  rip_up_local_opins = TRUE;
69 
70  reserve_locally_used_opins(pres_fac, rip_up_local_opins,
71  clb_opins_used_locally);
72 
73  success = feasible_routing();
74  if (success) {
75  vpr_printf(TIO_MESSAGE_INFO, "Successfully routed after %d routing iterations.\n", itry);
76  return (TRUE);
77  }
78 
79  if (itry == 1)
80  pres_fac = router_opts.initial_pres_fac;
81  else
82  pres_fac *= router_opts.pres_fac_mult;
83 
84  pres_fac = std::min(pres_fac, static_cast<float>(HUGE_POSITIVE_FLOAT / 1e5));
85 
86  pathfinder_update_cost(pres_fac, router_opts.acc_fac);
87  }
88 
89  vpr_printf(TIO_MESSAGE_INFO, "Routing failed.\n");
90  return (FALSE);
91 }
92 
93 static boolean breadth_first_route_net(int inet, float bend_cost) {
94 
95  /* Uses a maze routing (Dijkstra's) algorithm to route a net. The net *
96  * begins at the net output, and expands outward until it hits a target *
97  * pin. The algorithm is then restarted with the entire first wire segment *
98  * included as part of the source this time. For an n-pin net, the maze *
99  * router is invoked n-1 times to complete all the connections. Inet is *
100  * the index of the net to be routed. Bends are penalized by bend_cost *
101  * (which is typically zero for detailed routing and nonzero only for global *
102  * routing), since global routes with lots of bends are tougher to detailed *
103  * route (using a detailed router like SEGA). *
104  * If this routine finds that a net *cannot* be connected (due to a complete *
105  * lack of potential paths, rather than congestion), it returns FALSE, as *
106  * routing is impossible on this architecture. Otherwise it returns TRUE. */
107 
108  int i, inode, prev_node, remaining_connections_to_sink;
109  float pcost, new_pcost;
110  struct s_heap *current;
111  struct s_trace *tptr;
112 
113  free_traceback(inet);
115  mark_ends(inet);
116 
117  tptr = NULL;
118  remaining_connections_to_sink = 0;
119 
120  for (i = 1; i <= clb_net[inet].num_sinks; i++) { /* Need n-1 wires to connect n pins */
121  breadth_first_expand_trace_segment(tptr, remaining_connections_to_sink);
122  current = get_heap_head();
123 
124  if (current == NULL) { /* Infeasible routing. No possible path for net. */
125  vpr_printf (TIO_MESSAGE_INFO, "Cannot route net #%d (%s) to sink #%d -- no possible path.\n",
126  inet, clb_net[inet].name, i);
127  reset_path_costs(); /* Clean up before leaving. */
128  return (FALSE);
129  }
130 
131  inode = current->index;
132 
133  while (rr_node_route_inf[inode].target_flag == 0) {
134  pcost = rr_node_route_inf[inode].path_cost;
135  new_pcost = current->cost;
136  if (pcost > new_pcost) { /* New path is lowest cost. */
137  rr_node_route_inf[inode].path_cost = new_pcost;
138  prev_node = current->u.prev_node;
139  rr_node_route_inf[inode].prev_node = prev_node;
140  rr_node_route_inf[inode].prev_edge = current->prev_edge;
141 
142  if (pcost > 0.99 * HUGE_POSITIVE_FLOAT) /* First time touched. */
143  add_to_mod_list(&rr_node_route_inf[inode].path_cost);
144 
145  breadth_first_expand_neighbours(inode, new_pcost, inet,
146  bend_cost);
147  }
148 
149  free_heap_data(current);
150  current = get_heap_head();
151 
152  if (current == NULL) { /* Impossible routing. No path for net. */
153  vpr_printf (TIO_MESSAGE_INFO, "Cannot route net #%d (%s) to sink #%d -- no possible path.\n",
154  inet, clb_net[inet].name, i);
156  return (FALSE);
157  }
158 
159  inode = current->index;
160  }
161 
162  rr_node_route_inf[inode].target_flag--; /* Connected to this SINK. */
163  remaining_connections_to_sink = rr_node_route_inf[inode].target_flag;
164  tptr = update_traceback(current, inet);
165  free_heap_data(current);
166  }
167 
168  empty_heap();
170  return (TRUE);
171 }
172 
173 static void breadth_first_expand_trace_segment(struct s_trace *start_ptr,
174  int remaining_connections_to_sink) {
175 
176  /* Adds all the rr_nodes in the traceback segment starting at tptr (and *
177  * continuing to the end of the traceback) to the heap with a cost of zero. *
178  * This allows expansion to begin from the existing wiring. The *
179  * remaining_connections_to_sink value is 0 if the route segment ending *
180  * at this location is the last one to connect to the SINK ending the route *
181  * segment. This is the usual case. If it is not the last connection this *
182  * net must make to this SINK, I have a hack to ensure the next connection *
183  * to this SINK goes through a different IPIN. Without this hack, the *
184  * router would always put all the connections from this net to this SINK *
185  * through the same IPIN. With LUTs or cluster-based logic blocks, you *
186  * should never have a net connecting to two logically-equivalent pins on *
187  * the same logic block, so the hack will never execute. If your logic *
188  * block is an and-gate, however, nets might connect to two and-inputs on *
189  * the same logic block, and since the and-inputs are logically-equivalent, *
190  * this means two connections to the same SINK. */
191 
192  struct s_trace *tptr, *next_ptr;
193  int inode, sink_node, last_ipin_node;
194 
195  tptr = start_ptr;
196  if(tptr != NULL && rr_node[tptr->index].type == SINK) {
197  /* During logical equivalence case, only use one opin */
198  tptr = tptr->next;
199  }
200 
201  if (remaining_connections_to_sink == 0) { /* Usual case. */
202  while (tptr != NULL) {
204  tptr = tptr->next;
205  }
206  }
207 
208  else { /* This case never executes for most logic blocks. */
209 
210  /* Weird case. Lots of hacks. The cleanest way to do this would be to empty *
211  * the heap, update the congestion due to the partially-completed route, put *
212  * the whole route so far (excluding IPINs and SINKs) on the heap with cost *
213  * 0., and expand till you hit the next SINK. That would be slow, so I *
214  * do some hacks to enable incremental wavefront expansion instead. */
215 
216  if (tptr == NULL)
217  return; /* No route yet */
218 
219  next_ptr = tptr->next;
220  last_ipin_node = OPEN; /* Stops compiler from complaining. */
221 
222  /* Can't put last SINK on heap with NO_PREVIOUS, etc, since that won't let *
223  * us reach it again. Instead, leave the last traceback element (SINK) off *
224  * the heap. */
225 
226  while (next_ptr != NULL) {
227  inode = tptr->index;
229 
230  if (rr_node[inode].type == IPIN)
231  last_ipin_node = inode;
232 
233  tptr = next_ptr;
234  next_ptr = tptr->next;
235  }
236 
237  /* This will stop the IPIN node used to get to this SINK from being *
238  * reexpanded for the remainder of this net's routing. This will make us *
239  * hook up more IPINs to this SINK (which is what we want). If IPIN *
240  * doglegs are allowed in the graph, we won't be able to use this IPIN to *
241  * do a dogleg, since it won't be re-expanded. Shouldn't be a big problem. */
242 
244 
245  /* Also need to mark the SINK as having high cost, so another connection can *
246  * be made to it. */
247 
248  sink_node = tptr->index;
250 
251  /* Finally, I need to remove any pending connections to this SINK via the *
252  * IPIN I just used (since they would result in congestion). Scan through *
253  * the heap to do this. */
254 
255  invalidate_heap_entries(sink_node, last_ipin_node);
256  }
257 }
258 
259 static void breadth_first_expand_neighbours(int inode, float pcost, int inet,
260  float bend_cost) {
261 
262  /* Puts all the rr_nodes adjacent to inode on the heap. rr_nodes outside *
263  * the expanded bounding box specified in route_bb are not added to the *
264  * heap. pcost is the path_cost to get to inode. */
265 
266  int iconn, to_node, num_edges;
267  t_rr_type from_type, to_type;
268  float tot_cost;
269 
270  num_edges = rr_node[inode].num_edges;
271  for (iconn = 0; iconn < num_edges; iconn++) {
272  to_node = rr_node[inode].edges[iconn];
273 
274  if (rr_node[to_node].xhigh < route_bb[inet].xmin
275  || rr_node[to_node].xlow > route_bb[inet].xmax
276  || rr_node[to_node].yhigh < route_bb[inet].ymin
277  || rr_node[to_node].ylow > route_bb[inet].ymax)
278  continue; /* Node is outside (expanded) bounding box. */
279 
280  tot_cost = pcost + get_rr_cong_cost(to_node);
281 
282  if (bend_cost != 0.) {
283  from_type = rr_node[inode].type;
284  to_type = rr_node[to_node].type;
285  if ((from_type == CHANX && to_type == CHANY)
286  || (from_type == CHANY && to_type == CHANX))
287  tot_cost += bend_cost;
288  }
289 
290  node_to_heap(to_node, tot_cost, inode, iconn, OPEN, OPEN);
291  }
292 }
293 
294 static void breadth_first_add_source_to_heap(int inet) {
295 
296  /* Adds the SOURCE of this net to the heap. Used to start a net's routing. */
297 
298  int inode;
299  float cost;
300 
301  inode = net_rr_terminals[inet][0]; /* SOURCE */
302  cost = get_rr_cong_cost(inode);
303 
304  node_to_heap(inode, cost, NO_PREVIOUS, NO_PREVIOUS, OPEN, OPEN);
305 }
boolean feasible_routing(void)
Definition: route_common.c:298
short num_edges
Definition: vpr_types.h:901
int index
Definition: route_common.h:4
int index
Definition: vpr_types.h:866
float get_rr_cong_cost(int inode)
Definition: route_common.c:532
int * edges
Definition: vpr_types.h:903
struct s_heap * get_heap_head(void)
Definition: route_common.c:949
t_rr_node * rr_node
Definition: globals.c:70
void free_traceback(int inet)
Definition: route_common.c:587
int prev_node
Definition: route_common.h:7
void mark_ends(int inet)
Definition: route_common.c:546
t_rr_node_route_inf * rr_node_route_inf
Definition: route_common.c:21
static boolean breadth_first_route_net(int inet, float bend_cost)
void invalidate_heap_entries(int sink_node, int ipin_node)
#define NO_PREVIOUS
Definition: vpr_types.h:887
float pres_fac_mult
Definition: vpr_types.h:698
void free_heap_data(struct s_heap *hptr)
int max_router_iterations
Definition: vpr_types.h:701
float first_iter_pres_fac
Definition: vpr_types.h:696
void pathfinder_update_cost(float pres_fac, float acc_fac)
Definition: route_common.c:363
int num_nets
Definition: globals.c:27
boolean try_breadth_first_route(struct s_router_opts router_opts, t_ivec **clb_opins_used_locally, int width_fac)
Definition: util.h:12
void reset_path_costs(void)
Definition: route_common.c:490
static float pres_fac
#define min(a, b)
Definition: graphics.c:174
static t_ivec ** clb_opins_used_locally
static void breadth_first_expand_neighbours(int inode, float pcost, int inet, float bend_cost)
float bend_cost
Definition: vpr_types.h:700
union s_heap::@0 u
#define HUGE_POSITIVE_FLOAT
Definition: vpr_types.h:79
struct s_trace * next
Definition: vpr_types.h:870
boolean * is_global
int prev_edge
Definition: route_common.h:10
struct s_net * clb_net
Definition: globals.c:28
float initial_pres_fac
Definition: vpr_types.h:697
struct s_trace ** trace_head
Definition: globals.c:64
static void breadth_first_expand_trace_segment(struct s_trace *start_ptr, int remaining_connections_to_sink)
float cost
Definition: route_common.h:5
void node_to_heap(int inode, float cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream)
Definition: route_common.c:562
Definition: util.h:47
void pathfinder_update_one_cost(struct s_trace *route_segment_start, int add_or_sub, float pres_fac)
Definition: route_common.c:315
struct s_trace * update_traceback(struct s_heap *hptr, int inet)
Definition: route_common.c:421
enum e_rr_type t_rr_type
void add_to_mod_list(float *fptr)
Definition: route_common.c:898
Definition: slre.c:50
void reserve_locally_used_opins(float pres_fac, boolean rip_up_local_opins, t_ivec **clb_opins_used_locally)
float acc_fac
Definition: vpr_types.h:699
int ** net_rr_terminals
Definition: globals.c:78
struct s_bb * route_bb
Definition: route_common.c:23
static void breadth_first_add_source_to_heap(int inet)
void empty_heap(void)
Definition: route_common.c:991
messagelogger vpr_printf
Definition: util.c:17
int num_sinks
Definition: vpr_types.h:506
t_rr_type type
Definition: vpr_types.h:902
Definition: util.h:12