SRC/rr_graph2.h File Reference

This graph shows which files directly or indirectly include this file:

Functions
struct s_ivec ***	alloc_and_load_rr_node_indices (IN int nodes_per_chan, IN int nx, IN int ny, INOUT int index, IN t_seg_details seg_details)
void	free_rr_node_indices (IN t_ivec ***rr_node_indices)
int	get_rr_node_index (int x, int y, t_rr_type rr_type, int ptc, t_ivec ***rr_node_indices)
void	free_seg_details (t_seg_details *seg_details, int nodes_per_chan)
t_seg_details *	alloc_and_load_seg_details (INOUT int nodes_per_chan, IN int max_len, IN int num_seg_types, IN t_segment_inf segment_inf, IN boolean use_full_seg_groups, IN boolean is_global_graph, IN enum e_directionality directionality)
void	dump_seg_details (t_seg_details seg_details, int nodes_per_chan, char fname)
int	get_seg_start (IN t_seg_details *seg_details, IN int itrack, IN int chan_num, IN int seg_num)
int	get_seg_end (IN t_seg_details *seg_details, IN int itrack, IN int istart, IN int chan_num, IN int seg_max)
boolean	is_cbox (IN int chan, IN int seg, IN int track, IN t_seg_details *seg_details, IN enum e_directionality directionality)
boolean	is_sbox (IN int chan, IN int wire_seg, IN int sb_seg, IN int track, IN t_seg_details *seg_details, IN enum e_directionality directionality)
int	get_bidir_opin_connections (IN int i, IN int j, IN int ipin, IN struct s_linked_edge edge_list, IN int **opin_to_track_map, IN int Fc, IN boolean rr_edge_done, IN t_ivec **rr_node_indices, IN t_seg_details seg_details)
int	get_unidir_opin_connections (IN int chan, IN int seg, IN int Fc, IN t_rr_type chan_type, IN t_seg_details seg_details, INOUT t_linked_edge edge_list_ptr, INOUT int Fc_ofs, INOUT boolean rr_edge_done, IN int max_len, IN int nodes_per_chan, IN t_ivec **rr_node_indices, OUT boolean Fc_clipped)
int	get_track_to_ipins (int seg, int chan, int track, t_linked_edge edge_list_ptr, t_ivec 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 (IN int from_chan, IN int from_seg, IN int from_track, IN t_rr_type from_type, IN int to_seg, IN t_rr_type to_type, IN int chan_len, IN int nodes_per_chan, IN int opin_mux_size, IN int Fs_per_side, IN short **sblock_pattern, INOUT struct s_linked_edge edge_list, IN t_seg_details seg_details, IN enum e_directionality directionality, IN t_ivec *rr_node_indices, INOUT boolean rr_edge_done, IN struct s_ivec ***switch_block_conn)
short *****	alloc_sblock_pattern_lookup (IN int nx, IN int ny, IN int nodes_per_chan)
void	free_sblock_pattern_lookup (INOUT short *****sblock_pattern)
void	load_sblock_pattern_lookup (IN int i, IN int j, IN int nodes_per_chan, IN t_seg_details seg_details, IN int Fs, IN enum e_switch_block_type switch_block_type, INOUT short ****sblock_pattern)
Variables
boolean *	rr_edge_done

Function Documentation

struct s_ivec*** alloc_and_load_rr_node_indices	(	IN int	nodes_per_chan,
		IN int	nx,
		IN int	ny,
		INOUT int *	index,
		IN t_seg_details *	seg_details
	)			`[read]`

Definition at line 928 of file rr_graph2.c.

00934 00935 00936 00937 00938 00939 00940 00941 00942 00943 00944 00945 00946 00947 00948 00949         { 00950 00951 00952 00953 00954 00955 00956 00957 00958 00959 00960 00961 00962         } 00963 00964 00965 00966 00967         { 00968 00969 00970 00971 00972 00973 00974 00975 00976 00977 00978 00979 00980 00981 00982 00983 00984 00985 00986 00987 00988 00989 00990 00991 00992 00993 00994 00995 00996 00997 00998 00999 01000 01001 01002 01003 01004 01005 01006 01007 01008 01009 01010         } 01011 01012 01013 01014         { 01015 01016 01017 01018 01019 01020 01021 01022 01023 01024 01025         } 01026 01027 01028 01029 01030 01031 01032 01033 01034 01035 01036 01037 01038 01039 }

class="fragment">00933 { /* Allocates and loads all the structures needed for fast lookups of the * * index of an rr_node. rr_node_indices is a matrix containing the index * * of the *first* rr_node at a given (i,j) location. */ int i, j, k, ofs; t_ivec ***indices; t_ivec tmp; t_type_ptr type; /* Alloc the lookup table */ indices = (t_ivec ***) my_malloc(sizeof(t_ivec **) * NUM_RR_TYPES); indices[IPIN] = (t_ivec **) my_malloc(sizeof(t_ivec *) * (nx + 2)); indices[SINK] = (t_ivec **) my_malloc(sizeof(t_ivec *) * (nx + 2)); for(i = 0; i <= (nx + 1); ++i) indices[IPIN][i] = (t_ivec *) my_malloc(sizeof(t_ivec) * (ny + 2)); indices[SINK][i] = (t_ivec *) my_malloc(sizeof(t_ivec) * (ny + 2)); for(j = 0; j <= (ny + 1); ++j) { indices[IPIN][i][j].nelem = 0; indices[IPIN][i][j].list = NULL; indices[SINK][i][j].nelem = 0; indices[SINK][i][j].list = NULL; } /* Count indices for block nodes */ for(i = 0; i <= (nx + 1); i++) for(j = 0; j <= (ny + 1); j++) { ofs = grid[i][j].offset; if(0 == ofs) { type = grid[i][j].type; /* Load the pin class lookups. The ptc nums for SINK and SOURCE * are disjoint so they can share the list. */ tmp.nelem = type->num_class; tmp.list = NULL; if(tmp.nelem > 0) { tmp.list = (int *)my_malloc(sizeof(int) * tmp.nelem); for(k = 0; k < tmp.nelem; ++k) { tmp.list[k] = *index; ++(*index); } } indices[SINK][i][j] = tmp; /* Load the pin lookups. The ptc nums for IPIN and OPIN * are disjoint so they can share the list. */ tmp.nelem = type->num_pins; tmp.list = NULL; if(tmp.nelem > 0) { tmp.list = (int *)my_malloc(sizeof(int) * tmp.nelem); for(k = 0; k < tmp.nelem; ++k) { tmp.list[k] = *index; ++(*index); } } indices[IPIN][i][j] = tmp; } } /* Point offset blocks of a large block to base block */ for(i = 0; i <= (nx + 1); i++) for(j = 0; j <= (ny + 1); j++) { ofs = grid[i][j].offset; if(ofs > 0) { /* NOTE: this only supports vertical large blocks */ indices[SINK][i][j] = indices[SINK][i][j - ofs]; indices[IPIN][i][j] = indices[IPIN][i][j - ofs]; } } /* SOURCE and SINK have unique ptc values so their data can be shared. * IPIN and OPIN have unique ptc values so their data can be shared. */ indices[SOURCE] = indices[SINK]; indices[OPIN] = indices[IPIN]; /* Load the data for x and y channels */ load_chan_rr_indices(nodes_per_chan, nx + 1, ny + 1, CHANX, seg_details, index, indices); load_chan_rr_indices(nodes_per_chan, ny + 1, nx + 1, CHANY, seg_details, index, indices); return indices;

Here is the call graph for this function:

Here is the caller graph for this function:

t_seg_details* alloc_and_load_seg_details	(	INOUT int *	nodes_per_chan,
		IN int	max_len,
		IN int	num_seg_types,
		IN t_segment_inf *	segment_inf,
		IN boolean	use_full_seg_groups,
		IN boolean	is_global_graph,
		IN enum e_directionality	directionality
	)

Definition at line 241 of file rr_graph2.c.

00248 {
00249 
00250     /* Allocates and loads the seg_details data structure.  Max_len gives the   *
00251      * maximum length of a segment (dimension of array).  The code below tries  *
00252      * to:                                                                      *
00253      * (1) stagger the start points of segments of the same type evenly;        *
00254      * (2) spread out the limited number of connection boxes or switch boxes    *
00255      *     evenly along the length of a segment, starting at the segment ends;  *
00256      * (3) stagger the connection and switch boxes on different long lines,     *
00257      *     as they will not be staggered by different segment start points.     */
00258 
00259     int i, cur_track, ntracks, itrack, length, j, index;
00260     int wire_switch, opin_switch, fac, num_sets, tmp;
00261     int group_start, first_track;
00262     int *sets_per_seg_type = NULL;
00263     t_seg_details *seg_details = NULL;
00264     boolean longline;
00265 
00266     /* Unidir tracks are assigned in pairs, and bidir tracks individually */
00267     if(directionality == BI_DIRECTIONAL)
00268         {
00269             fac = 1;
00270         }
00271     else
00272         {
00273             assert(directionality == UNI_DIRECTIONAL);
00274             fac = 2;
00275         }
00276     assert(*nodes_per_chan % fac == 0);
00277 
00278     /* Map segment type fractions and groupings to counts of tracks */
00279     sets_per_seg_type = get_seg_track_counts((*nodes_per_chan / fac),
00280                                              num_seg_types,
00281                                              segment_inf,
00282                                              use_full_seg_groups);
00283 
00284     /* Count the number tracks actually assigned. */
00285     tmp = 0;
00286     for(i = 0; i < num_seg_types; ++i)
00287         {
00288             tmp += sets_per_seg_type[i] * fac;
00289         }
00290     assert(use_full_seg_groups || (tmp == *nodes_per_chan));
00291     *nodes_per_chan = tmp;
00292 
00293     seg_details = (t_seg_details *)
00294         my_malloc(*nodes_per_chan * sizeof(t_seg_details));
00295 
00296     /* Setup the seg_details data */
00297     cur_track = 0;
00298     for(i = 0; i < num_seg_types; ++i)
00299         {
00300             first_track = cur_track;
00301 
00302             num_sets = sets_per_seg_type[i];
00303             ntracks = fac * num_sets;
00304             if(ntracks < 1)
00305                 {
00306                     continue;
00307                 }
00308             /* Avoid divide by 0 if ntracks */
00309             longline = segment_inf[i].longline;
00310             length = segment_inf[i].length;
00311             if(longline)
00312                 {
00313                     length = max_len;
00314                 }
00315 
00316             wire_switch = segment_inf[i].wire_switch;
00317             opin_switch = segment_inf[i].opin_switch;
00318             assert((wire_switch == opin_switch)
00319                    || (directionality != UNI_DIRECTIONAL));
00320 
00321             /* Set up the tracks of same type */
00322             group_start = 0;
00323             for(itrack = 0; itrack < ntracks; itrack++)
00324                 {
00325 
00326                     /* Remember the start track of the current wire group */
00327                     if((itrack / fac) % length == 0 && (itrack % fac) == 0)
00328                         {
00329                             group_start = cur_track;
00330                         }
00331 
00332                     seg_details[cur_track].length = length;
00333                     seg_details[cur_track].longline = longline;
00334 
00335                     /* Stagger the start points in for each track set. The 
00336                      * pin mappings should be aware of this when chosing an
00337                      * intelligent way of connecting pins and tracks.
00338                      * cur_track is used as an offset so that extra tracks
00339                      * from different segment types are hopefully better
00340                      * balanced. */
00341                     seg_details[cur_track].start =
00342                         (cur_track / fac) % length + 1;
00343 
00344                     /* These properties are used for vpr_to_phy_track to determine
00345                      * * twisting of wires. */
00346                     seg_details[cur_track].group_start = group_start;
00347                     seg_details[cur_track].group_size =
00348                         min(ntracks + first_track - group_start,
00349                             length * fac);
00350                     assert(0 == seg_details[cur_track].group_size % fac);
00351                     if(0 == seg_details[cur_track].group_size)
00352                         {
00353                             seg_details[cur_track].group_size = length * fac;
00354                         }
00355 
00356                     /* Setup the cb and sb patterns. Global route graphs can't depopulate cb and sb
00357                      * since this is a property of a detailed route. */
00358                     seg_details[cur_track].cb =
00359                         (boolean *) my_malloc(length * sizeof(boolean));
00360                     seg_details[cur_track].sb =
00361                         (boolean *) my_malloc((length + 1) * sizeof(boolean));
00362                     for(j = 0; j < length; ++j)
00363                         {
00364                             if(is_global_graph)
00365                                 {
00366                                     seg_details[cur_track].cb[j] = TRUE;
00367                                 }
00368                             else
00369                                 {
00370                                     index = j;
00371 
00372                                     /* Rotate longline's so they vary across the FPGA */
00373                                     if(longline)
00374                                         {
00375                                             index = (index + itrack) % length;
00376                                         }
00377 
00378                                     /* Reverse the order for tracks going in DEC_DIRECTION */
00379                                     if(itrack % fac == 1)
00380                                         {
00381                                             index = (length - 1) - j;
00382                                         }
00383 
00384                                     /* Use the segment's pattern. */
00385                                     index = j % segment_inf[i].cb_len;
00386                                     seg_details[cur_track].cb[j] =
00387                                         segment_inf[i].cb[index];
00388                                 }
00389                         }
00390                     for(j = 0; j < (length + 1); ++j)
00391                         {
00392                             if(is_global_graph)
00393                                 {
00394                                     seg_details[cur_track].sb[j] = TRUE;
00395                                 }
00396                             else
00397                                 {
00398                                     index = j;
00399 
00400                                     /* Rotate longline's so they vary across the FPGA */
00401                                     if(longline)
00402                                         {
00403                                             index =
00404                                                 (index + itrack) % (length +
00405                                                                     1);
00406                                         }
00407 
00408                                     /* Reverse the order for tracks going in DEC_DIRECTION */
00409                                     if(itrack % fac == 1)
00410                                         {
00411                                             index = ((length + 1) - 1) - j;
00412                                         }
00413 
00414                                     /* Use the segment's pattern. */
00415                                     index = j % segment_inf[i].sb_len;
00416                                     seg_details[cur_track].sb[j] =
00417                                         segment_inf[i].sb[index];
00418                                 }
00419                         }
00420 
00421                     seg_details[cur_track].Rmetal = segment_inf[i].Rmetal;
00422                     seg_details[cur_track].Cmetal = segment_inf[i].Cmetal;
00423 
00424                     seg_details[cur_track].wire_switch = wire_switch;
00425                     seg_details[cur_track].opin_switch = opin_switch;
00426 
00427                     if(BI_DIRECTIONAL == directionality)
00428                         {
00429                             seg_details[cur_track].direction = BI_DIRECTION;
00430                         }
00431                     else
00432                         {
00433                             assert(UNI_DIRECTIONAL == directionality);
00434                             seg_details[cur_track].direction =
00435                                 (itrack % 2) ? DEC_DIRECTION : INC_DIRECTION;
00436                         }
00437 
00438                     switch (segment_inf[i].directionality)
00439                         {
00440                         case UNI_DIRECTIONAL:
00441                             seg_details[cur_track].drivers = SINGLE;
00442                             break;
00443                         case BI_DIRECTIONAL:
00444                             seg_details[cur_track].drivers = MULTI_BUFFERED;
00445                             break;
00446                         }
00447 
00448                     seg_details[cur_track].index = i;
00449 
00450                     ++cur_track;
00451                 }
00452         }                       /* End for each segment type. */
00453 
00454         /* free variables */
00455         free(sets_per_seg_type);
00456 
00457     return seg_details;
00458 }

Here is the call graph for this function:

Here is the caller graph for this function:

short***** alloc_sblock_pattern_lookup	(	IN int	nx,
		IN int	ny,
		IN int	nodes_per_chan
	)

Definition at line 1893 of file rr_graph2.c.

01896 {
01897     int i, j, from_side, to_side, itrack, items;
01898     short *****result;
01899     short *****i_list;
01900     short ****j_list;
01901     short ***from_list;
01902     short **to_list;
01903     short *track_list;
01904 
01905     /* loading up the sblock connection pattern matrix. It's a huge matrix because
01906      * for nonquantized W, it's impossible to make simple permutations to figure out
01907      * where muxes are and how to connect to them such that their sizes are balanced */
01908 
01909     /* Do chunked allocations to make freeing easier, speed up malloc and free, and
01910      * reduce some of the memory overhead. Could use fewer malloc's but this way
01911      * avoids all considerations of pointer sizes and allignment. */
01912 
01913     /* Alloc each list of pointers in one go. items is a running product that increases
01914      * with each new dimension of the matrix. */
01915     items = 1;
01916     items *= (nx + 1);
01917     i_list = (short *****)my_malloc(sizeof(short ****) * items);
01918     items *= (ny + 1);
01919     j_list = (short ****)my_malloc(sizeof(short ***) * items);
01920     items *= (4);
01921     from_list = (short ***)my_malloc(sizeof(short **) * items);
01922     items *= (4);
01923     to_list = (short **)my_malloc(sizeof(short *) * items);
01924     items *= (nodes_per_chan);
01925     track_list = (short *)my_malloc(sizeof(short) * items);
01926 
01927     /* Build the pointer lists to form the multidimensional array */
01928     result = i_list;
01929     i_list += (nx + 1);         /* Skip forward nx+1 items */
01930     for(i = 0; i < (nx + 1); ++i)
01931         {
01932 
01933             result[i] = j_list;
01934             j_list += (ny + 1); /* Skip forward ny+1 items */
01935             for(j = 0; j < (ny + 1); ++j)
01936                 {
01937 
01938                     result[i][j] = from_list;
01939                     from_list += (4);   /* Skip forward 4 items */
01940                     for(from_side = 0; from_side < 4; ++from_side)
01941                         {
01942 
01943                             result[i][j][from_side] = to_list;
01944                             to_list += (4);     /* Skip forward 4 items */
01945                             for(to_side = 0; to_side < 4; ++to_side)
01946                                 {
01947 
01948                                     result[i][j][from_side][to_side] =
01949                                         track_list;
01950                                     track_list += (nodes_per_chan);     /* Skip forward nodes_per_chan items */
01951                                     for(itrack = 0; itrack < nodes_per_chan;
01952                                         itrack++)
01953                                         {
01954 
01955                                             /* Set initial value to be unset */
01956                                             result[i][j][from_side][to_side]
01957                                                 [itrack] = UN_SET;
01958                                         }
01959                                 }
01960                         }
01961                 }
01962         }
01963 
01964     /* This is the outer pointer to the full matrix */
01965     return result;
01966 }

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,
		char *	fname
	)

Definition at line 481 of file rr_graph2.c.

00484 {
00485 
00486     FILE *fp;
00487     int i, j;
00488     const char *drivers_names[] = { "multi_buffered",
00489         "multi_muxed",
00490         "multi_merged",
00491         "single"
00492     };
00493     const char *direction_names[] = { "inc_direction",
00494         "dec_direction",
00495         "bi_direction"
00496     };
00497 
00498     fp = my_fopen(fname, "w");
00499 
00500     for(i = 0; i < nodes_per_chan; i++)
00501         {
00502             fprintf(fp, "Track: %d.\n", i);
00503             fprintf(fp, "Length: %d,  Start: %d,  Long line: %d  "
00504                     "wire_switch: %d  opin_switch: %d.\n",
00505                     seg_details[i].length,
00506                     seg_details[i].start,
00507                     seg_details[i].longline,
00508                     seg_details[i].wire_switch, seg_details[i].opin_switch);
00509 
00510             fprintf(fp, "Rmetal: %g  Cmetal: %g\n",
00511                     seg_details[i].Rmetal, seg_details[i].Cmetal);
00512 
00513             fprintf(fp, "Direction: %s  Drivers: %s\n",
00514                     direction_names[seg_details[i].direction],
00515                     drivers_names[seg_details[i].drivers]);
00516 
00517             fprintf(fp, "Start Track: %d  End Track: %d\n",
00518                     seg_details[i].start_track, seg_details[i].end_track);
00519 
00520             fprintf(fp, "cb list:  ");
00521             for(j = 0; j < seg_details[i].length; j++)
00522                 fprintf(fp, "%d ", seg_details[i].cb[j]);
00523             fprintf(fp, "\n");
00524 
00525             fprintf(fp, "sb list: ");
00526             for(j = 0; j <= seg_details[i].length; j++)
00527                 fprintf(fp, "%d ", seg_details[i].sb[j]);
00528             fprintf(fp, "\n");
00529 
00530             fprintf(fp, "\n");
00531         }
00532 
00533     fclose(fp);
00534 }

Here is the call graph for this function:

Here is the caller graph for this function:

void free_rr_node_indices ( IN t_ivec *** rr_node_indices )

Definition at line 1043 of file rr_graph2.c.

01044 {
01045         int i, j, ofs;
01046     /* This function must unallocate the structure allocated in 
01047      * alloc_and_load_rr_node_indices. */
01048         for(i = 0; i <= (nx + 1); ++i)
01049         {
01050                 for(j = 0; j <= (ny + 1); ++j)
01051                 {
01052                         ofs = grid[i][j].offset;
01053                     if(ofs > 0)
01054                         {
01055                             /* Vertical large blocks reference is same as offset 0 */
01056                             rr_node_indices[SINK][i][j].list = NULL;
01057                                 rr_node_indices[IPIN][i][j].list = NULL;
01058                                 continue;
01059                         }
01060                         if(rr_node_indices[SINK][i][j].list != NULL) {
01061                                 free(rr_node_indices[SINK][i][j].list);
01062                         }
01063                         if(rr_node_indices[IPIN][i][j].list != NULL) {
01064                                 free(rr_node_indices[IPIN][i][j].list);
01065                         }
01066                 }
01067                 free(rr_node_indices[SINK][i]);
01068                 free(rr_node_indices[IPIN][i]);
01069         }
01070         free(rr_node_indices[SINK]);
01071         free(rr_node_indices[IPIN]);
01072 
01073         for(i = 0; i < (nx + 1); ++i)
01074         {
01075                 for(j = 0; j < (ny + 1); ++j)
01076                 {
01077                         if(rr_node_indices[CHANY][i][j].list != NULL) {
01078                                 free(rr_node_indices[CHANY][i][j].list);
01079                         }
01080                 }
01081                 free(rr_node_indices[CHANY][i]);
01082         }
01083         free(rr_node_indices[CHANY]);
01084 
01085         for(i = 0; i < (ny + 1); ++i)
01086         {
01087                 for(j = 0; j < (nx + 1); ++j)
01088                 {
01089                         if(rr_node_indices[CHANX][i][j].list != NULL) {
01090                                 free(rr_node_indices[CHANX][i][j].list);
01091                         }
01092                 }
01093                 free(rr_node_indices[CHANX][i]);
01094         }
01095         free(rr_node_indices[CHANX]);
01096 
01097         free(rr_node_indices);
01098 }

Here is the caller graph for this function:

void free_sblock_pattern_lookup ( INOUT short ***** sblock_pattern )

Definition at line 1970 of file rr_graph2.c.

01971 {
01972     /* This free function corresponds to the chunked matrix 
01973      * allocation above and there should only be one free
01974      * call for each dimension. */
01975 
01976     /* Free dimensions from the inner one, outwards so
01977      * we can still access them. The comments beside
01978      * each one indicate the corresponding name used when
01979      * allocating them. */
01980     free(****sblock_pattern);   /* track_list */
01981     free(***sblock_pattern);    /* to_list */
01982     free(**sblock_pattern);     /* from_list */
01983     free(*sblock_pattern);      /* j_list */
01984     free(sblock_pattern);       /* i_list */
01985 }

Here is the caller graph for this function:

void free_seg_details	(	t_seg_details *	seg_details,
		int	nodes_per_chan
	)

Definition at line 461 of file rr_graph2.c.

00463 {
00464 
00465     /* Frees all the memory allocated to an array of seg_details structures. */
00466 
00467     int i;
00468 
00469     for(i = 0; i < nodes_per_chan; i++)
00470         {
00471             free(seg_details[i].cb);
00472             free(seg_details[i].sb);
00473         }
00474     free(seg_details);
00475 }

Here is the caller graph for this function:

int get_bidir_opin_connections	(	IN int	i,
		IN int	j,
		IN int	ipin,
		IN struct s_linked_edge **	edge_list,
		IN int *****	opin_to_track_map,
		IN int	Fc,
		IN boolean *	rr_edge_done,
		IN t_ivec ***	rr_node_indices,
		IN t_seg_details *	seg_details
	)

Definition at line 621 of file rr_graph2.c.

00630 {
00631 
00632     int iside, num_conn, ofs, tr_i, tr_j, chan, seg;
00633     int to_track, to_switch, to_node, iconn;
00634         int is_connected_track;
00635     t_type_ptr type;
00636     t_rr_type to_type;
00637 
00638     type = grid[i][j].type;
00639     ofs = grid[i][j].offset;
00640 
00641     num_conn = 0;
00642 
00643     /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
00644     for(iside = 0; iside < 4; iside++)
00645         {
00646 
00647             /* Figure out coords of channel segment based on side */
00648             tr_i = ((iside == LEFT) ? (i - 1) : i);
00649             tr_j = ((iside == BOTTOM) ? (j - 1) : j);
00650 
00651             to_type = ((iside == LEFT) || (iside == RIGHT)) ? CHANY : CHANX;
00652 
00653             chan = ((to_type == CHANX) ? tr_j : tr_i);
00654             seg = ((to_type == CHANX) ? tr_i : tr_j);
00655 
00656             /* Don't connect where no tracks on fringes */
00657             if((tr_i < 0) || (tr_i > nx))
00658                 {
00659                     continue;
00660                 }
00661             if((tr_j < 0) || (tr_j > ny))
00662                 {
00663                     continue;
00664                 }
00665             if((CHANX == to_type) && (tr_i < 1))
00666                 {
00667                     continue;
00668                 }
00669             if((CHANY == to_type) && (tr_j < 1))
00670                 {
00671                     continue;
00672                 }
00673 
00674                 is_connected_track = FALSE;
00675 
00676             /* Itterate of the opin to track connections */
00677             for(iconn = 0; iconn < Fc; ++iconn)
00678                 {
00679                     to_track =
00680                         opin_to_track_map[type->
00681                                           index][ipin][ofs][iside][iconn];
00682 
00683                     /* Skip unconnected connections */
00684                     if(OPEN == to_track || is_connected_track)
00685                         {
00686                                 is_connected_track = TRUE;
00687                             assert(OPEN ==
00688                                    opin_to_track_map[type->
00689                                                      index][ipin][ofs][iside]
00690                                    [0]);
00691                             continue;
00692                         }
00693 
00694                     /* Only connect to wire if there is a CB */
00695                     if(is_cbox
00696                        (chan, seg, to_track, seg_details, BI_DIRECTIONAL))
00697                         {
00698                             to_switch = seg_details[to_track].wire_switch;
00699                             to_node =
00700                                 get_rr_node_index(tr_i, tr_j, to_type,
00701                                                   to_track, rr_node_indices);
00702 
00703                             *edge_list =
00704                                 insert_in_edge_list(*edge_list, to_node,
00705                                                     to_switch);
00706                             rr_edge_done[to_node] = TRUE;
00707                             ++num_conn;
00708                         }
00709                 }
00710         }
00711 
00712     return num_conn;
00713 }

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 ***	rr_node_indices
	)

Definition at line 1102 of file rr_graph2.c.

01107 {
01108     /* Returns the index of the specified routing resource node.  (x,y) are     *
01109      * the location within the FPGA, rr_type specifies the type of resource,    *
01110      * and ptc gives the number of this resource.  ptc is the class number,   *
01111      * pin number or track number, depending on what type of resource this      *
01112      * is.  All ptcs start at 0 and go up to pins_per_clb-1 or the equivalent. *
01113      * The order within a clb is:  SOURCEs + SINKs (type->num_class of them); IPINs,  *
01114      * and OPINs (pins_per_clb of them); CHANX; and CHANY (nodes_per_chan of    *
01115      * each).  For (x,y) locations that point at pads the order is:  type->capacity     *
01116      * occurances of SOURCE, SINK, OPIN, IPIN (one for each pad), then one      *
01117      * associated channel (if there is a channel at (x,y)).  All IO pads are    *
01118      * bidirectional, so while each will be used only as an INPAD or as an      *
01119      * OUTPAD, all the switches necessary to do both must be in each pad.       *
01120      *                                                                          *
01121      * Note that for segments (CHANX and CHANY) of length > 1, the segment is   *
01122      * given an rr_index based on the (x,y) location at which it starts (i.e.   *
01123      * lowest (x,y) location at which this segment exists).                     *
01124      * This routine also performs error checking to make sure the node in       *
01125      * question exists.                                                         */
01126 
01127     int iclass, tmp;
01128     t_type_ptr type;
01129     t_ivec lookup;
01130 
01131     assert(ptc >= 0);
01132     assert(x >= 0 && x <= (nx + 1));
01133     assert(y >= 0 && y <= (ny + 1));
01134 
01135     type = grid[x][y].type;
01136 
01137     /* Currently need to swap x and y for CHANX because of chan, seg convention */
01138     if(CHANX == rr_type)
01139         {
01140             tmp = x;
01141             x = y;
01142             y = tmp;
01143         }
01144 
01145     /* Start of that block.  */
01146     lookup = rr_node_indices[rr_type][x][y];
01147 
01148     /* Check valid ptc num */
01149     assert(ptc >= 0);
01150     assert(ptc < lookup.nelem);
01151 
01152 #ifdef DEBUG
01153     switch (rr_type)
01154         {
01155         case SOURCE:
01156             assert(ptc < type->num_class);
01157             assert(type->class_inf[ptc].type == DRIVER);
01158             break;
01159 
01160         case SINK:
01161             assert(ptc < type->num_class);
01162             assert(type->class_inf[ptc].type == RECEIVER);
01163             break;
01164 
01165         case OPIN:
01166             assert(ptc < type->num_pins);
01167             iclass = type->pin_class[ptc];
01168             assert(type->class_inf[iclass].type == DRIVER);
01169             break;
01170 
01171         case IPIN:
01172             assert(ptc < type->num_pins);
01173             iclass = type->pin_class[ptc];
01174             assert(type->class_inf[iclass].type == RECEIVER);
01175             break;
01176 
01177         case CHANX:
01178         case CHANY:
01179             break;
01180 
01181         default:
01182             printf("Error:  Bad rr_node passed to get_rr_node_index.\n"
01183                    "Request for type=%d ptc=%d at (%d, %d).\n",
01184                    rr_type, ptc, x, y);
01185             exit(1);
01186         }
01187 #endif
01188 
01189     return lookup.list[ptc];
01190 }

Here is the caller graph for this function:

int get_seg_end	(	IN t_seg_details *	seg_details,
		IN int	itrack,
		IN int	istart,
		IN int	chan_num,
		IN int	seg_max
	)

Definition at line 578 of file rr_graph2.c.

00583 {
00584     int len, ofs, end, first_full;
00585 
00586     len = seg_details[itrack].length;
00587     ofs = seg_details[itrack].start;
00588 
00589     /* Normal endpoint */
00590     end = istart + len - 1;
00591 
00592     /* If start is against edge it may have been clipped */
00593     if(1 == istart)
00594         {
00595             /* If the (staggered) startpoint of first full wire wasn't
00596              * also 1, we must be the clipped wire */
00597             first_full = (len - (chan_num % len) + ofs - 1) % len + 1;
00598             if(first_full > 1)
00599                 {
00600                     /* then we stop just before the first full seg */
00601                     end = first_full - 1;
00602                 }
00603         }
00604 
00605     /* Clip against far edge */
00606     if(end > seg_max)
00607         {
00608             end = seg_max;
00609         }
00610 
00611     return end;
00612 }

Here is the caller graph for this function:

int get_seg_start	(	IN t_seg_details *	seg_details,
		IN int	itrack,
		IN int	chan_num,
		IN int	seg_num
	)

Definition at line 541 of file rr_graph2.c.

00545 {
00546 
00547     int seg_start, length, start;
00548 
00549     seg_start = 1;
00550     if(FALSE == seg_details[itrack].longline)
00551         {
00552 
00553             length = seg_details[itrack].length;
00554             start = seg_details[itrack].start;
00555 
00556             /* Start is guaranteed to be between 1 and length.  Hence adding length to *
00557              * the quantity in brackets below guarantees it will be nonnegative.       */
00558 
00559             assert(start > 0);
00560             assert(start <= length);
00561 
00562             /* NOTE: Start points are staggered between different channels.
00563              * The start point must stagger backwards as chan_num increases.
00564              * Unidirectional routing expects this to allow the N-to-N 
00565              * assumption to be made with respect to ending wires in the core. */
00566             seg_start =
00567                 seg_num - (seg_num + length + chan_num - start) % length;
00568             if(seg_start < 1)
00569                 {
00570                     seg_start = 1;
00571                 }
00572         }
00573 
00574     return seg_start;
00575 }

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 ***	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 1194 of file rr_graph2.c.

01205 {
01206 
01207     /* This counts the fan-out from wire segment (chan, seg, track) to blocks on either side */
01208 
01209     t_linked_edge *edge_list_head;
01210     int j, pass, iconn, phy_track, end, to_node, max_conn, ipin, side, x,
01211         y, num_conn;
01212     t_type_ptr type;
01213     int off;
01214 
01215     /* End of this wire */
01216     end = get_seg_end(seg_details, track, seg, chan, chan_length);
01217 
01218     edge_list_head = *edge_list_ptr;
01219     num_conn = 0;
01220 
01221     for(j = seg; j <= end; j++)
01222         {
01223             if(is_cbox(chan, j, track, seg_details, directionality))
01224                 {
01225                     for(pass = 0; pass < 2; ++pass)
01226                         {
01227                             if(CHANX == chan_type)
01228                                 {
01229                                     x = j;
01230                                     y = chan + pass;
01231                                     side = (0 == pass ? TOP : BOTTOM);
01232                                 }
01233                             else
01234                                 {
01235                                     assert(CHANY == chan_type);
01236                                     x = chan + pass;
01237                                     y = j;
01238                                     side = (0 == pass ? RIGHT : LEFT);
01239                                 }
01240 
01241                             /* PAJ - if the pointed to is an EMPTY then shouldn't look for ipins */
01242                             if(grid[x][y].type == EMPTY_TYPE)
01243                                 continue;
01244 
01245                             /* Move from logical (straight) to physical (twisted) track index 
01246                              * - algorithm assigns ipin connections to same physical track index
01247                              * so that the logical track gets distributed uniformly */
01248                             phy_track =
01249                                 vpr_to_phy_track(track, chan, j, seg_details,
01250                                                  directionality);
01251 
01252                             /* We need the type to find the ipin map for this type */
01253                             type = grid[x][y].type;
01254                             off = grid[x][y].offset;
01255 
01256                             max_conn =
01257                                 track_to_ipin_lookup[type->
01258                                                      index][phy_track][off]
01259                                 [side].nelem;
01260                             for(iconn = 0; iconn < max_conn; iconn++)
01261                                 {
01262                                     ipin =
01263                                         track_to_ipin_lookup[type->
01264                                                              index][phy_track]
01265                                         [off][side].list[iconn];
01266 
01267                                     /* Check there is a connection and Fc map isn't wrong */
01268                                     assert(type->pinloc[off][side][ipin]);
01269                                     assert(type->is_global_pin[ipin] ==
01270                                            FALSE);
01271 
01272                                     to_node =
01273                                         get_rr_node_index(x, y, IPIN, ipin,
01274                                                           rr_node_indices);
01275                                     edge_list_head =
01276                                         insert_in_edge_list(edge_list_head,
01277                                                             to_node,
01278                                                             wire_to_ipin_switch);
01279                                 }
01280                             num_conn += max_conn;
01281                         }
01282                 }
01283         }
01284 
01285     *edge_list_ptr = edge_list_head;
01286     return (num_conn);
01287 }

Here is the call graph for this function:

Here is the caller graph for this function:

int get_track_to_tracks	(	IN int	from_chan,
		IN int	from_seg,
		IN int	from_track,
		IN t_rr_type	from_type,
		IN int	to_seg,
		IN t_rr_type	to_type,
		IN int	chan_len,
		IN int	nodes_per_chan,
		IN int *	opin_mux_size,
		IN int	Fs_per_side,
		IN short *****	sblock_pattern,
		INOUT struct s_linked_edge **	edge_list,
		IN t_seg_details *	seg_details,
		IN enum e_directionality	directionality,
		IN t_ivec ***	rr_node_indices,
		INOUT boolean *	rr_edge_done,
		IN struct s_ivec ***	switch_block_conn
	)

Definition at line 1307 of file rr_graph2.c.

01324 {
01325     int num_conn;
01326     int from_switch, from_end, from_sb, from_first;
01327     int to_chan, to_sb;
01328     int start, end;
01329     struct s_ivec conn_tracks;
01330     boolean from_is_sbox, is_behind, Fs_clipped;
01331     enum e_side from_side_a, from_side_b, to_side;
01332 
01333     assert(from_seg ==
01334            get_seg_start(seg_details, from_track, from_chan, from_seg));
01335 
01336     from_switch = seg_details[from_track].wire_switch;
01337     from_end =
01338         get_seg_end(seg_details, from_track, from_seg, from_chan, chan_len);
01339     from_first = from_seg - 1;
01340 
01341     /* Figure out the sides of SB the from_wire will use */
01342     if(CHANX == from_type)
01343         {
01344             from_side_a = RIGHT;
01345             from_side_b = LEFT;
01346         }
01347     else
01348         {
01349             assert(CHANY == from_type);
01350             from_side_a = TOP;
01351             from_side_b = BOTTOM;
01352         }
01353 
01354     /* Figure out if the to_wire is connecting to a SB 
01355      * that is behind it. */
01356     is_behind = FALSE;
01357     if(to_type == from_type)
01358         {
01359             /* If inline, check that they only are trying
01360              * to connect at endpoints. */
01361             assert((to_seg == (from_end + 1)) || (to_seg == (from_seg - 1)));
01362             if(to_seg > from_end)
01363                 {
01364                     is_behind = TRUE;
01365                 }
01366         }
01367     else
01368         {
01369             /* If bending, check that they are adjacent to
01370              * our channel. */
01371             assert((to_seg == from_chan) || (to_seg == (from_chan + 1)));
01372             if(to_seg > from_chan)
01373                 {
01374                     is_behind = TRUE;
01375                 }
01376         }
01377 
01378     /* Figure out the side of SB the to_wires will use.
01379      * The to_seg and from_chan are in same direction. */
01380     if(CHANX == to_type)
01381         {
01382             to_side = (is_behind ? RIGHT : LEFT);
01383         }
01384     else
01385         {
01386             assert(CHANY == to_type);
01387             to_side = (is_behind ? TOP : BOTTOM);
01388         }
01389 
01390     /* Set the loop bounds */
01391     start = from_first;
01392     end = from_end;
01393 
01394     /* If we are connecting in same direction the connection is 
01395      * on one of the two sides so clip the bounds to the SB of
01396      * interest and proceed normally. */
01397     if(to_type == from_type)
01398         {
01399             start = (is_behind ? end : start);
01400             end = start;
01401         }
01402 
01403     /* Iterate over the SBs */
01404     num_conn = 0;
01405     for(from_sb = start; from_sb <= end; ++from_sb)
01406         {
01407             /* Figure out if we are at a sbox */
01408             from_is_sbox = is_sbox(from_chan, from_seg, from_sb, from_track,
01409                                    seg_details, directionality);
01410             /* end of wire must be an sbox */
01411             if(from_sb == from_end || from_sb == from_first)
01412                 {
01413                     from_is_sbox = TRUE;        /* Endpoints always default to true */
01414                 }
01415 
01416             /* to_chan is the current segment if different directions,
01417              * otherwise to_chan is the from_chan */
01418             to_chan = from_sb;
01419             to_sb = from_chan;
01420             if(from_type == to_type)
01421                 {
01422                     to_chan = from_chan;
01423                     to_sb = from_sb;
01424                 }
01425 
01426             /* Do the edges going to the left or down */
01427             if(from_sb < from_end)
01428                 {
01429                     if(BI_DIRECTIONAL == directionality)
01430                         {
01431                             conn_tracks =
01432                                 switch_block_conn[from_side_a][to_side]
01433                                 [from_track];
01434                             num_conn +=
01435                                 get_bidir_track_to_chan_seg(conn_tracks,
01436                                                             rr_node_indices,
01437                                                             to_chan, to_seg,
01438                                                             to_sb, to_type,
01439                                                             seg_details,
01440                                                             from_is_sbox,
01441                                                             from_switch,
01442                                                             rr_edge_done,
01443                                                             directionality,
01444                                                             edge_list);
01445                         }
01446                     if(UNI_DIRECTIONAL == directionality)
01447                         {
01448                             /* No fanout if no SB. */
01449                             /* We are connecting from the top or right of SB so it
01450                              * makes the most sense to only there from DEC_DIRECTION wires. */
01451                             if((from_is_sbox) &&
01452                                (DEC_DIRECTION ==
01453                                 seg_details[from_track].direction))
01454                                 {
01455                                     num_conn +=
01456                                         get_unidir_track_to_chan_seg((from_sb
01457                                                                       ==
01458                                                                       from_first),
01459                                                                      from_track,
01460                                                                      to_chan,
01461                                                                      to_seg,
01462                                                                      to_sb,
01463                                                                      to_type,
01464                                                                      nodes_per_chan,
01465                                                                      nx, ny,
01466                                                                      from_side_a,
01467                                                                      to_side,
01468                                                                      Fs_per_side,
01469                                                                      opin_mux_size,
01470                                                                      sblock_pattern,
01471                                                                      rr_node_indices,
01472                                                                      seg_details,
01473                                                                      rr_edge_done,
01474                                                                      &Fs_clipped,
01475                                                                      edge_list);
01476                                 }
01477                         }
01478                 }
01479 
01480             /* Do the edges going to the right or up */
01481             if(from_sb > from_first)
01482                 {
01483                     if(BI_DIRECTIONAL == directionality)
01484                         {
01485                             conn_tracks =
01486                                 switch_block_conn[from_side_b][to_side]
01487                                 [from_track];
01488                             num_conn +=
01489                                 get_bidir_track_to_chan_seg(conn_tracks,
01490                                                             rr_node_indices,
01491                                                             to_chan, to_seg,
01492                                                             to_sb, to_type,
01493                                                             seg_details,
01494                                                             from_is_sbox,
01495                                                             from_switch,
01496                                                             rr_edge_done,
01497                                                             directionality,
01498                                                             edge_list);
01499                         }
01500                     if(UNI_DIRECTIONAL == directionality)
01501                         {
01502                             /* No fanout if no SB. */
01503                             /* We are connecting from the bottom or left of SB so it
01504                              * makes the most sense to only there from INC_DIRECTION wires. */
01505                             if((from_is_sbox) &&
01506                                (INC_DIRECTION ==
01507                                 seg_details[from_track].direction))
01508                                 {
01509                                     num_conn +=
01510                                         get_unidir_track_to_chan_seg((from_sb
01511                                                                       ==
01512                                                                       from_end),
01513                                                                      from_track,
01514                                                                      to_chan,
01515                                                                      to_seg,
01516                                                                      to_sb,
01517                                                                      to_type,
01518                                                                      nodes_per_chan,
01519                                                                      nx, ny,
01520                                                                      from_side_b,
01521                                                                      to_side,
01522                                                                      Fs_per_side,
01523                                                                      opin_mux_size,
01524                                                                      sblock_pattern,
01525                                                                      rr_node_indices,
01526                                                                      seg_details,
01527                                                                      rr_edge_done,
01528                                                                      &Fs_clipped,
01529                                                                      edge_list);
01530                                 }
01531                         }
01532                 }
01533         }
01534 
01535     return num_conn;
01536 }

Here is the call graph for this function:

Here is the caller graph for this function:

int get_unidir_opin_connections	(	IN int	chan,
		IN int	seg,
		IN int	Fc,
		IN t_rr_type	chan_type,
		IN t_seg_details *	seg_details,
		INOUT t_linked_edge **	edge_list_ptr,
		INOUT int **	Fc_ofs,
		INOUT boolean *	rr_edge_done,
		IN int	max_len,
		IN int	nodes_per_chan,
		IN t_ivec ***	rr_node_indices,
		OUT boolean *	Fc_clipped
	)

Definition at line 718 of file rr_graph2.c.

00730 {
00731     /* Gets a linked list of Fc nodes to connect to in given
00732      * chan seg.  Fc_ofs is used for the for the opin staggering
00733      * pattern. */
00734 
00735     int *inc_muxes = NULL;
00736     int *dec_muxes = NULL;
00737     int num_inc_muxes, num_dec_muxes, iconn;
00738     int inc_inode, dec_inode;
00739     int inc_mux, dec_mux;
00740     int inc_track, dec_track;
00741     int x, y;
00742     int num_edges;
00743 
00744     *Fc_clipped = FALSE;
00745 
00746     /* Fc is assigned in pairs so check it is even. */
00747     assert(Fc % 2 == 0);
00748 
00749     /* get_rr_node_indices needs x and y coords. */
00750     x = ((CHANX == chan_type) ? seg : chan);
00751     y = ((CHANX == chan_type) ? chan : seg);
00752 
00753     /* Get the lists of possible muxes. */
00754     inc_muxes = label_wire_muxes(chan, seg, seg_details, max_len,
00755                                  INC_DIRECTION, nodes_per_chan,
00756                                  &num_inc_muxes);
00757     dec_muxes =
00758         label_wire_muxes(chan, seg, seg_details, max_len, DEC_DIRECTION,
00759                          nodes_per_chan, &num_dec_muxes);
00760 
00761     /* Clip Fc to the number of muxes. */
00762     if(((Fc / 2) > num_inc_muxes) || ((Fc / 2) > num_dec_muxes))
00763         {
00764             *Fc_clipped = TRUE;
00765             Fc = 2 * min(num_inc_muxes, num_dec_muxes);
00766         }
00767 
00768     /* Assign tracks to meet Fc demand */
00769     num_edges = 0;
00770     for(iconn = 0; iconn < (Fc / 2); ++iconn)
00771         {
00772             /* Figure of the next mux to use */
00773             inc_mux = Fc_ofs[chan][seg] % num_inc_muxes;
00774             dec_mux = Fc_ofs[chan][seg] % num_dec_muxes;
00775             ++Fc_ofs[chan][seg];
00776 
00777             /* Figure out the track it corresponds to. */
00778             inc_track = inc_muxes[inc_mux];
00779             dec_track = dec_muxes[dec_mux];
00780 
00781             /* Figure the inodes of those muxes */
00782             inc_inode =
00783                 get_rr_node_index(x, y, chan_type, inc_track,
00784                                   rr_node_indices);
00785             dec_inode =
00786                 get_rr_node_index(x, y, chan_type, dec_track,
00787                                   rr_node_indices);
00788 
00789             /* Add to the list. */
00790             if(FALSE == rr_edge_done[inc_inode])
00791                 {
00792                     rr_edge_done[inc_inode] = TRUE;
00793                     *edge_list_ptr = insert_in_edge_list(*edge_list_ptr,
00794                                                          inc_inode,
00795                                                          seg_details
00796                                                          [inc_track].
00797                                                          opin_switch);
00798                     ++num_edges;
00799                 }
00800             if(FALSE == rr_edge_done[dec_inode])
00801                 {
00802                     rr_edge_done[dec_inode] = TRUE;
00803                     *edge_list_ptr = insert_in_edge_list(*edge_list_ptr,
00804                                                          dec_inode,
00805                                                          seg_details
00806                                                          [dec_track].
00807                                                          opin_switch);
00808                     ++num_edges;
00809                 }
00810         }
00811 
00812     if(inc_muxes)
00813         {
00814             free(inc_muxes);
00815             inc_muxes = NULL;
00816         }
00817     if(dec_muxes)
00818         {
00819             free(dec_muxes);
00820             dec_muxes = NULL;
00821         }
00822 
00823     return num_edges;
00824 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 827 of file rr_graph2.c.

00832 {
00833 
00834     int start, length, ofs, fac, start_seg;
00835 
00836     fac = 1;
00837     if(UNI_DIRECTIONAL == directionality)
00838         {
00839             fac = 2;
00840         }
00841 
00842     start = seg_details[track].start;
00843     length = seg_details[track].length;
00844 
00845     /* Make sure they gave us correct start */
00846     start_seg = get_seg_start(seg_details, track, chan, seg);
00847 
00848     ofs = seg - start_seg;
00849 
00850     assert(ofs >= 0);
00851     assert(ofs < length);
00852 
00853     /* If unidir segment that is going backwards, we need to flip the ofs */
00854     if(DEC_DIRECTION == seg_details[track].direction)
00855         {
00856             ofs = (length - 1) - ofs;
00857         }
00858 
00859     return seg_details[track].cb[ofs];
00860 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 1753 of file rr_graph2.c.

01759 {
01760 
01761     int start, length, ofs, fac;
01762 
01763     fac = 1;
01764     if(UNI_DIRECTIONAL == directionality)
01765         {
01766             fac = 2;
01767         }
01768 
01769     start = seg_details[track].start;
01770     length = seg_details[track].length;
01771 
01772     /* Make sure they gave us correct start */
01773     wire_seg = get_seg_start(seg_details, track, chan, wire_seg);
01774 
01775     ofs = sb_seg - wire_seg + 1;        /* Ofset 0 is behind us, so add 1 */
01776 
01777     assert(ofs >= 0);
01778     assert(ofs < (length + 1));
01779 
01780     /* If unidir segment that is going backwards, we need to flip the ofs */
01781     if((ofs % fac) > 0)
01782         {
01783             ofs = length - ofs;
01784         }
01785 
01786     return seg_details[track].sb[ofs];
01787 }

Here is the call graph for this function:

Here is the caller graph for this function:

void load_sblock_pattern_lookup	(	IN int	i,
		IN int	j,
		IN int	nodes_per_chan,
		IN t_seg_details *	seg_details,
		IN int	Fs,
		IN enum e_switch_block_type	switch_block_type,
		INOUT short *****	sblock_pattern
	)

Definition at line 1989 of file rr_graph2.c.

01996 {
01997 
01998     /* This routine loads a lookup table for sblock topology. The lookup table is huge
01999      * because the sblock varies from location to location. The i, j means the owning
02000      * location of the sblock under investigation. */
02001 
02002     int side_cw_incoming_wire_count, side_ccw_incoming_wire_count,
02003         opp_incoming_wire_count;
02004     int to_side, side, side_cw, side_ccw, side_opp, itrack;
02005     int Fs_per_side, chan, seg, chan_len, sb_seg;
02006     boolean is_core_sblock, is_corner_sblock, x_edge, y_edge;
02007     int *incoming_wire_label[4];
02008     int *wire_mux_on_track[4];
02009     int num_incoming_wires[4];
02010     int num_ending_wires[4];
02011     int num_wire_muxes[4];
02012     boolean skip, vert, pos_dir;
02013     enum e_direction dir;
02014 
02015     Fs_per_side = 1;
02016     if(Fs != -1)
02017         {
02018             Fs_per_side = Fs / 3;
02019         }
02020 
02021     /* SB's have coords from (0, 0) to (nx, ny) */
02022     assert(i >= 0);
02023     assert(i <= nx);
02024     assert(j >= 0);
02025     assert(j <= ny);
02026 
02027     /* May 12 - 15, 2007
02028      *
02029      * I identify three types of sblocks in the chip: 1) The core sblock, whose special
02030      * property is that the number of muxes (and ending wires) on each side is the same (very useful
02031      * property, since it leads to a N-to-N assignment problem with ending wires). 2) The corner sblock
02032      * which is same as a L=1 core sblock with 2 sides only (again N-to-N assignment problem). 3) The
02033      * fringe / chip edge sblock which is most troublesome, as balance in each side of muxes is 
02034      * attainable but balance in the entire sblock is not. The following code first identifies the
02035      * incoming wires, which can be classified into incoming passing wires with sbox and incoming
02036      * ending wires (the word "incoming" is sometimes dropped for ease of discussion). It appropriately 
02037      * labels all the wires on each side by the following order: By the call to label_incoming_wires, 
02038      * which labels for one side, the order is such that the incoming ending wires (always with sbox) 
02039      * are labelled first 0,1,2,... p-1, then the incoming passing wires with sbox are labelled 
02040      * p,p+1,p+2,... k-1 (for total of k). By this convention, one can easily distinguish the ending
02041      * wires from the passing wires by checking a label against num_ending_wires variable. 
02042      *
02043      * After labelling all the incoming wires, this routine labels the muxes on the side we're currently
02044      * connecting to (iterated for four sides of the sblock), called the to_side. The label scheme is
02045      * the natural order of the muxes by their track #. Also we find the number of muxes.
02046      *
02047      * For each to_side, the total incoming wires that connect to the muxes on to_side 
02048      * come from three sides: side_1 (to_side's right), side_2 (to_side's left) and opp_side.
02049      * The problem of balancing mux size is then: considering all incoming passing wires
02050      * with sbox on side_1, side_2 and opp_side, how to assign them to the muxes on to_side
02051      * (with specified Fs) in a way that mux size is imbalanced by at most 1. I solve this
02052      * problem by this approach: the first incoming passing wire will connect to 0, 1, 2, 
02053      * ..., Fs_per_side - 1, then the next incoming passing wire will connect to 
02054      * Fs_per_side, Fs_per_side+1, ..., Fs_per_side*2-1, and so on. This consistent STAGGERING
02055      * ensures N-to-N assignment is perfectly balanced and M-to-N assignment is imbalanced by no
02056      * more than 1.
02057      *
02058      * For the sblock_pattern_init_mux_lookup lookup table, I will only need the lookup
02059      * table to remember the first/init mux to connect, since the convention is Fs_per_side consecutive
02060      * muxes to connect. Then how do I determine the order of the incoming wires? I use the labels
02061      * on side_1, then labels on side_2, then labels on opp_side. Effectively I listed all
02062      * incoming passing wires from the three sides, and order them to each make Fs_per_side
02063      * consecutive connections to muxes, and use % to rotate to keep imbalance at most 1. 
02064      */
02065 
02066     /* SB's range from (0, 0) to (nx, ny) */
02067     /* First find all four sides' incoming wires */
02068     x_edge = ((i < 1) || (i >= nx));
02069     y_edge = ((j < 1) || (j >= ny));
02070 
02071     is_corner_sblock = (x_edge && y_edge);
02072     is_core_sblock = (!x_edge && !y_edge);
02073 
02074     /* "Label" the wires around the switch block by connectivity. */
02075     for(side = 0; side < 4; ++side)
02076         {
02077             /* Assume the channel segment doesn't exist. */
02078             wire_mux_on_track[side] = NULL;
02079             incoming_wire_label[side] = NULL;
02080             num_incoming_wires[side] = 0;
02081             num_ending_wires[side] = 0;
02082             num_wire_muxes[side] = 0;
02083 
02084             /* Skip the side and leave the zero'd value if the
02085              * channel segment doesn't exist. */
02086             skip = TRUE;
02087             switch (side)
02088                 {
02089                 case TOP:
02090                     if(j < ny)
02091                         {
02092                             skip = FALSE;
02093                         };
02094                     break;
02095                 case RIGHT:
02096                     if(i < nx)
02097                         {
02098                             skip = FALSE;
02099                         }
02100                     break;
02101                 case BOTTOM:
02102                     if(j > 0)
02103                         {
02104                             skip = FALSE;
02105                         }
02106                     break;
02107                 case LEFT:
02108                     if(i > 0)
02109                         {
02110                             skip = FALSE;
02111                         }
02112                     break;
02113                 }
02114             if(skip)
02115                 {
02116                     continue;
02117                 }
02118 
02119             /* Figure out the channel and segment for a certain direction */
02120             vert = ((side == TOP) || (side == BOTTOM));
02121             pos_dir = ((side == TOP) || (side == RIGHT));
02122             chan = (vert ? i : j);
02123             sb_seg = (vert ? j : i);
02124             seg = (pos_dir ? (sb_seg + 1) : sb_seg);
02125             chan_len = (vert ? ny : nx);
02126 
02127             /* Figure out all the tracks on a side that are ending and the
02128              * ones that are passing through and have a SB. */
02129             dir = (pos_dir ? DEC_DIRECTION : INC_DIRECTION);
02130             incoming_wire_label[side] =
02131                 label_incoming_wires(chan, seg, sb_seg, seg_details, chan_len,
02132                                      dir, nodes_per_chan,
02133                                      &num_incoming_wires[side],
02134                                      &num_ending_wires[side]);
02135 
02136             /* Figure out all the tracks on a side that are starting. */
02137             dir = (pos_dir ? INC_DIRECTION : DEC_DIRECTION);
02138             wire_mux_on_track[side] = label_wire_muxes(chan, seg,
02139                                                        seg_details, chan_len,
02140                                                        dir, nodes_per_chan,
02141                                                        &num_wire_muxes[side]);
02142         }
02143 
02144     for(to_side = 0; to_side < 4; to_side++)
02145         {
02146             /* Can't do anything if no muxes on this side. */
02147             if(0 == num_wire_muxes[to_side])
02148                 {
02149                     continue;
02150                 }
02151 
02152             /* Figure out side rotations */
02153             assert((TOP == 0) && (RIGHT == 1) && (BOTTOM == 2)
02154                    && (LEFT == 3));
02155             side_cw = (to_side + 1) % 4;
02156             side_opp = (to_side + 2) % 4;
02157             side_ccw = (to_side + 3) % 4;
02158 
02159             /* For the core sblock:
02160              * The new order for passing wires should appear as
02161              * 0,1,2..,scw-1, for passing wires with sbox on side_cw 
02162              * scw,scw+1,...,sccw-1, for passing wires with sbox on side_ccw
02163              * sccw,sccw+1,... for passing wires with sbox on side_opp.
02164              * This way, I can keep the imbalance to at most 1.
02165              *
02166              * For the fringe sblocks, I don't distinguish between
02167              * passing and ending wires so the above statement still holds
02168              * if you replace "passing" by "incoming" */
02169 
02170             side_cw_incoming_wire_count = 0;
02171             if(incoming_wire_label[side_cw])
02172                 {
02173                     for(itrack = 0; itrack < nodes_per_chan; itrack++)
02174                         {
02175                             /* Ending wire, or passing wire with sbox. */
02176                             if(incoming_wire_label[side_cw][itrack] != UN_SET)
02177                                 {
02178 
02179                                     if((is_corner_sblock || is_core_sblock) &&
02180                                        (incoming_wire_label[side_cw][itrack] <
02181                                         num_ending_wires[side_cw]))
02182                                         {
02183                                             /* The ending wires in core sblocks form N-to-N assignment 
02184                                              * problem, so can use any pattern such as Wilton. This N-to-N 
02185                                              * mapping depends on the fact that start points stagger across
02186                                              * channels. */
02187                                             assert(num_ending_wires[side_cw]
02188                                                    ==
02189                                                    num_wire_muxes[to_side]);
02190                                             sblock_pattern[i][j][side_cw]
02191                                                 [to_side][itrack] =
02192                                                 get_simple_switch_block_track
02193                                                 (side_cw, to_side,
02194                                                  incoming_wire_label[side_cw]
02195                                                  [itrack], switch_block_type,
02196                                                  num_wire_muxes[to_side]);
02197 
02198                                         }
02199                                     else
02200                                         {
02201 
02202                                             /* These are passing wires with sbox only for core sblocks
02203                                              * or passing and ending wires (for fringe cases). */
02204                                             sblock_pattern[i][j][side_cw]
02205                                                 [to_side][itrack] =
02206                                                 (side_cw_incoming_wire_count *
02207                                                  Fs_per_side) %
02208                                                 num_wire_muxes[to_side];
02209                                             side_cw_incoming_wire_count++;
02210                                         }
02211                                 }
02212                         }
02213                 }
02214 
02215 
02216             side_ccw_incoming_wire_count = 0;
02217             for(itrack = 0; itrack < nodes_per_chan; itrack++)
02218                 {
02219 
02220                     /* if that side has no channel segment skip it */
02221                     if(incoming_wire_label[side_ccw] == NULL)
02222                         break;
02223 
02224                     /* not ending wire nor passing wire with sbox */
02225                     if(incoming_wire_label[side_ccw][itrack] != UN_SET)
02226                         {
02227 
02228                             if((is_corner_sblock || is_core_sblock) &&
02229                                (incoming_wire_label[side_ccw][itrack] <
02230                                 num_ending_wires[side_ccw]))
02231                                 {
02232                                     /* The ending wires in core sblocks form N-to-N assignment problem, so can
02233                                      * use any pattern such as Wilton */
02234                                     assert(incoming_wire_label[side_ccw]
02235                                            [itrack] <
02236                                            num_wire_muxes[to_side]);
02237                                     sblock_pattern[i][j][side_ccw][to_side]
02238                                         [itrack] =
02239                                         get_simple_switch_block_track
02240                                         (side_ccw, to_side,
02241                                          incoming_wire_label[side_ccw]
02242                                          [itrack], switch_block_type,
02243                                          num_wire_muxes[to_side]);
02244                                 }
02245                             else
02246                                 {
02247 
02248                                     /* These are passing wires with sbox only for core sblocks
02249                                      * or passing and ending wires (for fringe cases). */
02250                                     sblock_pattern[i][j][side_ccw][to_side]
02251                                         [itrack] =
02252                                         ((side_ccw_incoming_wire_count +
02253                                           side_cw_incoming_wire_count) *
02254                                          Fs_per_side) %
02255                                         num_wire_muxes[to_side];
02256                                     side_ccw_incoming_wire_count++;
02257                                 }
02258                         }
02259                 }
02260 
02261 
02262             opp_incoming_wire_count = 0;
02263             if(incoming_wire_label[side_opp])
02264                 {
02265                     for(itrack = 0; itrack < nodes_per_chan; itrack++)
02266                         {
02267                             /* not ending wire nor passing wire with sbox */
02268                             if(incoming_wire_label[side_opp][itrack] !=
02269                                UN_SET)
02270                                 {
02271 
02272                                     /* corner sblocks for sure have no opposite channel segments so don't care about them */
02273                                     if(is_core_sblock)
02274                                         {
02275                                             if(incoming_wire_label[side_opp]
02276                                                [itrack] <
02277                                                num_ending_wires[side_opp])
02278                                                 {
02279                                                     /* The ending wires in core sblocks form N-to-N assignment problem, so can
02280                                                      * use any pattern such as Wilton */
02281                                                     /* In the direct connect case, I know for sure the init mux is at the same track #
02282                                                      * as this ending wire, but still need to find the init mux label for Fs > 3 */
02283                                                     sblock_pattern[i][j]
02284                                                         [side_opp][to_side]
02285                                                         [itrack] =
02286                                                         find_label_of_track
02287                                                         (wire_mux_on_track
02288                                                          [to_side],
02289                                                          num_wire_muxes
02290                                                          [to_side], itrack);
02291                                                 }
02292                                             else
02293                                                 {
02294                                                     /* These are passing wires with sbox for core sblocks */
02295                                                     sblock_pattern[i][j]
02296                                                         [side_opp][to_side]
02297                                                         [itrack] =
02298                                                         ((side_ccw_incoming_wire_count + side_cw_incoming_wire_count) * Fs_per_side + opp_incoming_wire_count * (Fs_per_side - 1)) % num_wire_muxes[to_side];
02299                                                     opp_incoming_wire_count++;
02300                                                 }
02301                                         }
02302                                     else
02303                                         {
02304                                             if(incoming_wire_label[side_opp]
02305                                                [itrack] <
02306                                                num_ending_wires[side_opp])
02307                                                 {
02308                                                     sblock_pattern[i][j]
02309                                                         [side_opp][to_side]
02310                                                         [itrack] =
02311                                                         find_label_of_track
02312                                                         (wire_mux_on_track
02313                                                          [to_side],
02314                                                          num_wire_muxes
02315                                                          [to_side], itrack);
02316                                                 }
02317                                             else
02318                                                 {
02319                                                     /* These are passing wires with sbox for fringe sblocks */
02320                                                     sblock_pattern[i][j]
02321                                                         [side_opp][to_side]
02322                                                         [itrack] =
02323                                                         ((side_ccw_incoming_wire_count + side_cw_incoming_wire_count) * Fs_per_side + opp_incoming_wire_count * (Fs_per_side - 1)) % num_wire_muxes[to_side];
02324                                                     opp_incoming_wire_count++;
02325                                                 }
02326                                         }
02327                                 }
02328                         }
02329                 }
02330         }
02331 
02332     for(side = 0; side < 4; ++side)
02333         {
02334             if(incoming_wire_label[side])
02335                 {
02336                     free(incoming_wire_label[side]);
02337                 }
02338             if(wire_mux_on_track[side])
02339                 {
02340                     free(wire_mux_on_track[side]);
02341                 }
02342         }
02343 }

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

boolean* rr_edge_done

Definition at line 27 of file rr_graph2.c.

SRC/rr_graph2.h File Reference

Functions

Variables

Function Documentation

Variable Documentation