VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
rr_graph2.h File Reference
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

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)
 
void free_rr_node_indices (INP t_ivec ***L_rr_node_indices)
 
int get_rr_node_index (int x, int y, t_rr_type rr_type, int ptc, t_ivec ***L_rr_node_indices)
 
void free_seg_details (t_seg_details *seg_details, int nodes_per_chan)
 
t_seg_detailsalloc_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)
 
void dump_seg_details (t_seg_details *seg_details, int nodes_per_chan, const char *fname)
 
int get_seg_start (INP t_seg_details *seg_details, INP int itrack, INP int chan_num, INP int seg_num)
 
int get_seg_end (INP t_seg_details *seg_details, INP int itrack, INP int istart, INP int chan_num, INP int seg_max)
 
boolean is_cbox (INP int chan, INP int seg, INP int track, INP t_seg_details *seg_details, INP enum e_directionality directionality)
 
boolean is_sbox (INP int chan, INP int wire_seg, INP int sb_seg, INP int track, INP t_seg_details *seg_details, INP enum e_directionality directionality)
 
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)
 
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)
 
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)
 
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)
 
short ***** alloc_sblock_pattern_lookup (INP int L_nx, INP int L_ny, INP int nodes_per_chan)
 
void free_sblock_pattern_lookup (INOUTP short *****sblock_pattern)
 
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)
 

Variables

booleanrr_edge_done
 

Function Documentation

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 at line 707 of file rr_graph2.c.

708  {
709 
710  /* Allocates and loads all the structures needed for fast lookups of the *
711  * index of an rr_node. rr_node_indices is a matrix containing the index *
712  * of the *first* rr_node at a given (i,j) location. */
713 
714  int i, j, k, ofs;
715  t_ivec ***indices;
716  t_ivec tmp;
717  t_type_ptr type;
718 
719  /* Alloc the lookup table */
720  indices = (t_ivec ***) my_malloc(sizeof(t_ivec **) * NUM_RR_TYPES);
721  indices[IPIN] = (t_ivec **) my_malloc(sizeof(t_ivec *) * (L_nx + 2));
722  indices[SINK] = (t_ivec **) my_malloc(sizeof(t_ivec *) * (L_nx + 2));
723  for (i = 0; i <= (L_nx + 1); ++i) {
724  indices[IPIN][i] = (t_ivec *) my_malloc(sizeof(t_ivec) * (L_ny + 2));
725  indices[SINK][i] = (t_ivec *) my_malloc(sizeof(t_ivec) * (L_ny + 2));
726  for (j = 0; j <= (L_ny + 1); ++j) {
727  indices[IPIN][i][j].nelem = 0;
728  indices[IPIN][i][j].list = NULL;
729 
730  indices[SINK][i][j].nelem = 0;
731  indices[SINK][i][j].list = NULL;
732  }
733  }
734 
735  /* Count indices for block nodes */
736  for (i = 0; i <= (L_nx + 1); i++) {
737  for (j = 0; j <= (L_ny + 1); j++) {
738  ofs = grid[i][j].offset;
739  if (0 == ofs) {
740  type = grid[i][j].type;
741 
742  /* Load the pin class lookups. The ptc nums for SINK and SOURCE
743  * are disjoint so they can share the list. */
744  tmp.nelem = type->num_class;
745  tmp.list = NULL;
746  if (tmp.nelem > 0) {
747  tmp.list = (int *) my_malloc(sizeof(int) * tmp.nelem);
748  for (k = 0; k < tmp.nelem; ++k) {
749  tmp.list[k] = *index;
750  ++(*index);
751  }
752  }
753  indices[SINK][i][j] = tmp;
754 
755  /* Load the pin lookups. The ptc nums for IPIN and OPIN
756  * are disjoint so they can share the list. */
757  tmp.nelem = type->num_pins;
758  tmp.list = NULL;
759  if (tmp.nelem > 0) {
760  tmp.list = (int *) my_malloc(sizeof(int) * tmp.nelem);
761  for (k = 0; k < tmp.nelem; ++k) {
762  tmp.list[k] = *index;
763  ++(*index);
764  }
765  }
766  indices[IPIN][i][j] = tmp;
767  }
768  }
769  }
770 
771  /* Point offset blocks of a large block to base block */
772  for (i = 0; i <= (L_nx + 1); i++) {
773  for (j = 0; j <= (L_ny + 1); j++) {
774  ofs = grid[i][j].offset;
775  if (ofs > 0) {
776  /* NOTE: this only supports vertical large blocks */
777  indices[SINK][i][j] = indices[SINK][i][j - ofs];
778  indices[IPIN][i][j] = indices[IPIN][i][j - ofs];
779  }
780  }
781  }
782 
783  /* SOURCE and SINK have unique ptc values so their data can be shared.
784  * IPIN and OPIN have unique ptc values so their data can be shared. */
785  indices[SOURCE] = indices[SINK];
786  indices[OPIN] = indices[IPIN];
787 
788  /* Load the data for x and y channels */
789  load_chan_rr_indices(nodes_per_chan, L_nx + 1, L_ny + 1, CHANX, seg_details,
790  index, indices);
791  load_chan_rr_indices(nodes_per_chan, L_ny + 1, L_nx + 1, CHANY, seg_details,
792  index, indices);
793 
794  return indices;
795 }
t_type_ptr type
Definition: vpr_types.h:522
int * list
Definition: util.h:49
static void * my_malloc(int ibytes)
Definition: graphics.c:499
int nelem
Definition: util.h:48
struct s_grid_tile ** grid
Definition: globals.c:59
Definition: util.h:47
static void load_chan_rr_indices(INP int nodes_per_chan, INP int chan_len, INP int num_chans, INP t_rr_type type, INP t_seg_details *seg_details, INOUTP int *index, INOUTP t_ivec ***indices)
Definition: rr_graph2.c:660

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 at line 175 of file rr_graph2.c.

178  {
179 
180  /* Allocates and loads the seg_details data structure. Max_len gives the *
181  * maximum length of a segment (dimension of array). The code below tries *
182  * to: *
183  * (1) stagger the start points of segments of the same type evenly; *
184  * (2) spread out the limited number of connection boxes or switch boxes *
185  * evenly along the length of a segment, starting at the segment ends; *
186  * (3) stagger the connection and switch boxes on different long lines, *
187  * as they will not be staggered by different segment start points. */
188 
189  int i, cur_track, ntracks, itrack, length, j, index;
190  int wire_switch, opin_switch, fac, num_sets, tmp;
191  int group_start, first_track;
192  int *sets_per_seg_type = NULL;
193  t_seg_details *seg_details = NULL;
194  boolean longline;
195 
196  /* Unidir tracks are assigned in pairs, and bidir tracks individually */
197  if (directionality == BI_DIRECTIONAL) {
198  fac = 1;
199  } else {
200  assert(directionality == UNI_DIRECTIONAL);
201  fac = 2;
202  }
203  assert(*nodes_per_chan % fac == 0);
204 
205  /* Map segment type fractions and groupings to counts of tracks */
206  sets_per_seg_type = get_seg_track_counts((*nodes_per_chan / fac),
207  num_seg_types, segment_inf, use_full_seg_groups);
208 
209  /* Count the number tracks actually assigned. */
210  tmp = 0;
211  for (i = 0; i < num_seg_types; ++i) {
212  tmp += sets_per_seg_type[i] * fac;
213  }
214  assert(use_full_seg_groups || (tmp == *nodes_per_chan));
215  *nodes_per_chan = tmp;
216 
217  seg_details = (t_seg_details *) my_malloc(
218  *nodes_per_chan * sizeof(t_seg_details));
219 
220  /* Setup the seg_details data */
221  cur_track = 0;
222  for (i = 0; i < num_seg_types; ++i) {
223  first_track = cur_track;
224 
225  num_sets = sets_per_seg_type[i];
226  ntracks = fac * num_sets;
227  if (ntracks < 1) {
228  continue;
229  }
230  /* Avoid divide by 0 if ntracks */
231  longline = segment_inf[i].longline;
232  length = segment_inf[i].length;
233  if (longline) {
234  length = max_len;
235  }
236 
237  wire_switch = segment_inf[i].wire_switch;
238  opin_switch = segment_inf[i].opin_switch;
239  assert(
240  (wire_switch == opin_switch) || (directionality != UNI_DIRECTIONAL));
241 
242  /* Set up the tracks of same type */
243  group_start = 0;
244  for (itrack = 0; itrack < ntracks; itrack++) {
245 
246  /* Remember the start track of the current wire group */
247  if ((itrack / fac) % length == 0 && (itrack % fac) == 0) {
248  group_start = cur_track;
249  }
250 
251  seg_details[cur_track].length = length;
252  seg_details[cur_track].longline = longline;
253 
254  /* Stagger the start points in for each track set. The
255  * pin mappings should be aware of this when chosing an
256  * intelligent way of connecting pins and tracks.
257  * cur_track is used as an offset so that extra tracks
258  * from different segment types are hopefully better
259  * balanced. */
260  seg_details[cur_track].start = (cur_track / fac) % length + 1;
261 
262  /* These properties are used for vpr_to_phy_track to determine
263  * * twisting of wires. */
264  seg_details[cur_track].group_start = group_start;
265  seg_details[cur_track].group_size =
266  std::min(ntracks + first_track - group_start,
267  length * fac);
268  assert(0 == seg_details[cur_track].group_size % fac);
269  if (0 == seg_details[cur_track].group_size) {
270  seg_details[cur_track].group_size = length * fac;
271  }
272 
273  /* Setup the cb and sb patterns. Global route graphs can't depopulate cb and sb
274  * since this is a property of a detailed route. */
275  seg_details[cur_track].cb = (boolean *) my_malloc(
276  length * sizeof(boolean));
277  seg_details[cur_track].sb = (boolean *) my_malloc(
278  (length + 1) * sizeof(boolean));
279  for (j = 0; j < length; ++j) {
280  if (is_global_graph) {
281  seg_details[cur_track].cb[j] = TRUE;
282  } else {
283  index = j;
284 
285  /* Rotate longline's so they vary across the FPGA */
286  if (longline) {
287  index = (index + itrack) % length;
288  }
289 
290  /* Reverse the order for tracks going in DEC_DIRECTION */
291  if (itrack % fac == 1) {
292  index = (length - 1) - j;
293  }
294 
295  /* Use the segment's pattern. */
296  index = j % segment_inf[i].cb_len;
297  seg_details[cur_track].cb[j] = segment_inf[i].cb[index];
298  }
299  }
300  for (j = 0; j < (length + 1); ++j) {
301  if (is_global_graph) {
302  seg_details[cur_track].sb[j] = TRUE;
303  } else {
304  index = j;
305 
306  /* Rotate longline's so they vary across the FPGA */
307  if (longline) {
308  index = (index + itrack) % (length + 1);
309  }
310 
311  /* Reverse the order for tracks going in DEC_DIRECTION */
312  if (itrack % fac == 1) {
313  index = ((length + 1) - 1) - j;
314  }
315 
316  /* Use the segment's pattern. */
317  index = j % segment_inf[i].sb_len;
318  seg_details[cur_track].sb[j] = segment_inf[i].sb[index];
319  }
320  }
321 
322  seg_details[cur_track].Rmetal = segment_inf[i].Rmetal;
323  seg_details[cur_track].Cmetal = segment_inf[i].Cmetal;
324  //seg_details[cur_track].Cmetal_per_m = segment_inf[i].Cmetal_per_m;
325 
326  seg_details[cur_track].wire_switch = wire_switch;
327  seg_details[cur_track].opin_switch = opin_switch;
328 
329  if (BI_DIRECTIONAL == directionality) {
330  seg_details[cur_track].direction = BI_DIRECTION;
331  } else {
332  assert(UNI_DIRECTIONAL == directionality);
333  seg_details[cur_track].direction =
334  (itrack % 2) ? DEC_DIRECTION : INC_DIRECTION;
335  }
336 
337  switch (segment_inf[i].directionality) {
338  case UNI_DIRECTIONAL:
339  seg_details[cur_track].drivers = SINGLE;
340  break;
341  case BI_DIRECTIONAL:
342  seg_details[cur_track].drivers = MULTI_BUFFERED;
343  break;
344  }
345 
346  seg_details[cur_track].index = i;
347 
348  ++cur_track;
349  }
350  } /* End for each segment type. */
351 
352  /* free variables */
353  free(sets_per_seg_type);
354 
355  return seg_details;
356 }
short wire_switch
Definition: vpr_types.h:809
float Rmetal
Definition: vpr_types.h:811
boolean
Definition: util.h:11
enum e_drivers drivers
Definition: vpr_types.h:815
float Cmetal
Definition: vpr_types.h:812
short opin_switch
Definition: vpr_types.h:810
#define min(a, b)
Definition: graphics.c:174
static void * my_malloc(int ibytes)
Definition: graphics.c:499
enum e_direction direction
Definition: vpr_types.h:814
boolean longline
Definition: vpr_types.h:806
boolean * sb
Definition: vpr_types.h:807
Definition: util.h:12
boolean * cb
Definition: vpr_types.h:808
static int * get_seg_track_counts(INP int num_sets, INP int num_seg_types, INP t_segment_inf *segment_inf, INP boolean use_full_seg_groups)
Definition: rr_graph2.c:109

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

short***** alloc_sblock_pattern_lookup ( INP int  L_nx,
INP int  L_ny,
INP int  nodes_per_chan 
)

Definition at line 1444 of file rr_graph2.c.

1444  {
1445  int i, j, from_side, to_side, itrack, items;
1446  short *****result;
1447  short *****i_list;
1448  short ****j_list;
1449  short ***from_list;
1450  short **to_list;
1451  short *track_list;
1452 
1453  /* loading up the sblock connection pattern matrix. It's a huge matrix because
1454  * for nonquantized W, it's impossible to make simple permutations to figure out
1455  * where muxes are and how to connect to them such that their sizes are balanced */
1456 
1457  /* Do chunked allocations to make freeing easier, speed up malloc and free, and
1458  * reduce some of the memory overhead. Could use fewer malloc's but this way
1459  * avoids all considerations of pointer sizes and allignment. */
1460 
1461  /* Alloc each list of pointers in one go. items is a running product that increases
1462  * with each new dimension of the matrix. */
1463  items = 1;
1464  items *= (L_nx + 1);
1465  i_list = (short *****) my_malloc(sizeof(short ****) * items);
1466  items *= (L_ny + 1);
1467  j_list = (short ****) my_malloc(sizeof(short ***) * items);
1468  items *= (4);
1469  from_list = (short ***) my_malloc(sizeof(short **) * items);
1470  items *= (4);
1471  to_list = (short **) my_malloc(sizeof(short *) * items);
1472  items *= (nodes_per_chan);
1473  track_list = (short *) my_malloc(sizeof(short) * items);
1474 
1475  /* Build the pointer lists to form the multidimensional array */
1476  result = i_list;
1477  i_list += (L_nx + 1); /* Skip forward nx+1 items */
1478  for (i = 0; i < (L_nx + 1); ++i) {
1479 
1480  result[i] = j_list;
1481  j_list += (L_ny + 1); /* Skip forward ny+1 items */
1482  for (j = 0; j < (L_ny + 1); ++j) {
1483 
1484  result[i][j] = from_list;
1485  from_list += (4); /* Skip forward 4 items */
1486  for (from_side = 0; from_side < 4; ++from_side) {
1487 
1488  result[i][j][from_side] = to_list;
1489  to_list += (4); /* Skip forward 4 items */
1490  for (to_side = 0; to_side < 4; ++to_side) {
1491 
1492  result[i][j][from_side][to_side] = track_list;
1493  track_list += (nodes_per_chan); /* Skip forward nodes_per_chan items */
1494  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1495 
1496  /* Set initial value to be unset */
1497  result[i][j][from_side][to_side][itrack] = UN_SET;
1498  }
1499  }
1500  }
1501  }
1502  }
1503 
1504  /* This is the outer pointer to the full matrix */
1505  return result;
1506 }
static void * my_malloc(int ibytes)
Definition: graphics.c:499
#define UN_SET
Definition: rr_graph2.c:19

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void dump_seg_details ( t_seg_details seg_details,
int  nodes_per_chan,
const char *  fname 
)

Definition at line 373 of file rr_graph2.c.

374  {
375 
376  FILE *fp;
377  int i, j;
378  const char *drivers_names[] = { "multi_buffered", "single" };
379  const char *direction_names[] = { "inc_direction", "dec_direction",
380  "bi_direction" };
381 
382  fp = my_fopen(fname, "w", 0);
383 
384  for (i = 0; i < nodes_per_chan; i++) {
385  fprintf(fp, "Track: %d.\n", i);
386  fprintf(fp, "Length: %d, Start: %d, Long line: %d "
387  "wire_switch: %d opin_switch: %d.\n", seg_details[i].length,
388  seg_details[i].start, seg_details[i].longline,
389  seg_details[i].wire_switch, seg_details[i].opin_switch);
390 
391  fprintf(fp, "Rmetal: %g Cmetal: %g\n", seg_details[i].Rmetal,
392  seg_details[i].Cmetal);
393 
394  fprintf(fp, "Direction: %s Drivers: %s\n",
395  direction_names[seg_details[i].direction],
396  drivers_names[seg_details[i].drivers]);
397 
398  fprintf(fp, "cb list: ");
399  for (j = 0; j < seg_details[i].length; j++)
400  fprintf(fp, "%d ", seg_details[i].cb[j]);
401  fprintf(fp, "\n");
402 
403  fprintf(fp, "sb list: ");
404  for (j = 0; j <= seg_details[i].length; j++)
405  fprintf(fp, "%d ", seg_details[i].sb[j]);
406  fprintf(fp, "\n");
407 
408  fprintf(fp, "\n");
409  }
410 
411  fclose(fp);
412 }
FILE * my_fopen(const char *fname, const char *flag, int prompt)
Definition: util.c:54

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void free_rr_node_indices ( INP t_ivec ***  L_rr_node_indices)

Definition at line 797 of file rr_graph2.c.

797  {
798  int i, j, ofs;
799  /* This function must unallocate the structure allocated in
800  * alloc_and_load_rr_node_indices. */
801  for (i = 0; i <= (nx + 1); ++i) {
802  for (j = 0; j <= (ny + 1); ++j) {
803  ofs = grid[i][j].offset;
804  if (ofs > 0) {
805  /* Vertical large blocks reference is same as offset 0 */
806  L_rr_node_indices[SINK][i][j].list = NULL;
807  L_rr_node_indices[IPIN][i][j].list = NULL;
808  continue;
809  }
810  if (L_rr_node_indices[SINK][i][j].list != NULL) {
811  free(L_rr_node_indices[SINK][i][j].list);
812  }
813  if (L_rr_node_indices[IPIN][i][j].list != NULL) {
814  free(L_rr_node_indices[IPIN][i][j].list);
815  }
816  }
817  free(L_rr_node_indices[SINK][i]);
818  free(L_rr_node_indices[IPIN][i]);
819  }
820  free(L_rr_node_indices[SINK]);
821  free(L_rr_node_indices[IPIN]);
822 
823  for (i = 0; i < (nx + 1); ++i) {
824  for (j = 0; j < (ny + 1); ++j) {
825  if (L_rr_node_indices[CHANY][i][j].list != NULL) {
826  free(L_rr_node_indices[CHANY][i][j].list);
827  }
828  }
829  free(L_rr_node_indices[CHANY][i]);
830  }
831  free(L_rr_node_indices[CHANY]);
832 
833  for (i = 0; i < (ny + 1); ++i) {
834  for (j = 0; j < (nx + 1); ++j) {
835  if (L_rr_node_indices[CHANX][i][j].list != NULL) {
836  free(L_rr_node_indices[CHANX][i][j].list);
837  }
838  }
839  free(L_rr_node_indices[CHANX][i]);
840  }
841  free(L_rr_node_indices[CHANX]);
842 
843  free(L_rr_node_indices);
844 }
int * list
Definition: util.h:49
int nx
Definition: globals.c:46
struct s_grid_tile ** grid
Definition: globals.c:59
int ny
Definition: globals.c:47

+ Here is the caller graph for this function:

void free_sblock_pattern_lookup ( INOUTP short *****  sblock_pattern)

Definition at line 1508 of file rr_graph2.c.

1508  {
1509  /* This free function corresponds to the chunked matrix
1510  * allocation above and there should only be one free
1511  * call for each dimension. */
1512 
1513  /* Free dimensions from the inner one, outwards so
1514  * we can still access them. The comments beside
1515  * each one indicate the corresponding name used when
1516  * allocating them. */
1517  free(****sblock_pattern); /* track_list */
1518  free(***sblock_pattern); /* to_list */
1519  free(**sblock_pattern); /* from_list */
1520  free(*sblock_pattern); /* j_list */
1521  free(sblock_pattern); /* i_list */
1522 }

+ Here is the caller graph for this function:

void free_seg_details ( t_seg_details seg_details,
int  nodes_per_chan 
)

Definition at line 358 of file rr_graph2.c.

358  {
359 
360  /* Frees all the memory allocated to an array of seg_details structures. */
361 
362  int i;
363 
364  for (i = 0; i < nodes_per_chan; i++) {
365  free(seg_details[i].cb);
366  free(seg_details[i].sb);
367  }
368  free(seg_details);
369 }

+ Here is the caller graph for this function:

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 at line 478 of file rr_graph2.c.

481  {
482 
483  int iside, num_conn, ofs, tr_i, tr_j, chan, seg;
484  int to_track, to_switch, to_node, iconn;
485  int is_connected_track;
486  t_type_ptr type;
487  t_rr_type to_type;
488 
489  type = grid[i][j].type;
490  ofs = grid[i][j].offset;
491 
492  num_conn = 0;
493 
494  /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
495  for (iside = 0; iside < 4; iside++) {
496 
497  /* Figure out coords of channel segment based on side */
498  tr_i = ((iside == LEFT) ? (i - 1) : i);
499  tr_j = ((iside == BOTTOM) ? (j - 1) : j);
500 
501  to_type = ((iside == LEFT) || (iside == RIGHT)) ? CHANY : CHANX;
502 
503  chan = ((to_type == CHANX) ? tr_j : tr_i);
504  seg = ((to_type == CHANX) ? tr_i : tr_j);
505 
506  /* Don't connect where no tracks on fringes */
507  if ((tr_i < 0) || (tr_i > nx)) {
508  continue;
509  }
510  if ((tr_j < 0) || (tr_j > ny)) {
511  continue;
512  }
513  if ((CHANX == to_type) && (tr_i < 1)) {
514  continue;
515  }
516  if ((CHANY == to_type) && (tr_j < 1)) {
517  continue;
518  }
519 
520  is_connected_track = FALSE;
521 
522  /* Itterate of the opin to track connections */
523  for (iconn = 0; iconn < Fc; ++iconn) {
524  to_track = opin_to_track_map[type->index][ipin][ofs][iside][iconn];
525 
526  /* Skip unconnected connections */
527  if (OPEN == to_track || is_connected_track) {
528  is_connected_track = TRUE;
529  assert(
530  OPEN == opin_to_track_map[type-> index][ipin][ofs][iside] [0]);
531  continue;
532  }
533 
534  /* Only connect to wire if there is a CB */
535  if (is_cbox(chan, seg, to_track, seg_details, BI_DIRECTIONAL)) {
536  to_switch = seg_details[to_track].wire_switch;
537  to_node = get_rr_node_index(tr_i, tr_j, to_type, to_track,
538  L_rr_node_indices);
539 
540  *edge_list = insert_in_edge_list(*edge_list, to_node,
541  to_switch);
542  L_rr_edge_done[to_node] = TRUE;
543  ++num_conn;
544  }
545  }
546  }
547 
548  return num_conn;
549 }
t_type_ptr type
Definition: vpr_types.h:522
boolean is_cbox(INP int chan, INP int seg, INP int track, INP t_seg_details *seg_details, INP enum e_directionality directionality)
Definition: rr_graph2.c:636
t_linked_edge * insert_in_edge_list(INP t_linked_edge *head, INP int edge, INP short iswitch)
Definition: rr_graph_util.c:7
Definition: util.h:12
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
int nx
Definition: globals.c:46
struct s_grid_tile ** grid
Definition: globals.c:59
enum e_rr_type t_rr_type
Definition: slre.c:50
int ny
Definition: globals.c:47
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int get_rr_node_index ( int  x,
int  y,
t_rr_type  rr_type,
int  ptc,
t_ivec ***  L_rr_node_indices 
)

Definition at line 846 of file rr_graph2.c.

847  {
848  /* Returns the index of the specified routing resource node. (x,y) are *
849  * the location within the FPGA, rr_type specifies the type of resource, *
850  * and ptc gives the number of this resource. ptc is the class number, *
851  * pin number or track number, depending on what type of resource this *
852  * is. All ptcs start at 0 and go up to pins_per_clb-1 or the equivalent. *
853  * The order within a clb is: SOURCEs + SINKs (type->num_class of them); IPINs, *
854  * and OPINs (pins_per_clb of them); CHANX; and CHANY (nodes_per_chan of *
855  * each). For (x,y) locations that point at pads the order is: type->capacity *
856  * occurances of SOURCE, SINK, OPIN, IPIN (one for each pad), then one *
857  * associated channel (if there is a channel at (x,y)). All IO pads are *
858  * bidirectional, so while each will be used only as an INPAD or as an *
859  * OUTPAD, all the switches necessary to do both must be in each pad. *
860  * *
861  * Note that for segments (CHANX and CHANY) of length > 1, the segment is *
862  * given an rr_index based on the (x,y) location at which it starts (i.e. *
863  * lowest (x,y) location at which this segment exists). *
864  * This routine also performs error checking to make sure the node in *
865  * question exists. */
866 
867  int iclass, tmp;
868  t_type_ptr type;
869  t_ivec lookup;
870 
871  assert(ptc >= 0);
872  assert(x >= 0 && x <= (nx + 1));
873  assert(y >= 0 && y <= (ny + 1));
874 
875  type = grid[x][y].type;
876 
877  /* Currently need to swap x and y for CHANX because of chan, seg convention */
878  if (CHANX == rr_type) {
879  tmp = x;
880  x = y;
881  y = tmp;
882  }
883 
884  /* Start of that block. */
885  lookup = L_rr_node_indices[rr_type][x][y];
886 
887  /* Check valid ptc num */
888  assert(ptc >= 0);
889  assert(ptc < lookup.nelem);
890 
891 #ifdef DEBUG
892  switch (rr_type) {
893  case SOURCE:
894  assert(ptc < type->num_class);
895  assert(type->class_inf[ptc].type == DRIVER);
896  break;
897 
898  case SINK:
899  assert(ptc < type->num_class);
900  assert(type->class_inf[ptc].type == RECEIVER);
901  break;
902 
903  case OPIN:
904  assert(ptc < type->num_pins);
905  iclass = type->pin_class[ptc];
906  assert(type->class_inf[iclass].type == DRIVER);
907  break;
908 
909  case IPIN:
910  assert(ptc < type->num_pins);
911  iclass = type->pin_class[ptc];
912  assert(type->class_inf[iclass].type == RECEIVER);
913  break;
914 
915  case CHANX:
916  case CHANY:
917  break;
918 
919  default:
920  vpr_printf(TIO_MESSAGE_ERROR, "Bad rr_node passed to get_rr_node_index.\n");
921  vpr_printf(TIO_MESSAGE_ERROR, "Request for type=%d ptc=%d at (%d, %d).\n", rr_type, ptc, x, y);
922  exit(1);
923  }
924 #endif
925 
926  return lookup.list[ptc];
927 }
t_type_ptr type
Definition: vpr_types.h:522
struct s_class * class_inf
int * list
Definition: util.h:49
int nelem
Definition: util.h:48
int nx
Definition: globals.c:46
struct s_grid_tile ** grid
Definition: globals.c:59
Definition: util.h:47
enum e_pin_type type
int ny
Definition: globals.c:47
messagelogger vpr_printf
Definition: util.c:17

+ Here is the caller graph for this function:

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 at line 446 of file rr_graph2.c.

447  {
448  int len, ofs, end, first_full;
449 
450  len = seg_details[itrack].length;
451  ofs = seg_details[itrack].start;
452 
453  /* Normal endpoint */
454  end = istart + len - 1;
455 
456  /* If start is against edge it may have been clipped */
457  if (1 == istart) {
458  /* If the (staggered) startpoint of first full wire wasn't
459  * also 1, we must be the clipped wire */
460  first_full = (len - (chan_num % len) + ofs - 1) % len + 1;
461  if (first_full > 1) {
462  /* then we stop just before the first full seg */
463  end = first_full - 1;
464  }
465  }
466 
467  /* Clip against far edge */
468  if (end > seg_max) {
469  end = seg_max;
470  }
471 
472  return end;
473 }

+ Here is the caller graph for this function:

int get_seg_start ( INP t_seg_details seg_details,
INP int  itrack,
INP int  chan_num,
INP int  seg_num 
)

Definition at line 416 of file rr_graph2.c.

417  {
418 
419  int seg_start, length, start;
420 
421  seg_start = 1;
422  if (FALSE == seg_details[itrack].longline) {
423 
424  length = seg_details[itrack].length;
425  start = seg_details[itrack].start;
426 
427  /* Start is guaranteed to be between 1 and length. Hence adding length to *
428  * the quantity in brackets below guarantees it will be nonnegative. */
429 
430  assert(start > 0);
431  assert(start <= length);
432 
433  /* NOTE: Start points are staggered between different channels.
434  * The start point must stagger backwards as chan_num increases.
435  * Unidirectional routing expects this to allow the N-to-N
436  * assumption to be made with respect to ending wires in the core. */
437  seg_start = seg_num - (seg_num + length + chan_num - start) % length;
438  if (seg_start < 1) {
439  seg_start = 1;
440  }
441  }
442 
443  return seg_start;
444 }
Definition: util.h:12

+ Here is the caller graph for this function:

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 at line 929 of file rr_graph2.c.

933  {
934 
935  /* This counts the fan-out from wire segment (chan, seg, track) to blocks on either side */
936 
937  t_linked_edge *edge_list_head;
938  int j, pass, iconn, phy_track, end, to_node, max_conn, ipin, side, x, y,
939  num_conn;
940  t_type_ptr type;
941  int off;
942 
943  /* End of this wire */
944  end = get_seg_end(seg_details, track, seg, chan, chan_length);
945 
946  edge_list_head = *edge_list_ptr;
947  num_conn = 0;
948 
949  for (j = seg; j <= end; j++) {
950  if (is_cbox(chan, j, track, seg_details, directionality)) {
951  for (pass = 0; pass < 2; ++pass) {
952  if (CHANX == chan_type) {
953  x = j;
954  y = chan + pass;
955  side = (0 == pass ? TOP : BOTTOM);
956  } else {
957  assert(CHANY == chan_type);
958  x = chan + pass;
959  y = j;
960  side = (0 == pass ? RIGHT : LEFT);
961  }
962 
963  /* PAJ - if the pointed to is an EMPTY then shouldn't look for ipins */
964  if (grid[x][y].type == EMPTY_TYPE)
965  continue;
966 
967  /* Move from logical (straight) to physical (twisted) track index
968  * - algorithm assigns ipin connections to same physical track index
969  * so that the logical track gets distributed uniformly */
970  phy_track = vpr_to_phy_track(track, chan, j, seg_details,
971  directionality);
972 
973  /* We need the type to find the ipin map for this type */
974  type = grid[x][y].type;
975  off = grid[x][y].offset;
976 
977  max_conn =
978  track_to_ipin_lookup[type->index][phy_track][off][side].nelem;
979  for (iconn = 0; iconn < max_conn; iconn++) {
980  ipin =
981  track_to_ipin_lookup[type->index][phy_track][off][side].list[iconn];
982 
983  /* Check there is a connection and Fc map isn't wrong */
984  assert(type->pinloc[off][side][ipin]);
985  assert(type->is_global_pin[ipin] == FALSE);
986 
987  to_node = get_rr_node_index(x, y, IPIN, ipin,
988  L_rr_node_indices);
989  edge_list_head = insert_in_edge_list(edge_list_head,
990  to_node, wire_to_ipin_switch);
991  }
992  num_conn += max_conn;
993  }
994  }
995  }
996 
997  *edge_list_ptr = edge_list_head;
998  return (num_conn);
999 }
t_type_ptr type
Definition: vpr_types.h:522
boolean is_cbox(INP int chan, INP int seg, INP int track, INP t_seg_details *seg_details, INP enum e_directionality directionality)
Definition: rr_graph2.c:636
t_type_ptr EMPTY_TYPE
Definition: globals.c:41
int * list
Definition: util.h:49
t_linked_edge * insert_in_edge_list(INP t_linked_edge *head, INP int edge, INP short iswitch)
Definition: rr_graph_util.c:7
static int vpr_to_phy_track(INP int itrack, INP int chan_num, INP int seg_num, INP t_seg_details *seg_details, INP enum e_directionality directionality)
Definition: rr_graph2.c:1415
Definition: util.h:12
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
int nelem
Definition: util.h:48
struct s_grid_tile ** grid
Definition: globals.c:59
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 * is_global_pin

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 at line 1017 of file rr_graph2.c.

1025  {
1026  int num_conn;
1027  int from_switch, from_end, from_sb, from_first;
1028  int to_chan, to_sb;
1029  int start, end;
1030  struct s_ivec conn_tracks;
1031  boolean from_is_sbox, is_behind, Fs_clipped;
1032  enum e_side from_side_a, from_side_b, to_side;
1033 
1034  assert(
1035  from_seg == get_seg_start(seg_details, from_track, from_chan, from_seg));
1036 
1037  from_switch = seg_details[from_track].wire_switch;
1038  from_end = get_seg_end(seg_details, from_track, from_seg, from_chan,
1039  chan_len);
1040  from_first = from_seg - 1;
1041 
1042  /* Figure out the sides of SB the from_wire will use */
1043  if (CHANX == from_type) {
1044  from_side_a = RIGHT;
1045  from_side_b = LEFT;
1046  } else {
1047  assert(CHANY == from_type);
1048  from_side_a = TOP;
1049  from_side_b = BOTTOM;
1050  }
1051 
1052  /* Figure out if the to_wire is connecting to a SB
1053  * that is behind it. */
1054  is_behind = FALSE;
1055  if (to_type == from_type) {
1056  /* If inline, check that they only are trying
1057  * to connect at endpoints. */
1058  assert((to_seg == (from_end + 1)) || (to_seg == (from_seg - 1)));
1059  if (to_seg > from_end) {
1060  is_behind = TRUE;
1061  }
1062  } else {
1063  /* If bending, check that they are adjacent to
1064  * our channel. */
1065  assert((to_seg == from_chan) || (to_seg == (from_chan + 1)));
1066  if (to_seg > from_chan) {
1067  is_behind = TRUE;
1068  }
1069  }
1070 
1071  /* Figure out the side of SB the to_wires will use.
1072  * The to_seg and from_chan are in same direction. */
1073  if (CHANX == to_type) {
1074  to_side = (is_behind ? RIGHT : LEFT);
1075  } else {
1076  assert(CHANY == to_type);
1077  to_side = (is_behind ? TOP : BOTTOM);
1078  }
1079 
1080  /* Set the loop bounds */
1081  start = from_first;
1082  end = from_end;
1083 
1084  /* If we are connecting in same direction the connection is
1085  * on one of the two sides so clip the bounds to the SB of
1086  * interest and proceed normally. */
1087  if (to_type == from_type) {
1088  start = (is_behind ? end : start);
1089  end = start;
1090  }
1091 
1092  /* Iterate over the SBs */
1093  num_conn = 0;
1094  for (from_sb = start; from_sb <= end; ++from_sb) {
1095  /* Figure out if we are at a sbox */
1096  from_is_sbox = is_sbox(from_chan, from_seg, from_sb, from_track,
1097  seg_details, directionality);
1098  /* end of wire must be an sbox */
1099  if (from_sb == from_end || from_sb == from_first) {
1100  from_is_sbox = TRUE; /* Endpoints always default to true */
1101  }
1102 
1103  /* to_chan is the current segment if different directions,
1104  * otherwise to_chan is the from_chan */
1105  to_chan = from_sb;
1106  to_sb = from_chan;
1107  if (from_type == to_type) {
1108  to_chan = from_chan;
1109  to_sb = from_sb;
1110  }
1111 
1112  /* Do the edges going to the left or down */
1113  if (from_sb < from_end) {
1114  if (BI_DIRECTIONAL == directionality) {
1115  conn_tracks =
1116  switch_block_conn[from_side_a][to_side][from_track];
1117  num_conn += get_bidir_track_to_chan_seg(conn_tracks,
1118  L_rr_node_indices, to_chan, to_seg, to_sb, to_type,
1119  seg_details, from_is_sbox, from_switch, L_rr_edge_done,
1120  directionality, edge_list);
1121  }
1122  if (UNI_DIRECTIONAL == directionality) {
1123  /* No fanout if no SB. */
1124  /* We are connecting from the top or right of SB so it
1125  * makes the most sense to only there from DEC_DIRECTION wires. */
1126  if ((from_is_sbox)
1127  && (DEC_DIRECTION == seg_details[from_track].direction)) {
1128  num_conn += get_unidir_track_to_chan_seg(
1129  (boolean)(from_sb == from_first), from_track, to_chan,
1130  to_seg, to_sb, to_type, nodes_per_chan, nx, ny,
1131  from_side_a, to_side, Fs_per_side, opin_mux_size,
1132  sblock_pattern, L_rr_node_indices, seg_details,
1133  L_rr_edge_done, &Fs_clipped, edge_list);
1134  }
1135  }
1136  }
1137 
1138  /* Do the edges going to the right or up */
1139  if (from_sb > from_first) {
1140  if (BI_DIRECTIONAL == directionality) {
1141  conn_tracks =
1142  switch_block_conn[from_side_b][to_side][from_track];
1143  num_conn += get_bidir_track_to_chan_seg(conn_tracks,
1144  L_rr_node_indices, to_chan, to_seg, to_sb, to_type,
1145  seg_details, from_is_sbox, from_switch, L_rr_edge_done,
1146  directionality, edge_list);
1147  }
1148  if (UNI_DIRECTIONAL == directionality) {
1149  /* No fanout if no SB. */
1150  /* We are connecting from the bottom or left of SB so it
1151  * makes the most sense to only there from INC_DIRECTION wires. */
1152  if ((from_is_sbox)
1153  && (INC_DIRECTION == seg_details[from_track].direction)) {
1154  num_conn += get_unidir_track_to_chan_seg(
1155  (boolean)(from_sb == from_end), from_track, to_chan, to_seg,
1156  to_sb, to_type, nodes_per_chan, nx, ny, from_side_b,
1157  to_side, Fs_per_side, opin_mux_size, sblock_pattern,
1158  L_rr_node_indices, seg_details, L_rr_edge_done,
1159  &Fs_clipped, edge_list);
1160  }
1161  }
1162  }
1163  }
1164 
1165  return num_conn;
1166 }
boolean is_sbox(INP int chan, INP int wire_seg, INP int sb_seg, INP int track, INP t_seg_details *seg_details, INP enum e_directionality directionality)
Definition: rr_graph2.c:1332
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
e_side
Definition: util.h:12
static int get_bidir_track_to_chan_seg(INP struct s_ivec conn_tracks, INP t_ivec ***L_rr_node_indices, INP int to_chan, INP int to_seg, INP int to_sb, INP t_rr_type to_type, INP t_seg_details *seg_details, INP boolean from_is_sbox, INP int from_switch, INOUTP boolean *L_rr_edge_done, INP enum e_directionality directionality, INOUTP struct s_linked_edge **edge_list)
Definition: rr_graph2.c:1168
int nx
Definition: globals.c:46
static int get_unidir_track_to_chan_seg(INP boolean is_end_sb, INP int from_track, INP int to_chan, INP int to_seg, INP int to_sb, INP t_rr_type to_type, INP int nodes_per_chan, INP int L_nx, INP int L_ny, INP enum e_side from_side, INP enum e_side to_side, INP int Fs_per_side, INP int *opin_mux_size, INP short *****sblock_pattern, INP t_ivec ***L_rr_node_indices, INP t_seg_details *seg_details, INOUTP boolean *L_rr_edge_done, OUTP boolean *Fs_clipped, INOUTP struct s_linked_edge **edge_list)
Definition: rr_graph2.c:1228
Definition: util.h:47
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
int ny
Definition: globals.c:47
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 at line 551 of file rr_graph2.c.

556  {
557  /* Gets a linked list of Fc nodes to connect to in given
558  * chan seg. Fc_ofs is used for the for the opin staggering
559  * pattern. */
560 
561  int *inc_muxes = NULL;
562  int *dec_muxes = NULL;
563  int num_inc_muxes, num_dec_muxes, iconn;
564  int inc_inode, dec_inode;
565  int inc_mux, dec_mux;
566  int inc_track, dec_track;
567  int x, y;
568  int num_edges;
569 
570  *Fc_clipped = FALSE;
571 
572  /* Fc is assigned in pairs so check it is even. */
573  assert(Fc % 2 == 0);
574 
575  /* get_rr_node_indices needs x and y coords. */
576  x = ((CHANX == chan_type) ? seg : chan);
577  y = ((CHANX == chan_type) ? chan : seg);
578 
579  /* Get the lists of possible muxes. */
580  inc_muxes = label_wire_muxes(chan, seg, seg_details, max_len, INC_DIRECTION,
581  nodes_per_chan, &num_inc_muxes);
582  dec_muxes = label_wire_muxes(chan, seg, seg_details, max_len, DEC_DIRECTION,
583  nodes_per_chan, &num_dec_muxes);
584 
585  /* Clip Fc to the number of muxes. */
586  if (((Fc / 2) > num_inc_muxes) || ((Fc / 2) > num_dec_muxes)) {
587  *Fc_clipped = TRUE;
588  Fc = 2 * std::min(num_inc_muxes, num_dec_muxes);
589  }
590 
591  /* Assign tracks to meet Fc demand */
592  num_edges = 0;
593  for (iconn = 0; iconn < (Fc / 2); ++iconn) {
594  /* Figure of the next mux to use */
595  inc_mux = Fc_ofs[chan][seg] % num_inc_muxes;
596  dec_mux = Fc_ofs[chan][seg] % num_dec_muxes;
597  ++Fc_ofs[chan][seg];
598 
599  /* Figure out the track it corresponds to. */
600  inc_track = inc_muxes[inc_mux];
601  dec_track = dec_muxes[dec_mux];
602 
603  /* Figure the inodes of those muxes */
604  inc_inode = get_rr_node_index(x, y, chan_type, inc_track,
605  L_rr_node_indices);
606  dec_inode = get_rr_node_index(x, y, chan_type, dec_track,
607  L_rr_node_indices);
608 
609  /* Add to the list. */
610  if (FALSE == L_rr_edge_done[inc_inode]) {
611  L_rr_edge_done[inc_inode] = TRUE;
612  *edge_list_ptr = insert_in_edge_list(*edge_list_ptr, inc_inode,
613  seg_details[inc_track].opin_switch);
614  ++num_edges;
615  }
616  if (FALSE == L_rr_edge_done[dec_inode]) {
617  L_rr_edge_done[dec_inode] = TRUE;
618  *edge_list_ptr = insert_in_edge_list(*edge_list_ptr, dec_inode,
619  seg_details[dec_track].opin_switch);
620  ++num_edges;
621  }
622  }
623 
624  if (inc_muxes) {
625  free(inc_muxes);
626  inc_muxes = NULL;
627  }
628  if (dec_muxes) {
629  free(dec_muxes);
630  dec_muxes = NULL;
631  }
632 
633  return num_edges;
634 }
t_linked_edge * insert_in_edge_list(INP t_linked_edge *head, INP int edge, INP short iswitch)
Definition: rr_graph_util.c:7
Definition: util.h:12
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
#define min(a, b)
Definition: graphics.c:174
static int * label_wire_muxes(INP int chan_num, INP int seg_num, INP t_seg_details *seg_details, INP int max_len, INP enum e_direction dir, INP int nodes_per_chan, OUTP int *num_wire_muxes)
Definition: rr_graph2.c:1917
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

boolean is_cbox ( INP int  chan,
INP int  seg,
INP int  track,
INP t_seg_details seg_details,
INP enum e_directionality  directionality 
)

Definition at line 636 of file rr_graph2.c.

638  {
639 
640  int length, ofs, start_seg;
641 
642  length = seg_details[track].length;
643 
644  /* Make sure they gave us correct start */
645  start_seg = get_seg_start(seg_details, track, chan, seg);
646 
647  ofs = seg - start_seg;
648 
649  assert(ofs >= 0);
650  assert(ofs < length);
651 
652  /* If unidir segment that is going backwards, we need to flip the ofs */
653  if (DEC_DIRECTION == seg_details[track].direction) {
654  ofs = (length - 1) - ofs;
655  }
656 
657  return seg_details[track].cb[ofs];
658 }
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

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

boolean is_sbox ( INP int  chan,
INP int  wire_seg,
INP int  sb_seg,
INP int  track,
INP t_seg_details seg_details,
INP enum e_directionality  directionality 
)

Definition at line 1332 of file rr_graph2.c.

1334  {
1335 
1336  int length, ofs, fac;
1337 
1338  fac = 1;
1339  if (UNI_DIRECTIONAL == directionality) {
1340  fac = 2;
1341  }
1342 
1343  length = seg_details[track].length;
1344 
1345  /* Make sure they gave us correct start */
1346  wire_seg = get_seg_start(seg_details, track, chan, wire_seg);
1347 
1348  ofs = sb_seg - wire_seg + 1; /* Ofset 0 is behind us, so add 1 */
1349 
1350  assert(ofs >= 0);
1351  assert(ofs < (length + 1));
1352 
1353  /* If unidir segment that is going backwards, we need to flip the ofs */
1354  if ((ofs % fac) > 0) {
1355  ofs = length - ofs;
1356  }
1357 
1358  return seg_details[track].sb[ofs];
1359 }
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

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 at line 1524 of file rr_graph2.c.

1527  {
1528 
1529  /* This routine loads a lookup table for sblock topology. The lookup table is huge
1530  * because the sblock varies from location to location. The i, j means the owning
1531  * location of the sblock under investigation. */
1532 
1533  int side_cw_incoming_wire_count, side_ccw_incoming_wire_count,
1534  opp_incoming_wire_count;
1535  int to_side, side, side_cw, side_ccw, side_opp, itrack;
1536  int Fs_per_side, chan, seg, chan_len, sb_seg;
1537  boolean is_core_sblock, is_corner_sblock, x_edge, y_edge;
1538  int *incoming_wire_label[4];
1539  int *wire_mux_on_track[4];
1540  int num_incoming_wires[4];
1541  int num_ending_wires[4];
1542  int num_wire_muxes[4];
1543  boolean skip, vert, pos_dir;
1544  enum e_direction dir;
1545 
1546  Fs_per_side = 1;
1547  if (Fs != -1) {
1548  Fs_per_side = Fs / 3;
1549  }
1550 
1551  /* SB's have coords from (0, 0) to (nx, ny) */
1552  assert(i >= 0);
1553  assert(i <= nx);
1554  assert(j >= 0);
1555  assert(j <= ny);
1556 
1557  /* May 12 - 15, 2007
1558  *
1559  * I identify three types of sblocks in the chip: 1) The core sblock, whose special
1560  * property is that the number of muxes (and ending wires) on each side is the same (very useful
1561  * property, since it leads to a N-to-N assignment problem with ending wires). 2) The corner sblock
1562  * which is same as a L=1 core sblock with 2 sides only (again N-to-N assignment problem). 3) The
1563  * fringe / chip edge sblock which is most troublesome, as balance in each side of muxes is
1564  * attainable but balance in the entire sblock is not. The following code first identifies the
1565  * incoming wires, which can be classified into incoming passing wires with sbox and incoming
1566  * ending wires (the word "incoming" is sometimes dropped for ease of discussion). It appropriately
1567  * labels all the wires on each side by the following order: By the call to label_incoming_wires,
1568  * which labels for one side, the order is such that the incoming ending wires (always with sbox)
1569  * are labelled first 0,1,2,... p-1, then the incoming passing wires with sbox are labelled
1570  * p,p+1,p+2,... k-1 (for total of k). By this convention, one can easily distinguish the ending
1571  * wires from the passing wires by checking a label against num_ending_wires variable.
1572  *
1573  * After labelling all the incoming wires, this routine labels the muxes on the side we're currently
1574  * connecting to (iterated for four sides of the sblock), called the to_side. The label scheme is
1575  * the natural order of the muxes by their track #. Also we find the number of muxes.
1576  *
1577  * For each to_side, the total incoming wires that connect to the muxes on to_side
1578  * come from three sides: side_1 (to_side's right), side_2 (to_side's left) and opp_side.
1579  * The problem of balancing mux size is then: considering all incoming passing wires
1580  * with sbox on side_1, side_2 and opp_side, how to assign them to the muxes on to_side
1581  * (with specified Fs) in a way that mux size is imbalanced by at most 1. I solve this
1582  * problem by this approach: the first incoming passing wire will connect to 0, 1, 2,
1583  * ..., Fs_per_side - 1, then the next incoming passing wire will connect to
1584  * Fs_per_side, Fs_per_side+1, ..., Fs_per_side*2-1, and so on. This consistent STAGGERING
1585  * ensures N-to-N assignment is perfectly balanced and M-to-N assignment is imbalanced by no
1586  * more than 1.
1587  *
1588  * For the sblock_pattern_init_mux_lookup lookup table, I will only need the lookup
1589  * table to remember the first/init mux to connect, since the convention is Fs_per_side consecutive
1590  * muxes to connect. Then how do I determine the order of the incoming wires? I use the labels
1591  * on side_1, then labels on side_2, then labels on opp_side. Effectively I listed all
1592  * incoming passing wires from the three sides, and order them to each make Fs_per_side
1593  * consecutive connections to muxes, and use % to rotate to keep imbalance at most 1.
1594  */
1595 
1596  /* SB's range from (0, 0) to (nx, ny) */
1597  /* First find all four sides' incoming wires */
1598  x_edge = (boolean)((i < 1) || (i >= nx));
1599  y_edge = (boolean)((j < 1) || (j >= ny));
1600 
1601  is_corner_sblock = (boolean)(x_edge && y_edge);
1602  is_core_sblock = (boolean)(!x_edge && !y_edge);
1603 
1604  /* "Label" the wires around the switch block by connectivity. */
1605  for (side = 0; side < 4; ++side) {
1606  /* Assume the channel segment doesn't exist. */
1607  wire_mux_on_track[side] = NULL;
1608  incoming_wire_label[side] = NULL;
1609  num_incoming_wires[side] = 0;
1610  num_ending_wires[side] = 0;
1611  num_wire_muxes[side] = 0;
1612 
1613  /* Skip the side and leave the zero'd value if the
1614  * channel segment doesn't exist. */
1615  skip = TRUE;
1616  switch (side) {
1617  case TOP:
1618  if (j < ny) {
1619  skip = FALSE;
1620  }
1621  ;
1622  break;
1623  case RIGHT:
1624  if (i < nx) {
1625  skip = FALSE;
1626  }
1627  break;
1628  case BOTTOM:
1629  if (j > 0) {
1630  skip = FALSE;
1631  }
1632  break;
1633  case LEFT:
1634  if (i > 0) {
1635  skip = FALSE;
1636  }
1637  break;
1638  }
1639  if (skip) {
1640  continue;
1641  }
1642 
1643  /* Figure out the channel and segment for a certain direction */
1644  vert = (boolean) ((side == TOP) || (side == BOTTOM));
1645  pos_dir = (boolean) ((side == TOP) || (side == RIGHT));
1646  chan = (vert ? i : j);
1647  sb_seg = (vert ? j : i);
1648  seg = (pos_dir ? (sb_seg + 1) : sb_seg);
1649  chan_len = (vert ? ny : nx);
1650 
1651  /* Figure out all the tracks on a side that are ending and the
1652  * ones that are passing through and have a SB. */
1653  dir = (pos_dir ? DEC_DIRECTION : INC_DIRECTION);
1654  incoming_wire_label[side] = label_incoming_wires(chan, seg, sb_seg,
1655  seg_details, chan_len, dir, nodes_per_chan,
1656  &num_incoming_wires[side], &num_ending_wires[side]);
1657 
1658  /* Figure out all the tracks on a side that are starting. */
1659  dir = (pos_dir ? INC_DIRECTION : DEC_DIRECTION);
1660  wire_mux_on_track[side] = label_wire_muxes(chan, seg, seg_details,
1661  chan_len, dir, nodes_per_chan, &num_wire_muxes[side]);
1662  }
1663 
1664  for (to_side = 0; to_side < 4; to_side++) {
1665  /* Can't do anything if no muxes on this side. */
1666  if (0 == num_wire_muxes[to_side]) {
1667  continue;
1668  }
1669 
1670  /* Figure out side rotations */
1671  assert((TOP == 0) && (RIGHT == 1) && (BOTTOM == 2) && (LEFT == 3));
1672  side_cw = (to_side + 1) % 4;
1673  side_opp = (to_side + 2) % 4;
1674  side_ccw = (to_side + 3) % 4;
1675 
1676  /* For the core sblock:
1677  * The new order for passing wires should appear as
1678  * 0,1,2..,scw-1, for passing wires with sbox on side_cw
1679  * scw,scw+1,...,sccw-1, for passing wires with sbox on side_ccw
1680  * sccw,sccw+1,... for passing wires with sbox on side_opp.
1681  * This way, I can keep the imbalance to at most 1.
1682  *
1683  * For the fringe sblocks, I don't distinguish between
1684  * passing and ending wires so the above statement still holds
1685  * if you replace "passing" by "incoming" */
1686 
1687  side_cw_incoming_wire_count = 0;
1688  if (incoming_wire_label[side_cw]) {
1689  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1690  /* Ending wire, or passing wire with sbox. */
1691  if (incoming_wire_label[side_cw][itrack] != UN_SET) {
1692 
1693  if ((is_corner_sblock || is_core_sblock)
1694  && (incoming_wire_label[side_cw][itrack]
1695  < num_ending_wires[side_cw])) {
1696  /* The ending wires in core sblocks form N-to-N assignment
1697  * problem, so can use any pattern such as Wilton. This N-to-N
1698  * mapping depends on the fact that start points stagger across
1699  * channels. */
1700  assert(
1701  num_ending_wires[side_cw] == num_wire_muxes[to_side]);
1702  sblock_pattern[i][j][side_cw][to_side][itrack] =
1703  get_simple_switch_block_track((enum e_side)side_cw, (enum e_side)to_side,
1704  incoming_wire_label[side_cw][itrack],
1705  switch_block_type,
1706  num_wire_muxes[to_side]);
1707 
1708  } else {
1709 
1710  /* These are passing wires with sbox only for core sblocks
1711  * or passing and ending wires (for fringe cases). */
1712  sblock_pattern[i][j][side_cw][to_side][itrack] =
1713  (side_cw_incoming_wire_count * Fs_per_side)
1714  % num_wire_muxes[to_side];
1715  side_cw_incoming_wire_count++;
1716  }
1717  }
1718  }
1719  }
1720 
1721  side_ccw_incoming_wire_count = 0;
1722  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1723 
1724  /* if that side has no channel segment skip it */
1725  if (incoming_wire_label[side_ccw] == NULL)
1726  break;
1727 
1728  /* not ending wire nor passing wire with sbox */
1729  if (incoming_wire_label[side_ccw][itrack] != UN_SET) {
1730 
1731  if ((is_corner_sblock || is_core_sblock)
1732  && (incoming_wire_label[side_ccw][itrack]
1733  < num_ending_wires[side_ccw])) {
1734  /* The ending wires in core sblocks form N-to-N assignment problem, so can
1735  * use any pattern such as Wilton */
1736  assert(
1737  incoming_wire_label[side_ccw] [itrack] < num_wire_muxes[to_side]);
1738  sblock_pattern[i][j][side_ccw][to_side][itrack] =
1739  get_simple_switch_block_track((enum e_side)side_ccw, (enum e_side)to_side,
1740  incoming_wire_label[side_ccw][itrack],
1741  switch_block_type, num_wire_muxes[to_side]);
1742  } else {
1743 
1744  /* These are passing wires with sbox only for core sblocks
1745  * or passing and ending wires (for fringe cases). */
1746  sblock_pattern[i][j][side_ccw][to_side][itrack] =
1747  ((side_ccw_incoming_wire_count
1748  + side_cw_incoming_wire_count) * Fs_per_side)
1749  % num_wire_muxes[to_side];
1750  side_ccw_incoming_wire_count++;
1751  }
1752  }
1753  }
1754 
1755  opp_incoming_wire_count = 0;
1756  if (incoming_wire_label[side_opp]) {
1757  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
1758  /* not ending wire nor passing wire with sbox */
1759  if (incoming_wire_label[side_opp][itrack] != UN_SET) {
1760 
1761  /* corner sblocks for sure have no opposite channel segments so don't care about them */
1762  if (is_core_sblock) {
1763  if (incoming_wire_label[side_opp][itrack]
1764  < num_ending_wires[side_opp]) {
1765  /* The ending wires in core sblocks form N-to-N assignment problem, so can
1766  * use any pattern such as Wilton */
1767  /* In the direct connect case, I know for sure the init mux is at the same track #
1768  * as this ending wire, but still need to find the init mux label for Fs > 3 */
1769  sblock_pattern[i][j][side_opp][to_side][itrack] =
1771  wire_mux_on_track[to_side],
1772  num_wire_muxes[to_side], itrack);
1773  } else {
1774  /* These are passing wires with sbox for core sblocks */
1775  sblock_pattern[i][j][side_opp][to_side][itrack] =
1776  ((side_ccw_incoming_wire_count
1777  + side_cw_incoming_wire_count)
1778  * Fs_per_side
1779  + opp_incoming_wire_count
1780  * (Fs_per_side - 1))
1781  % num_wire_muxes[to_side];
1782  opp_incoming_wire_count++;
1783  }
1784  } else {
1785  if (incoming_wire_label[side_opp][itrack]
1786  < num_ending_wires[side_opp]) {
1787  sblock_pattern[i][j][side_opp][to_side][itrack] =
1789  wire_mux_on_track[to_side],
1790  num_wire_muxes[to_side], itrack);
1791  } else {
1792  /* These are passing wires with sbox for fringe sblocks */
1793  sblock_pattern[i][j][side_opp][to_side][itrack] =
1794  ((side_ccw_incoming_wire_count
1795  + side_cw_incoming_wire_count)
1796  * Fs_per_side
1797  + opp_incoming_wire_count
1798  * (Fs_per_side - 1))
1799  % num_wire_muxes[to_side];
1800  opp_incoming_wire_count++;
1801  }
1802  }
1803  }
1804  }
1805  }
1806  }
1807 
1808  for (side = 0; side < 4; ++side) {
1809  if (incoming_wire_label[side]) {
1810  free(incoming_wire_label[side]);
1811  }
1812  if (wire_mux_on_track[side]) {
1813  free(wire_mux_on_track[side]);
1814  }
1815  }
1816 }
boolean
Definition: util.h:11
int get_simple_switch_block_track(INP enum e_side from_side, INP enum e_side to_side, INP int from_track, INP enum e_switch_block_type switch_block_type, INP int nodes_per_chan)
static int find_label_of_track(int *wire_mux_on_track, int num_wire_muxes, int from_track)
Definition: rr_graph2.c:2035
e_side
Definition: util.h:12
#define UN_SET
Definition: rr_graph2.c:19
int nx
Definition: globals.c:46
static int * label_incoming_wires(INP int chan_num, INP int seg_num, INP int sb_seg, INP t_seg_details *seg_details, INP int max_len, INP enum e_direction dir, INP int nodes_per_chan, OUTP int *num_incoming_wires, OUTP int *num_ending_wires)
Definition: rr_graph2.c:1970
e_direction
Definition: vpr_types.h:798
int ny
Definition: globals.c:47
static int * label_wire_muxes(INP int chan_num, INP int seg_num, INP t_seg_details *seg_details, INP int max_len, INP enum e_direction dir, INP int nodes_per_chan, OUTP int *num_wire_muxes)
Definition: rr_graph2.c:1917
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Variable Documentation

boolean* rr_edge_done