44 static int num_trace_allocated = 0;
45 static int num_heap_allocated = 0;
46 static int num_linked_f_pointer_allocated = 0;
101 t_ivec ** saved_clb_opins_used_locally) {
111 int inet, iblk, iclass, ipin, num_local_opins;
112 struct s_trace *tptr, *tempptr;
115 for (inet = 0; inet <
num_nets; inet++) {
118 tptr = best_routing[inet];
119 while (tptr != NULL) {
120 tempptr = tptr->
next;
139 for (iclass = 0; iclass < type->
num_class; iclass++) {
140 num_local_opins = clb_opins_used_locally[iblk][iclass].
nelem;
141 for (ipin = 0; ipin < num_local_opins; ipin++) {
142 saved_clb_opins_used_locally[iblk][iclass].
list[ipin] =
143 clb_opins_used_locally[iblk][iclass].
list[ipin];
151 t_ivec ** saved_clb_opins_used_locally) {
160 int inet, iblk, ipin, iclass, num_local_opins;
163 for (inet = 0; inet <
num_nets; inet++) {
170 best_routing[inet] = NULL;
177 for (iclass = 0; iclass < type->
num_class; iclass++) {
178 num_local_opins = clb_opins_used_locally[iblk][iclass].
nelem;
179 for (ipin = 0; ipin < num_local_opins; ipin++) {
180 clb_opins_used_locally[iblk][iclass].
list[ipin] =
181 saved_clb_opins_used_locally[iblk][iclass].
list[ipin];
194 int inet, serial_num, inode;
199 for (inet = 0; inet <
num_nets; inet++) {
205 while (tptr != NULL) {
207 serial_num += (inet + 1)
212 serial_num -=
rr_node[inode].
type * (inet + 1) * 100;
213 serial_num %= 2000000000;
217 vpr_printf(TIO_MESSAGE_INFO,
"Serial number (magic cookie) for the routing is: %d\n", serial_num);
224 boolean * Fc_clipped,
t_direct_inf *directs,
int num_directs) {
265 directs, num_directs,
FALSE,
269 #ifdef CLOCKS_PER_SEC
270 vpr_printf(TIO_MESSAGE_INFO,
"Build rr_graph took %g seconds.\n", (
float)(end - begin) / CLOCKS_PER_SEC);
272 vpr_printf(TIO_MESSAGE_INFO,
"Build rr_graph took %g seconds.\n", (
float)(end - begin) / CLK_PER_SEC);
283 vpr_printf(TIO_MESSAGE_INFO,
"Confirming Router Algorithm: BREADTH_FIRST.\n");
287 vpr_printf(TIO_MESSAGE_INFO,
"Confirming Router Algorithm: TIMING_DRIVEN.\n");
327 int inode, occ, capacity;
329 tptr = route_segment_start;
345 if (occ < capacity) {
349 + (occ + 1 - capacity) * pres_fac;
373 int inode, occ, capacity;
379 if (occ > capacity) {
380 rr_node_route_inf[inode].
acc_cost += (occ - capacity) * acc_fac;
382 + (occ + 1 - capacity) * pres_fac;
388 else if (occ == capacity) {
409 if (rr_modified_head != NULL) {
410 vpr_printf(TIO_MESSAGE_ERROR,
"in init_route_structs. List of modified rr nodes is not empty.\n");
415 vpr_printf(TIO_MESSAGE_ERROR,
"in init_route_structs. Heap is not empty.\n");
436 struct s_trace *tptr, *prevptr, *temptail, *ret_ptr;
448 if (rr_type !=
SINK) {
449 vpr_printf(TIO_MESSAGE_ERROR,
"in update_traceback. Expected type = SINK (%d).\n",
SINK);
450 vpr_printf(TIO_MESSAGE_ERROR,
"\tGot type = %d while tracing back net %d.\n", rr_type, inet);
469 prevptr->
index = inode;
471 prevptr->
next = tptr;
474 iedge = rr_node_route_inf[inode].
prev_edge;
475 inode = rr_node_route_inf[inode].
prev_node;
480 ret_ptr = tptr->
next;
503 if (rr_modified_head != NULL) {
510 while (mod_ptr->
next != NULL) {
512 mod_ptr = mod_ptr->
next;
524 rr_modified_head = NULL;
527 num_linked_f_pointer_allocated -= num_mod_ptrs;
563 float backward_path_cost,
float R_upstream) {
574 if (cost >= rr_node_route_inf[inode].path_cost)
592 struct s_trace *tptr, *tempptr;
600 while (tptr != NULL) {
601 tempptr = tptr->
next;
620 return (clb_opins_used_locally);
639 t_ivec *** saved_clb_opins_used_locally_ptr) {
646 t_ivec **saved_clb_opins_used_locally;
647 int iblk, iclass, num_local_opins;
660 for (iclass = 0; iclass < type->
num_class; iclass++) {
661 num_local_opins = clb_opins_used_locally[iblk][iclass].
nelem;
662 saved_clb_opins_used_locally[iblk][iclass].
nelem = num_local_opins;
664 if (num_local_opins == 0) {
665 saved_clb_opins_used_locally[iblk][iclass].
list = NULL;
667 saved_clb_opins_used_locally[iblk][iclass].
list =
668 (
int *)
my_malloc(num_local_opins *
sizeof(
int));
673 *saved_clb_opins_used_locally_ptr = saved_clb_opins_used_locally;
674 return (best_routing);
686 int iblk, clb_pin, iclass, num_local_opins;
687 int class_low, class_high;
698 for (iclass = 0; iclass < type->
num_class; iclass++)
699 clb_opins_used_locally[iblk][iclass].nelem = 0;
701 for (clb_pin = 0; clb_pin < type->
num_pins; clb_pin++) {
713 assert(iclass >= class_low && iclass <= class_high);
714 clb_opins_used_locally[iblk][iclass].
nelem++;
719 for (iclass = 0; iclass < type->
num_class; iclass++) {
720 num_local_opins = clb_opins_used_locally[iblk][iclass].
nelem;
722 if (num_local_opins == 0)
723 clb_opins_used_locally[iblk][iclass].
list = NULL;
725 clb_opins_used_locally[iblk][iclass].
list = (
int *)
my_malloc(
726 num_local_opins *
sizeof(
int));
730 return (clb_opins_used_locally);
757 if(route_bb != NULL) {
767 heap_free_head = NULL;
768 linked_f_pointer_free_head = NULL;
772 t_ivec ** saved_clb_opins_used_locally) {
780 block[i].type->num_class - 1);
782 free(saved_clb_opins_used_locally);
792 if (rr_node_route_inf != NULL) {
793 vpr_printf(TIO_MESSAGE_ERROR,
"in alloc_and_load_rr_node_route_structs: old rr_node_route_inf array exists.\n");
803 rr_node_route_inf[inode].
acc_cost = 1.;
816 assert(rr_node_route_inf != NULL);
822 rr_node_route_inf[inode].
acc_cost = 1.;
833 free(rr_node_route_inf);
834 rr_node_route_inf = NULL;
851 int k, xmax, ymax, xmin, ymin, x, y, inet;
853 for (inet = 0; inet <
num_nets; inet++) {
872 }
else if (x > xmax) {
878 }
else if (y > ymax) {
912 rr_modified_head = mod_ptr;
934 while ((ito >= 1) && (heap[ifrom]->
cost < heap[ito]->
cost)) {
935 temp_ptr = heap[ito];
936 heap[ito] = heap[ifrom];
937 heap[ifrom] = temp_ptr;
956 struct s_heap *heap_head, *temp_ptr;
960 vpr_printf(TIO_MESSAGE_WARNING,
"Empty heap occurred in get_heap_head.\n");
961 vpr_printf(TIO_MESSAGE_WARNING,
"Some blocks are impossible to connect in this architecture.\n");
975 if (heap[ito + 1]->
cost < heap[ito]->
cost)
977 if (heap[ito]->
cost > heap[ifrom]->
cost)
979 temp_ptr = heap[ito];
980 heap[ito] = heap[ifrom];
981 heap[ifrom] = temp_ptr;
1006 if (heap_free_head == NULL) {
1008 heap_free_head->
u.
next = NULL;
1012 heap_free_head = heap_free_head->
u.
next;
1014 num_heap_allocated++;
1022 heap_free_head = hptr;
1024 num_heap_allocated--;
1037 if (heap[i]->
index == sink_node && heap[i]->
u.prev_node == ipin_node)
1047 if (trace_free_head == NULL) {
1049 trace_free_head->
next = NULL;
1052 trace_free_head = trace_free_head->
next;
1054 num_trace_allocated++;
1064 trace_free_head = tptr;
1066 num_trace_allocated--;
1079 if (linked_f_pointer_free_head == NULL) {
1082 linked_f_pointer_free_head->
next = NULL;
1086 linked_f_pointer_free_head = linked_f_pointer_free_head->
next;
1089 num_linked_f_pointer_allocated++;
1099 int inet, inode, ipin, bnum, ilow, jlow, node_block_pin, iclass;
1102 const char *
name_type[] = {
"SOURCE",
"SINK",
"IPIN",
"OPIN",
"CHANX",
"CHANY",
1103 "INTRA_CLUSTER_EDGE" };
1106 fp = fopen(route_file,
"w");
1108 fprintf(fp,
"Array size: %d x %d logic blocks.\n",
nx,
ny);
1109 fprintf(fp,
"\nRouting:");
1110 for (inet = 0; inet <
num_nets; inet++) {
1113 fprintf(fp,
"\n\nNet %d (%s)\n\n", inet,
clb_net[inet].name);
1114 fprintf(fp,
"\n\nUsed in local cluster only, reserved one CLB pin\n\n");
1116 fprintf(fp,
"\n\nNet %d (%s)\n\n", inet,
clb_net[inet].name);
1119 while (tptr != NULL) {
1120 inode = tptr->
index;
1125 fprintf(fp,
"Node:\t%d\t%6s (%d,%d) ", inode, name_type[rr_type], ilow, jlow);
1127 if ((ilow !=
rr_node[inode].xhigh)
1128 || (jlow !=
rr_node[inode].yhigh))
1129 fprintf(fp,
"to (%d,%d) ",
rr_node[inode].xhigh,
1137 fprintf(fp,
" Pad: ");
1139 fprintf(fp,
" Pin: ");
1145 fprintf(fp,
" Track: ");
1151 fprintf(fp,
" Pad: ");
1153 fprintf(fp,
" Class: ");
1158 vpr_printf(TIO_MESSAGE_ERROR,
"in print_route: Unexpected traceback element type: %d (%s).\n",
1159 rr_type, name_type[rr_type]);
1164 fprintf(fp,
"%d ",
rr_node[inode].ptc_num);
1178 fprintf(fp,
"\n\nNet %d (%s): global net connecting:\n\n", inet,
1187 fprintf(fp,
"Block %s (#%d) at (%d, %d), Pin class %d.\n",
1198 fprintf(fp,
"\nNum_heap_allocated: %d Num_trace_allocated: %d\n",
1199 num_heap_allocated, num_trace_allocated);
1200 fprintf(fp,
"Num_linked_f_pointer_allocated: %d\n",
1201 num_linked_f_pointer_allocated);
1217 int iblk, num_local_opin, inode, from_node, iconn, num_edges, to_node;
1220 struct s_heap *heap_head_ptr;
1223 if (rip_up_local_opins) {
1226 for (iclass = 0; iclass < type->
num_class; iclass++) {
1227 num_local_opin = clb_opins_used_locally[iblk][iclass].
nelem;
1229 for (ipin = 0; ipin < num_local_opin; ipin++) {
1230 inode = clb_opins_used_locally[iblk][iclass].
list[ipin];
1239 for (iclass = 0; iclass < type->
num_class; iclass++) {
1240 num_local_opin = clb_opins_used_locally[iblk][iclass].
nelem;
1243 if (num_local_opin != 0) {
1246 for (iconn = 0; iconn < num_edges; iconn++) {
1252 for (ipin = 0; ipin < num_local_opin; ipin++) {
1254 inode = heap_head_ptr->
index;
1256 clb_opins_used_locally[iblk][iclass].
list[ipin] = inode;
1278 if (occ < capacity) {
1279 rr_node_route_inf[inode].
pres_cost = 1.;
1282 + (occ + 1 - capacity) * pres_fac;
boolean feasible_routing(void)
static void load_route_bb(int bb_factor)
static void free_trace_data(struct s_trace *tptr)
float get_rr_cong_cost(int inode)
FILE * my_fopen(const char *fname, const char *flag, int prompt)
enum e_router_algorithm router_algorithm
struct s_trace ** trace_tail
struct s_heap * get_heap_head(void)
void free_traceback(int inet)
t_rr_node_route_inf * rr_node_route_inf
void get_class_range_for_block(INP int iblk, OUTP int *class_low, OUTP int *class_high)
struct s_class * class_inf
static struct s_linked_f_pointer * rr_modified_head
void save_routing(struct s_trace **best_routing, t_ivec **clb_opins_used_locally, t_ivec **saved_clb_opins_used_locally)
t_rr_indexed_data * rr_indexed_data
short global_route_switch
void invalidate_heap_entries(int sink_node, int ipin_node)
void free_heap_data(struct s_heap *hptr)
void free_chunk_memory_trace(void)
static float ** net_delay
enum e_graph_type t_graph_type
void * my_chunk_malloc(size_t size, t_chunk *chunk_info)
boolean try_route(int width_fac, struct s_router_opts router_opts, struct s_det_routing_arch det_routing_arch, t_segment_inf *segment_inf, t_timing_inf timing_inf, float **net_delay, t_slack *slacks, t_chan_width_dist chan_width_dist, t_ivec **clb_opins_used_locally, boolean *Fc_clipped, t_direct_inf *directs, int num_directs)
boolean timing_analysis_enabled
void free_saved_routing(struct s_trace **best_routing, t_ivec **saved_clb_opins_used_locally)
void * my_calloc(size_t nelem, size_t size)
void free_trace_structs(void)
void pathfinder_update_cost(float pres_fac, float acc_fac)
void get_serial_num(void)
static struct s_heap * alloc_heap_data(void)
static void add_to_heap(struct s_heap *hptr)
struct s_linked_vptr * chunk_ptr_head
boolean try_breadth_first_route(struct s_router_opts router_opts, t_ivec **clb_opins_used_locally, int width_fac)
static struct s_linked_f_pointer * alloc_linked_f_pointer(void)
boolean getEchoEnabled(void)
static const char * name_type[]
void reset_path_costs(void)
static struct s_heap ** heap
static t_ivec ** clb_opins_used_locally
#define HUGE_POSITIVE_FLOAT
static struct s_linked_f_pointer * linked_f_pointer_free_head
static void * my_malloc(int ibytes)
void alloc_and_load_rr_node_route_structs(void)
void init_route_structs(int bb_factor)
enum e_directionality directionality
void build_rr_graph(INP t_graph_type graph_type, INP int L_num_types, INP t_type_ptr types, INP int L_nx, INP int L_ny, INP struct s_grid_tile **L_grid, INP int chan_width, INP struct s_chan_width_dist *chan_capacity_inf, INP enum e_switch_block_type sb_type, INP int Fs, INP int num_seg_types, INP int num_switches, INP t_segment_inf *segment_inf, INP int global_route_switch, INP int delayless_switch, INP t_timing_inf timing_inf, INP int wire_to_ipin_switch, INP enum e_base_cost_type base_cost_type, INP t_direct_inf *directs, INP int num_directs, INP boolean ignore_Fc_0, OUTP int *Warnings)
void init_chan(int cfactor, t_chan_width_dist chan_width_dist)
void free_ivec_vector(struct s_ivec *ivec_vector, int nrmin, int nrmax)
t_ivec ** alloc_route_structs(void)
struct s_trace ** trace_head
void print_route(char *route_file)
boolean isEchoFileEnabled(enum e_echo_files echo_option)
void restore_routing(struct s_trace **best_routing, t_ivec **clb_opins_used_locally, t_ivec **saved_clb_opins_used_locally)
enum e_route_type route_type
void node_to_heap(int inode, float cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream)
struct s_grid_tile ** grid
boolean is_empty_heap(void)
void alloc_route_static_structs(void)
struct s_linked_f_pointer * next
static t_ivec ** alloc_and_load_clb_opins_used_locally(void)
static struct s_heap * heap_free_head
void pathfinder_update_one_cost(struct s_trace *route_segment_start, int add_or_sub, float pres_fac)
void reset_rr_node_route_structs(void)
struct s_trace * update_traceback(struct s_heap *hptr, int inet)
struct s_trace ** alloc_saved_routing(t_ivec **clb_opins_used_locally, t_ivec ***saved_clb_opins_used_locally_ptr)
enum e_switch_block_type switch_block_type
static void * my_realloc(void *memblk, int ibytes)
static void adjust_one_rr_occ_and_pcost(int inode, int add_or_sub, float pres_fac)
void add_to_mod_list(float *fptr)
static struct s_trace * alloc_trace_data(void)
void reserve_locally_used_opins(float pres_fac, boolean rip_up_local_opins, t_ivec **clb_opins_used_locally)
void free_rr_node_route_structs(void)
struct s_type_descriptor * type_descriptors
char * getEchoFileName(enum e_echo_files echo_option)
static t_chunk linked_f_pointer_ch
void free_chunk_memory(t_chunk *chunk_info)
void free_route_structs()
short wire_to_ipin_switch
boolean try_timing_driven_route(struct s_router_opts router_opts, float **net_delay, t_slack *slacks, t_ivec **clb_opins_used_locally, boolean timing_analysis_enabled)
enum e_base_cost_type base_cost_type
static struct s_trace * trace_free_head
static struct s_trace ** best_routing