VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
rr_graph.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include <math.h>
3 #include <assert.h>
4 #include <string.h>
5 #include "util.h"
6 #include "vpr_types.h"
7 #include "globals.h"
8 #include "rr_graph_util.h"
9 #include "rr_graph.h"
10 #include "rr_graph2.h"
11 #include "rr_graph_sbox.h"
12 #include "check_rr_graph.h"
13 #include "rr_graph_timing_params.h"
14 #include "rr_graph_indexed_data.h"
15 #include "vpr_utils.h"
16 #include "read_xml_arch_file.h"
17 #include "ReadOptions.h"
18 
19 /* #define ENABLE_DUMP */
20 /* #define MUX_SIZE_DIST_DISPLAY */
21 
22 /* mux size statistic data structures */
23 
24 typedef struct s_mux {
25  int size;
26  struct s_mux *next;
27 } t_mux;
28 
29 typedef struct s_mux_size_distribution {
30  int mux_count;
31  int max_index;
32  int *distr;
35 
36 typedef struct s_clb_to_clb_directs {
44 
45 /* UDSD Modifications by WMF End */
46 
47 /******************* Variables local to this module. ***********************/
48 
49 /* Used to free "chunked" memory. If NULL, no rr_graph exists right now. */
50 static t_chunk rr_mem_ch = {NULL, 0, NULL};
51 
52 /* Status of current chunk being dished out by calls to my_chunk_malloc. */
53 
54 /********************* Subroutines local to this module. *******************/
55 static int ****alloc_and_load_pin_to_track_map(INP enum e_pin_type pin_type,
56  INP int nodes_per_chan, INP int *Fc, INP t_type_ptr Type,
57  INP boolean perturb_switch_pattern,
58  INP enum e_directionality directionality);
59 
61  INP int ****pin_to_track_map, INP int *Fc, INP int height,
62  INP int num_pins, INP int nodes_per_chan);
63 
64 static void build_bidir_rr_opins(INP int i, INP int j,
65  INOUTP t_rr_node * L_rr_node, INP t_ivec *** L_rr_node_indices,
66  INP int *****opin_to_track_map, INP int **Fc_out,
67  INP boolean * L_rr_edge_done, INP t_seg_details * seg_details,
68  INP struct s_grid_tile **L_grid, INP int delayless_switch,
69  INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs);
70 
71 static void build_unidir_rr_opins(INP int i, INP int j,
72  INP struct s_grid_tile **L_grid, INP int **Fc_out,
73  INP int nodes_per_chan, INP t_seg_details * seg_details,
74  INOUTP int **Fc_xofs, INOUTP int **Fc_yofs,
75  INOUTP t_rr_node * L_rr_node, INOUTP boolean * L_rr_edge_done,
76  OUTP boolean * Fc_clipped, INP t_ivec *** L_rr_node_indices, INP int delayless_switch,
77  INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs);
78 
79 static int get_opin_direct_connecions(int x, int y, int opin, INOUTP t_linked_edge ** edge_list_ptr, INP t_ivec *** L_rr_node_indices,
80  INP int delayless_switch, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs);
81 
82 static void alloc_and_load_rr_graph(INP int num_nodes,
83  INP t_rr_node * L_rr_node, INP int num_seg_types,
84  INP t_seg_details * seg_details, INP boolean * L_rr_edge_done,
85  INP struct s_ivec ****track_to_ipin_lookup,
86  INP int *****opin_to_track_map, INP struct s_ivec ***switch_block_conn,
87  INP struct s_grid_tile **L_grid, INP int L_nx, INP int L_ny, INP int Fs,
88  INP short *****sblock_pattern, INP int **Fc_out, INP int **Fc_xofs,
89  INP int **Fc_yofs, INP t_ivec *** L_rr_node_indices,
90  INP int nodes_per_chan, INP enum e_switch_block_type sb_type,
91  INP int delayless_switch, INP enum e_directionality directionality,
92  INP int wire_to_ipin_switch, OUTP boolean * Fc_clipped, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs);
93 
95  INOUTP int ****tracks_connected_to_pin, INP int num_phys_pins,
96  INP int *pin_num_ordering, INP int *side_ordering,
97  INP int *offset_ordering, INP int nodes_per_chan, INP int Fc,
98  INP enum e_directionality directionality);
99 
101  INOUTP int ****tracks_connected_to_pin, INP int num_phys_pins,
102  INP int *pin_num_ordering, INP int *side_ordering,
103  INP int *offset_ordering, INP int nodes_per_chan, INP int Fc,
104  INP enum e_directionality directionality);
105 
106 static void check_all_tracks_reach_pins(t_type_ptr type,
107  int ****tracks_connected_to_pin, int nodes_per_chan, int Fc,
108  enum e_pin_type ipin_or_opin);
109 
110 static boolean *alloc_and_load_perturb_ipins(INP int nodes_per_chan,
111  INP int L_num_types, INP int **Fc_in, INP int **Fc_out,
112  INP enum e_directionality directionality);
113 
114 static void build_rr_sinks_sources(INP int i, INP int j,
115  INP t_rr_node * L_rr_node, INP t_ivec *** L_rr_node_indices,
116  INP int delayless_switch, INP struct s_grid_tile **L_grid);
117 
118 static void build_rr_xchan(INP int i, INP int j,
119  INP struct s_ivec ****track_to_ipin_lookup,
120  INP struct s_ivec ***switch_block_conn, INP int cost_index_offset,
121  INP int nodes_per_chan, INP int *opin_mux_size,
122  INP short *****sblock_pattern, INP int Fs_per_side,
123  INP t_seg_details * seg_details, INP t_ivec *** L_rr_node_indices,
124  INP boolean * L_rr_edge_done, INOUTP t_rr_node * L_rr_node,
125  INP int wire_to_ipin_switch, INP enum e_directionality directionality);
126 
127 static void build_rr_ychan(INP int i, INP int j,
128  INP struct s_ivec ****track_to_ipin_lookup,
129  INP struct s_ivec ***switch_block_conn, INP int cost_index_offset,
130  INP int nodes_per_chan, INP int *opin_mux_size,
131  INP short *****sblock_pattern, INP int Fs_per_side,
132  INP t_seg_details * seg_details, INP t_ivec *** L_rr_node_indices,
133  INP boolean * L_rr_edge_done, INOUTP t_rr_node * L_rr_node,
134  INP int wire_to_ipin_switch, INP enum e_directionality directionality);
135 
136 static void rr_graph_externals(t_timing_inf timing_inf,
137  t_segment_inf * segment_inf, int num_seg_types, int nodes_per_chan,
138  int wire_to_ipin_switch, enum e_base_cost_type base_cost_type);
139 
140 void alloc_and_load_edges_and_switches(INP t_rr_node * L_rr_node, INP int inode,
141  INP int num_edges, INP boolean * L_rr_edge_done,
142  INP t_linked_edge * edge_list_head);
143 
144 static void alloc_net_rr_terminals(void);
145 
146 static void alloc_and_load_rr_clb_source(t_ivec *** L_rr_node_indices);
147 
149 
150 #if 0
151 static void load_uniform_opin_switch_pattern_paired(INP int *Fc_out,
152  INP int num_pins,
153  INP int *pins_in_chan_seg,
154  INP int num_wire_inc_muxes,
155  INP int num_wire_dec_muxes,
156  INP int *wire_inc_muxes,
157  INP int *wire_dec_muxes,
158  INOUTP t_rr_node * L_rr_node,
159  INOUTP boolean *
160  L_rr_edge_done,
162  seg_details,
163  OUTP boolean * Fc_clipped);
164 #endif
165 void watch_edges(int inode, t_linked_edge * edge_list_head);
166 #if MUX_SIZE_DIST_DISPLAY
167 static void view_mux_size_distribution(t_ivec *** L_rr_node_indices,
168  int nodes_per_chan,
169  t_seg_details * seg_details_x,
170  t_seg_details * seg_details_y);
171 static void print_distribution(FILE * fptr,
172  t_mux_size_distribution * distr_struct);
173 #endif
174 
175 static void free_type_pin_to_track_map(int***** ipin_to_track_map,
176  t_type_ptr types);
177 
178 static void free_type_track_to_ipin_map(struct s_ivec**** track_to_pin_map,
179  t_type_ptr types, int nodes_per_chan);
180 
182  INP int nodes_per_chan, INP int global_route_switch);
183 
184 /* UDSD Modifications by WMF End */
185 
186 static int **alloc_and_load_actual_fc(INP int L_num_types, INP t_type_ptr types,
187  INP int nodes_per_chan, INP boolean is_Fc_out,
188  INP enum e_directionality directionality, OUTP boolean * Fc_clipped, INP boolean ignore_Fc_0);
189 
190 /******************* Subroutine definitions *******************************/
191 
192 void build_rr_graph(INP t_graph_type graph_type, INP int L_num_types,
193  INP t_type_ptr types, INP int L_nx, INP int L_ny,
194  INP struct s_grid_tile **L_grid, INP int chan_width,
195  INP struct s_chan_width_dist *chan_capacity_inf,
196  INP enum e_switch_block_type sb_type, INP int Fs, INP int num_seg_types,
197  INP int num_switches, INP t_segment_inf * segment_inf,
198  INP int global_route_switch, INP int delayless_switch,
199  INP t_timing_inf timing_inf, INP int wire_to_ipin_switch,
200  INP enum e_base_cost_type base_cost_type, INP t_direct_inf *directs,
201  INP int num_directs, INP boolean ignore_Fc_0, OUTP int *Warnings) {
202  /* Temp structures used to build graph */
203  int nodes_per_chan, i, j;
204  t_seg_details *seg_details = NULL;
205  int **Fc_in = NULL; /* [0..num_types-1][0..num_pins-1] */
206  int **Fc_out = NULL; /* [0..num_types-1][0..num_pins-1] */
207 
208  int *****opin_to_track_map = NULL; /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
209  int *****ipin_to_track_map = NULL; /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
210  t_ivec ****track_to_ipin_lookup = NULL; /* [0..num_types-1][0..nodes_per_chan-1][0..height][0..3] */
211  t_ivec ***switch_block_conn = NULL;
212  short *****unidir_sb_pattern = NULL;
213  boolean *L_rr_edge_done = NULL;
214  boolean is_global_graph;
215  boolean Fc_clipped;
216  boolean use_full_seg_groups;
217  boolean *perturb_ipins = NULL;
218  enum e_directionality directionality;
219  int **Fc_xofs = NULL; /* [0..ny-1][0..nx-1] */
220  int **Fc_yofs = NULL; /* [0..nx-1][0..ny-1] */
221  t_clb_to_clb_directs *clb_to_clb_directs;
222 
223  rr_node_indices = NULL;
224  rr_node = NULL;
225  num_rr_nodes = 0;
226 
227  /* Reset warning flag */
228  *Warnings = RR_GRAPH_NO_WARN;
229 
230  /* Decode the graph_type */
231  is_global_graph = FALSE;
232  if (GRAPH_GLOBAL == graph_type) {
233  is_global_graph = TRUE;
234  }
235  use_full_seg_groups = FALSE;
236  if (GRAPH_UNIDIR_TILEABLE == graph_type) {
237  use_full_seg_groups = TRUE;
238  }
239  directionality = UNI_DIRECTIONAL;
240  if (GRAPH_BIDIR == graph_type) {
241  directionality = BI_DIRECTIONAL;
242  }
243  if (is_global_graph) {
244  directionality = BI_DIRECTIONAL;
245  }
246 
247  /* Global routing uses a single longwire track */
248  nodes_per_chan = (is_global_graph ? 1 : chan_width);
249  assert(nodes_per_chan > 0);
250 
251  clb_to_clb_directs = NULL;
252  if(num_directs > 0) {
253  clb_to_clb_directs = alloc_and_load_clb_to_clb_directs(directs, num_directs);
254  }
255 
256  /* START SEG_DETAILS */
257  if (is_global_graph) {
258  /* Sets up a single unit length segment type for global routing. */
259  seg_details = alloc_and_load_global_route_seg_details(nodes_per_chan,
260  global_route_switch);
261  } else {
262  /* Setup segments including distrubuting tracks and staggering.
263  * If use_full_seg_groups is specified, nodes_per_chan may be
264  * changed. Warning should be singled to caller if this happens. */
265  seg_details = alloc_and_load_seg_details(&nodes_per_chan,
266  std::max(L_nx, L_ny), num_seg_types, segment_inf,
267  use_full_seg_groups, is_global_graph, directionality);
268  if ((is_global_graph ? 1 : chan_width) != nodes_per_chan) {
270  }
272  dump_seg_details(seg_details, nodes_per_chan,
274  } else
275  ;
276  }
277  /* END SEG_DETAILS */
278 
279  /* START FC */
280  /* Determine the actual value of Fc */
281  if (is_global_graph) {
282  Fc_in = (int **) my_malloc(sizeof(int) * L_num_types);
283  Fc_out = (int **) my_malloc(sizeof(int) * L_num_types);
284  for (i = 0; i < L_num_types; ++i) {
285  for (j = 0; j < types[i].num_pins; ++j) {
286  Fc_in[i][j] = 1;
287  Fc_out[i][j] = 1;
288  }
289  }
290  } else {
291  Fc_clipped = FALSE;
292  Fc_in = alloc_and_load_actual_fc(L_num_types, types, nodes_per_chan,
293  FALSE, directionality, &Fc_clipped, ignore_Fc_0);
294  if (Fc_clipped) {
295  *Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
296  }
297  Fc_clipped = FALSE;
298  Fc_out = alloc_and_load_actual_fc(L_num_types, types, nodes_per_chan,
299  TRUE, directionality, &Fc_clipped, ignore_Fc_0);
300  if (Fc_clipped) {
301  *Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
302  }
303 
304 #ifdef VERBOSE
305  for (i = 1; i < L_num_types; ++i) { /* Skip "<EMPTY>" */
306  for (j = 0; j < type_descriptors[i].num_pins; ++j) {
307  if (type_descriptors[i].is_Fc_full_flex[j]) {
308  vpr_printf(TIO_MESSAGE_INFO, "Fc Actual Values: type = %s, Fc_out = full, Fc_in = %d.\n",
309  type_descriptors[i].name, Fc_in[i][j]);
310  }
311  else {
312  vpr_printf(TIO_MESSAGE_INFO, "Fc Actual Values: type = %s, Fc_out = %d, Fc_in = %d.\n",
313  type_descriptors[i].name, Fc_out[i][j], Fc_in[i][j]);
314  }
315  }
316  }
317 #endif /* VERBOSE */
318  }
319 
320  perturb_ipins = alloc_and_load_perturb_ipins(nodes_per_chan, L_num_types,
321  Fc_in, Fc_out, directionality);
322  /* END FC */
323 
324  /* Alloc node lookups, count nodes, alloc rr nodes */
325  num_rr_nodes = 0;
326  rr_node_indices = alloc_and_load_rr_node_indices(nodes_per_chan, L_nx, L_ny,
327  &num_rr_nodes, seg_details);
329  memset(rr_node, 0, sizeof(t_rr_node) * num_rr_nodes);
330  L_rr_edge_done = (boolean *) my_malloc(sizeof(boolean) * num_rr_nodes);
331  memset(L_rr_edge_done, 0, sizeof(boolean) * num_rr_nodes);
332 
333  /* These are data structures used by the the unidir opin mapping. */
334  if (UNI_DIRECTIONAL == directionality) {
335  Fc_xofs = (int **) alloc_matrix(0, L_ny, 0, L_nx, sizeof(int));
336  Fc_yofs = (int **) alloc_matrix(0, L_nx, 0, L_ny, sizeof(int));
337  for (i = 0; i <= L_nx; ++i) {
338  for (j = 0; j <= L_ny; ++j) {
339  Fc_xofs[j][i] = 0;
340  Fc_yofs[i][j] = 0;
341  }
342  }
343  }
344 
345  /* START SB LOOKUP */
346  /* Alloc and load the switch block lookup */
347  if (is_global_graph) {
348  assert(nodes_per_chan == 1);
349  switch_block_conn = alloc_and_load_switch_block_conn(1, SUBSET, 3);
350  } else if (BI_DIRECTIONAL == directionality) {
351  switch_block_conn = alloc_and_load_switch_block_conn(nodes_per_chan,
352  sb_type, Fs);
353  } else {
354  assert(UNI_DIRECTIONAL == directionality);
355 
356  unidir_sb_pattern = alloc_sblock_pattern_lookup(L_nx, L_ny,
357  nodes_per_chan);
358  for (i = 0; i <= L_nx; i++) {
359  for (j = 0; j <= L_ny; j++) {
360  load_sblock_pattern_lookup(i, j, nodes_per_chan, seg_details,
361  Fs, sb_type, unidir_sb_pattern);
362  }
363  }
364  }
365  /* END SB LOOKUP */
366 
367  /* START IPINP MAP */
368  /* Create ipin map lookups */
369  ipin_to_track_map = (int *****) my_malloc(sizeof(int ****) * L_num_types);
370  track_to_ipin_lookup = (struct s_ivec ****) my_malloc(
371  sizeof(struct s_ivec ***) * L_num_types);
372  for (i = 0; i < L_num_types; ++i) {
373  ipin_to_track_map[i] = alloc_and_load_pin_to_track_map(RECEIVER,
374  nodes_per_chan, Fc_in[i], &types[i], perturb_ipins[i],
375  directionality);
376  track_to_ipin_lookup[i] = alloc_and_load_track_to_pin_lookup(
377  ipin_to_track_map[i], Fc_in[i], types[i].height,
378  types[i].num_pins, nodes_per_chan);
379  }
380  /* END IPINP MAP */
381 
382  /* START OPINP MAP */
383  /* Create opin map lookups */
384  if (BI_DIRECTIONAL == directionality) {
385  opin_to_track_map = (int *****) my_malloc(
386  sizeof(int ****) * L_num_types);
387  for (i = 0; i < L_num_types; ++i) {
388  opin_to_track_map[i] = alloc_and_load_pin_to_track_map(DRIVER,
389  nodes_per_chan, Fc_out[i], &types[i], FALSE, directionality);
390  }
391  }
392  /* END OPINP MAP */
393 
394  /* UDSD Modifications by WMF begin */
395  /* I'm adding 2 new fields to t_rr_node, and I want them initialized to 0. */
396  for (i = 0; i < num_rr_nodes; i++) {
397  rr_node[i].num_wire_drivers = 0;
398  rr_node[i].num_opin_drivers = 0;
399  }
400 
401  alloc_and_load_rr_graph(num_rr_nodes, rr_node, num_seg_types, seg_details,
402  L_rr_edge_done, track_to_ipin_lookup, opin_to_track_map,
403  switch_block_conn, L_grid, L_nx, L_ny, Fs, unidir_sb_pattern,
404  Fc_out, Fc_xofs, Fc_yofs, rr_node_indices, nodes_per_chan, sb_type,
405  delayless_switch, directionality, wire_to_ipin_switch, &Fc_clipped, directs, num_directs, clb_to_clb_directs);
406 
407 #ifdef MUX_SIZE_DIST_DISPLAY
408  if (UNI_DIRECTIONAL == directionality)
409  {
410  view_mux_size_distribution(rr_node_indices, nodes_per_chan,
411  seg_details, seg_details);
412  }
413 #endif
414 
415  /* Update rr_nodes capacities if global routing */
416  if (graph_type == GRAPH_GLOBAL) {
417  for (i = 0; i < num_rr_nodes; i++) {
418  if (rr_node[i].type == CHANX || rr_node[i].type == CHANY) {
419  rr_node[i].capacity = chan_width;
420  }
421  }
422  }
423 
424  rr_graph_externals(timing_inf, segment_inf, num_seg_types, nodes_per_chan,
425  wire_to_ipin_switch, base_cost_type);
428  } else
429  ;
430 
431  check_rr_graph(graph_type, types, L_nx, L_ny, nodes_per_chan, Fs,
432  num_seg_types, num_switches, segment_inf, global_route_switch,
433  delayless_switch, wire_to_ipin_switch, seg_details, Fc_in, Fc_out,
434  opin_to_track_map, ipin_to_track_map, track_to_ipin_lookup,
435  switch_block_conn, perturb_ipins);
436 
437  /* Free all temp structs */
438  if (seg_details) {
439  free_seg_details(seg_details, nodes_per_chan);
440  seg_details = NULL;
441  }
442  if (Fc_in) {
443  free_matrix(Fc_in,0, L_num_types, 0, sizeof(int));
444  Fc_in = NULL;
445  }
446  if (Fc_out) {
447  free_matrix(Fc_out,0, L_num_types, 0, sizeof(int));
448  Fc_out = NULL;
449  }
450  if (perturb_ipins) {
451  free(perturb_ipins);
452  perturb_ipins = NULL;
453  }
454  if (switch_block_conn) {
455  free_switch_block_conn(switch_block_conn, nodes_per_chan);
456  switch_block_conn = NULL;
457  }
458  if (L_rr_edge_done) {
459  free(L_rr_edge_done);
460  L_rr_edge_done = NULL;
461  }
462  if (Fc_xofs) {
463  free_matrix(Fc_xofs, 0, L_ny, 0, sizeof(int));
464  Fc_xofs = NULL;
465  }
466  if (Fc_yofs) {
467  free_matrix(Fc_yofs, 0, L_nx, 0, sizeof(int));
468  Fc_yofs = NULL;
469  }
470  if (unidir_sb_pattern) {
471  free_sblock_pattern_lookup(unidir_sb_pattern);
472  unidir_sb_pattern = NULL;
473  }
474  if (opin_to_track_map) {
475  for (i = 0; i < L_num_types; ++i) {
476  free_matrix4(opin_to_track_map[i], 0, types[i].num_pins - 1, 0,
477  types[i].height - 1, 0, 3, 0, sizeof(int));
478  }
479  free(opin_to_track_map);
480  }
481 
482  free_type_pin_to_track_map(ipin_to_track_map, types);
483  free_type_track_to_ipin_map(track_to_ipin_lookup, types, nodes_per_chan);
484  if(clb_to_clb_directs != NULL) {
485  free(clb_to_clb_directs);
486  }
487 }
488 
489 static void rr_graph_externals(t_timing_inf timing_inf,
490  t_segment_inf * segment_inf, int num_seg_types, int nodes_per_chan,
491  int wire_to_ipin_switch, enum e_base_cost_type base_cost_type) {
493  alloc_and_load_rr_indexed_data(segment_inf, num_seg_types, rr_node_indices,
494  nodes_per_chan, wire_to_ipin_switch, base_cost_type);
495 
499 }
500 
501 static boolean *
502 alloc_and_load_perturb_ipins(INP int nodes_per_chan, INP int L_num_types,
503  INP int **Fc_in, INP int **Fc_out, INP enum e_directionality directionality) {
504  int i;
505  float Fc_ratio;
506  boolean *result = NULL;
507 
508  result = (boolean *) my_malloc(L_num_types * sizeof(boolean));
509 
510  if (BI_DIRECTIONAL == directionality) {
511  result[0] = FALSE;
512  for (i = 1; i < L_num_types; ++i) {
513  result[i] = FALSE;
514 
515  if (Fc_in[i][0] > Fc_out[i][0]) {
516  Fc_ratio = (float) Fc_in[i][0] / (float) Fc_out[i][0];
517  } else {
518  Fc_ratio = (float) Fc_out[i][0] / (float) Fc_in[i][0];
519  }
520 
521  if ((Fc_in[i][0] <= nodes_per_chan - 2)
522  && (fabs(Fc_ratio - nint(Fc_ratio))
523  < (0.5 / (float) nodes_per_chan))) {
524  result[i] = TRUE;
525  }
526  }
527  } else {
528  /* Unidirectional routing uses mux balancing patterns and
529  * thus shouldn't need perturbation. */
530  assert(UNI_DIRECTIONAL == directionality);
531  for (i = 0; i < L_num_types; ++i) {
532  result[i] = FALSE;
533  }
534  }
535 
536  return result;
537 }
538 
539 static t_seg_details *
541  INP int global_route_switch) {
542  t_seg_details *result = NULL;
543 
544  assert(nodes_per_chan == 1);
545  result = (t_seg_details *) my_malloc(sizeof(t_seg_details));
546 
547  result->index = 0;
548  result->length = 1;
549  result->wire_switch = global_route_switch;
550  result->opin_switch = global_route_switch;
551  result->longline = FALSE;
552  result->direction = BI_DIRECTION;
553  result->Cmetal = 0.0;
554  result->Rmetal = 0.0;
555  result->start = 1;
556  result->drivers = MULTI_BUFFERED;
557  result->cb = (boolean *) my_malloc(sizeof(boolean) * 1);
558  result->cb[0] = TRUE;
559  result->sb = (boolean *) my_malloc(sizeof(boolean) * 2);
560  result->sb[0] = TRUE;
561  result->sb[1] = TRUE;
562  result->group_size = 1;
563  result->group_start = 0;
564 
565  return result;
566 }
567 
568 /* Calculates the actual Fc values for the given nodes_per_chan value */
569 static int **
571  INP int nodes_per_chan, INP boolean is_Fc_out,
572  INP enum e_directionality directionality, OUTP boolean * Fc_clipped, INP boolean ignore_Fc_0) {
573 
574  int i, j;
575  int **Result = NULL;
576  int fac, num_sets;
577 
578  *Fc_clipped = FALSE;
579 
580  /* Unidir tracks formed in pairs, otherwise no effect. */
581  fac = 1;
582  if (UNI_DIRECTIONAL == directionality) {
583  fac = 2;
584  }
585 
586  assert((nodes_per_chan % fac) == 0);
587  num_sets = nodes_per_chan / fac;
588 
589  int max_pins = types[0].num_pins;
590  for (i = 1; i < L_num_types; ++i) {
591  if (types[i].num_pins > max_pins) {
592  max_pins = types[i].num_pins;
593  }
594  }
595 
596  Result = (int **) alloc_matrix(0, L_num_types, 0, max_pins, sizeof(int));
597 
598  for (i = 1; i < L_num_types; ++i) {
599  float *Fc = (float *) my_malloc(sizeof(float) * types[i].num_pins); /* [0..num_pins-1] */
600  for (j = 0; j < types[i].num_pins; ++j) {
601  Fc[j] = types[i].Fc[j];
602 
603  if(Fc[j] == 0 && ignore_Fc_0 == FALSE) {
604  /* Special case indicating that this pin does not connect to general-purpose routing */
605  Result[i][j] = 0;
606  } else {
607  /* General case indicating that this pin connects to general-purpose routing */
608  if (types[i].is_Fc_frac[j]) {
609  Result[i][j] = fac * nint(num_sets * Fc[j]);
610  } else {
611  Result[i][j] = (int)Fc[j];
612  }
613 
614  if (is_Fc_out && types[i].is_Fc_full_flex[j]) {
615  Result[i][j] = nodes_per_chan;
616  }
617 
618  Result[i][j] = std::max(Result[i][j], fac);
619  if (Result[i][j] > nodes_per_chan) {
620  *Fc_clipped = TRUE;
621  Result[i][j] = nodes_per_chan;
622  }
623  }
624  assert(Result[i][j] % fac == 0);
625  }
626  free(Fc);
627  }
628 
629  return Result;
630 }
631 
632 /* frees the track to ipin mapping for each physical grid type */
633 static void free_type_track_to_ipin_map(struct s_ivec**** track_to_pin_map,
634  t_type_ptr types, int nodes_per_chan) {
635  int i, itrack, ioff, iside;
636  for (i = 0; i < num_types; i++) {
637  if (track_to_pin_map[i] != NULL) {
638  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
639  for (ioff = 0; ioff < types[i].height; ioff++) {
640  for (iside = 0; iside < 4; iside++) {
641  if (track_to_pin_map[i][itrack][ioff][iside].list
642  != NULL) {
643  free(track_to_pin_map[i][itrack][ioff][iside].list);
644  }
645  }
646  }
647  }
648  free_matrix3(track_to_pin_map[i], 0, nodes_per_chan - 1, 0,
649  types[i].height - 1, 0, sizeof(struct s_ivec));
650  }
651  }
652  free(track_to_pin_map);
653 }
654 
655 /* frees the ipin to track mapping for each physical grid type */
656 static void free_type_pin_to_track_map(int***** ipin_to_track_map,
657  t_type_ptr types) {
658  int i;
659  for (i = 0; i < num_types; i++) {
660  free_matrix4(ipin_to_track_map[i], 0, types[i].num_pins - 1, 0,
661  types[i].height - 1, 0, 3, 0, sizeof(int));
662  }
663  free(ipin_to_track_map);
664 }
665 
666 /* Does the actual work of allocating the rr_graph and filling all the *
667  * appropriate values. Everything up to this was just a prelude! */
668 static void alloc_and_load_rr_graph(INP int num_nodes,
669  INP t_rr_node * L_rr_node, INP int num_seg_types,
670  INP t_seg_details * seg_details, INP boolean * L_rr_edge_done,
671  INP struct s_ivec ****track_to_ipin_lookup,
672  INP int *****opin_to_track_map, INP struct s_ivec ***switch_block_conn,
673  INP struct s_grid_tile **L_grid, INP int L_nx, INP int L_ny, INP int Fs,
674  INP short *****sblock_pattern, INP int **Fc_out, INP int **Fc_xofs,
675  INP int **Fc_yofs, INP t_ivec *** L_rr_node_indices,
676  INP int nodes_per_chan, INP enum e_switch_block_type sb_type,
677  INP int delayless_switch, INP enum e_directionality directionality,
678  INP int wire_to_ipin_switch, OUTP boolean * Fc_clipped,
679  INP t_direct_inf *directs, INP int num_directs,
680  INP t_clb_to_clb_directs *clb_to_clb_directs) {
681 
682  int i, j;
683  boolean clipped;
684  int *opin_mux_size = NULL;
685 
686  /* If Fc gets clipped, this will be flagged to true */
687  *Fc_clipped = FALSE;
688 
689  /* Connection SINKS and SOURCES to their pins. */
690  for (i = 0; i <= (L_nx + 1); i++) {
691  for (j = 0; j <= (L_ny + 1); j++) {
692  build_rr_sinks_sources(i, j, L_rr_node, L_rr_node_indices,
693  delayless_switch, L_grid);
694  }
695  }
696 
697  /* Build opins */
698  for (i = 0; i <= (L_nx + 1); ++i) {
699  for (j = 0; j <= (L_ny + 1); ++j) {
700  if (BI_DIRECTIONAL == directionality) {
701  build_bidir_rr_opins(i, j, L_rr_node, L_rr_node_indices,
702  opin_to_track_map, Fc_out, L_rr_edge_done, seg_details,
703  L_grid, delayless_switch,
704  directs, num_directs, clb_to_clb_directs);
705  } else {
706  assert(UNI_DIRECTIONAL == directionality);
707  build_unidir_rr_opins(i, j, L_grid, Fc_out, nodes_per_chan,
708  seg_details, Fc_xofs, Fc_yofs, L_rr_node,
709  L_rr_edge_done, &clipped, L_rr_node_indices, delayless_switch,
710  directs, num_directs, clb_to_clb_directs);
711  if (clipped) {
712  *Fc_clipped = TRUE;
713  }
714  }
715  }
716  }
717 
718  /* We make a copy of the current fanin values for the nodes to
719  * know the number of OPINs driving each mux presently */
720  opin_mux_size = (int *) my_malloc(sizeof(int) * num_nodes);
721  for (i = 0; i < num_nodes; ++i) {
722  opin_mux_size[i] = L_rr_node[i].fan_in;
723  }
724 
725  /* Build channels */
726  assert(Fs % 3 == 0);
727  for (i = 0; i <= L_nx; i++) {
728  for (j = 0; j <= L_ny; j++) {
729  if (i > 0) {
730  build_rr_xchan(i, j, track_to_ipin_lookup, switch_block_conn,
731  CHANX_COST_INDEX_START, nodes_per_chan, opin_mux_size,
732  sblock_pattern, Fs / 3, seg_details, L_rr_node_indices,
733  L_rr_edge_done, L_rr_node, wire_to_ipin_switch,
734  directionality);
735  }
736  if (j > 0) {
737  build_rr_ychan(i, j, track_to_ipin_lookup, switch_block_conn,
738  CHANX_COST_INDEX_START + num_seg_types, nodes_per_chan,
739  opin_mux_size, sblock_pattern, Fs / 3, seg_details,
740  L_rr_node_indices, L_rr_edge_done, L_rr_node,
741  wire_to_ipin_switch, directionality);
742  }
743  }
744  }
745  free(opin_mux_size);
746 }
747 
748 static void build_bidir_rr_opins(INP int i, INP int j,
749  INOUTP t_rr_node * L_rr_node, INP t_ivec *** L_rr_node_indices,
750  INP int *****opin_to_track_map, INP int **Fc_out,
751  INP boolean * L_rr_edge_done, INP t_seg_details * seg_details,
752  INP struct s_grid_tile **L_grid, INP int delayless_switch,
753  INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs) {
754 
755  int ipin, inode, num_edges, *Fc, ofs;
756  t_type_ptr type;
757  struct s_linked_edge *edge_list, *next;
758 
759  /* OPINP edges need to be done at once so let the offset 0
760  * block do the work. */
761  if (L_grid[i][j].offset > 0) {
762  return;
763  }
764 
765  type = L_grid[i][j].type;
766  Fc = Fc_out[type->index];
767 
768  for (ipin = 0; ipin < type->num_pins; ++ipin) {
769  /* We only are working with opins so skip non-drivers */
770  if (type->class_inf[type->pin_class[ipin]].type != DRIVER) {
771  continue;
772  }
773 
774  num_edges = 0;
775  edge_list = NULL;
776  if(Fc[ipin] != 0) {
777  for (ofs = 0; ofs < type->height; ++ofs) {
778  num_edges += get_bidir_opin_connections(i, j + ofs, ipin,
779  &edge_list, opin_to_track_map, Fc[ipin], L_rr_edge_done,
780  L_rr_node_indices, seg_details);
781  }
782  }
783 
784  /* Add in direct connections */
785  num_edges += get_opin_direct_connecions(i, j, ipin, &edge_list, L_rr_node_indices, delayless_switch, directs, num_directs, clb_to_clb_directs);
786 
787  inode = get_rr_node_index(i, j, OPIN, ipin, L_rr_node_indices);
788  alloc_and_load_edges_and_switches(L_rr_node, inode, num_edges,
789  L_rr_edge_done, edge_list);
790  while (edge_list != NULL) {
791  next = edge_list->next;
792  free(edge_list);
793  edge_list = next;
794  }
795  }
796 }
797 
798 void free_rr_graph(void) {
799  int i;
800 
801  /* Frees all the routing graph data structures, if they have been *
802  * allocated. I use rr_mem_chunk_list_head as a flag to indicate *
803  * whether or not the graph has been allocated -- if it is not NULL, *
804  * a routing graph exists and can be freed. Hence, you can call this *
805  * routine even if you're not sure of whether a rr_graph exists or not. */
806 
807  if (rr_mem_ch.chunk_ptr_head == NULL) /* Nothing to free. */
808  return;
809 
810  free_chunk_memory(&rr_mem_ch); /* Frees ALL "chunked" data */
811 
812  /* Before adding any more free calls here, be sure the data is NOT chunk *
813  * allocated, as ALL the chunk allocated data is already free! */
814 
815  if(net_rr_terminals != NULL) {
816  free(net_rr_terminals);
817  }
818  for (i = 0; i < num_rr_nodes; i++) {
819  if (rr_node[i].edges != NULL) {
820  free(rr_node[i].edges);
821  }
822  if (rr_node[i].switches != NULL) {
823  free(rr_node[i].switches);
824  }
825  }
826 
827  assert(rr_node_indices);
829  free(rr_node);
830  free(rr_indexed_data);
831  for (i = 0; i < num_blocks; i++) {
832  free(rr_blk_source[i]);
833  }
834  free(rr_blk_source);
835  rr_blk_source = NULL;
836  net_rr_terminals = NULL;
837  rr_node = NULL;
838  rr_node_indices = NULL;
839  rr_indexed_data = NULL;
840  num_rr_nodes = 0;
841 }
842 
843 static void alloc_net_rr_terminals(void) {
844  int inet;
845 
846  net_rr_terminals = (int **) my_malloc(num_nets * sizeof(int *));
847 
848  for (inet = 0; inet < num_nets; inet++) {
849  net_rr_terminals[inet] = (int *) my_chunk_malloc(
850  (clb_net[inet].num_sinks + 1) * sizeof(int),
851  &rr_mem_ch);
852  }
853 }
854 
855 void load_net_rr_terminals(t_ivec *** L_rr_node_indices) {
856 
857  /* Allocates and loads the net_rr_terminals data structure. For each net *
858  * it stores the rr_node index of the SOURCE of the net and all the SINKs *
859  * of the net. [0..num_nets-1][0..num_pins-1]. Entry [inet][pnum] stores *
860  * the rr index corresponding to the SOURCE (opin) or SINK (ipin) of pnum. */
861 
862  int inet, ipin, inode, iblk, i, j, node_block_pin, iclass;
863  t_type_ptr type;
864 
865  for (inet = 0; inet < num_nets; inet++) {
866  for (ipin = 0; ipin <= clb_net[inet].num_sinks; ipin++) {
867  iblk = clb_net[inet].node_block[ipin];
868  i = block[iblk].x;
869  j = block[iblk].y;
870  type = block[iblk].type;
871 
872  /* In the routing graph, each (x, y) location has unique pins on it
873  * so when there is capacity, blocks are packed and their pin numbers
874  * are offset to get their actual rr_node */
875  node_block_pin = clb_net[inet].node_block_pin[ipin];
876 
877  iclass = type->pin_class[node_block_pin];
878 
879  inode = get_rr_node_index(i, j, (ipin == 0 ? SOURCE : SINK), /* First pin is driver */
880  iclass, L_rr_node_indices);
881  net_rr_terminals[inet][ipin] = inode;
882  }
883  }
884 }
885 
886 static void alloc_and_load_rr_clb_source(t_ivec *** L_rr_node_indices) {
887 
888  /* Saves the rr_node corresponding to each SOURCE and SINK in each CLB *
889  * in the FPGA. Currently only the SOURCE rr_node values are used, and *
890  * they are used only to reserve pins for locally used OPINs in the router. *
891  * [0..num_blocks-1][0..num_class-1]. The values for blocks that are pads *
892  * are NOT valid. */
893 
894  int iblk, i, j, iclass, inode;
895  int class_low, class_high;
896  t_rr_type rr_type;
897  t_type_ptr type;
898 
899  rr_blk_source = (int **) my_malloc(num_blocks * sizeof(int *));
900 
901  for (iblk = 0; iblk < num_blocks; iblk++) {
902  type = block[iblk].type;
903  get_class_range_for_block(iblk, &class_low, &class_high);
904  rr_blk_source[iblk] = (int *) my_malloc(type->num_class * sizeof(int));
905  for (iclass = 0; iclass < type->num_class; iclass++) {
906  if (iclass >= class_low && iclass <= class_high) {
907  i = block[iblk].x;
908  j = block[iblk].y;
909 
910  if (type->class_inf[iclass].type == DRIVER)
911  rr_type = SOURCE;
912  else
913  rr_type = SINK;
914 
915  inode = get_rr_node_index(i, j, rr_type, iclass,
916  L_rr_node_indices);
917  rr_blk_source[iblk][iclass] = inode;
918  } else {
919  rr_blk_source[iblk][iclass] = OPEN;
920  }
921  }
922  }
923 }
924 
925 static void build_rr_sinks_sources(INP int i, INP int j,
926  INP t_rr_node * L_rr_node, INP t_ivec *** L_rr_node_indices,
927  INP int delayless_switch, INP struct s_grid_tile **L_grid) {
928 
929  /* Loads IPIN, SINK, SOURCE, and OPIN.
930  * Loads IPINP to SINK edges, and SOURCE to OPINP edges */
931 
932  int ipin, iclass, inode, pin_num, to_node, num_edges;
933  int num_class, num_pins;
934  t_type_ptr type;
935  struct s_class *class_inf;
936  int *pin_class;
937  const t_pb_graph_node *pb_graph_node;
938  int iport, ipb_pin, iporttype, z;
939 
940  /* Since we share nodes within a large block, only
941  * start tile can initialize sinks, sources, and pins */
942  if (L_grid[i][j].offset > 0)
943  return;
944 
945  type = L_grid[i][j].type;
946  num_class = type->num_class;
947  class_inf = type->class_inf;
948  num_pins = type->num_pins;
949  pin_class = type->pin_class;
950  z = 0;
951 
952  /* SINKS and SOURCE to OPINP edges */
953  for (iclass = 0; iclass < num_class; iclass++) {
954  if (class_inf[iclass].type == DRIVER) { /* SOURCE */
955  inode = get_rr_node_index(i, j, SOURCE, iclass, L_rr_node_indices);
956 
957  num_edges = class_inf[iclass].num_pins;
958  L_rr_node[inode].num_edges = num_edges;
959  L_rr_node[inode].edges = (int *) my_malloc(num_edges * sizeof(int));
960  L_rr_node[inode].switches = (short *) my_malloc(
961  num_edges * sizeof(short));
962 
963  for (ipin = 0; ipin < class_inf[iclass].num_pins; ipin++) {
964  pin_num = class_inf[iclass].pinlist[ipin];
965  to_node = get_rr_node_index(i, j, OPIN, pin_num,
966  L_rr_node_indices);
967  L_rr_node[inode].edges[ipin] = to_node;
968  L_rr_node[inode].switches[ipin] = delayless_switch;
969 
970  ++L_rr_node[to_node].fan_in;
971  }
972 
973  L_rr_node[inode].cost_index = SOURCE_COST_INDEX;
974  L_rr_node[inode].type = SOURCE;
975  } else { /* SINK */
976  assert(class_inf[iclass].type == RECEIVER);
977  inode = get_rr_node_index(i, j, SINK, iclass, L_rr_node_indices);
978 
979  /* NOTE: To allow route throughs through clbs, change the lines below to *
980  * make an edge from the input SINK to the output SOURCE. Do for just the *
981  * special case of INPUTS = class 0 and OUTPUTS = class 1 and see what it *
982  * leads to. If route throughs are allowed, you may want to increase the *
983  * base cost of OPINs and/or SOURCES so they aren't used excessively. */
984 
985  /* Initialize to unconnected to fix values */
986  L_rr_node[inode].num_edges = 0;
987  L_rr_node[inode].edges = NULL;
988  L_rr_node[inode].switches = NULL;
989 
990  L_rr_node[inode].cost_index = SINK_COST_INDEX;
991  L_rr_node[inode].type = SINK;
992  }
993 
994  /* Things common to both SOURCEs and SINKs. */
995  L_rr_node[inode].capacity = class_inf[iclass].num_pins;
996  L_rr_node[inode].occ = 0;
997  L_rr_node[inode].xlow = i;
998  L_rr_node[inode].xhigh = i;
999  L_rr_node[inode].ylow = j;
1000  L_rr_node[inode].yhigh = j + type->height - 1;
1001  L_rr_node[inode].R = 0;
1002  L_rr_node[inode].C = 0;
1003  L_rr_node[inode].ptc_num = iclass;
1004  L_rr_node[inode].direction = (enum e_direction)OPEN;
1005  L_rr_node[inode].drivers = (enum e_drivers)OPEN;
1006  }
1007 
1008  iporttype = iport = ipb_pin = 0;
1009 
1010  pb_graph_node = type->pb_graph_head;
1011  if(pb_graph_node != NULL && pb_graph_node->num_input_ports == 0) {
1012  iporttype = 1;
1013  }
1014  /* Connect IPINS to SINKS and dummy for OPINS */
1015  for (ipin = 0; ipin < num_pins; ipin++) {
1016  iclass = pin_class[ipin];
1017  z = ipin / (type->pb_type->num_clock_pins + type->pb_type->num_output_pins + type->pb_type->num_input_pins);
1018 
1019  if (class_inf[iclass].type == RECEIVER) {
1020  inode = get_rr_node_index(i, j, IPIN, ipin, L_rr_node_indices);
1021  to_node = get_rr_node_index(i, j, SINK, iclass, L_rr_node_indices);
1022 
1023  L_rr_node[inode].num_edges = 1;
1024  L_rr_node[inode].edges = (int *) my_malloc(sizeof(int));
1025  L_rr_node[inode].switches = (short *) my_malloc(sizeof(short));
1026 
1027  L_rr_node[inode].edges[0] = to_node;
1028  L_rr_node[inode].switches[0] = delayless_switch;
1029 
1030  ++L_rr_node[to_node].fan_in;
1031 
1032  L_rr_node[inode].cost_index = IPIN_COST_INDEX;
1033  L_rr_node[inode].type = IPIN;
1034 
1035  /* Add in information so that I can identify which cluster pin this rr_node connects to later */
1036  L_rr_node[inode].z = z;
1037  if(iporttype == 0) {
1038  L_rr_node[inode].pb_graph_pin = &pb_graph_node->input_pins[iport][ipb_pin];
1039  ipb_pin++;
1040  if(ipb_pin >= pb_graph_node->num_input_pins[iport]) {
1041  iport++;
1042  ipb_pin = 0;
1043  if(iport >= pb_graph_node->num_input_ports) {
1044  iporttype++;
1045  iport = 0;
1046  if(pb_graph_node->num_clock_ports == 0) {
1047  iporttype = 0;
1048  }
1049  }
1050  }
1051  } else {
1052  assert(iporttype == 1);
1053  L_rr_node[inode].pb_graph_pin = &pb_graph_node->clock_pins[iport][ipb_pin];
1054  if(ipb_pin >= pb_graph_node->num_clock_pins[iport]) {
1055  iport++;
1056  ipb_pin = 0;
1057  if(iport >= pb_graph_node->num_clock_ports) {
1058  iporttype = 0;
1059  iport = 0;
1060  if(pb_graph_node->num_input_ports == 0) {
1061  iporttype = 1;
1062  }
1063  }
1064  }
1065  }
1066  } else {
1067  assert(class_inf[iclass].type == DRIVER);
1068 
1069  inode = get_rr_node_index(i, j, OPIN, ipin, L_rr_node_indices);
1070 
1071  /* Add in information so that I can identify which cluster pin this rr_node connects to later */
1072  L_rr_node[inode].z = z;
1073 
1074  L_rr_node[inode].num_edges = 0;
1075  L_rr_node[inode].edges = NULL;
1076 
1077  L_rr_node[inode].switches = NULL;
1078 
1079  L_rr_node[inode].cost_index = OPIN_COST_INDEX;
1080  L_rr_node[inode].type = OPIN;
1081 
1082  L_rr_node[inode].pb_graph_pin = &pb_graph_node->output_pins[iport][ipb_pin];
1083  if(ipb_pin >= pb_graph_node->num_output_pins[iport]) {
1084  iport++;
1085  ipb_pin = 0;
1086  if(iport >= pb_graph_node->num_output_ports) {
1087  iport = 0;
1088  if(pb_graph_node->num_input_ports == 0) {
1089  iporttype = 1;
1090  } else {
1091  iporttype = 0;
1092  }
1093  }
1094  }
1095  }
1096 
1097  /* Common to both DRIVERs and RECEIVERs */
1098  L_rr_node[inode].capacity = 1;
1099  L_rr_node[inode].occ = 0;
1100  L_rr_node[inode].xlow = i;
1101  L_rr_node[inode].xhigh = i;
1102  L_rr_node[inode].ylow = j;
1103  L_rr_node[inode].yhigh = j + type->height - 1;
1104  L_rr_node[inode].C = 0;
1105  L_rr_node[inode].R = 0;
1106  L_rr_node[inode].ptc_num = ipin;
1107  L_rr_node[inode].direction = (enum e_direction)OPEN;
1108  L_rr_node[inode].drivers = (enum e_drivers)OPEN;
1109  }
1110 }
1111 
1112 static void build_rr_xchan(INP int i, INP int j,
1113  INP struct s_ivec ****track_to_ipin_lookup,
1114  INP struct s_ivec ***switch_block_conn, INP int cost_index_offset,
1115  INP int nodes_per_chan, INP int *opin_mux_size,
1116  INP short *****sblock_pattern, INP int Fs_per_side,
1117  INP t_seg_details * seg_details, INP t_ivec *** L_rr_node_indices,
1118  INOUTP boolean * L_rr_edge_done, INOUTP t_rr_node * L_rr_node,
1119  INP int wire_to_ipin_switch, INP enum e_directionality directionality) {
1120 
1121  /* Loads up all the routing resource nodes in the x-directed channel *
1122  * segments starting at (i,j). */
1123 
1124  int itrack, istart, iend, num_edges, inode, length;
1125  struct s_linked_edge *edge_list, *next;
1126 
1127  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1128  istart = get_seg_start(seg_details, itrack, j, i);
1129  iend = get_seg_end(seg_details, itrack, istart, j, nx);
1130 
1131  if (i > istart)
1132  continue; /* Not the start of this segment. */
1133 
1134  edge_list = NULL;
1135 
1136  /* First count number of edges and put the edges in a linked list. */
1137  num_edges = 0;
1138 
1139  num_edges += get_track_to_ipins(istart, j, itrack, &edge_list,
1140  L_rr_node_indices, track_to_ipin_lookup, seg_details, CHANX, nx,
1141  wire_to_ipin_switch, directionality);
1142 
1143  if (j > 0) {
1144  num_edges += get_track_to_tracks(j, istart, itrack, CHANX, j, CHANY,
1145  nx, nodes_per_chan, opin_mux_size, Fs_per_side,
1146  sblock_pattern, &edge_list, seg_details, directionality,
1147  L_rr_node_indices, L_rr_edge_done, switch_block_conn);
1148  }
1149 
1150  if (j < ny) {
1151  num_edges += get_track_to_tracks(j, istart, itrack, CHANX, j + 1,
1152  CHANY, nx, nodes_per_chan, opin_mux_size, Fs_per_side,
1153  sblock_pattern, &edge_list, seg_details, directionality,
1154  L_rr_node_indices, L_rr_edge_done, switch_block_conn);
1155  }
1156 
1157  if (istart > 1) {
1158  num_edges += get_track_to_tracks(j, istart, itrack, CHANX,
1159  istart - 1, CHANX, nx, nodes_per_chan, opin_mux_size,
1160  Fs_per_side, sblock_pattern, &edge_list, seg_details,
1161  directionality, L_rr_node_indices, L_rr_edge_done,
1162  switch_block_conn);
1163  }
1164 
1165  if (iend < nx) {
1166  num_edges += get_track_to_tracks(j, istart, itrack, CHANX, iend + 1,
1167  CHANX, nx, nodes_per_chan, opin_mux_size, Fs_per_side,
1168  sblock_pattern, &edge_list, seg_details, directionality,
1169  L_rr_node_indices, L_rr_edge_done, switch_block_conn);
1170  }
1171 
1172  inode = get_rr_node_index(i, j, CHANX, itrack, L_rr_node_indices);
1173  alloc_and_load_edges_and_switches(L_rr_node, inode, num_edges,
1174  L_rr_edge_done, edge_list);
1175 
1176  while (edge_list != NULL) {
1177  next = edge_list->next;
1178  free(edge_list);
1179  edge_list = next;
1180  }
1181 
1182  /* Edge arrays have now been built up. Do everything else. */
1183  L_rr_node[inode].cost_index = cost_index_offset
1184  + seg_details[itrack].index;
1185  L_rr_node[inode].occ = 0;
1186 
1187  L_rr_node[inode].capacity = 1; /* GLOBAL routing handled elsewhere */
1188 
1189  L_rr_node[inode].xlow = istart;
1190  L_rr_node[inode].xhigh = iend;
1191  L_rr_node[inode].ylow = j;
1192  L_rr_node[inode].yhigh = j;
1193 
1194  length = iend - istart + 1;
1195  L_rr_node[inode].R = length * seg_details[itrack].Rmetal;
1196  L_rr_node[inode].C = length * seg_details[itrack].Cmetal;
1197 
1198  L_rr_node[inode].ptc_num = itrack;
1199  L_rr_node[inode].type = CHANX;
1200  L_rr_node[inode].direction = seg_details[itrack].direction;
1201  L_rr_node[inode].drivers = seg_details[itrack].drivers;
1202  }
1203 }
1204 
1205 static void build_rr_ychan(INP int i, INP int j,
1206  INP struct s_ivec ****track_to_ipin_lookup,
1207  INP struct s_ivec ***switch_block_conn, INP int cost_index_offset,
1208  INP int nodes_per_chan, INP int *opin_mux_size,
1209  INP short *****sblock_pattern, INP int Fs_per_side,
1210  INP t_seg_details * seg_details, INP t_ivec *** L_rr_node_indices,
1211  INP boolean * L_rr_edge_done, INOUTP t_rr_node * L_rr_node,
1212  INP int wire_to_ipin_switch, INP enum e_directionality directionality) {
1213 
1214  /* Loads up all the routing resource nodes in the y-directed channel *
1215  * segments starting at (i,j). */
1216 
1217  int itrack, istart, iend, num_edges, inode, length;
1218  struct s_linked_edge *edge_list, *next;
1219 
1220  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1221  istart = get_seg_start(seg_details, itrack, i, j);
1222  iend = get_seg_end(seg_details, itrack, istart, i, ny);
1223 
1224  if (j > istart)
1225  continue; /* Not the start of this segment. */
1226 
1227  edge_list = NULL;
1228 
1229  /* First count number of edges and put the edges in a linked list. */
1230  num_edges = 0;
1231 
1232  num_edges += get_track_to_ipins(istart, i, itrack, &edge_list,
1233  L_rr_node_indices, track_to_ipin_lookup, seg_details, CHANY, ny,
1234  wire_to_ipin_switch, directionality);
1235 
1236  if (i > 0) {
1237  num_edges += get_track_to_tracks(i, istart, itrack, CHANY, i, CHANX,
1238  ny, nodes_per_chan, opin_mux_size, Fs_per_side,
1239  sblock_pattern, &edge_list, seg_details, directionality,
1240  L_rr_node_indices, L_rr_edge_done, switch_block_conn);
1241  }
1242 
1243  if (i < nx) {
1244  num_edges += get_track_to_tracks(i, istart, itrack, CHANY, i + 1,
1245  CHANX, ny, nodes_per_chan, opin_mux_size, Fs_per_side,
1246  sblock_pattern, &edge_list, seg_details, directionality,
1247  L_rr_node_indices, L_rr_edge_done, switch_block_conn);
1248  }
1249 
1250  if (istart > 1) {
1251  num_edges += get_track_to_tracks(i, istart, itrack, CHANY,
1252  istart - 1, CHANY, ny, nodes_per_chan, opin_mux_size,
1253  Fs_per_side, sblock_pattern, &edge_list, seg_details,
1254  directionality, L_rr_node_indices, L_rr_edge_done,
1255  switch_block_conn);
1256  }
1257 
1258  if (iend < ny) {
1259  num_edges += get_track_to_tracks(i, istart, itrack, CHANY, iend + 1,
1260  CHANY, ny, nodes_per_chan, opin_mux_size, Fs_per_side,
1261  sblock_pattern, &edge_list, seg_details, directionality,
1262  L_rr_node_indices, L_rr_edge_done, switch_block_conn);
1263  }
1264 
1265  inode = get_rr_node_index(i, j, CHANY, itrack, L_rr_node_indices);
1266  alloc_and_load_edges_and_switches(L_rr_node, inode, num_edges,
1267  L_rr_edge_done, edge_list);
1268 
1269  while (edge_list != NULL) {
1270  next = edge_list->next;
1271  free(edge_list);
1272  edge_list = next;
1273  }
1274 
1275  /* Edge arrays have now been built up. Do everything else. */
1276  L_rr_node[inode].cost_index = cost_index_offset
1277  + seg_details[itrack].index;
1278  L_rr_node[inode].occ = 0;
1279 
1280  L_rr_node[inode].capacity = 1; /* GLOBAL routing handled elsewhere */
1281 
1282  L_rr_node[inode].xlow = i;
1283  L_rr_node[inode].xhigh = i;
1284  L_rr_node[inode].ylow = istart;
1285  L_rr_node[inode].yhigh = iend;
1286 
1287  length = iend - istart + 1;
1288  L_rr_node[inode].R = length * seg_details[itrack].Rmetal;
1289  L_rr_node[inode].C = length * seg_details[itrack].Cmetal;
1290 
1291  L_rr_node[inode].ptc_num = itrack;
1292  L_rr_node[inode].type = CHANY;
1293  L_rr_node[inode].direction = seg_details[itrack].direction;
1294  L_rr_node[inode].drivers = seg_details[itrack].drivers;
1295  }
1296 }
1297 
1298 void watch_edges(int inode, t_linked_edge * edge_list_head) {
1299  t_linked_edge *list_ptr;
1300  int i, to_node;
1301 
1302  list_ptr = edge_list_head;
1303  i = 0;
1304 
1305  vpr_printf(TIO_MESSAGE_TRACE, "!!! Watching Node %d !!!!\n", inode);
1306  print_rr_node(stdout, rr_node, inode);
1307  vpr_printf(TIO_MESSAGE_TRACE, "Currently connects to:\n");
1308  while (list_ptr != NULL) {
1309  to_node = list_ptr->edge;
1310  print_rr_node(stdout, rr_node, to_node);
1311  list_ptr = list_ptr->next;
1312  i++;
1313  }
1314 }
1315 
1317  INP int num_edges, INOUTP boolean * L_rr_edge_done,
1318  INP t_linked_edge * edge_list_head) {
1319 
1320  /* Sets up all the edge related information for rr_node inode (num_edges, *
1321  * the edges array and the switches array). The edge_list_head points to *
1322  * a list of the num_edges edges and switches to put in the arrays. This *
1323  * linked list is freed by this routine. This routine also resets the *
1324  * rr_edge_done array for the next rr_node (i.e. set it so that no edges *
1325  * are marked as having been seen before). */
1326 
1327  t_linked_edge *list_ptr;
1328  int i;
1329 
1330  /* Check we aren't overwriting edges */
1331  assert(L_rr_node[inode].num_edges < 1);
1332  assert(NULL == L_rr_node[inode].edges);
1333  assert(NULL == L_rr_node[inode].switches);
1334 
1335  L_rr_node[inode].num_edges = num_edges;
1336  L_rr_node[inode].edges = (int *) my_malloc(num_edges * sizeof(int));
1337  L_rr_node[inode].switches = (short *) my_malloc(num_edges * sizeof(short));
1338 
1339  i = 0;
1340  list_ptr = edge_list_head;
1341  while (list_ptr && (i < num_edges)) {
1342  L_rr_node[inode].edges[i] = list_ptr->edge;
1343  L_rr_node[inode].switches[i] = list_ptr->iswitch;
1344 
1345  ++L_rr_node[list_ptr->edge].fan_in;
1346 
1347  /* Unmark the edge since we are done considering fanout from node. */
1348  L_rr_edge_done[list_ptr->edge] = FALSE;
1349 
1350  list_ptr = list_ptr->next;
1351  ++i;
1352  }
1353  assert(list_ptr == NULL);
1354  assert(i == num_edges);
1355 }
1356 
1357 static int ****
1359  INP int nodes_per_chan, INP int *Fc, INP t_type_ptr Type,
1360  INP boolean perturb_switch_pattern,
1361  INP enum e_directionality directionality) {
1362 
1363  int **num_dir; /* [0..height][0..3] Number of *physical* pins on each side. */
1364  int ***dir_list; /* [0..height][0..3][0..num_pins-1] list of pins of correct type *
1365  * * on each side. Max possible space alloced for simplicity */
1366 
1367  int i, j, k, iside, ipin, iclass, num_phys_pins, pindex, ioff;
1368  int *pin_num_ordering, *side_ordering, *offset_ordering;
1369  int **num_done_per_dir; /* [0..height][0..3] */
1370  int ****tracks_connected_to_pin; /* [0..num_pins-1][0..height][0..3][0..Fc-1] */
1371 
1372  /* NB: This wastes some space. Could set tracks_..._pin[ipin][ioff][iside] =
1373  * NULL if there is no pin on that side, or that pin is of the wrong type.
1374  * Probably not enough memory to worry about, esp. as it's temporary.
1375  * If pin ipin on side iside does not exist or is of the wrong type,
1376  * tracks_connected_to_pin[ipin][iside][0] = OPEN. */
1377 
1378  if (Type->num_pins < 1) {
1379  return NULL;
1380  }
1381 
1382  /* Currently, only two possible Fc values exist: 0 or default.
1383  * Finding the max. value of Fc in block will result in the
1384  * default value, which works for now. In the future, when
1385  * the Fc values of all pins can vary, the max value will continue
1386  * to work for matrix (de)allocation purposes. However, all looping
1387  * will have to be modified to account for pin-based Fc values. */
1388  int max_Fc = 0;
1389  for (i = 0; i < Type->num_pins; ++i) {
1390  iclass = Type->pin_class[i];
1391  if (Fc[i] > max_Fc && Type->class_inf[iclass].type == pin_type) {
1392  max_Fc = Fc[i];
1393  }
1394  }
1395 
1396  tracks_connected_to_pin = (int ****) alloc_matrix4(0, Type->num_pins - 1, 0,
1397  Type->height - 1, 0, 3, 0, max_Fc, sizeof(int));
1398 
1399  for (ipin = 0; ipin < Type->num_pins; ipin++) {
1400  for (ioff = 0; ioff < Type->height; ioff++) {
1401  for (iside = 0; iside < 4; iside++) {
1402  for (i = 0; i < max_Fc; ++i) {
1403  tracks_connected_to_pin[ipin][ioff][iside][i] = OPEN; /* Unconnected. */
1404  }
1405  }
1406  }
1407  }
1408 
1409  num_dir = (int **) alloc_matrix(0, Type->height - 1, 0, 3, sizeof(int));
1410  dir_list = (int ***) alloc_matrix3(0, Type->height - 1, 0, 3, 0,
1411  Type->num_pins - 1, sizeof(int));
1412 
1413  /* Defensive coding. Try to crash hard if I use an unset entry. */
1414  for (i = 0; i < Type->height; i++)
1415  for (j = 0; j < 4; j++)
1416  for (k = 0; k < Type->num_pins; k++)
1417  dir_list[i][j][k] = (-1);
1418 
1419  for (i = 0; i < Type->height; i++)
1420  for (j = 0; j < 4; j++)
1421  num_dir[i][j] = 0;
1422 
1423  for (ipin = 0; ipin < Type->num_pins; ipin++) {
1424  iclass = Type->pin_class[ipin];
1425  if (Type->class_inf[iclass].type != pin_type) /* Doing either ipins OR opins */
1426  continue;
1427 
1428  /* Pins connecting only to global resources get no switches -> keeps the *
1429  * area model accurate. */
1430 
1431  if (Type->is_global_pin[ipin])
1432  continue;
1433  for (ioff = 0; ioff < Type->height; ioff++) {
1434  for (iside = 0; iside < 4; iside++) {
1435  if (Type->pinloc[ioff][iside][ipin] == 1) {
1436  dir_list[ioff][iside][num_dir[ioff][iside]] = ipin;
1437  num_dir[ioff][iside]++;
1438  }
1439  }
1440  }
1441  }
1442 
1443  num_phys_pins = 0;
1444  for (ioff = 0; ioff < Type->height; ioff++) {
1445  for (iside = 0; iside < 4; iside++)
1446  num_phys_pins += num_dir[ioff][iside]; /* Num. physical pins per type */
1447  }
1448  num_done_per_dir = (int **) alloc_matrix(0, Type->height - 1, 0, 3,
1449  sizeof(int));
1450  for (ioff = 0; ioff < Type->height; ioff++) {
1451  for (iside = 0; iside < 4; iside++) {
1452  num_done_per_dir[ioff][iside] = 0;
1453  }
1454  }
1455  pin_num_ordering = (int *) my_malloc(num_phys_pins * sizeof(int));
1456  side_ordering = (int *) my_malloc(num_phys_pins * sizeof(int));
1457  offset_ordering = (int *) my_malloc(num_phys_pins * sizeof(int));
1458 
1459  /* Connection block I use distributes pins evenly across the tracks *
1460  * of ALL sides of the clb at once. Ensures that each pin connects *
1461  * to spaced out tracks in its connection block, and that the other *
1462  * pins (potentially in other C blocks) connect to the remaining tracks *
1463  * first. Doesn't matter for large Fc, but should make a fairly *
1464  * good low Fc block that leverages the fact that usually lots of pins *
1465  * are logically equivalent. */
1466 
1467  iside = LEFT;
1468  ioff = Type->height - 1;
1469  ipin = 0;
1470  pindex = -1;
1471 
1472  while (ipin < num_phys_pins) {
1473  if (iside == TOP) {
1474  iside = RIGHT;
1475  } else if (iside == RIGHT) {
1476  if (ioff <= 0) {
1477  iside = BOTTOM;
1478  } else {
1479  ioff--;
1480  }
1481  } else if (iside == BOTTOM) {
1482  iside = LEFT;
1483  } else {
1484  assert(iside == LEFT);
1485  if (ioff >= Type->height - 1) {
1486  pindex++;
1487  iside = TOP;
1488  } else {
1489  ioff++;
1490  }
1491  }
1492 
1493  assert(pindex < num_phys_pins);
1494  /* Number of physical pins bounds number of logical pins */
1495 
1496  if (num_done_per_dir[ioff][iside] >= num_dir[ioff][iside])
1497  continue;
1498  pin_num_ordering[ipin] = dir_list[ioff][iside][pindex];
1499  side_ordering[ipin] = iside;
1500  offset_ordering[ipin] = ioff;
1501  assert(Type->pinloc[ioff][iside][dir_list[ioff][iside][pindex]]);
1502  num_done_per_dir[ioff][iside]++;
1503  ipin++;
1504  }
1505 
1506  if (perturb_switch_pattern) {
1507  load_perturbed_switch_pattern(Type, tracks_connected_to_pin,
1508  num_phys_pins, pin_num_ordering, side_ordering, offset_ordering,
1509  nodes_per_chan, max_Fc, directionality);
1510  } else {
1511  load_uniform_switch_pattern(Type, tracks_connected_to_pin,
1512  num_phys_pins, pin_num_ordering, side_ordering, offset_ordering,
1513  nodes_per_chan, max_Fc, directionality);
1514  }
1515  check_all_tracks_reach_pins(Type, tracks_connected_to_pin, nodes_per_chan,
1516  max_Fc, pin_type);
1517 
1518  /* Free all temporary storage. */
1519  free_matrix(num_dir, 0, Type->height - 1, 0, sizeof(int));
1520  free_matrix3(dir_list, 0, Type->height - 1, 0, 3, 0, sizeof(int));
1521  free_matrix(num_done_per_dir, 0, Type->height - 1, 0, sizeof(int));
1522  free(pin_num_ordering);
1523  free(side_ordering);
1524  free(offset_ordering);
1525 
1526  return tracks_connected_to_pin;
1527 }
1528 
1530  INOUTP int ****tracks_connected_to_pin, INP int num_phys_pins,
1531  INP int *pin_num_ordering, INP int *side_ordering,
1532  INP int *offset_ordering, INP int nodes_per_chan, INP int Fc,
1533  enum e_directionality directionality) {
1534 
1535  /* Loads the tracks_connected_to_pin array with an even distribution of *
1536  * switches across the tracks for each pin. For example, each pin connects *
1537  * to every 4.3rd track in a channel, with exactly which tracks a pin *
1538  * connects to staggered from pin to pin. */
1539 
1540  int i, j, ipin, iside, ioff, itrack, k;
1541  float f_track, fc_step;
1542  int group_size;
1543  float step_size;
1544 
1545  /* Uni-directional drive is implemented to ensure no directional bias and this means
1546  * two important comments noted below */
1547  /* 1. Spacing should be (W/2)/(Fc/2), and step_size should be spacing/(num_phys_pins),
1548  * and lay down 2 switches on an adjacent pair of tracks at a time to ensure
1549  * no directional bias. Basically, treat W (even) as W/2 pairs of tracks, and
1550  * assign switches to a pair at a time. Can do this because W is guaranteed to
1551  * be even-numbered; however same approach cannot be applied to Fc_out pattern
1552  * when L > 1 and W <> 2L multiple.
1553  *
1554  * 2. This generic pattern should be considered the tileable physical layout,
1555  * meaning all track # here are physical #'s,
1556  * so later must use vpr_to_phy conversion to find actual logical #'s to connect.
1557  * This also means I will not use get_output_block_companion_track to ensure
1558  * no bias, since that describes a logical # -> that would confuse people. */
1559 
1560  step_size = (float) nodes_per_chan / (float) (Fc * num_phys_pins);
1561 
1562  if (directionality == BI_DIRECTIONAL) {
1563  group_size = 1;
1564  } else {
1565  assert(directionality == UNI_DIRECTIONAL);
1566  group_size = 2;
1567  }
1568 
1569  assert((nodes_per_chan % group_size == 0) && (Fc % group_size == 0));
1570 
1571  fc_step = (float) nodes_per_chan / (float) Fc;
1572 
1573  for (i = 0; i < num_phys_pins; i++) {
1574  ipin = pin_num_ordering[i];
1575  iside = side_ordering[i];
1576  ioff = offset_ordering[i];
1577 
1578  /* Bi-directional treats each track separately, uni-directional works with pairs of tracks */
1579  for (j = 0; j < (Fc / group_size); j++) {
1580  f_track = (i * step_size) + (j * fc_step);
1581  itrack = ((int) f_track) * group_size;
1582 
1583  /* Catch possible floating point round error */
1584  itrack = std::min(itrack, nodes_per_chan - group_size);
1585 
1586  /* Assign the group of tracks for the Fc pattern */
1587  for (k = 0; k < group_size; ++k) {
1588  tracks_connected_to_pin[ipin][ioff][iside][group_size * j + k] =
1589  itrack + k;
1590  }
1591  }
1592  }
1593 }
1594 
1596  INOUTP int ****tracks_connected_to_pin, INP int num_phys_pins,
1597  INP int *pin_num_ordering, INP int *side_ordering,
1598  INP int *offset_ordering, INP int nodes_per_chan, INP int Fc,
1599  enum e_directionality directionality) {
1600 
1601  /* Loads the tracks_connected_to_pin array with an unevenly distributed *
1602  * set of switches across the channel. This is done for inputs when *
1603  * Fc_input = Fc_output to avoid creating "pin domains" -- certain output *
1604  * pins being able to talk only to certain input pins because their switch *
1605  * patterns exactly line up. Distribute Fc/2 + 1 switches over half the *
1606  * channel and Fc/2 - 1 switches over the other half to make the switch *
1607  * pattern different from the uniform one of the outputs. Also, have half *
1608  * the pins put the "dense" part of their connections in the first half of *
1609  * the channel and the other half put the "dense" part in the second half, *
1610  * to make sure each track can connect to about the same number of ipins. */
1611 
1612  int i, j, ipin, iside, itrack, ihalf, iconn, ioff;
1613  int Fc_dense, Fc_sparse, Fc_half[2];
1614  float f_track, spacing_dense, spacing_sparse, spacing[2];
1615  float step_size;
1616 
1617  assert(directionality == BI_DIRECTIONAL);
1618 
1619  step_size = (float) nodes_per_chan / (float) (Fc * num_phys_pins);
1620 
1621  Fc_dense = (Fc / 2) + 1;
1622  Fc_sparse = Fc - Fc_dense; /* Works for even or odd Fc */
1623 
1624  spacing_dense = (float) nodes_per_chan / (float) (2 * Fc_dense);
1625  spacing_sparse = (float) nodes_per_chan / (float) (2 * Fc_sparse);
1626 
1627  for (i = 0; i < num_phys_pins; i++) {
1628  ipin = pin_num_ordering[i];
1629  iside = side_ordering[i];
1630  ioff = offset_ordering[i];
1631 
1632  /* Flip every pin to balance switch density */
1633  spacing[i % 2] = spacing_dense;
1634  Fc_half[i % 2] = Fc_dense;
1635  spacing[(i + 1) % 2] = spacing_sparse;
1636  Fc_half[(i + 1) % 2] = Fc_sparse;
1637 
1638  f_track = i * step_size; /* Start point. Staggered from pin to pin */
1639  iconn = 0;
1640 
1641  for (ihalf = 0; ihalf < 2; ihalf++) { /* For both dense and sparse halves. */
1642  for (j = 0; j < Fc_half[ihalf]; ++j) {
1643  itrack = (int) f_track;
1644 
1645  /* Can occasionally get wraparound due to floating point rounding.
1646  This is okay because the starting position > 0 when this occurs
1647  so connection is valid and fine */
1648  itrack = itrack % nodes_per_chan;
1649  tracks_connected_to_pin[ipin][ioff][iside][iconn] = itrack;
1650 
1651  f_track += spacing[ihalf];
1652  iconn++;
1653  }
1654  }
1655  } /* End for all physical pins. */
1656 }
1657 
1659  int ****tracks_connected_to_pin, int nodes_per_chan, int Fc,
1660  enum e_pin_type ipin_or_opin) {
1661 
1662  /* Checks that all tracks can be reached by some pin. */
1663 
1664  int iconn, iside, itrack, ipin, ioff;
1665  int *num_conns_to_track; /* [0..nodes_per_chan-1] */
1666 
1667  assert(nodes_per_chan > 0);
1668 
1669  num_conns_to_track = (int *) my_calloc(nodes_per_chan, sizeof(int));
1670 
1671  for (ipin = 0; ipin < type->num_pins; ipin++) {
1672  for (ioff = 0; ioff < type->height; ioff++) {
1673  for (iside = 0; iside < 4; iside++) {
1674  if (tracks_connected_to_pin[ipin][ioff][iside][0] != OPEN) { /* Pin exists */
1675  for (iconn = 0; iconn < Fc; iconn++) {
1676  itrack =
1677  tracks_connected_to_pin[ipin][ioff][iside][iconn];
1678  num_conns_to_track[itrack]++;
1679  }
1680  }
1681  }
1682  }
1683  }
1684 
1685  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1686  if (num_conns_to_track[itrack] <= 0) {
1687  vpr_printf(TIO_MESSAGE_ERROR, "check_all_tracks_reach_pins: Track %d does not connect to any CLB %ss.\n",
1688  itrack, (ipin_or_opin == DRIVER ? "OPIN" : "IPIN"));
1689  }
1690  }
1691 
1692  free(num_conns_to_track);
1693 }
1694 
1695 /* Allocates and loads the track to ipin lookup for each physical grid type. This
1696  * is the same information as the ipin_to_track map but accessed in a different way. */
1697 
1698 static struct s_ivec ***
1699 alloc_and_load_track_to_pin_lookup(INP int ****pin_to_track_map, INP int *Fc,
1700  INP int height, INP int num_pins, INP int nodes_per_chan) {
1701  int ipin, iside, itrack, iconn, ioff, pin_counter;
1702  struct s_ivec ***track_to_pin_lookup;
1703 
1704  /* [0..nodes_per_chan-1][0..height][0..3]. For each track number it stores a vector
1705  * for each of the four sides. x-directed channels will use the TOP and
1706  * BOTTOM vectors to figure out what clb input pins they connect to above
1707  * and below them, respectively, while y-directed channels use the LEFT
1708  * and RIGHT vectors. Each vector contains an nelem field saying how many
1709  * ipins it connects to. The list[0..nelem-1] array then gives the pin
1710  * numbers. */
1711 
1712  /* Note that a clb pin that connects to a channel on its RIGHT means that *
1713  * that channel connects to a clb pin on its LEFT. The convention used *
1714  * here is always in the perspective of the CLB */
1715 
1716  if (num_pins < 1) {
1717  return NULL;
1718  }
1719 
1720  /* Alloc and zero the the lookup table */
1721  track_to_pin_lookup = (struct s_ivec ***) alloc_matrix3(0,
1722  nodes_per_chan - 1, 0, height - 1, 0, 3, sizeof(struct s_ivec));
1723  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1724  for (ioff = 0; ioff < height; ioff++) {
1725  for (iside = 0; iside < 4; iside++) {
1726  track_to_pin_lookup[itrack][ioff][iside].nelem = 0;
1727  track_to_pin_lookup[itrack][ioff][iside].list = NULL;
1728  }
1729  }
1730  }
1731 
1732  /* Counting pass. */
1733  for (ipin = 0; ipin < num_pins; ipin++) {
1734  for (ioff = 0; ioff < height; ioff++) {
1735  for (iside = 0; iside < 4; iside++) {
1736  if (pin_to_track_map[ipin][ioff][iside][0] == OPEN)
1737  continue;
1738 
1739  for (iconn = 0; iconn < Fc[ipin]; iconn++) {
1740  itrack = pin_to_track_map[ipin][ioff][iside][iconn];
1741  track_to_pin_lookup[itrack][ioff][iside].nelem++;
1742  }
1743  }
1744  }
1745  }
1746 
1747  /* Allocate space. */
1748  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1749  for (ioff = 0; ioff < height; ioff++) {
1750  for (iside = 0; iside < 4; iside++) {
1751  track_to_pin_lookup[itrack][ioff][iside].list = NULL; /* Defensive code */
1752  if (track_to_pin_lookup[itrack][ioff][iside].nelem != 0) {
1753  track_to_pin_lookup[itrack][ioff][iside].list =
1754  (int *) my_malloc(
1755  track_to_pin_lookup[itrack][ioff][iside].nelem
1756  * sizeof(int));
1757  track_to_pin_lookup[itrack][ioff][iside].nelem = 0;
1758  }
1759  }
1760  }
1761  }
1762 
1763  /* Loading pass. */
1764  for (ipin = 0; ipin < num_pins; ipin++) {
1765  for (ioff = 0; ioff < height; ioff++) {
1766  for (iside = 0; iside < 4; iside++) {
1767  if (pin_to_track_map[ipin][ioff][iside][0] == OPEN)
1768  continue;
1769 
1770  for (iconn = 0; iconn < Fc[ipin]; iconn++) {
1771  itrack = pin_to_track_map[ipin][ioff][iside][iconn];
1772  pin_counter =
1773  track_to_pin_lookup[itrack][ioff][iside].nelem;
1774  track_to_pin_lookup[itrack][ioff][iside].list[pin_counter] =
1775  ipin;
1776  track_to_pin_lookup[itrack][ioff][iside].nelem++;
1777  }
1778  }
1779  }
1780  }
1781 
1782  return track_to_pin_lookup;
1783 }
1784 
1785 /* A utility routine to dump the contents of the routing resource graph *
1786  * (everything -- connectivity, occupancy, cost, etc.) into a file. Used *
1787  * only for debugging. */
1788 void dump_rr_graph(INP const char *file_name) {
1789 
1790  int inode;
1791  FILE *fp;
1792 
1793  fp = my_fopen(file_name, "w", 0);
1794 
1795  for (inode = 0; inode < num_rr_nodes; inode++) {
1796  print_rr_node(fp, rr_node, inode);
1797  fprintf(fp, "\n");
1798  }
1799 
1800 #if 0
1801  fprintf(fp, "\n\n%d rr_indexed_data entries.\n\n", num_rr_indexed_data);
1802 
1803  for (index = 0; index < num_rr_indexed_data; index++)
1804  {
1805  print_rr_indexed_data(fp, index);
1806  fprintf(fp, "\n");
1807  }
1808 #endif
1809 
1810  fclose(fp);
1811 }
1812 
1813 /* Prints all the data about node inode to file fp. */
1814 void print_rr_node(FILE * fp, t_rr_node * L_rr_node, int inode) {
1815 
1816  static const char *name_type[] = { "SOURCE", "SINK", "IPIN", "OPIN",
1817  "CHANX", "CHANY", "INTRA_CLUSTER_EDGE" };
1818  static const char *direction_name[] = { "OPEN", "INC_DIRECTION",
1819  "DEC_DIRECTION", "BI_DIRECTION" };
1820  static const char *drivers_name[] = { "OPEN", "MULTI_BUFFER", "SINGLE" };
1821 
1822  t_rr_type rr_type;
1823  int iconn;
1824 
1825  rr_type = L_rr_node[inode].type;
1826 
1827  /* Make sure we don't overrun const arrays */
1828  assert((int)rr_type < (int)(sizeof(name_type) / sizeof(char *)));
1829  assert(
1830  (L_rr_node[inode].direction + 1) < (int)(sizeof(direction_name) / sizeof(char *)));
1831  assert(
1832  (L_rr_node[inode].drivers + 1) < (int)(sizeof(drivers_name) / sizeof(char *)));
1833 
1834  fprintf(fp, "Node: %d %s ", inode, name_type[rr_type]);
1835  if ((L_rr_node[inode].xlow == L_rr_node[inode].xhigh)
1836  && (L_rr_node[inode].ylow == L_rr_node[inode].yhigh)) {
1837  fprintf(fp, "(%d, %d) ", L_rr_node[inode].xlow, L_rr_node[inode].ylow);
1838  } else {
1839  fprintf(fp, "(%d, %d) to (%d, %d) ", L_rr_node[inode].xlow,
1840  L_rr_node[inode].ylow, L_rr_node[inode].xhigh,
1841  L_rr_node[inode].yhigh);
1842  }
1843  fprintf(fp, "Ptc_num: %d ", L_rr_node[inode].ptc_num);
1844  fprintf(fp, "Direction: %s ",
1845  direction_name[L_rr_node[inode].direction + 1]);
1846  fprintf(fp, "Drivers: %s ", drivers_name[L_rr_node[inode].drivers + 1]);
1847  fprintf(fp, "\n");
1848 
1849  fprintf(fp, "%d edge(s):", L_rr_node[inode].num_edges);
1850  for (iconn = 0; iconn < L_rr_node[inode].num_edges; iconn++)
1851  fprintf(fp, " %d", L_rr_node[inode].edges[iconn]);
1852  fprintf(fp, "\n");
1853 
1854  fprintf(fp, "Switch types:");
1855  for (iconn = 0; iconn < L_rr_node[inode].num_edges; iconn++)
1856  fprintf(fp, " %d", L_rr_node[inode].switches[iconn]);
1857  fprintf(fp, "\n");
1858 
1859  fprintf(fp, "Occ: %d Capacity: %d\n", L_rr_node[inode].occ,
1860  L_rr_node[inode].capacity);
1861  if (rr_type != INTRA_CLUSTER_EDGE) {
1862  fprintf(fp, "R: %g C: %g\n", L_rr_node[inode].R, L_rr_node[inode].C);
1863  }
1864  fprintf(fp, "Cost_index: %d\n", L_rr_node[inode].cost_index);
1865 }
1866 
1867 /* Prints all the rr_indexed_data of index to file fp. */
1868 void print_rr_indexed_data(FILE * fp, int index) {
1869 
1870  fprintf(fp, "Index: %d\n", index);
1871 
1872  fprintf(fp, "ortho_cost_index: %d ",
1873  rr_indexed_data[index].ortho_cost_index);
1874  fprintf(fp, "base_cost: %g ", rr_indexed_data[index].saved_base_cost);
1875  fprintf(fp, "saved_base_cost: %g\n",
1876  rr_indexed_data[index].saved_base_cost);
1877 
1878  fprintf(fp, "Seg_index: %d ", rr_indexed_data[index].seg_index);
1879  fprintf(fp, "inv_length: %g\n", rr_indexed_data[index].inv_length);
1880 
1881  fprintf(fp, "T_linear: %g ", rr_indexed_data[index].T_linear);
1882  fprintf(fp, "T_quadratic: %g ", rr_indexed_data[index].T_quadratic);
1883  fprintf(fp, "C_load: %g\n", rr_indexed_data[index].C_load);
1884 }
1885 
1886 static void build_unidir_rr_opins(INP int i, INP int j,
1887  INP struct s_grid_tile **L_grid, INP int **Fc_out,
1888  INP int nodes_per_chan, INP t_seg_details * seg_details,
1889  INOUTP int **Fc_xofs, INOUTP int **Fc_yofs,
1890  INOUTP t_rr_node * L_rr_node, INOUTP boolean * L_rr_edge_done,
1891  OUTP boolean * Fc_clipped, INP t_ivec *** L_rr_node_indices, INP int delayless_switch,
1892  INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs) {
1893  /* This routine returns a list of the opins rr_nodes on each
1894  * side/offset of the block. You must free the result with
1895  * free_matrix. */
1896 
1897  t_type_ptr type;
1898  int ipin, iclass, ofs, chan, seg, max_len, inode, max_Fc = -1;
1899  enum e_side side;
1900  t_rr_type chan_type;
1901  t_linked_edge *edge_list = NULL, *next;
1902  boolean clipped, vert, pos_dir;
1903  int num_edges;
1904  int **Fc_ofs;
1905 
1906  *Fc_clipped = FALSE;
1907 
1908  /* Only the base block of a set should use this function */
1909  if (L_grid[i][j].offset > 0) {
1910  return;
1911  }
1912 
1913  type = L_grid[i][j].type;
1914 
1915  /* Currently, only two possible Fc values exist: 0 or default.
1916  * Finding the max. value of Fc in block will result in the
1917  * default value, which works for now. In the future, when
1918  * the Fc values of all pins can vary, the max value will continue
1919  * to work for matrix allocation purposes. However, all looping
1920  * will have to be modified to account for pin-based Fc values. */
1921  if (type->index > 0) {
1922  max_Fc = 0;
1923  for (ipin = 0; ipin < type->num_pins; ++ipin) {
1924  iclass = type->pin_class[ipin];
1925  if (Fc_out[type->index][ipin] > max_Fc && type->class_inf[iclass].type == DRIVER) {
1926  max_Fc = Fc_out[type->index][ipin];
1927  }
1928  }
1929  }
1930 
1931  /* Go through each pin and find its fanout. */
1932  for (ipin = 0; ipin < type->num_pins; ++ipin) {
1933  /* Skip global pins and ipins */
1934  iclass = type->pin_class[ipin];
1935  if (type->class_inf[iclass].type != DRIVER) {
1936  continue;
1937  }
1938  if (type->is_global_pin[ipin]) {
1939  continue;
1940  }
1941 
1942  num_edges = 0;
1943  edge_list = NULL;
1944  if(Fc_out[type->index][ipin] != 0) {
1945  for (ofs = 0; ofs < type->height; ++ofs) {
1946  for (side = (enum e_side)0; side < 4; side = (enum e_side)(side + 1)) {
1947  /* Can't do anything if pin isn't at this location */
1948  if (0 == type->pinloc[ofs][side][ipin]) {
1949  continue;
1950  }
1951 
1952  /* Figure out the chan seg at that side.
1953  * side is the side of the logic or io block. */
1954  vert = (boolean) ((side == TOP) || (side == BOTTOM));
1955  pos_dir = (boolean) ((side == TOP) || (side == RIGHT));
1956  chan_type = (vert ? CHANX : CHANY);
1957  chan = (vert ? (j + ofs) : i);
1958  seg = (vert ? i : (j + ofs));
1959  max_len = (vert ? nx : ny);
1960  Fc_ofs = (vert ? Fc_xofs : Fc_yofs);
1961  if (FALSE == pos_dir) {
1962  --chan;
1963  }
1964 
1965  /* Skip the location if there is no channel. */
1966  if (chan < 0) {
1967  continue;
1968  }
1969  if (seg < 1) {
1970  continue;
1971  }
1972  if (seg > (vert ? nx : ny)) {
1973  continue;
1974  }
1975  if (chan > (vert ? ny : nx)) {
1976  continue;
1977  }
1978 
1979  /* Get the list of opin to mux connections for that chan seg. */
1980  num_edges += get_unidir_opin_connections(chan, seg,
1981  max_Fc, chan_type, seg_details, &edge_list,
1982  Fc_ofs, L_rr_edge_done, max_len, nodes_per_chan,
1983  L_rr_node_indices, &clipped);
1984  if (clipped) {
1985  *Fc_clipped = TRUE;
1986  }
1987  }
1988  }
1989  }
1990 
1991  /* Add in direct connections */
1992  num_edges += get_opin_direct_connecions(i, j, ipin, &edge_list, L_rr_node_indices, delayless_switch, directs, num_directs, clb_to_clb_directs);
1993 
1994  /* Add the edges */
1995  inode = get_rr_node_index(i, j, OPIN, ipin, L_rr_node_indices);
1996  alloc_and_load_edges_and_switches(rr_node, inode, num_edges,
1997  L_rr_edge_done, edge_list);
1998  while (edge_list != NULL) {
1999  next = edge_list->next;
2000  free(edge_list);
2001  edge_list = next;
2002  }
2003  }
2004 }
2005 #if 0
2006 static void
2007 load_uniform_opin_switch_pattern_paired(INP int *Fc_out,
2008  INP int num_pins,
2009  INP int *pins_in_chan_seg,
2010  INP int num_wire_inc_muxes,
2011  INP int num_wire_dec_muxes,
2012  INP int *wire_inc_muxes,
2013  INP int *wire_dec_muxes,
2014  INOUTP t_rr_node * L_rr_node,
2015  INOUTP boolean * L_rr_edge_done,
2016  INP t_seg_details * seg_details,
2017  OUTP boolean * Fc_clipped)
2018 {
2019 
2020  /* Directionality is assumed to be uni-directional */
2021 
2022  /* Make turn-based assignment to avoid overlap when Fc_ouput is low. This is a bipartite
2023  * matching problem. Out of "num_wire_muxes" muxes "Fc_output" of them is assigned
2024  * to each outpin (total "num_pins" of them); assignment is uniform (spacing - spreadout)
2025  * and staggered to avoid overlap when Fc_output is low. */
2026 
2027  /* The natural order wires muxes are stored in wire_muxes is alternating in directionality
2028  * already (by my implementation), so no need to do anything extra to avoid directional bias */
2029 
2030  /* TODO: Due to spacing, it's possible to have directional bias: all Fc_out wires connected
2031  * to one opin goes in either INC or DEC -> whereas I want a mix of both.
2032  * SOLUTION: Use quantization of 2 to ensure that if an opin connects to one wire, it
2033  * must also connect to its companion wire, which runs in the opposite direction. This
2034  * means instead of having num_wire_muxes as the matching set, pick out the INC wires
2035  * in num_wires_muxes as the matching set (the DEC wires are their companions) April 17, 2007
2036  * NEWS: That solution does not work, as treating wires in groups will lead to serious
2037  * abnormal patterns (conns crossing multiple blocks) for W nonquantized to multiples of 2L.
2038  * So, I'm chaning that approach to a new one that avoids directional bias: I will separate
2039  * the INC muxes and DEC muxes into two sets. Each set is uniformly assigned to opins with
2040  * Fc_output/2; this should be identical as before for normal cases and contains all conns
2041  * in the same chan segment for the nonquantized cases. */
2042 
2043  /* Finally, separated the two approaches: 1. Take all wire muxes and assign them to opins
2044  * one at a time (load_uniform_opin_switch_pattern) 2. Take pairs (by companion)
2045  * of wire muxes and assign them to opins a pair at a time (load_uniform_opin_switch_pattern_paired).
2046  * The first is used for fringe channel segments (ends of channels, where
2047  * there are lots of muxes due to partial wire segments) and the second is used in core */
2048 
2049  /* float spacing, step_size, f_mux; */
2050  int ipin, iconn, num_edges, init_mux;
2051  int from_node, to_node, to_track;
2052  int xlow, ylow;
2053  t_linked_edge *edge_list;
2054  int *wire_muxes;
2055  int k, num_wire_muxes, Fc_output_per_side, CurFc;
2056  int count_inc, count_dec;
2057  t_type_ptr type;
2058 
2059  *Fc_clipped = FALSE;
2060 
2061  count_inc = count_dec = 0;
2062 
2063  for (ipin = 0; ipin < num_pins; ipin++)
2064  {
2065  from_node = pins_in_chan_seg[ipin];
2066  xlow = L_rr_node[from_node].xlow;
2067  ylow = L_rr_node[from_node].ylow;
2068  type = grid[xlow][ylow].type;
2069  edge_list = NULL;
2070  num_edges = 0;
2071 
2072  /* Assigning the INC muxes first, then DEC muxes */
2073  for (k = 0; k < 2; ++k)
2074  {
2075  if (k == 0)
2076  {
2077  num_wire_muxes = num_wire_inc_muxes;
2078  wire_muxes = wire_inc_muxes;
2079  }
2080  else
2081  {
2082  num_wire_muxes = num_wire_dec_muxes;
2083  wire_muxes = wire_dec_muxes;
2084  }
2085 
2086  /* Half the Fc will be assigned for each direction. */
2087  assert(Fc_out[type->index] % 2 == 0);
2088  Fc_output_per_side = Fc_out[type->index] / 2;
2089 
2090  /* Clip the demand. Make sure to use a new variable so
2091  * on the second pass it is not clipped. */
2092  CurFc = Fc_output_per_side;
2093  if (Fc_output_per_side > num_wire_muxes)
2094  {
2095  *Fc_clipped = TRUE;
2096  CurFc = num_wire_muxes;
2097  }
2098 
2099  if (k == 0)
2100  {
2101  init_mux = (count_inc) % num_wire_muxes;
2102  count_inc += CurFc;
2103  }
2104  else
2105  {
2106  init_mux = (count_dec) % num_wire_muxes;
2107  count_dec += CurFc;
2108  }
2109 
2110  for (iconn = 0; iconn < CurFc; iconn++)
2111  {
2112  /* FINALLY, make the outpin to mux connection */
2113  /* Latest update: I'm not using Uniform Pattern, but a similarly staggered pattern */
2114  to_node =
2115  wire_muxes[(init_mux +
2116  iconn) % num_wire_muxes];
2117 
2118  L_rr_node[to_node].num_opin_drivers++; /* keep track of mux size */
2119  to_track = L_rr_node[to_node].ptc_num;
2120 
2121  if (FALSE == L_rr_edge_done[to_node])
2122  {
2123  /* Use of alloc_and_load_edges_and_switches
2124  * must be accompanied by rr_edge_done check. */
2125  L_rr_edge_done[to_node] = TRUE;
2126  edge_list =
2127  insert_in_edge_list(edge_list,
2128  to_node,
2129  seg_details
2130  [to_track].
2131  wire_switch);
2132  num_edges++;
2133  }
2134  }
2135  }
2136 
2137  if (num_edges < 1)
2138  {
2139  vpr_printf(TIO_MESSAGE_ERROR, "opin %d at (%d,%d) does not connect to any tracks.\n",
2140  L_rr_node[from_node].ptc_num, L_rr_node[from_node].xlow, L_rr_node[from_node].ylow);
2141  exit(1);
2142  }
2143 
2144  alloc_and_load_edges_and_switches(L_rr_node, from_node, num_edges,
2145  L_rr_edge_done, edge_list);
2146  }
2147 }
2148 #endif
2149 
2150 #if MUX_SIZE_DIST_DISPLAY
2151 /* This routine prints and dumps statistics on the mux sizes on a sblock
2152  * per sblock basis, over the entire chip. Mux sizes should be balanced (off by
2153  * at most 1) for all muxes in the same sblock in the core, and corner sblocks.
2154  * Fringe sblocks will have imbalance due to missing one side and constrains on
2155  * where wires must connect. Comparing two core sblock sblocks, muxes need not
2156  * be balanced if W is not quantized to 2L multiples, again for reasons that
2157  * there could be sblocks with different number of muxes but same number of incoming
2158  * wires that need to make connections to these muxes (we don't want to under-connect
2159  * user-specified Fc and Fs). */
2160 static void
2161 view_mux_size_distribution(t_ivec *** L_rr_node_indices,
2162  int nodes_per_chan,
2163  t_seg_details * seg_details_x,
2164  t_seg_details * seg_details_y)
2165 {
2166 
2167  int i, j, itrack, seg_num, chan_num, max_len;
2168  int start, end, inode, max_value, min_value;
2169  int array_count, k, num_muxes;
2170  short direction, side;
2171  float *percent_range_array;
2172  float percent_range, percent_range_sum, avg_percent_range;
2173  float std_dev_percent_range, deviation_f;
2174  int range, *range_array, global_max_range;
2175  float avg_range, range_sum, std_dev_range;
2176  t_seg_details *seg_details;
2177  t_mux *new_mux, *sblock_mux_list_head, *current, *next;
2178 
2179 #ifdef ENABLE_DUMP
2180  FILE *dump_file_per_sblock, *dump_file;
2181 #endif /* ENABLE_DUMP */
2182  t_mux_size_distribution *distr_list, *distr_current, *new_distribution,
2183  *distr_next;
2184 
2185 #ifdef ENABLE_DUMP
2186  dump_file = my_fopen("mux_size_dump.txt", "w", 0);
2187  dump_file_per_sblock = my_fopen("mux_size_per_sblock_dump.txt", "w", 0);
2188 #endif /* ENABLE_DUMP */
2189 
2190  sblock_mux_list_head = NULL;
2191  percent_range_array =
2192  (float *)my_malloc((nx - 1) * (ny - 1) * sizeof(float));
2193  range_array = (int *)my_malloc((nx - 1) * (ny - 1) * sizeof(int));
2194  array_count = 0;
2195  percent_range_sum = 0.0;
2196  range_sum = 0.0;
2197  global_max_range = 0;
2198  min_value = 0;
2199  max_value = 0;
2200  seg_num = 0;
2201  chan_num = 0;
2202  direction = 0;
2203  seg_details = 0;
2204  max_len = 0;
2205  distr_list = NULL;
2206 
2207  /* With the specified range, I'm only looking at core sblocks */
2208  for (j = (ny - 1); j > 0; j--)
2209  {
2210  for (i = 1; i < nx; i++)
2211  {
2212  num_muxes = 0;
2213  for (side = 0; side < 4; side++)
2214  {
2215  switch (side)
2216  {
2217  case LEFT:
2218  seg_num = i;
2219  chan_num = j;
2220  direction = DEC_DIRECTION; /* only DEC have muxes in that sblock */
2221  seg_details = seg_details_x;
2222  max_len = nx;
2223  break;
2224 
2225  case RIGHT:
2226  seg_num = i + 1;
2227  chan_num = j;
2228  direction = INC_DIRECTION;
2229  seg_details = seg_details_x;
2230  max_len = nx;
2231  break;
2232 
2233  case TOP:
2234  seg_num = j + 1;
2235  chan_num = i;
2236  direction = INC_DIRECTION;
2237  seg_details = seg_details_y;
2238  max_len = ny;
2239  break;
2240 
2241  case BOTTOM:
2242  seg_num = j;
2243  chan_num = i;
2244  direction = DEC_DIRECTION;
2245  seg_details = seg_details_y;
2246  max_len = ny;
2247  break;
2248 
2249  default:
2250  assert(FALSE);
2251  }
2252 
2253  assert(nodes_per_chan > 0);
2254  for (itrack = 0; itrack < nodes_per_chan; itrack++)
2255  {
2256  start =
2257  get_seg_start(seg_details, itrack,
2258  seg_num, chan_num);
2259  end =
2260  get_seg_end(seg_details, itrack,
2261  start, chan_num, max_len);
2262 
2263  if ((seg_details[itrack].direction ==
2264  direction) && (((start == seg_num)
2265  && (direction ==
2266  INC_DIRECTION))
2267  || ((end == seg_num)
2268  && (direction ==
2269  DEC_DIRECTION))))
2270  { /* mux found */
2271  num_muxes++;
2272  if (side == LEFT || side == RIGHT)
2273  { /* CHANX */
2274  inode =
2276  (seg_num, chan_num,
2277  CHANX, itrack,
2278  L_rr_node_indices);
2279  }
2280  else
2281  {
2282  assert((side == TOP) || (side == BOTTOM)); /* CHANY */
2283  inode =
2285  (chan_num, seg_num,
2286  CHANY, itrack,
2287  L_rr_node_indices);
2288  }
2289 
2290  new_mux = (t_mux *)
2291  my_malloc(sizeof(t_mux));
2292  new_mux->size =
2293  rr_node[inode].
2294  num_wire_drivers +
2295  rr_node[inode].
2296  num_opin_drivers;
2297  new_mux->next = NULL;
2298 
2299  /* insert in linked list, descending */
2300  if (sblock_mux_list_head == NULL)
2301  {
2302  /* first entry */
2303  sblock_mux_list_head =
2304  new_mux;
2305  }
2306  else if (sblock_mux_list_head->
2307  size < new_mux->size)
2308  {
2309  /* insert before head */
2310  new_mux->next =
2311  sblock_mux_list_head;
2312  sblock_mux_list_head =
2313  new_mux;
2314  }
2315  else
2316  {
2317  /* insert after head */
2318  current =
2319  sblock_mux_list_head;
2320  next = current->next;
2321 
2322  while ((next != NULL)
2323  && (next->size >
2324  new_mux->size))
2325  {
2326  current = next;
2327  next =
2328  current->next;
2329  }
2330 
2331  if (next == NULL)
2332  {
2333  current->next =
2334  new_mux;
2335  }
2336  else
2337  {
2338  new_mux->next =
2339  current->next;
2340  current->next =
2341  new_mux;
2342  }
2343  }
2344  /* end of insert in linked list */
2345  }
2346  }
2347  } /* end of mux searching over all four sides of sblock */
2348  /* now sblock_mux_list_head holds a linked list of all muxes in this sblock */
2349 
2350  current = sblock_mux_list_head;
2351 
2352 #ifdef ENABLE_DUMP
2353  fprintf(dump_file_per_sblock,
2354  "sblock at (%d, %d) has mux sizes: {", i, j);
2355 #endif /* ENABLE_DUMP */
2356 
2357  if (current != NULL)
2358  {
2359  max_value = min_value = current->size;
2360  }
2361  while (current != NULL)
2362  {
2363  if (max_value < current->size)
2364  max_value = current->size;
2365  if (min_value > current->size)
2366  min_value = current->size;
2367 
2368 #ifdef ENABLE_DUMP
2369  fprintf(dump_file_per_sblock, "%d ",
2370  current->size);
2371  fprintf(dump_file, "%d\n", current->size);
2372 #endif /* ENABLE_DUMP */
2373 
2374  current = current->next;
2375  }
2376 
2377 #ifdef ENABLE_DUMP
2378  fprintf(dump_file_per_sblock, "}\n\tmax: %d\tmin:%d",
2379  max_value, min_value);
2380 #endif /* ENABLE_DUMP */
2381 
2382  range = max_value - min_value;
2383  percent_range = ((float)range) / ((float)min_value);
2384 
2385  if (global_max_range < range)
2386  global_max_range = range;
2387 
2388 #ifdef ENABLE_DUMP
2389  fprintf(dump_file_per_sblock,
2390  "\t\trange: %d\t\tpercent range:%.2f\n",
2391  range, percent_range);
2392 #endif /* ENABLE_DUMP */
2393 
2394  percent_range_array[array_count] = percent_range;
2395  range_array[array_count] = range;
2396 
2397  percent_range_sum += percent_range;
2398  range_sum += range;
2399 
2400  array_count++;
2401 
2402  /* I will use a distribution for each (core) sblock type.
2403  * There are more than 1 type of sblocks,
2404  * when quantization of W to 2L multiples is not observed. */
2405 
2406  distr_current = distr_list;
2407  while (distr_current != NULL
2408  && distr_current->mux_count != num_muxes)
2409  {
2410  distr_current = distr_current->next;
2411  }
2412 
2413  if (distr_current == NULL)
2414  {
2415  /* Create a distribution for the new sblock type,
2416  * and put it as head of linked list by convention */
2417 
2418  new_distribution = (t_mux_size_distribution *)
2420  new_distribution->mux_count = num_muxes;
2421  new_distribution->max_index = max_value;
2422  new_distribution->distr =
2423  (int *)my_calloc(max_value + 1, sizeof(int));
2424 
2425  /* filling in the distribution */
2426  current = sblock_mux_list_head;
2427  while (current != NULL)
2428  {
2429  assert(current->size <=
2430  new_distribution->max_index);
2431  new_distribution->distr[current->size]++;
2432  current = current->next;
2433  }
2434 
2435  /* add it to head */
2436  new_distribution->next = distr_list;
2437  distr_list = new_distribution;
2438  }
2439  else
2440  {
2441  /* distr_current->mux_count == num_muxes so add this sblock's mux sizes in this distribution */
2442  current = sblock_mux_list_head;
2443 
2444  while (current != NULL)
2445  {
2446  if (current->size >
2447  distr_current->max_index)
2448  {
2449  /* needs to realloc to expand the distribution array to hold the new large-valued data */
2450  distr_current->distr =
2451  my_realloc(distr_current->
2452  distr,
2453  (current->size +
2454  1) * sizeof(int));
2455 
2456  /* initializing the newly allocated elements */
2457  for (k =
2458  (distr_current->max_index +
2459  1); k <= current->size; k++)
2460  distr_current->distr[k] = 0;
2461 
2462  distr_current->max_index =
2463  current->size;
2464  distr_current->distr[current->
2465  size]++;
2466  }
2467  else
2468  {
2469  distr_current->distr[current->
2470  size]++;
2471  }
2472  current = current->next;
2473  }
2474  }
2475 
2476  /* done - now free memory */
2477  current = sblock_mux_list_head;
2478  while (current != NULL)
2479  {
2480  next = current->next;
2481  free(current);
2482  current = next;
2483  }
2484  sblock_mux_list_head = NULL;
2485  }
2486  }
2487 
2488  avg_percent_range = (float)percent_range_sum / array_count;
2489  avg_range = (float)range_sum / array_count;
2490 
2491  percent_range_sum = 0.0;
2492  range_sum = 0.0;
2493  for (k = 0; k < array_count; k++)
2494  {
2495  deviation_f = (percent_range_array[k] - avg_percent_range);
2496  percent_range_sum += deviation_f * deviation_f;
2497 
2498  deviation_f = ((float)range_array[k] - avg_range);
2499  range_sum += deviation_f * deviation_f;
2500  }
2501  std_dev_percent_range =
2502  sqrt(percent_range_sum / ((float)array_count - 1.0));
2503  std_dev_range = sqrt(range_sum / ((float)array_count - 1.0));
2504  vpr_printf(TIO_MESSAGE_INFO, "==== MUX size statistics ====\n");
2505  vpr_printf(TIO_MESSAGE_INFO, "Max range of mux size within a sblock: %d\n", global_max_range);
2506  vpr_printf(TIO_MESSAGE_INFO, "Average range of mux size within a sblock: %.2f\n", avg_range);
2507  vpr_printf(TIO_MESSAGE_INFO, "Std dev of range of mux size within a sblock: %.2f\n", std_dev_range);
2508  vpr_printf(TIO_MESSAGE_INFO, "Average percent range of mux size within a sblock: %.2f%%\n", avg_percent_range * 100.0);
2509  vpr_printf(TIO_MESSAGE_INFO, "Std dev of percent range of mux size within a sblock: %.2f%%\n", std_dev_percent_range * 100.0);
2510 
2511  vpr_printf(TIO_MESSAGE_INFO, " -- Detailed MUX size distribution by sblock type -- \n");
2512  distr_current = distr_list;
2513  while (distr_current != NULL)
2514  {
2515  print_distribution(stdout, distr_current);
2516 
2517  /* free */
2518  distr_next = distr_current->next;
2519 
2520  free(distr_current->distr);
2521  free(distr_current);
2522 
2523  distr_current = distr_next;
2524  }
2525 
2526  free(percent_range_array);
2527  free(range_array);
2528 #ifdef ENABLE_DUMP
2529  fclose(dump_file_per_sblock);
2530  fclose(dump_file);
2531 #endif /* ENABLE_DUMP */
2532 }
2533 
2534 static void
2535 print_distribution(FILE * fptr,
2536  t_mux_size_distribution * distr_struct)
2537 {
2538  int *distr;
2539  int k;
2540  float sum;
2541  boolean zeros;
2542 
2543  distr = distr_struct->distr;
2544  fprintf(fptr,
2545  "For Sblocks containing %d MUXes, the MUX size distribution is:\n",
2546  distr_struct->mux_count);
2547  fprintf(fptr, "\t\t\tSize\t\t\tFrequency (percent)\n");
2548 
2549  sum = 0.0;
2550  for (k = 0; k <= distr_struct->max_index; k++)
2551  sum += distr[k];
2552 
2553  zeros = TRUE;
2554  for (k = 0; k <= distr_struct->max_index; k++)
2555  {
2556  if (zeros && (distr[k] == 0))
2557  {
2558  /* do nothing for leading string of zeros */
2559  }
2560  else
2561  {
2562  zeros = FALSE; /* leading string of zeros ended */
2563  fprintf(fptr, "\t\t\t%d\t\t\t%d (%.2f%%)\n", k, distr[k],
2564  (float)distr[k] / sum * 100.0);
2565  }
2566  }
2567  fprintf(fptr, "\nEnd of this Sblock MUX size distribution.\n");
2568 
2569 }
2570 #endif
2571 
2572 /**
2573  * Parse out which CLB pins should connect directly to which other CLB pins then store that in a clb_to_clb_directs data structure
2574  * This data structure supplements the the info in the "directs" data structure
2575  * TODO: The function that does this parsing in placement is poorly done because it lacks generality on heterogeniety, should replace with this one
2576  */
2578  int i, j;
2579  t_clb_to_clb_directs *clb_to_clb_directs;
2580  char *pb_type_name, *port_name;
2581  int start_pin_index, end_pin_index;
2582  t_pb_type *pb_type;
2583 
2584  clb_to_clb_directs = (t_clb_to_clb_directs*)my_calloc(num_directs, sizeof(t_clb_to_clb_directs));
2585 
2586  pb_type_name = NULL;
2587  port_name = NULL;
2588 
2589  for(i = 0; i < num_directs; i++) {
2590  pb_type_name = (char*)my_malloc((strlen(directs[i].from_pin) + strlen(directs[i].to_pin)) * sizeof(char));
2591  port_name = (char*)my_malloc((strlen(directs[i].from_pin) + strlen(directs[i].to_pin)) * sizeof(char));
2592 
2593  // Load from pins
2594  // Parse out the pb_type name, port name, and pin range
2595  parse_direct_pin_name(directs[i].from_pin, directs[i].line, &start_pin_index, &end_pin_index, pb_type_name, port_name);
2596 
2597  // Figure out which type, port, and pin is used
2598  for(j = 0; j < num_types; j++) {
2599  if(strcmp(type_descriptors[j].name, pb_type_name) == 0) {
2600  break;
2601  }
2602  }
2603  assert(j < num_types);
2604  clb_to_clb_directs[i].from_clb_type = &type_descriptors[j];
2605  pb_type = clb_to_clb_directs[i].from_clb_type->pb_type;
2606 
2607  for(j = 0; j < pb_type->num_ports; j++) {
2608  if(strcmp(pb_type->ports[j].name, port_name) == 0) {
2609  break;
2610  }
2611  }
2612  assert(j < pb_type->num_ports);
2613 
2614  if(start_pin_index == OPEN) {
2615  assert(start_pin_index == end_pin_index);
2616  start_pin_index = 0;
2617  end_pin_index = pb_type->ports[j].num_pins - 1;
2618  }
2619  get_blk_pin_from_port_pin(clb_to_clb_directs[i].from_clb_type->index, j, start_pin_index, &clb_to_clb_directs[i].from_clb_pin_start_index);
2620  get_blk_pin_from_port_pin(clb_to_clb_directs[i].from_clb_type->index, j, end_pin_index, &clb_to_clb_directs[i].from_clb_pin_end_index);
2621 
2622  // Load to pins
2623  // Parse out the pb_type name, port name, and pin range
2624  parse_direct_pin_name(directs[i].to_pin, directs[i].line, &start_pin_index, &end_pin_index, pb_type_name, port_name);
2625 
2626  // Figure out which type, port, and pin is used
2627  for(j = 0; j < num_types; j++) {
2628  if(strcmp(type_descriptors[j].name, pb_type_name) == 0) {
2629  break;
2630  }
2631  }
2632  assert(j < num_types);
2633  clb_to_clb_directs[i].to_clb_type = &type_descriptors[j];
2634  pb_type = clb_to_clb_directs[i].to_clb_type->pb_type;
2635 
2636  for(j = 0; j < pb_type->num_ports; j++) {
2637  if(strcmp(pb_type->ports[j].name, port_name) == 0) {
2638  break;
2639  }
2640  }
2641  assert(j < pb_type->num_ports);
2642 
2643  if(start_pin_index == OPEN) {
2644  assert(start_pin_index == end_pin_index);
2645  start_pin_index = 0;
2646  end_pin_index = pb_type->ports[j].num_pins - 1;
2647  }
2648 
2649  get_blk_pin_from_port_pin(clb_to_clb_directs[i].to_clb_type->index, j, start_pin_index, &clb_to_clb_directs[i].to_clb_pin_start_index);
2650  get_blk_pin_from_port_pin(clb_to_clb_directs[i].to_clb_type->index, j, end_pin_index, &clb_to_clb_directs[i].to_clb_pin_end_index);
2651 
2652  if(abs(clb_to_clb_directs[i].from_clb_pin_start_index - clb_to_clb_directs[i].from_clb_pin_end_index) != abs(clb_to_clb_directs[i].to_clb_pin_start_index - clb_to_clb_directs[i].to_clb_pin_end_index)) {
2653  vpr_printf(TIO_MESSAGE_ERROR, "[LINE %d] Range mismatch from %s to %s.\n", directs[i].line, directs[i].from_pin, directs[i].to_pin);
2654  exit(1);
2655  }
2656 
2657  free(pb_type_name);
2658  free(port_name);
2659  }
2660  return clb_to_clb_directs;
2661 }
2662 
2663 /* Add all direct clb-pin-to-clb-pin edges to given opin */
2664 static int get_opin_direct_connecions(int x, int y, int opin, INOUTP t_linked_edge ** edge_list_ptr, INP t_ivec *** L_rr_node_indices,
2665  INP int delayless_switch, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs) {
2666  t_type_ptr type;
2667  int grid_ofs;
2668  int i, ipin, inode;
2669  t_linked_edge *edge_list_head;
2670  int max_index, min_index, offset, swap;
2671  int new_edges;
2672 
2673  type = grid[x][y].type;
2674  edge_list_head = *edge_list_ptr;
2675  new_edges = 0;
2676 
2677  /* Iterate through all direct connections */
2678  for(i = 0; i < num_directs; i++) {
2679  /* Find matching direct clb-to-clb connections with the same type as current grid location */
2680  if(clb_to_clb_directs[i].from_clb_type == type) {
2681  /* Compute index of opin with regards to given pins */
2682  if(clb_to_clb_directs[i].from_clb_pin_start_index > clb_to_clb_directs[i].from_clb_pin_end_index) {
2683  swap = TRUE;
2684  max_index = clb_to_clb_directs[i].from_clb_pin_start_index;
2685  min_index = clb_to_clb_directs[i].from_clb_pin_end_index;
2686  } else {
2687  swap = FALSE;
2688  min_index = clb_to_clb_directs[i].from_clb_pin_start_index;
2689  max_index = clb_to_clb_directs[i].from_clb_pin_end_index;
2690  }
2691  if(max_index >= opin && min_index <= opin) {
2692  offset = opin - min_index;
2693  /* This opin is specified to connect directly to an ipin, now compute which ipin to connect to */
2694  if(x + directs[i].x_offset < nx + 1 &&
2695  x + directs[i].x_offset > 0 &&
2696  y + directs[i].y_offset < ny + 1 &&
2697  y + directs[i].y_offset > 0) {
2698  ipin = OPEN;
2699  if(clb_to_clb_directs[i].to_clb_pin_start_index > clb_to_clb_directs[i].to_clb_pin_end_index) {
2700  if(swap == TRUE) {
2701  ipin = clb_to_clb_directs[i].to_clb_pin_end_index + offset;
2702  } else {
2703  ipin = clb_to_clb_directs[i].to_clb_pin_start_index - offset;
2704  }
2705  } else {
2706  if(swap == TRUE) {
2707  ipin = clb_to_clb_directs[i].to_clb_pin_end_index - offset;
2708  } else {
2709  ipin = clb_to_clb_directs[i].to_clb_pin_start_index + offset;
2710  }
2711  }
2712  /* Add new ipin edge to list of edges */
2713  grid_ofs = grid[x + directs[i].x_offset][y + directs[i].y_offset].offset;
2714  inode = get_rr_node_index(x + directs[i].x_offset, y + directs[i].y_offset - grid_ofs, IPIN, ipin, L_rr_node_indices);
2715  edge_list_head = insert_in_edge_list(edge_list_head, inode, delayless_switch);
2716  new_edges++;
2717  }
2718  }
2719  }
2720  }
2721  *edge_list_ptr = edge_list_head;
2722  return new_edges;
2723 }
2724 
2725 
2726 
t_type_ptr type
Definition: vpr_types.h:522
int * node_block_pin
Definition: vpr_types.h:509
void print_rr_indexed_data(FILE *fp, int index)
Definition: rr_graph.c:1868
Definition: util.h:57
short num_edges
Definition: vpr_types.h:901
static void build_rr_sinks_sources(INP int i, INP int j, INP t_rr_node *L_rr_node, INP t_ivec ***L_rr_node_indices, INP int delayless_switch, INP struct s_grid_tile **L_grid)
Definition: rr_graph.c:925
t_pb_graph_pin ** clock_pins
FILE * my_fopen(const char *fname, const char *flag, int prompt)
Definition: util.c:54
short wire_switch
Definition: vpr_types.h:809
void free_rr_graph(void)
Definition: rr_graph.c:798
int num_pins
void ** alloc_matrix(int nrmin, int nrmax, int ncmin, int ncmax, size_t elsize)
Definition: util.c:551
void free_matrix4(void *vptr, int nrmin, int nrmax, int ncmin, int ncmax, int ndmin, int ndmax, int nemin, size_t elsize)
Definition: util.c:678
void get_blk_pin_from_port_pin(int blk_type_index, int port, int port_pin, int *blk_pin)
Definition: vpr_utils.c:818
t_rr_node * rr_node
Definition: globals.c:70
int from_clb_pin_end_index
Definition: rr_graph.c:39
static t_chunk rr_mem_ch
Definition: rr_graph.c:50
struct s_clb_to_clb_directs t_clb_to_clb_directs
int size
Definition: rr_graph.c:25
void get_class_range_for_block(INP int iblk, OUTP int *class_low, OUTP int *class_high)
Definition: vpr_utils.c:162
static void build_rr_ychan(INP int i, INP int j, INP struct s_ivec ****track_to_ipin_lookup, INP struct s_ivec ***switch_block_conn, INP int cost_index_offset, INP int nodes_per_chan, INP int *opin_mux_size, INP short *****sblock_pattern, INP int Fs_per_side, INP t_seg_details *seg_details, INP t_ivec ***L_rr_node_indices, INP boolean *L_rr_edge_done, INOUTP t_rr_node *L_rr_node, INP int wire_to_ipin_switch, INP enum e_directionality directionality)
Definition: rr_graph.c:1205
struct s_class * class_inf
void free_matrix(void *vptr, int nrmin, int nrmax, int ncmin, size_t elsize)
Definition: util.c:573
float Rmetal
Definition: vpr_types.h:811
#define nint(a)
Definition: util.h:24
boolean
Definition: util.h:11
t_rr_indexed_data * rr_indexed_data
Definition: globals.c:74
void free_matrix3(void *vptr, int nrmin, int nrmax, int ncmin, int ncmax, int ndmin, size_t elsize)
Definition: util.c:663
int * list
Definition: util.h:49
static t_seg_details * alloc_and_load_global_route_seg_details(INP int nodes_per_chan, INP int global_route_switch)
Definition: rr_graph.c:540
int get_seg_start(INP t_seg_details *seg_details, INP int itrack, INP int chan_num, INP int seg_num)
Definition: rr_graph2.c:416
int x
Definition: vpr_types.h:563
enum e_graph_type t_graph_type
Definition: rr_graph.h:11
t_seg_details * alloc_and_load_seg_details(INOUTP int *nodes_per_chan, INP int max_len, INP int num_seg_types, INP t_segment_inf *segment_inf, INP boolean use_full_seg_groups, INP boolean is_global_graph, INP enum e_directionality directionality)
Definition: rr_graph2.c:175
int num_rr_indexed_data
Definition: globals.c:73
void check_rr_graph(INP t_graph_type graph_type, INP t_type_ptr types, INP int L_nx, INP int L_ny, INP int nodes_per_chan, INP int Fs, INP int num_seg_types, INP int num_switches, INP t_segment_inf *segment_inf, INP int global_route_switch, INP int delayless_switch, INP int wire_to_ipin_switch, t_seg_details *seg_details, int **Fc_in, int **Fc_out, int *****opin_to_track_map, int *****ipin_to_track_map, t_ivec ****track_to_ipin_lookup, t_ivec ***switch_block_conn, boolean *perturb_ipins)
void load_sblock_pattern_lookup(INP int i, INP int j, INP int nodes_per_chan, INP t_seg_details *seg_details, INP int Fs, INP enum e_switch_block_type switch_block_type, INOUTP short *****sblock_pattern)
Definition: rr_graph2.c:1524
void * my_chunk_malloc(size_t size, t_chunk *chunk_info)
Definition: util.c:184
t_linked_edge * insert_in_edge_list(INP t_linked_edge *head, INP int edge, INP short iswitch)
Definition: rr_graph_util.c:7
e_switch_block_type
enum e_drivers drivers
Definition: vpr_types.h:815
struct s_ivec *** alloc_and_load_rr_node_indices(INP int nodes_per_chan, INP int L_nx, INP int L_ny, INOUTP int *index, INP t_seg_details *seg_details)
Definition: rr_graph2.c:707
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
static void free_type_pin_to_track_map(int *****ipin_to_track_map, t_type_ptr types)
Definition: rr_graph.c:656
e_side
int num_nets
Definition: globals.c:27
int * node_block
Definition: vpr_types.h:507
int to_clb_pin_start_index
Definition: rr_graph.c:41
float Cmetal
Definition: vpr_types.h:812
struct s_mux_size_distribution t_mux_size_distribution
t_pb_graph_pin ** output_pins
struct s_linked_vptr * chunk_ptr_head
Definition: util.h:58
t_type_ptr type
Definition: vpr_types.h:561
static int **** alloc_and_load_pin_to_track_map(INP enum e_pin_type pin_type, INP int nodes_per_chan, INP int *Fc, INP t_type_ptr Type, INP boolean perturb_switch_pattern, INP enum e_directionality directionality)
Definition: rr_graph.c:1358
static void build_bidir_rr_opins(INP int i, INP int j, INOUTP t_rr_node *L_rr_node, INP t_ivec ***L_rr_node_indices, INP int *****opin_to_track_map, INP int **Fc_out, INP boolean *L_rr_edge_done, INP t_seg_details *seg_details, INP struct s_grid_tile **L_grid, INP int delayless_switch, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs)
Definition: rr_graph.c:748
#define INOUTP
Definition: util.h:21
int num_blocks
Definition: globals.c:30
boolean getEchoEnabled(void)
Definition: ReadOptions.c:67
void load_net_rr_terminals(t_ivec ***L_rr_node_indices)
Definition: rr_graph.c:855
static void load_uniform_switch_pattern(INP t_type_ptr type, INOUTP int ****tracks_connected_to_pin, INP int num_phys_pins, INP int *pin_num_ordering, INP int *side_ordering, INP int *offset_ordering, INP int nodes_per_chan, INP int Fc, INP enum e_directionality directionality)
static const char * name_type[]
Definition: draw.c:87
static void rr_graph_externals(t_timing_inf timing_inf, t_segment_inf *segment_inf, int num_seg_types, int nodes_per_chan, int wire_to_ipin_switch, enum e_base_cost_type base_cost_type)
Definition: rr_graph.c:489
Definition: util.h:12
static void free_type_track_to_ipin_map(struct s_ivec ****track_to_pin_map, t_type_ptr types, int nodes_per_chan)
Definition: rr_graph.c:633
short opin_switch
Definition: vpr_types.h:810
int get_bidir_opin_connections(INP int i, INP int j, INP int ipin, INP struct s_linked_edge **edge_list, INP int *****opin_to_track_map, INP int Fc, INP boolean *L_rr_edge_done, INP t_ivec ***L_rr_node_indices, INP t_seg_details *seg_details)
Definition: rr_graph2.c:478
int get_rr_node_index(int x, int y, t_rr_type rr_type, int ptc, t_ivec ***L_rr_node_indices)
Definition: rr_graph2.c:846
struct s_ivec *** alloc_and_load_switch_block_conn(INP int nodes_per_chan, INP enum e_switch_block_type switch_block_type, INP int Fs)
Definition: rr_graph_sbox.c:36
int y
Definition: vpr_types.h:564
#define min(a, b)
Definition: graphics.c:174
struct s_mux t_mux
int get_track_to_tracks(INP int from_chan, INP int from_seg, INP int from_track, INP t_rr_type from_type, INP int to_seg, INP t_rr_type to_type, INP int chan_len, INP int nodes_per_chan, INP int *opin_mux_size, INP int Fs_per_side, INP short *****sblock_pattern, INOUTP struct s_linked_edge **edge_list, INP t_seg_details *seg_details, INP enum e_directionality directionality, INP t_ivec ***L_rr_node_indices, INOUTP boolean *L_rr_edge_done, INP struct s_ivec ***switch_block_conn)
Definition: rr_graph2.c:1017
struct s_mux_size_distribution * next
Definition: rr_graph.c:33
static int ** alloc_and_load_actual_fc(INP int L_num_types, INP t_type_ptr types, INP int nodes_per_chan, INP boolean is_Fc_out, INP enum e_directionality directionality, OUTP boolean *Fc_clipped, INP boolean ignore_Fc_0)
Definition: rr_graph.c:570
t_type_descriptor * from_clb_type
Definition: rr_graph.c:37
static void build_unidir_rr_opins(INP int i, INP int j, INP struct s_grid_tile **L_grid, INP int **Fc_out, INP int nodes_per_chan, INP t_seg_details *seg_details, INOUTP int **Fc_xofs, INOUTP int **Fc_yofs, INOUTP t_rr_node *L_rr_node, INOUTP boolean *L_rr_edge_done, OUTP boolean *Fc_clipped, INP t_ivec ***L_rr_node_indices, INP int delayless_switch, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs)
Definition: rr_graph.c:1886
static void * my_malloc(int ibytes)
Definition: graphics.c:499
int get_unidir_opin_connections(INP int chan, INP int seg, INP int Fc, INP t_rr_type chan_type, INP t_seg_details *seg_details, INOUTP t_linked_edge **edge_list_ptr, INOUTP int **Fc_ofs, INOUTP boolean *L_rr_edge_done, INP int max_len, INP int nodes_per_chan, INP t_ivec ***L_rr_node_indices, OUTP boolean *Fc_clipped)
Definition: rr_graph2.c:551
int * pinlist
#define max(a, b)
Definition: graphics.c:171
void build_rr_graph(INP t_graph_type graph_type, INP int L_num_types, INP t_type_ptr types, INP int L_nx, INP int L_ny, INP struct s_grid_tile **L_grid, INP int chan_width, INP struct s_chan_width_dist *chan_capacity_inf, INP enum e_switch_block_type sb_type, INP int Fs, INP int num_seg_types, INP int num_switches, INP t_segment_inf *segment_inf, INP int global_route_switch, INP int delayless_switch, INP t_timing_inf timing_inf, INP int wire_to_ipin_switch, INP enum e_base_cost_type base_cost_type, INP t_direct_inf *directs, INP int num_directs, INP boolean ignore_Fc_0, OUTP int *Warnings)
Definition: rr_graph.c:192
struct s_block * block
Definition: globals.c:31
static void alloc_and_load_rr_clb_source(t_ivec ***L_rr_node_indices)
Definition: rr_graph.c:886
static void build_rr_xchan(INP int i, INP int j, INP struct s_ivec ****track_to_ipin_lookup, INP struct s_ivec ***switch_block_conn, INP int cost_index_offset, INP int nodes_per_chan, INP int *opin_mux_size, INP short *****sblock_pattern, INP int Fs_per_side, INP t_seg_details *seg_details, INP t_ivec ***L_rr_node_indices, INP boolean *L_rr_edge_done, INOUTP t_rr_node *L_rr_node, INP int wire_to_ipin_switch, INP enum e_directionality directionality)
e_drivers
Definition: vpr_types.h:793
struct s_net * clb_net
Definition: globals.c:28
int nelem
Definition: util.h:48
#define INP
Definition: util.h:19
int num_rr_nodes
Definition: globals.c:69
int nx
Definition: globals.c:46
void alloc_and_load_rr_indexed_data(INP t_segment_inf *segment_inf, INP int num_segment, INP t_ivec ***L_rr_node_indices, INP int nodes_per_chan, int wire_to_ipin_switch, enum e_base_cost_type base_cost_type)
char * name
static t_clb_to_clb_directs * alloc_and_load_clb_to_clb_directs(INP t_direct_inf *directs, INP int num_directs)
Definition: rr_graph.c:2577
enum e_direction direction
Definition: vpr_types.h:814
void print_rr_node(FILE *fp, t_rr_node *L_rr_node, int inode)
Definition: rr_graph.c:1814
e_direction
Definition: vpr_types.h:798
void dump_rr_graph(INP const char *file_name)
Definition: rr_graph.c:1788
boolean isEchoFileEnabled(enum e_echo_files echo_option)
Definition: ReadOptions.c:115
short capacity
Definition: vpr_types.h:899
e_pin_type
int num_opin_drivers
Definition: vpr_types.h:912
void add_rr_graph_C_from_switches(float C_ipin_cblock)
void parse_direct_pin_name(char *src_string, int line, int *start_pin_index, int *end_pin_index, char *pb_type_name, char *port_name)
Definition: vpr_utils.c:925
struct s_grid_tile ** grid
Definition: globals.c:59
static void alloc_net_rr_terminals(void)
Definition: rr_graph.c:843
void **** alloc_matrix4(int nrmin, int nrmax, int ncmin, int ncmax, int ndmin, int ndmax, int nemin, int nemax, size_t elsize)
Definition: util.c:611
void free_sblock_pattern_lookup(INOUTP short *****sblock_pattern)
Definition: rr_graph2.c:1508
Definition: util.h:47
e_base_cost_type
Definition: vpr_types.h:688
static int get_opin_direct_connecions(int x, int y, int opin, INOUTP t_linked_edge **edge_list_ptr, INP t_ivec ***L_rr_node_indices, INP int delayless_switch, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs)
Definition: rr_graph.c:2664
t_ivec *** rr_node_indices
Definition: globals.c:71
void free_seg_details(t_seg_details *seg_details, int nodes_per_chan)
Definition: rr_graph2.c:358
enum e_rr_type t_rr_type
boolean longline
Definition: vpr_types.h:806
static void alloc_and_load_rr_graph(INP int num_nodes, INP t_rr_node *L_rr_node, INP int num_seg_types, INP t_seg_details *seg_details, INP boolean *L_rr_edge_done, INP struct s_ivec ****track_to_ipin_lookup, INP int *****opin_to_track_map, INP struct s_ivec ***switch_block_conn, INP struct s_grid_tile **L_grid, INP int L_nx, INP int L_ny, INP int Fs, INP short *****sblock_pattern, INP int **Fc_out, INP int **Fc_xofs, INP int **Fc_yofs, INP t_ivec ***L_rr_node_indices, INP int nodes_per_chan, INP enum e_switch_block_type sb_type, INP int delayless_switch, INP enum e_directionality directionality, INP int wire_to_ipin_switch, OUTP boolean *Fc_clipped, INP t_direct_inf *directs, INP int num_directs, INP t_clb_to_clb_directs *clb_to_clb_directs)
Definition: rr_graph.c:668
struct s_pb_type * pb_type
int num_types
Definition: globals.c:37
static void * my_realloc(void *memblk, int ibytes)
Definition: graphics.c:512
int ** rr_blk_source
Definition: globals.c:87
int get_seg_end(INP t_seg_details *seg_details, INP int itrack, INP int istart, INP int chan_num, INP int seg_max)
Definition: rr_graph2.c:446
boolean * sb
Definition: vpr_types.h:807
static boolean * alloc_and_load_perturb_ipins(INP int nodes_per_chan, INP int L_num_types, INP int **Fc_in, INP int **Fc_out, INP enum e_directionality directionality)
Definition: rr_graph.c:502
Definition: rr_graph.c:24
t_port * ports
Definition: slre.c:50
short ***** alloc_sblock_pattern_lookup(INP int L_nx, INP int L_ny, INP int nodes_per_chan)
Definition: rr_graph2.c:1444
int ** net_rr_terminals
Definition: globals.c:78
t_pb_graph_node * pb_graph_head
static void check_all_tracks_reach_pins(t_type_ptr type, int ****tracks_connected_to_pin, int nodes_per_chan, int Fc, enum e_pin_type ipin_or_opin)
Definition: rr_graph.c:1658
struct s_type_descriptor * type_descriptors
Definition: globals.c:38
char * getEchoFileName(enum e_echo_files echo_option)
Definition: ReadOptions.c:122
#define OUTP
Definition: util.h:20
t_type_descriptor * to_clb_type
Definition: rr_graph.c:40
enum e_pin_type type
void free_switch_block_conn(struct s_ivec ***switch_block_conn, int nodes_per_chan)
Definition: rr_graph_sbox.c:92
void free_chunk_memory(t_chunk *chunk_info)
Definition: util.c:270
static void load_perturbed_switch_pattern(INP t_type_ptr type, INOUTP int ****tracks_connected_to_pin, INP int num_phys_pins, INP int *pin_num_ordering, INP int *side_ordering, INP int *offset_ordering, INP int nodes_per_chan, INP int Fc, INP enum e_directionality directionality)
void watch_edges(int inode, t_linked_edge *edge_list_head)
Definition: rr_graph.c:1298
int num_output_pins
boolean * is_global_pin
int ny
Definition: globals.c:47
void *** alloc_matrix3(int nrmin, int nrmax, int ncmin, int ncmax, int ndmin, int ndmax, size_t elsize)
Definition: util.c:585
messagelogger vpr_printf
Definition: util.c:17
int get_track_to_ipins(int seg, int chan, int track, t_linked_edge **edge_list_ptr, t_ivec ***L_rr_node_indices, struct s_ivec ****track_to_ipin_lookup, t_seg_details *seg_details, enum e_rr_type chan_type, int chan_length, int wire_to_ipin_switch, enum e_directionality directionality)
Definition: rr_graph2.c:929
int num_sinks
Definition: vpr_types.h:506
int num_input_pins
void dump_seg_details(t_seg_details *seg_details, int nodes_per_chan, const char *fname)
Definition: rr_graph2.c:373
t_rr_type type
Definition: vpr_types.h:902
static struct s_ivec *** alloc_and_load_track_to_pin_lookup(INP int ****pin_to_track_map, INP int *Fc, INP int height, INP int num_pins, INP int nodes_per_chan)
Definition: rr_graph.c:1699
struct s_linked_edge * next
Definition: rr_graph_util.h:4
t_pb_graph_pin ** input_pins
int num_clock_pins
Definition: util.h:12
void free_rr_node_indices(INP t_ivec ***L_rr_node_indices)
Definition: rr_graph2.c:797
boolean * cb
Definition: vpr_types.h:808
int num_wire_drivers
Definition: vpr_types.h:911
struct s_mux * next
Definition: rr_graph.c:26
int from_clb_pin_start_index
Definition: rr_graph.c:38
void alloc_and_load_edges_and_switches(INP t_rr_node *L_rr_node, INP int inode, INP int num_edges, INP boolean *L_rr_edge_done, INP t_linked_edge *edge_list_head)
e_directionality