VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
rr_graph_indexed_data.c
Go to the documentation of this file.
1 #include <math.h> /* Needed only for sqrt call (remove if sqrt removed) */
2 #include "util.h"
3 #include "vpr_types.h"
4 #include "globals.h"
5 #include "rr_graph_util.h"
6 #include "rr_graph2.h"
8 #include "read_xml_arch_file.h"
9 
10 /******************* Subroutines local to this module ************************/
11 
12 static void load_rr_indexed_data_base_costs(int nodes_per_chan,
13  t_ivec *** L_rr_node_indices, enum e_base_cost_type base_cost_type,
14  int wire_to_ipin_switch);
15 
16 static float get_delay_normalization_fac(int nodes_per_chan,
17  t_ivec *** L_rr_node_indices);
18 
19 static float get_average_opin_delay(t_ivec *** L_rr_node_indices,
20  int nodes_per_chan);
21 
22 static void load_rr_indexed_data_T_values(int index_start,
23  int num_indices_to_load, t_rr_type rr_type, int nodes_per_chan,
24  t_ivec *** L_rr_node_indices, t_segment_inf * segment_inf);
25 
26 /******************** Subroutine definitions *********************************/
27 
28 /* Allocates the rr_indexed_data array and loads it with appropriate values. *
29  * It currently stores the segment type (or OPEN if the index doesn't *
30  * correspond to an CHANX or CHANY type), the base cost of nodes of that *
31  * type, and some info to allow rapid estimates of time to get to a target *
32  * to be computed by the router. *
33  *
34  * Right now all SOURCES have the same base cost; and similarly there's only *
35  * one base cost for each of SINKs, OPINs, and IPINs (four total). This can *
36  * be changed just by allocating more space in the array below and changing *
37  * the cost_index values for these rr_nodes, if you want to make some pins *
38  * etc. more expensive than others. I give each segment type in an *
39  * x-channel its own cost_index, and each segment type in a y-channel its *
40  * own cost_index. */
42  INP int num_segment, INP t_ivec *** L_rr_node_indices,
43  INP int nodes_per_chan, int wire_to_ipin_switch,
44  enum e_base_cost_type base_cost_type) {
45 
46  int iseg, length, i, index;
47 
48  num_rr_indexed_data = CHANX_COST_INDEX_START + (2 * num_segment);
51 
52  /* For rr_types that aren't CHANX or CHANY, base_cost is valid, but most *
53  * * other fields are invalid. For IPINs, the T_linear field is also valid; *
54  * * all other fields are invalid. For SOURCES, SINKs and OPINs, all fields *
55  * * other than base_cost are invalid. Mark invalid fields as OPEN for safety. */
56 
57  for (i = SOURCE_COST_INDEX; i <= IPIN_COST_INDEX; i++) {
58  rr_indexed_data[i].ortho_cost_index = OPEN;
59  rr_indexed_data[i].seg_index = OPEN;
60  rr_indexed_data[i].inv_length = OPEN;
61  rr_indexed_data[i].T_linear = OPEN;
62  rr_indexed_data[i].T_quadratic = OPEN;
63  rr_indexed_data[i].C_load = OPEN;
64  }
65 
66  rr_indexed_data[IPIN_COST_INDEX].T_linear =
67  switch_inf[wire_to_ipin_switch].Tdel;
68 
69  /* X-directed segments. */
70 
71  for (iseg = 0; iseg < num_segment; iseg++) {
72  index = CHANX_COST_INDEX_START + iseg;
73 
74  rr_indexed_data[index].ortho_cost_index = index + num_segment;
75 
76  if (segment_inf[iseg].longline)
77  length = nx;
78  else
79  length = std::min(segment_inf[iseg].length, nx);
80 
81  rr_indexed_data[index].inv_length = 1. / length;
82  rr_indexed_data[index].seg_index = iseg;
83  }
84 
86  nodes_per_chan, L_rr_node_indices, segment_inf);
87 
88  /* Y-directed segments. */
89 
90  for (iseg = 0; iseg < num_segment; iseg++) {
91  index = CHANX_COST_INDEX_START + num_segment + iseg;
92 
93  rr_indexed_data[index].ortho_cost_index = index - num_segment;
94 
95  if (segment_inf[iseg].longline)
96  length = ny;
97  else
98  length = std::min(segment_inf[iseg].length, ny);
99 
100  rr_indexed_data[index].inv_length = 1. / length;
101  rr_indexed_data[index].seg_index = iseg;
102  }
103 
105  num_segment, CHANY, nodes_per_chan, L_rr_node_indices, segment_inf);
106 
107  load_rr_indexed_data_base_costs(nodes_per_chan, L_rr_node_indices,
108  base_cost_type, wire_to_ipin_switch);
109 
110 }
111 
112 static void load_rr_indexed_data_base_costs(int nodes_per_chan,
113  t_ivec *** L_rr_node_indices, enum e_base_cost_type base_cost_type,
114  int wire_to_ipin_switch) {
115 
116  /* Loads the base_cost member of rr_indexed_data according to the specified *
117  * base_cost_type. */
118 
119  float delay_normalization_fac;
120  int index;
121 
122  if (base_cost_type == DELAY_NORMALIZED) {
123  delay_normalization_fac = get_delay_normalization_fac(nodes_per_chan,
124  L_rr_node_indices);
125  } else {
126  delay_normalization_fac = 1.;
127  }
128 
129  if (base_cost_type == DEMAND_ONLY || base_cost_type == DELAY_NORMALIZED) {
130  rr_indexed_data[SOURCE_COST_INDEX].base_cost = delay_normalization_fac;
132  rr_indexed_data[OPIN_COST_INDEX].base_cost = delay_normalization_fac;
133 
134 #ifndef SPEC
136  * delay_normalization_fac;
137 #else /* Avoid roundoff for SPEC */
139  delay_normalization_fac;
140 #endif
141  }
142 
143  else if (base_cost_type == INTRINSIC_DELAY) {
147  L_rr_node_indices, nodes_per_chan);
149  switch_inf[wire_to_ipin_switch].Tdel;
150  }
151 
152  /* Load base costs for CHANX and CHANY segments */
153 
154  for (index = CHANX_COST_INDEX_START; index < num_rr_indexed_data; index++) {
155  if (base_cost_type == INTRINSIC_DELAY)
157  + rr_indexed_data[index].T_quadratic;
158  else
159  /* rr_indexed_data[index].base_cost = delay_normalization_fac /
160  rr_indexed_data[index].inv_length; */
161 
162  rr_indexed_data[index].base_cost = delay_normalization_fac;
163  /* rr_indexed_data[index].base_cost = delay_normalization_fac *
164  sqrt (1. / rr_indexed_data[index].inv_length); */
165  /* rr_indexed_data[index].base_cost = delay_normalization_fac *
166  (1. + 1. / rr_indexed_data[index].inv_length); */
167  }
168 
169  /* Save a copy of the base costs -- if dynamic costing is used by the *
170  * router, the base_cost values will get changed all the time and being *
171  * able to restore them from a saved version is useful. */
172 
173  for (index = 0; index < num_rr_indexed_data; index++) {
175  rr_indexed_data[index].base_cost;
176  }
177 }
178 
179 static float get_delay_normalization_fac(int nodes_per_chan,
180  t_ivec *** L_rr_node_indices) {
181 
182  /* Returns the average delay to go 1 CLB distance along a wire. */
183 
184  const int clb_dist = 3; /* Number of CLBs I think the average conn. goes. */
185 
186  int inode, itrack, cost_index;
187  float Tdel, Tdel_sum, frac_num_seg;
188 
189  Tdel_sum = 0.;
190 
191  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
192  inode = get_rr_node_index((nx + 1) / 2, (ny + 1) / 2, CHANX, itrack,
193  L_rr_node_indices);
194  cost_index = rr_node[inode].cost_index;
195  frac_num_seg = clb_dist * rr_indexed_data[cost_index].inv_length;
196  Tdel = frac_num_seg * rr_indexed_data[cost_index].T_linear
197  + frac_num_seg * frac_num_seg
198  * rr_indexed_data[cost_index].T_quadratic;
199  Tdel_sum += Tdel / (float) clb_dist;
200  }
201 
202  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
203  inode = get_rr_node_index((nx + 1) / 2, (ny + 1) / 2, CHANY, itrack,
204  L_rr_node_indices);
205  cost_index = rr_node[inode].cost_index;
206  frac_num_seg = clb_dist * rr_indexed_data[cost_index].inv_length;
207  Tdel = frac_num_seg * rr_indexed_data[cost_index].T_linear
208  + frac_num_seg * frac_num_seg
209  * rr_indexed_data[cost_index].T_quadratic;
210  Tdel_sum += Tdel / (float) clb_dist;
211  }
212 
213  return (Tdel_sum / (2. * nodes_per_chan));
214 }
215 
216 static float get_average_opin_delay(t_ivec *** L_rr_node_indices,
217  int nodes_per_chan) {
218 
219  /* Returns the average delay from an OPIN to a wire in an adjacent channel. */
220  /* RESEARCH TODO: Got to think if this heuristic needs to change for hetero, right now, I'll calculate
221  * the average delay of non-IO blocks */
222  int inode, ipin, iclass, iedge, itype, num_edges, to_switch, to_node,
223  num_conn;
224  float Cload, Tdel;
225 
226  Tdel = 0.;
227  num_conn = 0;
228  for (itype = 0; itype < num_types && &type_descriptors[itype] != IO_TYPE;
229  itype++) {
230  for (ipin = 0; ipin < type_descriptors[itype].num_pins; ipin++) {
231  iclass = type_descriptors[itype].pin_class[ipin];
232  if (type_descriptors[itype].class_inf[iclass].type == DRIVER) { /* OPIN */
233  inode = get_rr_node_index((nx + 1) / 2, (ny + 1) / 2, OPIN,
234  ipin, L_rr_node_indices);
235  num_edges = rr_node[inode].num_edges;
236 
237  for (iedge = 0; iedge < num_edges; iedge++) {
238  to_node = rr_node[inode].edges[iedge];
239  to_switch = rr_node[inode].switches[iedge];
240  Cload = rr_node[to_node].C;
241  Tdel += Cload * switch_inf[to_switch].R
242  + switch_inf[to_switch].Tdel;
243  num_conn++;
244  }
245  }
246  }
247  }
248 
249  Tdel /= (float) num_conn;
250  return (Tdel);
251 }
252 
253 static void load_rr_indexed_data_T_values(int index_start,
254  int num_indices_to_load, t_rr_type rr_type, int nodes_per_chan,
255  t_ivec *** L_rr_node_indices, t_segment_inf * segment_inf) {
256 
257  /* Loads the average propagation times through segments of each index type *
258  * for either all CHANX segment types or all CHANY segment types. It does *
259  * this by looking at all the segments in one channel in the middle of the *
260  * array and averaging the R and C values of all segments of the same type *
261  * and using them to compute average delay values for this type of segment. */
262 
263  int itrack, iseg, inode, cost_index, iswitch;
264  float *C_total, *R_total; /* [0..num_rr_indexed_data - 1] */
265  int *num_nodes_of_index; /* [0..num_rr_indexed_data - 1] */
266  float Rnode, Cnode, Rsw, Tsw;
267 
268  num_nodes_of_index = (int *) my_calloc(num_rr_indexed_data, sizeof(int));
269  C_total = (float *) my_calloc(num_rr_indexed_data, sizeof(float));
270  R_total = (float *) my_calloc(num_rr_indexed_data, sizeof(float));
271 
272  /* Get average C and R values for all the segments of this type in one *
273  * channel segment, near the middle of the array. */
274 
275  for (itrack = 0; itrack < nodes_per_chan; itrack++) {
276  inode = get_rr_node_index((nx + 1) / 2, (ny + 1) / 2, rr_type, itrack,
277  L_rr_node_indices);
278  cost_index = rr_node[inode].cost_index;
279  num_nodes_of_index[cost_index]++;
280  C_total[cost_index] += rr_node[inode].C;
281  R_total[cost_index] += rr_node[inode].R;
282  }
283 
284  for (cost_index = index_start;
285  cost_index < index_start + num_indices_to_load; cost_index++) {
286 
287  if (num_nodes_of_index[cost_index] == 0) { /* Segments don't exist. */
288  rr_indexed_data[cost_index].T_linear = OPEN;
289  rr_indexed_data[cost_index].T_quadratic = OPEN;
290  rr_indexed_data[cost_index].C_load = OPEN;
291  } else {
292  Rnode = R_total[cost_index] / num_nodes_of_index[cost_index];
293  Cnode = C_total[cost_index] / num_nodes_of_index[cost_index];
294  iseg = rr_indexed_data[cost_index].seg_index;
295  iswitch = segment_inf[iseg].wire_switch;
296  Rsw = switch_inf[iswitch].R;
297  Tsw = switch_inf[iswitch].Tdel;
298 
299  if (switch_inf[iswitch].buffered) {
300  rr_indexed_data[cost_index].T_linear = Tsw + Rsw * Cnode
301  + 0.5 * Rnode * Cnode;
302  rr_indexed_data[cost_index].T_quadratic = 0.;
303  rr_indexed_data[cost_index].C_load = 0.;
304  } else { /* Pass transistor */
305  rr_indexed_data[cost_index].C_load = Cnode;
306 
307  /* See Dec. 23, 1997 notes for deriviation of formulae. */
308 
309  rr_indexed_data[cost_index].T_linear = Tsw + 0.5 * Rsw * Cnode;
310  rr_indexed_data[cost_index].T_quadratic = (Rsw + Rnode) * 0.5
311  * Cnode;
312  }
313  }
314  }
315 
316  free(num_nodes_of_index);
317  free(C_total);
318  free(R_total);
319 }
short num_edges
Definition: vpr_types.h:901
float R
Definition: vpr_types.h:906
short cost_index
Definition: vpr_types.h:897
int * edges
Definition: vpr_types.h:903
t_rr_node * rr_node
Definition: globals.c:70
t_rr_indexed_data * rr_indexed_data
Definition: globals.c:74
float C
Definition: vpr_types.h:907
int num_rr_indexed_data
Definition: globals.c:73
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
int get_rr_node_index(int x, int y, t_rr_type rr_type, int ptc, t_ivec ***L_rr_node_indices)
Definition: rr_graph2.c:846
#define min(a, b)
Definition: graphics.c:174
static void * my_malloc(int ibytes)
Definition: graphics.c:499
static float get_delay_normalization_fac(int nodes_per_chan, t_ivec ***L_rr_node_indices)
#define INP
Definition: util.h:19
int nx
Definition: globals.c:46
void alloc_and_load_rr_indexed_data(INP t_segment_inf *segment_inf, INP int num_segment, INP t_ivec ***L_rr_node_indices, INP int nodes_per_chan, int wire_to_ipin_switch, enum e_base_cost_type base_cost_type)
struct s_switch_inf * switch_inf
Definition: globals.c:83
static void load_rr_indexed_data_base_costs(int nodes_per_chan, t_ivec ***L_rr_node_indices, enum e_base_cost_type base_cost_type, int wire_to_ipin_switch)
Definition: util.h:47
e_base_cost_type
Definition: vpr_types.h:688
float saved_base_cost
Definition: vpr_types.h:971
enum e_rr_type t_rr_type
int num_types
Definition: globals.c:37
short * switches
Definition: vpr_types.h:904
t_type_ptr IO_TYPE
Definition: globals.c:40
Definition: slre.c:50
struct s_type_descriptor * type_descriptors
Definition: globals.c:38
static float get_average_opin_delay(t_ivec ***L_rr_node_indices, int nodes_per_chan)
static void load_rr_indexed_data_T_values(int index_start, int num_indices_to_load, t_rr_type rr_type, int nodes_per_chan, t_ivec ***L_rr_node_indices, t_segment_inf *segment_inf)
int ny
Definition: globals.c:47