VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
cluster_legality.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include <assert.h>
3 #include <string.h>
4 
5 #include "util.h"
6 #include "physical_types.h"
7 #include "vpr_types.h"
8 #include "globals.h"
9 #include "route_export.h"
10 #include "route_common.h"
11 #include "cluster_legality.h"
12 #include "cluster_placement.h"
13 #include "rr_graph.h"
14 
15 static t_chunk rr_mem_ch = {NULL, 0, NULL};
16 
17 /*static struct s_linked_vptr *rr_mem_chunk_list_head = NULL;
18 static int chunk_bytes_avail = 0;
19 static char *chunk_next_avail_mem = NULL;*/
20 static struct s_trace **best_routing;
21 
22 /* nets_in_cluster: array of all nets contained in the cluster */
23 static int *nets_in_cluster; /* [0..num_nets_in_cluster-1] */
26 static int curr_cluster_index;
27 
31 static float pres_fac;
32 
33 /********************* Subroutines local to this module *********************/
34 static boolean is_net_in_cluster(INP int inet);
35 
36 static void add_net_rr_terminal_cluster(int iblk_net,
37  t_pb_graph_node * primitive, int ilogical_block,
38  t_model_ports * model_port, int ipin);
39 
40 static boolean breadth_first_route_net_cluster(int inet);
41 
43  struct s_trace *start_ptr, int remaining_connections_to_sink);
44 
45 static void breadth_first_expand_neighbours_cluster(int inode, float pcost,
46  int inet, boolean first_time);
47 
48 static void breadth_first_add_source_to_heap_cluster(int inet);
49 
50 static void alloc_net_rr_terminals_cluster(void);
51 
52 static void mark_ends_cluster(int inet);
53 
54 static float rr_node_intrinsic_cost(int inode);
55 
56 /************************ Subroutine definitions ****************************/
57 
58 static boolean is_net_in_cluster(INP int inet) {
59  int i;
60  for (i = 0; i < num_nets_in_cluster; i++) {
61  if (nets_in_cluster[i] == inet) {
62  return TRUE;
63  }
64  }
65  return FALSE;
66 }
67 
68 /* load rr_node for source and sinks of net if exists, return FALSE otherwise */
69 /* Todo: Note this is an inefficient way to determine port, better to use a lookup, worry about this if runtime becomes an issue */
70 static void add_net_rr_terminal_cluster(int iblk_net,
71  t_pb_graph_node * primitive, int ilogical_block,
72  t_model_ports * model_port, int ipin) {
73  /* Ensure at most one external input/clock source and one external output sink for net */
74  int i, net_pin;
75  t_port *prim_port;
76  const t_pb_type *pb_type;
77  boolean found;
78 
79  int input_port;
80  int output_port;
81  int clock_port;
82 
83  input_port = output_port = clock_port = 0;
84 
85  pb_type = primitive->pb_type;
86  prim_port = NULL;
87 
88  assert(pb_type->num_modes == 0);
89 
90  found = FALSE;
91  /* TODO: This is inelegant design, I should change the primitive ports in pb_type to be input, output, or clock instead of this lookup */
92  for (i = 0; i < pb_type->num_ports && !found; i++) {
93  prim_port = &pb_type->ports[i];
94  if (pb_type->ports[i].model_port == model_port) {
95  found = TRUE;
96  } else {
97  if (prim_port->is_clock) {
98  clock_port++;
99  assert(prim_port->type == IN_PORT);
100  } else if (prim_port->type == IN_PORT) {
101  input_port++;
102  } else if (prim_port->type == OUT_PORT) {
103  output_port++;
104  } else {
105  assert(0);
106  }
107  }
108  }
109  assert(found);
110  assert(ipin < prim_port->num_pins);
111  net_pin = OPEN;
112  if (prim_port->is_clock) {
113  for (i = 1; i <= vpack_net[iblk_net].num_sinks; i++) {
114  if (vpack_net[iblk_net].node_block[i] == ilogical_block
115  && vpack_net[iblk_net].node_block_port[i]
116  == model_port->index
117  && vpack_net[iblk_net].node_block_pin[i] == ipin) {
118  net_pin = i;
119  break;
120  }
121  }
122  assert(net_pin != OPEN);
123  assert(rr_node[primitive->clock_pins[clock_port][ipin].pin_count_in_cluster].num_edges == 1);
124  net_rr_terminals[iblk_net][net_pin] = rr_node[primitive->clock_pins[clock_port][ipin].pin_count_in_cluster].edges[0];
125  } else if (prim_port->type == IN_PORT) {
126  for (i = 1; i <= vpack_net[iblk_net].num_sinks; i++) {
127  if (vpack_net[iblk_net].node_block[i] == ilogical_block
128  && vpack_net[iblk_net].node_block_port[i]
129  == model_port->index
130  && vpack_net[iblk_net].node_block_pin[i] == ipin) {
131  net_pin = i;
132  break;
133  }
134  }
135  assert(net_pin != OPEN);
136  assert(rr_node[primitive->input_pins[input_port][ipin].pin_count_in_cluster].num_edges == 1);
137  net_rr_terminals[iblk_net][net_pin] = rr_node[primitive->input_pins[input_port][ipin].pin_count_in_cluster].edges[0];
138  } else if (prim_port->type == OUT_PORT) {
139  i = 0;
140  if (vpack_net[iblk_net].node_block[i] == ilogical_block
141  && vpack_net[iblk_net].node_block_port[i] == model_port->index
142  && vpack_net[iblk_net].node_block_pin[i] == ipin) {
143  net_pin = i;
144  }
145  assert(net_pin != OPEN);
146  net_rr_terminals[iblk_net][net_pin] =
147  primitive->output_pins[output_port][ipin].pin_count_in_cluster;
148  } else {
149  assert(0);
150  }
151 }
152 
154  int i, j, net_index;
155  boolean has_ext_sink, has_ext_source;
156  int curr_ext_output, curr_ext_input, curr_ext_clock;
157 
158  curr_ext_input = ext_input_rr_node_index;
159  curr_ext_output = ext_output_rr_node_index;
160  curr_ext_clock = ext_clock_rr_node_index;
161 
162  for (i = 0; i < num_nets_in_cluster; i++) {
163  net_index = nets_in_cluster[i];
164  has_ext_sink = FALSE;
165  has_ext_source = (boolean)
166  (logical_block[vpack_net[net_index].node_block[0]].clb_index
167  != curr_cluster_index);
168  if (has_ext_source) {
169  /* Instantiate a source of this net */
170  if (vpack_net[net_index].is_global) {
171  net_rr_terminals[net_index][0] = curr_ext_clock;
172  curr_ext_clock++;
173  } else {
174  net_rr_terminals[net_index][0] = curr_ext_input;
175  curr_ext_input++;
176  }
177  }
178  for (j = 1; j <= vpack_net[net_index].num_sinks; j++) {
179  if (logical_block[vpack_net[net_index].node_block[j]].clb_index
180  != curr_cluster_index) {
181  if (has_ext_sink || has_ext_source) {
182  /* Only need one node driving external routing, either this cluster drives external routing or another cluster does it */
183  net_rr_terminals[net_index][j] = OPEN;
184  } else {
185  /* External sink, only need to route once, externally routing will take care of the rest */
186  net_rr_terminals[net_index][j] = curr_ext_output;
187  curr_ext_output++;
188  has_ext_sink = TRUE;
189  }
190  }
191  }
192 
193  if (curr_ext_input > ext_output_rr_node_index
194  || curr_ext_output > ext_clock_rr_node_index
195  || curr_ext_clock > max_ext_index) {
196  /* failed, not enough pins of proper type, overran index */
197  assert(0);
198  }
199  }
200 }
201 
203  best_routing = (struct s_trace **) my_calloc(num_logical_nets,
204  sizeof(struct s_trace *));
205  nets_in_cluster = (int *) my_malloc(num_logical_nets * sizeof(int));
208 
209  /* inside a cluster, I do not consider rr_indexed_data cost, set to 1 since other costs are multiplied by it */
212  rr_indexed_data[0].base_cost = 1;
213 
214  /* alloc routing structures */
217 }
218 
220  int inet;
221  free(best_routing);
222  free(rr_indexed_data);
226 
227  free_chunk_memory(&rr_mem_ch);
228 
229  for (inet = 0; inet < num_logical_nets; inet++) {
230  free(saved_net_rr_terminals[inet]);
231  }
232  free(net_rr_terminals);
233  free(nets_in_cluster);
235 }
236 
238  INP t_pb_graph_node *pb_graph_node, INP const t_arch* arch, int mode) {
239 
240  int i, j, k, index;
241  boolean is_primitive;
242 
243  is_primitive = (boolean) (pb_graph_node->pb_type->num_modes == 0);
244 
245  for (i = 0; i < pb_graph_node->num_input_ports; i++) {
246  for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
247  index = pb_graph_node->input_pins[i][j].pin_count_in_cluster;
248  rr_node[index].pb_graph_pin = &pb_graph_node->input_pins[i][j];
249  rr_node[index].fan_in =
250  pb_graph_node->input_pins[i][j].num_input_edges;
252  pb_graph_node->input_pins[i][j].num_output_edges;
254  + (float) rr_node[index].num_edges / 5 + ((float)j/(float)pb_graph_node->num_input_pins[i])/(float)10; /* need to normalize better than 5 and 10, bias router to use earlier inputs pins */
255  rr_node[index].edges = (int *) my_malloc(
256  rr_node[index].num_edges * sizeof(int));
257  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
258  sizeof(short));
262  if (mode == 0) { /* default mode is the first mode */
263  rr_node[index].capacity = 1;
264  } else {
265  rr_node[index].capacity = 0;
266  }
267  for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges;
268  k++) {
269  /* TODO: Intention was to do bus-based implementation here */
270  rr_node[index].edges[k] =
271  pb_graph_node->input_pins[i][j].output_edges[k]->output_pins[0]->pin_count_in_cluster;
272  rr_node[index].switches[k] = arch->num_switches - 1; /* last switch in arch switch properties is a delayless switch */
273  assert(
274  pb_graph_node->input_pins[i][j].output_edges[k]->num_output_pins == 1);
275  }
277  if (is_primitive) {
278  /* This is a terminating pin, add SINK node */
279  assert(rr_node[index].num_edges == 0);
280  rr_node[index].num_edges = 1;
281  rr_node[index].edges = (int *) my_calloc(rr_node[index].num_edges, sizeof(int));
282  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges, sizeof(short));
284 
285  /* Create SINK node */
290  rr_node[num_rr_nodes].edges = NULL;
291  rr_node[num_rr_nodes].switches = NULL;
297  num_rr_nodes++;
298 
299  if(pb_graph_node->pb_type->class_type == LUT_CLASS) {
300  /* LUTs are special, they have logical equivalence at inputs, logical equivalence is represented by a single high capacity sink instead of multiple single capacity sinks */
301  rr_node[num_rr_nodes - 1].capacity = pb_graph_node->num_input_pins[i];
302  if(j != 0) {
303  num_rr_nodes--;
304  rr_node[index].edges[0] = num_rr_nodes - 1;
305  }
306  }
307  }
308  }
309  }
310 
311  for (i = 0; i < pb_graph_node->num_output_ports; i++) {
312  for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
313  index = pb_graph_node->output_pins[i][j].pin_count_in_cluster;
314  rr_node[index].pb_graph_pin = &pb_graph_node->output_pins[i][j];
315  rr_node[index].fan_in =
316  pb_graph_node->output_pins[i][j].num_input_edges;
318  pb_graph_node->output_pins[i][j].num_output_edges;
320  + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
321  rr_node[index].edges = (int *) my_malloc(
322  rr_node[index].num_edges * sizeof(int));
323  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
324  sizeof(short));
328  if (mode == 0) { /* Default mode is the first mode */
329  rr_node[index].capacity = 1;
330  } else {
331  rr_node[index].capacity = 0;
332  }
333  for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges;
334  k++) {
335  /* TODO: Intention was to do bus-based implementation here */
336  rr_node[index].edges[k] =
337  pb_graph_node->output_pins[i][j].output_edges[k]->output_pins[0]->pin_count_in_cluster;
338  rr_node[index].switches[k] = arch->num_switches - 1;
339  assert(
340  pb_graph_node->output_pins[i][j].output_edges[k]->num_output_pins == 1);
341  }
343  if (is_primitive) {
345  }
346  }
347  }
348 
349  for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
350  for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
351  index = pb_graph_node->clock_pins[i][j].pin_count_in_cluster;
352  rr_node[index].pb_graph_pin = &pb_graph_node->clock_pins[i][j];
353  rr_node[index].fan_in =
354  pb_graph_node->clock_pins[i][j].num_input_edges;
356  pb_graph_node->clock_pins[i][j].num_output_edges;
358  + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
359  rr_node[index].edges = (int *) my_malloc(
360  rr_node[index].num_edges * sizeof(int));
361  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
362  sizeof(short));
366  if (mode == 0) { /* default mode is the first mode (useful for routing */
367  rr_node[index].capacity = 1;
368  } else {
369  rr_node[index].capacity = 0;
370  }
371  for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges;
372  k++) {
373  /* TODO: Intention was to do bus-based implementation here */
374  rr_node[index].edges[k] =
375  pb_graph_node->clock_pins[i][j].output_edges[k]->output_pins[0]->pin_count_in_cluster;
376  rr_node[index].switches[k] = arch->num_switches - 1;
377  assert(
378  pb_graph_node->clock_pins[i][j].output_edges[k]->num_output_pins == 1);
379  }
381  if (is_primitive) {
382  /* This is a terminating pin, add SINK node */
383  assert(rr_node[index].num_edges == 0);
384  rr_node[index].num_edges = 1;
385  rr_node[index].edges = (int *) my_calloc(rr_node[index].num_edges, sizeof(int));
386  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges, sizeof(short));
388 
389  /* Create SINK node */
394  rr_node[num_rr_nodes].edges = NULL;
395  rr_node[num_rr_nodes].switches = NULL;
401  num_rr_nodes++;
402  }
403  }
404  }
405 
406  for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
407  for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children;
408  j++) {
409  for (k = 0;
410  k
411  < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb;
412  k++) {
414  &pb_graph_node->child_pb_graph_nodes[i][j][k], arch, i);
415  }
416  }
417  }
418 
419 }
420 
422  INP const t_arch *arch) {
423 
424  /**
425  * Structure: Model external routing and internal routing
426  *
427  * 1. Model external routing
428  * num input pins == num external sources for input pins, fully connect them to input pins (simulates external routing)
429  * num output pins == num external sinks for output pins, fully connect them to output pins (simulates external routing)
430  * num clock pins == num external sources for clock pins, fully connect them to clock pins (simulates external routing)
431  * 2. Model internal routing
432  *
433  */
434  /* make each rr_node one correspond with pin and correspond with pin's index pin_count_in_cluster */
435  int i, j, k, m, index, pb_graph_rr_index;
436  int count_pins;
437  t_pb_type * pb_type;
438  t_pb_graph_node *pb_graph_node;
439  int ipin;
440 
441  /* Create rr_graph */
442  pb_type = clb->type->pb_type;
443  pb_graph_node = clb->type->pb_graph_head;
444  num_rr_nodes = pb_graph_node->total_pb_pins + pb_type->num_input_pins
445  + pb_type->num_output_pins + pb_type->num_clock_pins;
446 
447  /* allocate memory for rr_node resources + additional memory for any additional sources/sinks, 2x is an overallocation but guarantees that there will be enough sources/sinks available */
448  rr_node = (t_rr_node *) my_calloc(num_rr_nodes * 2, sizeof(t_rr_node));
449  clb->pb->rr_graph = rr_node;
450 
451  alloc_and_load_rr_graph_for_pb_graph_node(pb_graph_node, arch, 0);
452 
453  curr_cluster_index = clb_index;
454 
455  /* Alloc and load rr_graph external sources and sinks */
456  ext_input_rr_node_index = pb_graph_node->total_pb_pins;
458  + pb_graph_node->total_pb_pins;
460  + pb_graph_node->total_pb_pins;
461  max_ext_index = pb_type->num_input_pins + pb_type->num_output_pins
462  + pb_type->num_clock_pins + pb_graph_node->total_pb_pins;
463 
464  for (i = 0; i < pb_type->num_input_pins; i++) {
465  index = i + pb_graph_node->total_pb_pins;
467  rr_node[index].fan_in = 0;
470  + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
471  rr_node[index].edges = (int *) my_malloc(
472  rr_node[index].num_edges * sizeof(int));
473  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
474  sizeof(int));
475  rr_node[index].capacity = 1;
476  }
477 
478  for (i = 0; i < pb_type->num_output_pins; i++) {
479  index = i + pb_type->num_input_pins + pb_graph_node->total_pb_pins;
480  rr_node[index].type = SINK;
481  rr_node[index].fan_in = pb_type->num_output_pins;
482  rr_node[index].num_edges = 0;
484  + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
485  rr_node[index].capacity = 1;
486  }
487 
488  for (i = 0; i < pb_type->num_clock_pins; i++) {
489  index = i + pb_type->num_input_pins + pb_type->num_output_pins
490  + pb_graph_node->total_pb_pins;
492  rr_node[index].fan_in = 0;
495  + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
496  rr_node[index].edges = (int *) my_malloc(
497  rr_node[index].num_edges * sizeof(int));
498  rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
499  sizeof(int));
500  rr_node[index].capacity = 1;
501  }
502 
503  ipin = 0;
504  for (i = 0; i < pb_graph_node->num_input_ports; i++) {
505  for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
506  pb_graph_rr_index =
507  pb_graph_node->input_pins[i][j].pin_count_in_cluster;
508  for (k = 0; k < pb_type->num_input_pins; k++) {
509  index = k + pb_graph_node->total_pb_pins;
510  rr_node[index].edges[ipin] = pb_graph_rr_index;
511  rr_node[index].switches[ipin] = arch->num_switches - 1;
512  }
513  rr_node[pb_graph_rr_index].pack_intrinsic_cost = MAX_SHORT; /* using an input pin should be made costly */
514  ipin++;
515  }
516  }
517 
518  /* Must attach output pins to input pins because if a connection cannot fit using intra-cluster routing, it can also use external routing */
519  for (i = 0; i < pb_graph_node->num_output_ports; i++) {
520  for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
521  count_pins = pb_graph_node->output_pins[i][j].num_output_edges
522  + pb_type->num_output_pins + pb_type->num_input_pins;
523  pb_graph_rr_index =
524  pb_graph_node->output_pins[i][j].pin_count_in_cluster;
525  rr_node[pb_graph_rr_index].edges = (int *) my_realloc(
526  rr_node[pb_graph_rr_index].edges,
527  (count_pins) * sizeof(int));
528  rr_node[pb_graph_rr_index].switches = (short *) my_realloc(
529  rr_node[pb_graph_rr_index].switches,
530  (count_pins) * sizeof(int));
531 
532  ipin = 0;
533  for (k = 0; k < pb_graph_node->num_input_ports; k++) {
534  for (m = 0; m < pb_graph_node->num_input_pins[k]; m++) {
535  index =
536  pb_graph_node->input_pins[k][m].pin_count_in_cluster;
537  rr_node[pb_graph_rr_index].edges[ipin
538  + pb_graph_node->output_pins[i][j].num_output_edges] =
539  index;
540  rr_node[pb_graph_rr_index].switches[ipin
541  + pb_graph_node->output_pins[i][j].num_output_edges] =
542  arch->num_switches - 1;
543  ipin++;
544  }
545  }
546  for (k = 0; k < pb_type->num_output_pins; k++) {
547  index = k + pb_type->num_input_pins
548  + pb_graph_node->total_pb_pins;
549  rr_node[pb_graph_rr_index].edges[k + pb_type->num_input_pins
550  + pb_graph_node->output_pins[i][j].num_output_edges] =
551  index;
552  rr_node[pb_graph_rr_index].switches[k + pb_type->num_input_pins
553  + pb_graph_node->output_pins[i][j].num_output_edges] =
554  arch->num_switches - 1;
555  }
556  rr_node[pb_graph_rr_index].num_edges += pb_type->num_output_pins
557  + pb_type->num_input_pins;
558  rr_node[pb_graph_rr_index].pack_intrinsic_cost = 1
559  + (float) rr_node[pb_graph_rr_index].num_edges / 5; /* need to normalize better than 5 */
560  }
561  }
562 
563  ipin = 0;
564  for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
565  for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
566  for (k = 0; k < pb_type->num_clock_pins; k++) {
567  index = k + pb_type->num_input_pins + pb_type->num_output_pins
568  + pb_graph_node->total_pb_pins;
569  pb_graph_rr_index =
570  pb_graph_node->clock_pins[i][j].pin_count_in_cluster;
571  rr_node[index].edges[ipin] = pb_graph_rr_index;
572  rr_node[index].switches[ipin] = arch->num_switches - 1;
573  }
574  ipin++;
575  }
576  }
577 
580 
581 }
582 
583 void free_legalizer_for_cluster(INP t_block* clb, boolean free_local_rr_graph) {
584  int i;
585 
587  if(free_local_rr_graph == TRUE) {
588  for (i = 0; i < num_rr_nodes; i++) {
589  if (clb->pb->rr_graph[i].edges != NULL) {
590  free(clb->pb->rr_graph[i].edges);
591  }
592  if (clb->pb->rr_graph[i].switches != NULL) {
593  free(clb->pb->rr_graph[i].switches);
594  }
595  }
596  free(clb->pb->rr_graph);
597  }
598 }
599 
601  int i;
602  for (i = 0; i < num_nets_in_cluster; i++) {
604  trace_head[nets_in_cluster[i]] = best_routing[nets_in_cluster[i]];
605  free_traceback(nets_in_cluster[i]);
606  best_routing[nets_in_cluster[i]] = NULL;
607  }
608 
610  num_nets_in_cluster = 0;
612 }
613 
614 /**
615  *
616  * internal_nets: index of nets to route [0..num_internal_nets - 1]
617  */
619 
620  /* Iterated maze router ala Pathfinder Negotiated Congestion algorithm, *
621  * (FPGA 95 p. 111). Returns TRUE if it can route this FPGA, FALSE if *
622  * it can't. */
623 
624  /* For different modes, when a mode is turned on, I set the max occupancy of all rr_nodes in the mode to 1 and all others to 0 */
625  /* TODO: There is a bug for route-throughs where edges in route-throughs do not get turned off because the rr_edge is in a particular mode but the two rr_nodes are outside */
626 
627  boolean success, is_routable;
628  int itry, inet, net_index;
629  struct s_router_opts router_opts;
630 
631  /* Usually the first iteration uses a very small (or 0) pres_fac to find *
632  * the shortest path and get a congestion map. For fast compiles, I set *
633  * pres_fac high even for the first iteration. */
634 
635  /* sets up a fast breadth-first router */
636  router_opts.first_iter_pres_fac = 10;
637  router_opts.max_router_iterations = 20;
638  router_opts.initial_pres_fac = 10;
639  router_opts.pres_fac_mult = 2;
640  router_opts.acc_fac = 1;
641 
642  reset_rr_node_route_structs(); /* Clear all prior rr_graph history */
643 
644  pres_fac = router_opts.first_iter_pres_fac;
645 
646  for (itry = 1; itry <= router_opts.max_router_iterations; itry++) {
647  for (inet = 0; inet < num_nets_in_cluster; inet++) {
648  net_index = nets_in_cluster[inet];
649 
651 
652  is_routable = breadth_first_route_net_cluster(net_index);
653 
654  /* Impossible to route? (disconnected rr_graph) */
655 
656  if (!is_routable) {
657  /* TODO: Inelegant, can be more intelligent */
658  vpr_printf(TIO_MESSAGE_INFO, "Failed routing net %s\n", vpack_net[net_index].name);
659  vpr_printf(TIO_MESSAGE_INFO, "Routing failed. Disconnected rr_graph.\n");
660  return FALSE;
661  }
662 
664 
665  }
666 
667  success = feasible_routing();
668  if (success) {
669  return (TRUE);
670  }
671 
672  if (itry == 1)
673  pres_fac = router_opts.initial_pres_fac;
674  else
675  pres_fac *= router_opts.pres_fac_mult;
676 
677  pres_fac = std::min(pres_fac, static_cast<float>(HUGE_POSITIVE_FLOAT / 1e5));
678 
680  }
681 
682  return (FALSE);
683 }
684 
685 static boolean breadth_first_route_net_cluster(int inet) {
686 
687  /* Uses a maze routing (Dijkstra's) algorithm to route a net. The net *
688  * begins at the net output, and expands outward until it hits a target *
689  * pin. The algorithm is then restarted with the entire first wire segment *
690  * included as part of the source this time. For an n-pin net, the maze *
691  * router is invoked n-1 times to complete all the connections. Inet is *
692  * the index of the net to be routed. *
693  * If this routine finds that a net *cannot* be connected (due to a complete *
694  * lack of potential paths, rather than congestion), it returns FALSE, as *
695  * routing is impossible on this architecture. Otherwise it returns TRUE. */
696 
697  int i, inode, prev_node, remaining_connections_to_sink;
698  float pcost, new_pcost;
699  struct s_heap *current;
700  struct s_trace *tptr;
701  boolean first_time;
702 
703  free_traceback(inet);
705  mark_ends_cluster(inet);
706 
707  tptr = NULL;
708  remaining_connections_to_sink = 0;
709 
710  for (i = 1; i <= vpack_net[inet].num_sinks; i++) { /* Need n-1 wires to connect n pins */
711 
712  /* Do not connect open terminals */
713  if (net_rr_terminals[inet][i] == OPEN)
714  continue;
715  /* Expand and begin routing */
717  remaining_connections_to_sink);
718  current = get_heap_head();
719 
720  if (current == NULL) { /* Infeasible routing. No possible path for net. */
721  reset_path_costs(); /* Clean up before leaving. */
722  return (FALSE);
723  }
724 
725  inode = current->index;
726 
727  while (rr_node_route_inf[inode].target_flag == 0) {
728  pcost = rr_node_route_inf[inode].path_cost;
729  new_pcost = current->cost;
730  if (pcost > new_pcost) { /* New path is lowest cost. */
731  rr_node_route_inf[inode].path_cost = new_pcost;
732  prev_node = current->u.prev_node;
733  rr_node_route_inf[inode].prev_node = prev_node;
734  rr_node_route_inf[inode].prev_edge = current->prev_edge;
735  first_time = FALSE;
736 
737  if (pcost > 0.99 * HUGE_POSITIVE_FLOAT) /* First time touched. */{
738  add_to_mod_list(&rr_node_route_inf[inode].path_cost);
739  first_time = TRUE;
740  }
741 
742  breadth_first_expand_neighbours_cluster(inode, new_pcost, inet,
743  first_time);
744  }
745 
746  free_heap_data(current);
747  current = get_heap_head();
748 
749  if (current == NULL) { /* Impossible routing. No path for net. */
751  return (FALSE);
752  }
753 
754  inode = current->index;
755  }
756 
757  rr_node_route_inf[inode].target_flag--; /* Connected to this SINK. */
758  remaining_connections_to_sink = rr_node_route_inf[inode].target_flag;
759  tptr = update_traceback(current, inet);
760  free_heap_data(current);
761  }
762 
763  empty_heap();
765  return (TRUE);
766 }
767 
769  struct s_trace *start_ptr, int remaining_connections_to_sink) {
770 
771  /* Adds all the rr_nodes in the traceback segment starting at tptr (and *
772  * continuing to the end of the traceback) to the heap with a cost of zero. *
773  * This allows expansion to begin from the existing wiring. The *
774  * remaining_connections_to_sink value is 0 if the route segment ending *
775  * at this location is the last one to connect to the SINK ending the route *
776  * segment. This is the usual case. If it is not the last connection this *
777  * net must make to this SINK, I have a hack to ensure the next connection *
778  * to this SINK goes through a different IPIN. Without this hack, the *
779  * router would always put all the connections from this net to this SINK *
780  * through the same IPIN. With LUTs or cluster-based logic blocks, you *
781  * should never have a net connecting to two logically-equivalent pins on *
782  * the same logic block, so the hack will never execute. If your logic *
783  * block is an and-gate, however, nets might connect to two and-inputs on *
784  * the same logic block, and since the and-inputs are logically-equivalent, *
785  * this means two connections to the same SINK. */
786 
787  struct s_trace *tptr, *next_ptr;
788  int inode, sink_node, last_ipin_node;
789 
790  tptr = start_ptr;
791 
792  if (remaining_connections_to_sink == 0) { /* Usual case. */
793  while (tptr != NULL) {
795  tptr = tptr->next;
796  }
797  }
798 
799  else { /* This case never executes for most logic blocks. */
800 
801  /* Weird case. Lots of hacks. The cleanest way to do this would be to empty *
802  * the heap, update the congestion due to the partially-completed route, put *
803  * the whole route so far (excluding IPINs and SINKs) on the heap with cost *
804  * 0., and expand till you hit the next SINK. That would be slow, so I *
805  * do some hacks to enable incremental wavefront expansion instead. */
806 
807  if (tptr == NULL)
808  return; /* No route yet */
809 
810  next_ptr = tptr->next;
811  last_ipin_node = OPEN; /* Stops compiler from complaining. */
812 
813  /* Can't put last SINK on heap with NO_PREVIOUS, etc, since that won't let *
814  * us reach it again. Instead, leave the last traceback element (SINK) off *
815  * the heap. */
816 
817  while (next_ptr != NULL) {
818  inode = tptr->index;
820 
821  if (rr_node[inode].type == INTRA_CLUSTER_EDGE)
822  {
823  if(rr_node[inode].pb_graph_pin != NULL && rr_node[inode].pb_graph_pin->num_output_edges == 0)
824  {
825  last_ipin_node = inode;
826  }
827  }
828 
829  tptr = next_ptr;
830  next_ptr = tptr->next;
831  }
832 
833  /* This will stop the IPIN node used to get to this SINK from being *
834  * reexpanded for the remainder of this net's routing. This will make us *
835  * hook up more IPINs to this SINK (which is what we want). If IPIN *
836  * doglegs are allowed in the graph, we won't be able to use this IPIN to *
837  * do a dogleg, since it won't be re-expanded. Shouldn't be a big problem. */
838  assert(last_ipin_node != OPEN);
840 
841  /* Also need to mark the SINK as having high cost, so another connection can *
842  * be made to it. */
843 
844  sink_node = tptr->index;
846 
847  /* Finally, I need to remove any pending connections to this SINK via the *
848  * IPIN I just used (since they would result in congestion). Scan through *
849  * the heap to do this. */
850 
851  invalidate_heap_entries(sink_node, last_ipin_node);
852  }
853 }
854 
855 static void breadth_first_expand_neighbours_cluster(int inode, float pcost,
856  int inet, boolean first_time) {
857 
858  /* Puts all the rr_nodes adjacent to inode on the heap. rr_nodes outside *
859  * the expanded bounding box specified in route_bb are not added to the *
860  * heap. pcost is the path_cost to get to inode. */
861 
862  int iconn, to_node, num_edges;
863  float tot_cost;
864 
865  num_edges = rr_node[inode].num_edges;
866  for (iconn = 0; iconn < num_edges; iconn++) {
867  to_node = rr_node[inode].edges[iconn];
868  /*if (first_time) { */
869  tot_cost = pcost
870  + get_rr_cong_cost(to_node) * rr_node_intrinsic_cost(to_node);
871  /*
872  } else {
873  tot_cost = pcost + get_rr_cong_cost(to_node);
874  }*/
875  node_to_heap(to_node, tot_cost, inode, iconn, OPEN, OPEN);
876  }
877 }
878 
880 
881  /* Adds the SOURCE of this net to the heap. Used to start a net's routing. */
882 
883  int inode;
884  float cost;
885 
886  inode = net_rr_terminals[inet][0]; /* SOURCE */
887  cost = get_rr_cong_cost(inode);
888 
889  node_to_heap(inode, cost, NO_PREVIOUS, NO_PREVIOUS, OPEN, OPEN);
890 }
891 
892 static void mark_ends_cluster(int inet) {
893 
894  /* Mark all the SINKs of this net as targets by setting their target flags *
895  * to the number of times the net must connect to each SINK. Note that *
896  * this number can occassionally be greater than 1 -- think of connecting *
897  * the same net to two inputs of an and-gate (and-gate inputs are logically *
898  * equivalent, so both will connect to the same SINK). */
899 
900  int ipin, inode;
901 
902  for (ipin = 1; ipin <= vpack_net[inet].num_sinks; ipin++) {
903  inode = net_rr_terminals[inet][ipin];
904  if (inode == OPEN)
905  continue;
907  assert(rr_node_route_inf[inode].target_flag > 0 && rr_node_route_inf[inode].target_flag <= rr_node[inode].capacity);
908  }
909 }
910 
912  int inet;
913 
914  net_rr_terminals = (int **) my_malloc(num_logical_nets * sizeof(int *));
916  num_logical_nets * sizeof(int *));
918 
919  for (inet = 0; inet < num_logical_nets; inet++) {
920  net_rr_terminals[inet] = (int *) my_chunk_malloc(
921  (vpack_net[inet].num_sinks + 1) * sizeof(int),
922  &rr_mem_ch);
923 
924  saved_net_rr_terminals[inet] = (int *) my_malloc(
925  (vpack_net[inet].num_sinks + 1) * sizeof(int));
926  }
927 }
928 
930  INP t_pb_graph_node **primitive_list) {
931 
932  /* Allocates and loads the net_rr_terminals data structure. For each net *
933  * it stores the rr_node index of the SOURCE of the net and all the SINKs *
934  * of the net. [0..num_logical_nets-1][0..num_pins-1]. */
935  int i;
936 
937  for (i = 0; i < get_array_size_of_molecule(molecule); i++) {
938  if (molecule->logical_block_ptrs[i] != NULL) {
940  molecule->logical_block_ptrs[i]->index, primitive_list[i]);
941  }
942  }
943 
945 }
946 
948  INP t_pb_graph_node *primitive) {
949 
950  /* Allocates and loads the net_rr_terminals data structure. For each net *
951  * it stores the rr_node index of the SOURCE of the net and all the SINKs *
952  * of the net. [0..num_logical_nets-1][0..num_pins-1]. */
953  int ipin, iblk_net;
954  t_model_ports *port;
955 
956  assert(primitive->pb_type->num_modes == 0);
957  /* check if primitive */
958  assert(logical_block[iblock].clb_index != NO_CLUSTER);
959  /* check if primitive and block is open */
960 
961  /* check if block type matches primitive type */
962  if (logical_block[iblock].model != primitive->pb_type->model) {
963  /* End early, model is incompatible */
964  assert(0);
965  }
966 
967  /* for each net of logical block, check if it is in cluster, if not add it */
968  /* also check if pins on primitive can fit logical block */
969 
970  port = logical_block[iblock].model->inputs;
971 
972  while (port) {
973  for (ipin = 0; ipin < port->size; ipin++) {
974  if (port->is_clock) {
975  assert(port->size == 1);
976  iblk_net = logical_block[iblock].clock_net;
977  } else {
978  iblk_net = logical_block[iblock].input_nets[port->index][ipin];
979  }
980  if (iblk_net == OPEN) {
981  continue;
982  }
983  if (!is_net_in_cluster(iblk_net)) {
986  }
987  add_net_rr_terminal_cluster(iblk_net, primitive, iblock, port,
988  ipin);
989  }
990  port = port->next;
991  }
992 
994  while (port) {
995  for (ipin = 0; ipin < port->size; ipin++) {
996  iblk_net = logical_block[iblock].output_nets[port->index][ipin];
997  if (iblk_net == OPEN) {
998  continue;
999  }
1000  if (!is_net_in_cluster(iblk_net)) {
1003  }
1004  add_net_rr_terminal_cluster(iblk_net, primitive, iblock, port,
1005  ipin);
1006  }
1007  port = port->next;
1008  }
1009 }
1010 
1012 
1013  /* This routing frees any routing currently held in best routing, *
1014  * then copies over the current routing (held in trace_head), and *
1015  * finally sets trace_head and trace_tail to all NULLs so that the *
1016  * connection to the saved routing is broken. This is necessary so *
1017  * that the next iteration of the router does not free the saved *
1018  * routing elements. Also, the routing path costs and net_rr_terminals is stripped from the
1019  * existing rr_graph so that the saved routing does not affect the graph */
1020 
1021  int inet, i, j;
1022  struct s_trace *tempptr;
1024 
1025  for (i = 0; i < num_nets_in_cluster; i++) {
1026  inet = nets_in_cluster[i];
1027  for (j = 0; j <= vpack_net[inet].num_sinks; j++) {
1028  saved_net_rr_terminals[inet][j] = net_rr_terminals[inet][j];
1029  }
1030 
1031  /* Free any previously saved routing. It is no longer best. */
1032  /* Also Save a pointer to the current routing in best_routing. */
1033 
1035  tempptr = trace_head[inet];
1036  trace_head[inet] = best_routing[inet];
1037  free_traceback(inet);
1038  best_routing[inet] = tempptr;
1039 
1040  /* Set the current (working) routing to NULL so the current trace *
1041  * elements won't be reused by the memory allocator. */
1042 
1043  trace_head[inet] = NULL;
1044  trace_tail[inet] = NULL;
1045  }
1046 }
1047 
1049 
1050  /* Deallocates any current routing in trace_head, and replaces it with *
1051  * the routing in best_routing. Best_routing is set to NULL to show that *
1052  * it no longer points to a valid routing. NOTE: trace_tail is not *
1053  * restored -- it is set to all NULLs since it is only used in *
1054  * update_traceback. If you need trace_tail restored, modify this *
1055  * routine. Also restores the locally used opin data. */
1056 
1057  int inet, i, j;
1058 
1059  for (i = 0; i < num_nets_in_cluster; i++) {
1060  inet = nets_in_cluster[i];
1061 
1063 
1064  /* Free any current routing. */
1065  free_traceback(inet);
1066 
1067  /* Set the current routing to the saved one. */
1068  trace_head[inet] = best_routing[inet];
1069  best_routing[inet] = NULL; /* No stored routing. */
1070 
1071  /* restore net terminals */
1072  for (j = 0; j <= vpack_net[inet].num_sinks; j++) {
1073  net_rr_terminals[inet][j] = saved_net_rr_terminals[inet][j];
1074  }
1075 
1076  /* restore old routing */
1078  }
1079  num_nets_in_cluster = saved_num_nets_in_cluster;
1080 }
1081 
1083 
1084  /* This routine updates the occupancy and pres_cost of the rr_nodes that are *
1085  * affected by the portion of the routing of one net that starts at *
1086  * route_segment_start. If route_segment_start is trace_head[inet], the *
1087  * cost of all the nodes in the routing of net inet are updated. If *
1088  * add_or_sub is -1 the net (or net portion) is ripped up, if it is 1 the *
1089  * net is added to the routing. The size of pres_fac determines how severly *
1090  * oversubscribed rr_nodes are penalized. */
1091 
1092  int i, j, net_index;
1093  struct s_trace *tptr, *prev;
1094  int inode;
1095  for (i = 0; i < max_ext_index; i++) {
1096  rr_node[i].net_num = OPEN;
1097  rr_node[i].prev_edge = OPEN;
1098  rr_node[i].prev_node = OPEN;
1099  }
1100  for (i = 0; i < num_nets_in_cluster; i++) {
1101  prev = NULL;
1102  net_index = nets_in_cluster[i];
1103  tptr = trace_head[net_index];
1104  if (tptr == NULL) /* No routing yet. */
1105  return;
1106 
1107  for (;;) {
1108  inode = tptr->index;
1109  rr_node[inode].net_num = net_index;
1110  if (prev != NULL) {
1111  rr_node[inode].prev_node = prev->index;
1112  for (j = 0; j < rr_node[prev->index].num_edges; j++) {
1113  if (rr_node[prev->index].edges[j] == inode) {
1114  rr_node[inode].prev_edge = j;
1115  break;
1116  }
1117  }
1118  assert(j != rr_node[prev->index].num_edges);
1119  } else {
1120  rr_node[inode].prev_node = OPEN;
1121  rr_node[inode].prev_edge = OPEN;
1122  }
1123 
1124  if (rr_node[inode].type == SINK) {
1125  tptr = tptr->next; /* Skip next segment. */
1126  if (tptr == NULL)
1127  break;
1128  }
1129 
1130  prev = tptr;
1131  tptr = tptr->next;
1132 
1133  } /* End while loop -- did an entire traceback. */
1134  }
1135 }
1136 
1137 boolean is_pin_open(int i) {
1138  return (boolean) (rr_node[i].occ == 0);
1139 }
1140 
1141 static float rr_node_intrinsic_cost(int inode) {
1142  /* This is a tie breaker to avoid using nodes with more edges whenever possible */
1143  float value;
1144  value = rr_node[inode].pack_intrinsic_cost;
1145  return value;
1146 }
1147 
1148 /* turns on mode for a pb by setting capacity of its rr_nodes to 1 */
1149 void set_pb_graph_mode(t_pb_graph_node *pb_graph_node, int mode, int isOn) {
1150  int i, j, index;
1151  int i_pb_type, i_pb_inst;
1152  const t_pb_type *pb_type;
1153 
1154  pb_type = pb_graph_node->pb_type;
1155  for (i_pb_type = 0; i_pb_type < pb_type->modes[mode].num_pb_type_children;
1156  i_pb_type++) {
1157  for (i_pb_inst = 0;
1158  i_pb_inst
1159  < pb_type->modes[mode].pb_type_children[i_pb_type].num_pb;
1160  i_pb_inst++) {
1161  for (i = 0;
1162  i
1163  < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_input_ports;
1164  i++) {
1165  for (j = 0;
1166  j
1167  < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_input_pins[i];
1168  j++) {
1169  index =
1170  pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].input_pins[i][j].pin_count_in_cluster;
1171  rr_node[index].capacity = isOn;
1172  }
1173  }
1174 
1175  for (i = 0;
1176  i
1177  < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_output_ports;
1178  i++) {
1179  for (j = 0;
1180  j
1181  < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_output_pins[i];
1182  j++) {
1183  index =
1184  pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].output_pins[i][j].pin_count_in_cluster;
1185  rr_node[index].capacity = isOn;
1186  }
1187  }
1188 
1189  for (i = 0;
1190  i
1191  < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_clock_ports;
1192  i++) {
1193  for (j = 0;
1194  j
1195  < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_clock_pins[i];
1196  j++) {
1197  index =
1198  pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].clock_pins[i][j].pin_count_in_cluster;
1199  rr_node[index].capacity = isOn;
1200  }
1201  }
1202  }
1203  }
1204 }
1205 
1206 /* If this is done post place and route, use the cb pins determined by place-and-route rather than letting the legalizer freely determine */
1208  int i, j, k, ipin, net_index, ext_net;
1209  int pin_offset;
1210  boolean has_ext_source, success;
1211  int curr_ext_output, curr_ext_input, curr_ext_clock;
1212  t_pb_graph_node *pb_graph_node;
1213 
1214  pb_graph_node = block[iblock].pb->pb_graph_node;
1215  pin_offset = block[iblock].z * (pb_graph_node->pb_type->num_input_pins + pb_graph_node->pb_type->num_output_pins + pb_graph_node->pb_type->num_clock_pins);
1216 
1217  curr_ext_input = ext_input_rr_node_index;
1218  curr_ext_output = ext_output_rr_node_index;
1219  curr_ext_clock = ext_clock_rr_node_index;
1220 
1221  for (i = 0; i < num_nets_in_cluster; i++) {
1222  net_index = nets_in_cluster[i];
1223  has_ext_source = (boolean)
1224  (logical_block[vpack_net[net_index].node_block[0]].clb_index
1225  != curr_cluster_index);
1226  if(has_ext_source) {
1227  ext_net = vpack_to_clb_net_mapping[net_index];
1228  assert(ext_net != OPEN);
1229  if (vpack_net[net_index].is_global) {
1230  free(rr_node[curr_ext_clock].edges);
1231  rr_node[curr_ext_clock].edges = NULL;
1232  rr_node[curr_ext_clock].num_edges = 0;
1233 
1234  success = FALSE;
1235  ipin = 0;
1236  /* force intra-cluster net to use pins from ext route */
1237  for(j = 0; j < pb_graph_node->num_clock_ports; j++) {
1238  for(k = 0; k < pb_graph_node->num_clock_pins[j]; k++) {
1239  if(ext_net == block[iblock].nets[ipin + pb_graph_node->pb_type->num_input_pins + pb_graph_node->pb_type->num_output_pins + pin_offset]) {
1240  success = TRUE;
1241  rr_node[curr_ext_clock].num_edges++;
1242  rr_node[curr_ext_clock].edges = (int*)my_realloc(rr_node[curr_ext_clock].edges, rr_node[curr_ext_clock].num_edges * sizeof(int));
1243  rr_node[curr_ext_clock].edges[rr_node[curr_ext_clock].num_edges - 1] = pb_graph_node->clock_pins[j][k].pin_count_in_cluster;
1244  }
1245  ipin++;
1246  }
1247  }
1248  assert(success);
1249  curr_ext_clock++;
1250  } else {
1251  free(rr_node[curr_ext_input].edges);
1252  rr_node[curr_ext_input].edges = NULL;
1253  rr_node[curr_ext_input].num_edges = 0;
1254 
1255  success = FALSE;
1256  ipin = 0;
1257  /* force intra-cluster net to use pins from ext route */
1258  for(j = 0; j < pb_graph_node->num_input_ports; j++) {
1259  for(k = 0; k < pb_graph_node->num_input_pins[j]; k++) {
1260  if(ext_net == block[iblock].nets[ipin + pin_offset]) {
1261  success = TRUE;
1262  rr_node[curr_ext_input].num_edges++;
1263  rr_node[curr_ext_input].edges = (int*)my_realloc(rr_node[curr_ext_input].edges, rr_node[curr_ext_input].num_edges * sizeof(int));
1264  rr_node[curr_ext_input].edges[rr_node[curr_ext_input].num_edges - 1] = pb_graph_node->input_pins[j][k].pin_count_in_cluster;
1265  }
1266  ipin++;
1267  }
1268  }
1269  curr_ext_input++;
1270  assert(success);
1271  }
1272  }
1273  }
1274 }
1275 
int * node_block_pin
Definition: vpr_types.h:509
boolean feasible_routing(void)
Definition: route_common.c:298
boolean is_clock
Definition: util.h:57
short num_edges
Definition: vpr_types.h:901
int index
Definition: route_common.h:4
t_pb_graph_pin ** clock_pins
static void alloc_net_rr_terminals_cluster(void)
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
static void add_net_rr_terminal_cluster(int iblk_net, t_pb_graph_node *primitive, int ilogical_block, t_model_ports *model_port, int ipin)
t_model_ports * model_port
int ** input_nets
Definition: vpr_types.h:211
struct s_trace ** trace_tail
Definition: globals.c:65
struct s_pb_type * pb_type_children
void free_cluster_legality_checker(void)
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 net_num
Definition: vpr_types.h:917
int prev_node
Definition: route_common.h:7
void free_legalizer_for_cluster(INP t_block *clb, boolean free_local_rr_graph)
t_rr_node_route_inf * rr_node_route_inf
Definition: route_common.c:21
static float rr_node_intrinsic_cost(int inode)
boolean
Definition: util.h:11
t_rr_indexed_data * rr_indexed_data
Definition: globals.c:74
t_mode * modes
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
static void breadth_first_expand_trace_segment_cluster(struct s_trace *start_ptr, int remaining_connections_to_sink)
float first_iter_pres_fac
Definition: vpr_types.h:696
int num_rr_indexed_data
Definition: globals.c:73
void restore_routing_cluster(void)
void * my_chunk_malloc(size_t size, t_chunk *chunk_info)
Definition: util.c:184
int prev_node
Definition: vpr_types.h:915
void alloc_and_load_rr_graph_for_pb_graph_node(INP t_pb_graph_node *pb_graph_node, INP const t_arch *arch, int mode)
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
struct s_model_ports * next
Definition: logic_types.h:28
void free_trace_structs(void)
Definition: route_common.c:733
enum PORTS type
void pathfinder_update_cost(float pres_fac, float acc_fac)
Definition: route_common.c:363
int num_nets
Definition: globals.c:27
void reload_ext_net_rr_terminal_cluster(void)
int num_logical_nets
Definition: globals.c:17
void force_post_place_route_cb_input_pins(int iblock)
t_pb_graph_pin ** output_pins
boolean is_clock
Definition: logic_types.h:26
#define MAX_SHORT
Definition: vpr_types.h:75
void reset_legalizer_for_cluster(t_block *clb)
Definition: util.h:12
void reset_path_costs(void)
Definition: route_common.c:490
static float pres_fac
void setup_intracluster_routing_for_molecule(INP t_pack_molecule *molecule, INP t_pb_graph_node **primitive_list)
boolean try_breadth_first_route_cluster(void)
#define min(a, b)
Definition: graphics.c:174
void save_and_reset_routing_cluster(void)
void set_pb_graph_mode(t_pb_graph_node *pb_graph_node, int mode, int isOn)
union s_heap::@0 u
#define HUGE_POSITIVE_FLOAT
Definition: vpr_types.h:79
struct s_trace * next
Definition: vpr_types.h:870
static void * my_malloc(int ibytes)
Definition: graphics.c:499
int get_array_size_of_molecule(t_pack_molecule *molecule)
boolean * is_global
void alloc_and_load_rr_node_route_structs(void)
Definition: route_common.c:785
int * vpack_to_clb_net_mapping
Definition: globals.c:34
#define NO_CLUSTER
Definition: vpr_types.h:98
int prev_edge
Definition: route_common.h:10
struct s_block * block
Definition: globals.c:31
#define INP
Definition: util.h:19
int num_rr_nodes
Definition: globals.c:69
float initial_pres_fac
Definition: vpr_types.h:697
struct s_trace ** trace_head
Definition: globals.c:64
t_model_ports * inputs
Definition: logic_types.h:35
static int num_nets_in_cluster
static void breadth_first_expand_neighbours_cluster(int inode, float pcost, int inet, boolean first_time)
t_model_ports * outputs
Definition: logic_types.h:36
short capacity
Definition: vpr_types.h:899
struct s_pb_graph_node *** child_pb_graph_nodes
int num_pb_type_children
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
void alloc_route_static_structs(void)
Definition: route_common.c:623
static char * model
Definition: read_blif.c:45
boolean is_pin_open(int i)
short fan_in
Definition: vpr_types.h:900
static boolean breadth_first_route_net_cluster(int inet)
int iblock
Definition: vpr_types.h:868
void pathfinder_update_one_cost(struct s_trace *route_segment_start, int add_or_sub, float pres_fac)
Definition: route_common.c:315
static boolean is_net_in_cluster(INP int inet)
struct s_pb_type * pb_type
void reset_rr_node_route_structs(void)
Definition: route_common.c:809
struct s_trace * update_traceback(struct s_heap *hptr, int inet)
Definition: route_common.c:421
static int ext_output_rr_node_index
short * switches
Definition: vpr_types.h:904
static int ext_input_rr_node_index
static void * my_realloc(void *memblk, int ibytes)
Definition: graphics.c:512
static int * nets_in_cluster
static int curr_cluster_index
t_pb_graph_pin * pb_graph_pin
Definition: vpr_types.h:918
void setup_intracluster_routing_for_logical_block(INP int iblock, INP t_pb_graph_node *primitive)
t_port * ports
void add_to_mod_list(float *fptr)
Definition: route_common.c:898
Definition: slre.c:50
static int max_ext_index
t_pb * pb
Definition: vpr_types.h:567
float acc_fac
Definition: vpr_types.h:699
void free_rr_node_route_structs(void)
Definition: route_common.c:828
float pack_intrinsic_cost
Definition: vpr_types.h:920
int ** net_rr_terminals
Definition: globals.c:78
int z
Definition: vpr_types.h:565
struct s_net * vpack_net
Definition: globals.c:19
static void mark_ends_cluster(int inet)
int prev_edge
Definition: vpr_types.h:916
void empty_heap(void)
Definition: route_common.c:991
static int ** saved_net_rr_terminals
void free_chunk_memory(t_chunk *chunk_info)
Definition: util.c:270
t_model * model
Definition: vpr_types.h:209
int num_output_pins
static void breadth_first_add_source_to_heap_cluster(int inet)
static int saved_num_nets_in_cluster
void alloc_and_load_legalizer_for_cluster(INP t_block *clb, INP int clb_index, INP const t_arch *arch)
void free_route_structs()
Definition: route_common.c:750
int ** output_nets
Definition: vpr_types.h:212
void save_cluster_solution(void)
messagelogger vpr_printf
Definition: util.c:17
t_pb_graph_node * pb_graph_node
Definition: vpr_types.h:180
int num_sinks
Definition: vpr_types.h:506
int num_input_pins
static int ext_clock_rr_node_index
void alloc_and_load_cluster_legality_checker(void)
static t_chunk rr_mem_ch
short occ
Definition: vpr_types.h:898
t_rr_type type
Definition: vpr_types.h:902
t_pb_graph_pin ** input_pins
struct s_logical_block * logical_block
Definition: globals.c:20
int num_clock_pins
Definition: util.h:12
static struct s_trace ** best_routing