00001 /************ Defines and types shared by all route files ********************/ 00002 00003 struct s_heap 00004 { 00005 int index; 00006 float cost; 00007 union 00008 { 00009 int prev_node; 00010 struct s_heap *next; 00011 } 00012 u; 00013 int prev_edge; 00014 float backward_path_cost; 00015 float R_upstream; 00016 }; 00017 00018 /* Used by the heap as its fundamental data structure. * 00019 * index: Index (ID) of this routing resource node. * 00020 * cost: Cost up to and including this node. * 00021 * u.prev_node: Index (ID) of the predecessor to this node for * 00022 * use in traceback. NO_PREVIOUS if none. * 00023 * u.next: pointer to the next s_heap structure in the free * 00024 * linked list. Not used when on the heap. * 00025 * prev_edge: Index of the edge (between 0 and num_edges-1) used to * 00026 * connect the previous node to this one. NO_PREVIOUS if * 00027 * there is no previous node. * 00028 * backward_path_cost: Used only by the timing-driven router. The "known" * 00029 * cost of the path up to and including this node. * 00030 * In this case, the .cost member contains not only * 00031 * the known backward cost but also an expected cost * 00032 * to the target. * 00033 * R_upstream: Used only by the timing-driven router. Stores the upstream * 00034 * resistance to ground from this node, including the * 00035 * resistance of the node itself (rr_node[index].R). */ 00036 00037 00038 typedef struct 00039 { 00040 int prev_node; 00041 float pres_cost; 00042 float acc_cost; 00043 float path_cost; 00044 float backward_path_cost; 00045 short prev_edge; 00046 short target_flag; 00047 } 00048 t_rr_node_route_inf; 00049 00050 /* Extra information about each rr_node needed only during routing (i.e. * 00051 * during the maze expansion). * 00052 * * 00053 * prev_node: Index of the previous node used to reach this one; * 00054 * used to generate the traceback. If there is no * 00055 * predecessor, prev_node = NO_PREVIOUS. * 00056 * pres_cost: Present congestion cost term for this node. * 00057 * acc_cost: Accumulated cost term from previous Pathfinder iterations. * 00058 * path_cost: Total cost of the path up to and including this node + * 00059 * the expected cost to the target if the timing_driven router * 00060 * is being used. * 00061 * backward_path_cost: Total cost of the path up to and including this * 00062 * node. Not used by breadth-first router. * 00063 * prev_edge: Index of the edge (from 0 to num_edges-1) that was used * 00064 * to reach this node from the previous node. If there is * 00065 * no predecessor, prev_edge = NO_PREVIOUS. * 00066 * target_flag: Is this node a target (sink) for the current routing? * 00067 * Number of times this node must be reached to fully route. */ 00068 00069 00070 00071 /**************** Variables shared by all route_files ***********************/ 00072 00073 extern t_rr_node_route_inf *rr_node_route_inf; /* [0..num_rr_nodes-1] */ 00074 extern struct s_bb *route_bb; /* [0..num_nets-1] */ 00075 00076 /******* Subroutines in route_common used only by other router modules ******/ 00077 00078 void pathfinder_update_one_cost(struct s_trace *route_segment_start, 00079 int add_or_sub, 00080 float pres_fac); 00081 00082 void pathfinder_update_cost(float pres_fac, 00083 float acc_fac); 00084 00085 struct s_trace *update_traceback(struct s_heap *hptr, 00086 int inet); 00087 00088 void reset_path_costs(void); 00089 00090 float get_rr_cong_cost(int inode); 00091 00092 void mark_ends(int inet); 00093 00094 void node_to_heap(int inode, 00095 float cost, 00096 int prev_node, 00097 int prev_edge, 00098 float backward_path_cost, 00099 float R_upstream); 00100 00101 boolean is_empty_heap(void); 00102 00103 void free_traceback(int inet); 00104 00105 void add_to_mod_list(float *fptr); 00106 00107 struct s_heap *get_heap_head(void); 00108 00109 void empty_heap(void); 00110 00111 void free_heap_data(struct s_heap *hptr); 00112 00113 void invalidate_heap_entries(int sink_node, 00114 int ipin_node); 00115 00116 void init_route_structs(int bb_factor); 00117 00118 void free_rr_node_route_structs(void); 00119 00120 void alloc_and_load_rr_node_route_structs(void); 00121 00122 void free_trace_structs(void); 00123 00124 void reserve_locally_used_opins(float pres_fac, 00125 boolean rip_up_local_opins, 00126 t_ivec ** fb_opins_used_locally);
1.6.1