vpr/SRC/route/rr_graph.h File Reference
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Typedefs | |
| typedef enum e_graph_type | t_graph_type |
Enumerations | |
| enum | e_graph_type { GRAPH_GLOBAL, GRAPH_BIDIR, GRAPH_UNIDIR, GRAPH_UNIDIR_TILEABLE } |
| enum | { RR_GRAPH_NO_WARN = 0x00, RR_GRAPH_WARN_FC_CLIPPED = 0x01, RR_GRAPH_WARN_CHAN_WIDTH_CHANGED = 0x02 } |
Functions | |
| void | build_rr_graph (INP t_graph_type graph_type, INP int num_types, INP t_type_ptr types, INP int nx, INP int ny, INP struct s_grid_tile **grid, INP int chan_width, INP struct s_chan_width_dist *chan_capacity_inf, INP enum e_switch_block_type sb_type, INP int Fs, INP int num_seg_types, INP int num_switches, INP t_segment_inf *segment_inf, INP int global_route_switch, INP int delayless_switch, INP t_timing_inf timing_inf, INP int wire_to_ipin_switch, INP enum e_base_cost_type base_cost_type, OUTP int *Warnings) |
| void | free_rr_graph (void) |
| void | dump_rr_graph (INP const char *file_name) |
| void | print_rr_indexed_data (FILE *fp, int index) |
| void | load_net_rr_terminals (t_ivec ***rr_node_indices) |
| void | print_rr_node (FILE *fp, t_rr_node *rr_node, int inode) |
Typedef Documentation
| typedef enum e_graph_type t_graph_type |
Definition at line 12 of file rr_graph.h.
Enumeration Type Documentation
| anonymous enum |
Warnings about the routing graph that can be returned. This is to avoid output messages during a value sweep
Definition at line 17 of file rr_graph.h.
{
RR_GRAPH_NO_WARN = 0x00,
RR_GRAPH_WARN_FC_CLIPPED = 0x01,
RR_GRAPH_WARN_CHAN_WIDTH_CHANGED = 0x02
};
| enum e_graph_type |
- Enumerator:
Definition at line 4 of file rr_graph.h.
{
GRAPH_GLOBAL, /**< One node per channel with wire capacity > 1 and full connectivity */
GRAPH_BIDIR, /**< Detailed bidirectional graph */
GRAPH_UNIDIR, /**< Detailed unidir graph, untilable */
/* RESEARCH TODO: Get this option debugged */
GRAPH_UNIDIR_TILEABLE /**< Detail unidir graph with wire groups multiples of 2*L */
};
Function Documentation
| void build_rr_graph | ( | INP t_graph_type | graph_type, |
| INP int | num_types, | ||
| INP t_type_ptr | types, | ||
| INP int | nx, | ||
| INP int | ny, | ||
| INP struct s_grid_tile ** | grid, | ||
| INP int | chan_width, | ||
| INP struct s_chan_width_dist * | chan_capacity_inf, | ||
| INP enum e_switch_block_type | sb_type, | ||
| INP int | Fs, | ||
| INP int | num_seg_types, | ||
| INP int | num_switches, | ||
| INP t_segment_inf * | segment_inf, | ||
| INP int | global_route_switch, | ||
| INP int | delayless_switch, | ||
| INP t_timing_inf | timing_inf, | ||
| INP int | wire_to_ipin_switch, | ||
| INP enum e_base_cost_type | base_cost_type, | ||
| OUTP int * | Warnings | ||
| ) |
Definition at line 258 of file rr_graph.c.
{
/* Temp structures used to build graph */
int nodes_per_chan, i, j;
t_seg_details *seg_details = NULL;
int *Fc_in = NULL;
int *Fc_out = NULL;
int *****opin_to_track_map = NULL; /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
int *****ipin_to_track_map = NULL; /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
t_ivec ****track_to_ipin_lookup = NULL; /* [0..num_types-1][0..nodes_per_chan-1][0..height][0..3] */
t_ivec ***switch_block_conn = NULL;
short *****unidir_sb_pattern = NULL;
boolean *rr_edge_done = NULL;
boolean is_global_graph;
boolean Fc_clipped;
boolean use_full_seg_groups;
boolean *perturb_ipins = NULL;
enum e_directionality directionality;
int **Fc_xofs = NULL; /* [0..ny-1][0..nx-1] */
int **Fc_yofs = NULL; /* [0..nx-1][0..ny-1] */
rr_node_indices = NULL;
rr_node = NULL;
num_rr_nodes = 0;
/* Reset warning flag */
*Warnings = RR_GRAPH_NO_WARN;
/* Decode the graph_type */
is_global_graph = FALSE;
if(GRAPH_GLOBAL == graph_type)
{
is_global_graph = TRUE;
}
use_full_seg_groups = FALSE;
if(GRAPH_UNIDIR_TILEABLE == graph_type)
{
use_full_seg_groups = TRUE;
}
directionality = UNI_DIRECTIONAL;
if(GRAPH_BIDIR == graph_type)
{
directionality = BI_DIRECTIONAL;
}
if(is_global_graph)
{
directionality = BI_DIRECTIONAL;
}
/* Global routing uses a single longwire track */
nodes_per_chan = (is_global_graph ? 1 : chan_width);
assert(nodes_per_chan > 0);
/* START SEG_DETAILS */
if(is_global_graph)
{
/* Sets up a single unit length segment type for global routing. */
seg_details =
alloc_and_load_global_route_seg_details(nodes_per_chan,
global_route_switch);
}
else
{
/* Setup segments including distrubuting tracks and staggering.
* If use_full_seg_groups is specified, nodes_per_chan may be
* changed. Warning should be singled to caller if this happens. */
seg_details = alloc_and_load_seg_details(&nodes_per_chan,
max(nx, ny),
num_seg_types,
segment_inf,
use_full_seg_groups,
is_global_graph,
directionality);
if((is_global_graph ? 1 : chan_width) != nodes_per_chan)
{
*Warnings |= RR_GRAPH_WARN_CHAN_WIDTH_CHANGED;
}
#ifdef CREATE_ECHO_FILES
dump_seg_details(seg_details, nodes_per_chan, "seg_details.txt");
#endif /* CREATE_ECHO_FILES */
}
/* END SEG_DETAILS */
/* START FC */
/* Determine the actual value of Fc */
if(is_global_graph)
{
Fc_in = (int *)my_malloc(sizeof(int) * num_types);
Fc_out = (int *)my_malloc(sizeof(int) * num_types);
for(i = 0; i < num_types; ++i)
{
Fc_in[i] = 1;
Fc_out[i] = 1;
}
}
else
{
Fc_clipped = FALSE;
Fc_in =
alloc_and_load_actual_fc(num_types, types, nodes_per_chan,
FALSE, directionality, &Fc_clipped);
if(Fc_clipped)
{
*Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
}
Fc_clipped = FALSE;
Fc_out =
alloc_and_load_actual_fc(num_types, types, nodes_per_chan,
TRUE, directionality, &Fc_clipped);
if(Fc_clipped)
{
*Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
}
#ifdef VERBOSE
for(i = 1; i < num_types; ++i)
{ /* Skip "<EMPTY>" */
if(type_descriptors[i].is_Fc_out_full_flex)
{
printf
("Fc Actual Values: Type = %s, Fc_out = full, Fc_in = %d.\n",
type_descriptors[i].name, Fc_input[i]);
}
else
{
printf
("Fc Actual Values: Type = %s, Fc_out = %d, Fc_in = %d.\n",
type_descriptors[i].name, Fc_output[i],
Fc_input[i]);
}
}
#endif /* VERBOSE */
}
perturb_ipins =
alloc_and_load_perturb_ipins(nodes_per_chan, num_types, Fc_in,
Fc_out, directionality);
/* END FC */
/* Alloc node lookups, count nodes, alloc rr nodes */
num_rr_nodes = 0;
rr_node_indices =
alloc_and_load_rr_node_indices(nodes_per_chan, nx, ny, &num_rr_nodes,
seg_details);
rr_node = (t_rr_node *) my_malloc(sizeof(t_rr_node) * num_rr_nodes);
memset(rr_node, 0, sizeof(t_rr_node) * num_rr_nodes);
rr_edge_done = (boolean *) my_malloc(sizeof(boolean) * num_rr_nodes);
memset(rr_edge_done, 0, sizeof(boolean) * num_rr_nodes);
/* These are data structures used by the the unidir opin mapping. */
if(UNI_DIRECTIONAL == directionality)
{
Fc_xofs = (int **)alloc_matrix(0, ny, 0, nx, sizeof(int));
Fc_yofs = (int **)alloc_matrix(0, nx, 0, ny, sizeof(int));
for(i = 0; i <= nx; ++i)
{
for(j = 0; j <= ny; ++j)
{
Fc_xofs[j][i] = 0;
Fc_yofs[i][j] = 0;
}
}
}
/* START SB LOOKUP */
/* Alloc and load the switch block lookup */
if(is_global_graph)
{
assert(nodes_per_chan == 1);
switch_block_conn =
alloc_and_load_switch_block_conn(1, SUBSET, 3);
}
else if(BI_DIRECTIONAL == directionality)
{
switch_block_conn =
alloc_and_load_switch_block_conn(nodes_per_chan, sb_type, Fs);
}
else
{
assert(UNI_DIRECTIONAL == directionality);
unidir_sb_pattern =
alloc_sblock_pattern_lookup(nx, ny, nodes_per_chan);
for(i = 0; i <= nx; i++)
{
for(j = 0; j <= ny; j++)
{
load_sblock_pattern_lookup(i, j, nodes_per_chan,
seg_details, Fs,
sb_type,
unidir_sb_pattern);
}
}
}
/* END SB LOOKUP */
/* START IPINP MAP */
/* Create ipin map lookups */
ipin_to_track_map = (int *****)my_malloc(sizeof(int ****) * num_types);
track_to_ipin_lookup =
(struct s_ivec ****)my_malloc(sizeof(struct s_ivec ***) * num_types);
for(i = 0; i < num_types; ++i)
{
ipin_to_track_map[i] = alloc_and_load_pin_to_track_map(RECEIVER,
nodes_per_chan,
Fc_in[i],
&types[i],
perturb_ipins
[i],
directionality);
track_to_ipin_lookup[i] =
alloc_and_load_track_to_pin_lookup(ipin_to_track_map[i],
Fc_in[i], types[i].height,
types[i].num_pins,
nodes_per_chan);
}
/* END IPINP MAP */
/* START OPINP MAP */
/* Create opin map lookups */
if(BI_DIRECTIONAL == directionality)
{
opin_to_track_map =
(int *****)my_malloc(sizeof(int ****) * num_types);
for(i = 0; i < num_types; ++i)
{
opin_to_track_map[i] =
alloc_and_load_pin_to_track_map(DRIVER,
nodes_per_chan,
Fc_out[i], &types[i],
FALSE,
directionality);
}
}
/* END OPINP MAP */
/* UDSD Modifications by WMF begin */
/* I'm adding 2 new fields to t_rr_node, and I want them initialized to 0. */
for(i = 0; i < num_rr_nodes; i++)
{
rr_node[i].num_wire_drivers = 0;
rr_node[i].num_opin_drivers = 0;
}
alloc_and_load_rr_graph(num_rr_nodes, rr_node, num_seg_types,
seg_details, rr_edge_done,
track_to_ipin_lookup, opin_to_track_map,
switch_block_conn, grid, nx,
ny, Fs, unidir_sb_pattern, Fc_out, Fc_xofs,
Fc_yofs, rr_node_indices, nodes_per_chan,
sb_type, delayless_switch, directionality,
wire_to_ipin_switch, &Fc_clipped);
#ifdef MUX_SIZE_DIST_DISPLAY
if(UNI_DIRECTIONAL == directionality)
{
view_mux_size_distribution(rr_node_indices, nodes_per_chan,
seg_details, seg_details);
}
#endif
/* Update rr_nodes capacities if global routing */
if(graph_type == GLOBAL) {
for(i = 0; i < num_rr_nodes; i++) {
if(rr_node[i].type == CHANX || rr_node[i].type == CHANY) {
rr_node[i].capacity = chan_width;
}
}
}
rr_graph_externals(timing_inf, segment_inf, num_seg_types,
nodes_per_chan, wire_to_ipin_switch, base_cost_type);
#ifdef CREATE_ECHO_FILES
dump_rr_graph("rr_graph.echo");
#endif /* CREATE_ECHO_FILES */
check_rr_graph(graph_type, num_types, types, nx, ny,
grid, nodes_per_chan, Fs, num_seg_types, num_switches, segment_inf,
global_route_switch, delayless_switch,
wire_to_ipin_switch, seg_details, Fc_in, Fc_out,
rr_node_indices, opin_to_track_map, ipin_to_track_map,
track_to_ipin_lookup, switch_block_conn, perturb_ipins);
/* Free all temp structs */
if(seg_details)
{
free_seg_details(seg_details, nodes_per_chan);
seg_details = NULL;
}
if(Fc_in)
{
free(Fc_in);
Fc_in = NULL;
}
if(Fc_out)
{
free(Fc_out);
Fc_out = NULL;
}
if(perturb_ipins)
{
free(perturb_ipins);
perturb_ipins = NULL;
}
if(switch_block_conn)
{
free_switch_block_conn(switch_block_conn, nodes_per_chan);
switch_block_conn = NULL;
}
if(rr_edge_done)
{
free(rr_edge_done);
rr_edge_done = NULL;
}
if(Fc_xofs)
{
free_matrix(Fc_xofs, 0, ny, 0, sizeof(int));
Fc_xofs = NULL;
}
if(Fc_yofs)
{
free_matrix(Fc_yofs, 0, nx, 0, sizeof(int));
Fc_yofs = NULL;
}
if(unidir_sb_pattern)
{
free_sblock_pattern_lookup(unidir_sb_pattern);
unidir_sb_pattern = NULL;
}
if(opin_to_track_map) {
for(i = 0; i < num_types; ++i)
{
free_matrix4(opin_to_track_map[i], 0, types[i].num_pins - 1,
0, types[i].height - 1, 0, 3, 0, sizeof(int));
}
free(opin_to_track_map);
}
free_type_pin_to_track_map(ipin_to_track_map, types, Fc_in);
free_type_track_to_ipin_map(track_to_ipin_lookup, types, nodes_per_chan);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void dump_rr_graph | ( | INP const char * | file_name | ) |
A utility routine to dump the contents of the routing resource graph (everything -- connectivity, occupancy, cost, etc.) into a file. Used only for debugging.
Definition at line 2229 of file rr_graph.c.
{
int inode;
FILE *fp;
fp = my_fopen(file_name, "w", 0);
for(inode = 0; inode < num_rr_nodes; inode++)
{
print_rr_node(fp, rr_node, inode);
fprintf(fp, "\n");
}
#if 0
fprintf(fp, "\n\n%d rr_indexed_data entries.\n\n", num_rr_indexed_data);
for(index = 0; index < num_rr_indexed_data; index++)
{
print_rr_indexed_data(fp, index);
fprintf(fp, "\n");
}
#endif
fclose(fp);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void free_rr_graph | ( | void | ) |
Frees all the routing graph data structures, if they have been allocated. I use rr_mem_chunk_list_head as a flag to indicate whether or not the graph has been allocated -- if it is not NULL, a routing graph exists and can be freed. Hence, you can call this routine even if you're not sure of whether a rr_graph exists or not.
Definition at line 1026 of file rr_graph.c.
{
int i;
if(rr_mem_chunk_list_head == NULL) /* Nothing to free. */
return;
free_chunk_memory(rr_mem_chunk_list_head); /* Frees ALL "chunked" data */
rr_mem_chunk_list_head = NULL; /* No chunks allocated now. */
chunk_bytes_avail = 0; /* 0 bytes left in current "chunk". */
chunk_next_avail_mem = NULL; /* No current chunk. */
/* Before adding any more free calls here, be sure the data is NOT chunk *
* allocated, as ALL the chunk allocated data is already free! */
free(net_rr_terminals);
for(i = 0; i < num_rr_nodes; i++) {
if(rr_node[i].edges != NULL) {
free(rr_node[i].edges);
}
if(rr_node[i].switches != NULL) {
free(rr_node[i].switches);
}
}
assert(rr_node_indices);
free_rr_node_indices(rr_node_indices);
free(rr_node);
free(rr_indexed_data);
for(i = 0; i < num_blocks; i++)
{
free(rr_blk_source[i]);
}
free(rr_blk_source);
rr_blk_source = NULL;
net_rr_terminals = NULL;
rr_node = NULL;
rr_node_indices = NULL;
rr_indexed_data = NULL;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void load_net_rr_terminals | ( | t_ivec *** | rr_node_indices | ) |
Allocates and loads the net_rr_terminals data structure. For each net it stores the rr_node index of the SOURCE of the net and all the SINKs of the net. [0..num_nets-1][0..num_pins-1]. Entry [inet][pnum] stores the rr index corresponding to the SOURCE (opin) or SINK (ipin) of pnum.
Definition at line 1092 of file rr_graph.c.
{
int inet, ipin, inode, iblk, i, j, k, node_block_pin, iclass;
t_type_ptr type;
for(inet = 0; inet < num_nets; inet++)
{
for(ipin = 0; ipin <= clb_net[inet].num_sinks; ipin++)
{
iblk = clb_net[inet].node_block[ipin];
i = block[iblk].x;
j = block[iblk].y;
k = block[iblk].z;
type = block[iblk].type;
/* In the routing graph, each (x, y) location has unique pins on it
* so when there is capacity, blocks are packed and their pin numbers
* are offset to get their actual rr_node */
node_block_pin = clb_net[inet].node_block_pin[ipin];
iclass = type->pin_class[node_block_pin];
inode = get_rr_node_index(i, j, (ipin == 0 ? SOURCE : SINK), /* First pin is driver */
iclass, rr_node_indices);
net_rr_terminals[inet][ipin] = inode;
}
}
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void print_rr_indexed_data | ( | FILE * | fp, |
| int | index | ||
| ) |
For debugging only
Prints all the rr_indexed_data of index to file fp.
Definition at line 2326 of file rr_graph.c.
{
fprintf(fp, "Index: %d\n", index);
fprintf(fp, "ortho_cost_index: %d ",
rr_indexed_data[index].ortho_cost_index);
fprintf(fp, "base_cost: %g ", rr_indexed_data[index].saved_base_cost);
fprintf(fp, "saved_base_cost: %g\n",
rr_indexed_data[index].saved_base_cost);
fprintf(fp, "Seg_index: %d ", rr_indexed_data[index].seg_index);
fprintf(fp, "inv_length: %g\n", rr_indexed_data[index].inv_length);
fprintf(fp, "T_linear: %g ", rr_indexed_data[index].T_linear);
fprintf(fp, "T_quadratic: %g ", rr_indexed_data[index].T_quadratic);
fprintf(fp, "C_load: %g\n", rr_indexed_data[index].C_load);
}
Here is the caller graph for this function:
| void print_rr_node | ( | FILE * | fp, |
| t_rr_node * | rr_node, | ||
| int | inode | ||
| ) |
Prints all the data about node inode to file fp.
Definition at line 2259 of file rr_graph.c.
{
static const char *name_type[] = {
"SOURCE", "SINK", "IPIN", "OPIN", "CHANX", "CHANY", "INTRA_CLUSTER_EDGE"
};
static const char *direction_name[] = {
"OPEN", "INC_DIRECTION", "DEC_DIRECTION", "BI_DIRECTION"
};
static const char *drivers_name[] = {
"OPEN", "MULTI_BUFFER", "SINGLE"
};
t_rr_type rr_type;
int iconn;
rr_type = rr_node[inode].type;
/* Make sure we don't overrun const arrays */
assert(rr_type < (sizeof(name_type) / sizeof(char *)));
assert((rr_node[inode].direction + 1) <
(sizeof(direction_name) / sizeof(char *)));
assert((rr_node[inode].drivers + 1) <
(sizeof(drivers_name) / sizeof(char *)));
fprintf(fp, "Node: %d %s ", inode, name_type[rr_type]);
if((rr_node[inode].xlow == rr_node[inode].xhigh) &&
(rr_node[inode].ylow == rr_node[inode].yhigh))
{
fprintf(fp, "(%d, %d) ", rr_node[inode].xlow,
rr_node[inode].ylow);
}
else
{
fprintf(fp, "(%d, %d) to (%d, %d) ", rr_node[inode].xlow,
rr_node[inode].ylow, rr_node[inode].xhigh,
rr_node[inode].yhigh);
}
fprintf(fp, "Ptc_num: %d ", rr_node[inode].ptc_num);
fprintf(fp, "Direction: %s ",
direction_name[rr_node[inode].direction + 1]);
fprintf(fp, "Drivers: %s ", drivers_name[rr_node[inode].drivers + 1]);
fprintf(fp, "\n");
fprintf(fp, "%d edge(s):", rr_node[inode].num_edges);
for(iconn = 0; iconn < rr_node[inode].num_edges; iconn++)
fprintf(fp, " %d", rr_node[inode].edges[iconn]);
fprintf(fp, "\n");
fprintf(fp, "Switch types:");
for(iconn = 0; iconn < rr_node[inode].num_edges; iconn++)
fprintf(fp, " %d", rr_node[inode].switches[iconn]);
fprintf(fp, "\n");
fprintf(fp, "Occ: %d Capacity: %d\n", rr_node[inode].occ,
rr_node[inode].capacity);
if(rr_type != INTRA_CLUSTER_EDGE) {
fprintf(fp, "R: %g C: %g\n", rr_node[inode].R, rr_node[inode].C);
}
fprintf(fp, "Cost_index: %d\n", rr_node[inode].cost_index);
}
Here is the caller graph for this function:
