Adding 'strong' look-ahead
diff --git a/vpr/SRC/route/route_timing.c b/vpr/SRC/route/route_timing.c
index a86b1c1..8004761 100755
--- a/vpr/SRC/route/route_timing.c
+++ b/vpr/SRC/route/route_timing.c
@@ -1,1306 +1,1509 @@
-#include <cstdio>
-#include <ctime>
-#include <cmath>
-#include <assert.h>
-#include <vector>
-#include <algorithm>
-#include "vpr_utils.h"
-#include "util.h"
-#include "vpr_types.h"
-#include "globals.h"
-#include "route_export.h"
-#include "route_common.h"
-#include "route_tree_timing.h"
-#include "route_timing.h"
-#include "heapsort.h"
-#include "path_delay.h"
-#include "net_delay.h"
-#include "stats.h"
-#include "ReadOptions.h"
-
-
-using namespace std;
-
-
-
-/******************** Subroutines local to route_timing.c ********************/
-
-static int get_max_pins_per_net(void);
-
-static void add_route_tree_to_heap(t_rt_node * rt_node, int target_node,
- float target_criticality, float astar_fac);
-
-static void timing_driven_expand_neighbours(struct s_heap *current,
- int inet, int itry,
- float bend_cost, float criticality_fac, int target_node,
- float astar_fac, int highfanout_rlim);
-
-static float get_timing_driven_expected_cost(int inode, int target_node,
- float criticality_fac, float R_upstream);
-#ifdef INTERPOSER_BASED_ARCHITECTURE
-static int get_num_expected_interposer_hops_to_target(int inode, int target_node);
-#endif
-
-static int get_expected_segs_to_target(int inode, int target_node,
- int *num_segs_ortho_dir_ptr);
-
-static void update_rr_base_costs(int inet, float largest_criticality);
-
-static void timing_driven_check_net_delays(float **net_delay);
-
-static int mark_node_expansion_by_bin(int inet, int target_node,
- t_rt_node * rt_node);
-
-static double get_overused_ratio();
-
-static bool should_route_net(int inet);
-static bool early_exit_heuristic(const t_router_opts& router_opts);
-struct more_sinks_than {
- inline bool operator() (const int& net_index1, const int& net_index2) {
- return g_clbs_nlist.net[net_index1].num_sinks() > g_clbs_nlist.net[net_index2].num_sinks();
- }
-};
-
-
-#ifdef PROFILE
-static void congestion_analysis();
-static void time_on_criticality_analysis();
-constexpr int fanout_per_bin = 4;
-constexpr float criticality_per_bin = 0.05;
-static vector<float> time_on_fanout;
-static vector<float> time_to_build_heap;
-static vector<int> itry_on_fanout;
-static vector<float> time_on_criticality;
-static vector<int> itry_on_criticality;
-#endif
-
-/************************ Subroutine definitions *****************************/
-bool try_timing_driven_route(struct s_router_opts router_opts,
- float **net_delay, t_slack * slacks, t_ivec ** clb_opins_used_locally,
- bool timing_analysis_enabled, const t_timing_inf &timing_inf) {
-
- /* Timing-driven routing algorithm. The timing graph (includes slack) *
- * must have already been allocated, and net_delay must have been allocated. *
- * Returns true if the routing succeeds, false otherwise. */
-#ifdef PROFILE
- const int max_fanout {get_max_pins_per_net()};
- time_on_fanout.resize((max_fanout / fanout_per_bin) + 1, 0);
- time_to_build_heap.resize((max_fanout / fanout_per_bin) + 1, 0);
- itry_on_fanout.resize((max_fanout / fanout_per_bin) + 1, 0);
- time_on_criticality.resize((1 / criticality_per_bin) + 1, 0);
- itry_on_criticality.resize((1 / criticality_per_bin) + 1, 0);
-#endif
-
- auto sorted_nets = vector<int>(g_clbs_nlist.net.size());
-
- for (size_t i = 0; i < g_clbs_nlist.net.size(); ++i) {
- sorted_nets[i] = i;
- }
-
- // sort so net with most sinks is first.
- std::sort(sorted_nets.begin(), sorted_nets.end(), more_sinks_than());
-
- timing_driven_route_structs route_structs{}; // allocs route strucs (calls default constructor)
- // contains:
- // float *pin_criticality; /* [1..max_pins_per_net-1] */
- // int *sink_order; /* [1..max_pins_per_net-1] */;
- // t_rt_node **rt_node_of_sink; /* [1..max_pins_per_net-1] */
-
- /* First do one routing iteration ignoring congestion to get reasonable net
- delay estimates. Set criticalities to 1 when timing analysis is on to
- optimize timing, and to 0 when timing analysis is off to optimize routability. */
-
- float init_timing_criticality_val = (timing_analysis_enabled ? 1.0 : 0.0);
-
- /* Variables used to do the optimization of the routing, aborting visibly
- * impossible Ws */
- double overused_ratio;
- vector<double> historical_overuse_ratio;
- historical_overuse_ratio.reserve(router_opts.max_router_iterations + 1);
-
- // for unroutable large circuits, the time per iteration seems to increase dramatically
- vector<float> time_per_iteration;
- time_per_iteration.reserve(router_opts.max_router_iterations + 1);
-
- for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
- if (g_clbs_nlist.net[inet].is_global == false) {
- for (unsigned int ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ++ipin) {
- slacks->timing_criticality[inet][ipin] = init_timing_criticality_val;
- }
-#ifdef PATH_COUNTING
- slacks->path_criticality[inet][ipin] = init_timing_criticality_val;
-#endif
- } else {
- /* Set delay of global signals to zero. Non-global net delays are set by
- update_net_delays_from_route_tree() inside timing_driven_route_net(),
- which is only called for non-global nets. */
- for (unsigned int ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ++ipin) {
- net_delay[inet][ipin] = 0.;
- }
- }
- }
-
- float pres_fac = router_opts.first_iter_pres_fac; /* Typically 0 -> ignore cong. */
-
- for (int itry = 1; itry <= router_opts.max_router_iterations; ++itry) {
- clock_t begin = clock();
-
- /* Reset "is_routed" and "is_fixed" flags to indicate nets not pre-routed (yet) */
- for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
- g_clbs_nlist.net[inet].is_routed = false;
- g_clbs_nlist.net[inet].is_fixed = false;
- }
-
- for (unsigned int i = 0; i < g_clbs_nlist.net.size(); ++i) {
- bool is_routable = try_timing_driven_route_net(
- sorted_nets[i],
- itry,
- pres_fac,
- router_opts,
- route_structs.pin_criticality,
- route_structs.sink_order,
- route_structs.rt_node_of_sink,
- net_delay,
- slacks
- );
-
- if (!is_routable) {
- return (false);
- }
- }
-
- clock_t end = clock();
- float time = static_cast<float>(end - begin) / CLOCKS_PER_SEC;
- time_per_iteration.push_back(time);
-
- if (itry == 1 && early_exit_heuristic(router_opts)) return false;
-
- /* Make sure any CLB OPINs used up by subblocks being hooked directly
- to them are reserved for that purpose. */
-
- bool rip_up_local_opins = (itry == 1 ? false : true);
- reserve_locally_used_opins(pres_fac, router_opts.acc_fac, rip_up_local_opins, clb_opins_used_locally);
-
- /* Pathfinder guys quit after finding a feasible route. I may want to keep
- going longer, trying to improve timing. Think about this some. */
-
- bool success = feasible_routing();
-
- /* Verification to check the ratio of overused nodes, depending on the configuration
- * may abort the routing if the ratio is too high. */
- overused_ratio = get_overused_ratio();
- historical_overuse_ratio.push_back(overused_ratio);
-
- /* Determine when routing is impossible hence should be aborted */
- if (itry > 5){
-
- int expected_success_route_iter = predict_success_route_iter(historical_overuse_ratio, router_opts);
- if (expected_success_route_iter == UNDEFINED) {
- return false;
- }
-
-#ifdef REGRESSION_EXIT
- if (itry > 15) {
- // compare their slopes over the last 5 iterations
- double time_per_iteration_slope = linear_regression_vector(time_per_iteration, itry-5);
- double congestion_per_iteration_slope = linear_regression_vector(historical_overuse_ratio, itry-5);
- if (router_opts.congestion_analysis)
- vpr_printf_info("%f s/iteration %f %/iteration\n", time_per_iteration_slope, congestion_per_iteration_slope);
- // time is increasing and congestion is non-decreasing (grows faster than 10% per iteration)
- if (congestion_per_iteration_slope > 0 && time_per_iteration_slope > 0.1*time_per_iteration.back()
- && time_per_iteration_slope > 1) { // filter out noise
- vpr_printf_info("Time per iteration growing too fast at slope %f s/iteration \n\
- while congestion grows at %f %/iteration, unlikely to finish.\n",
- time_per_iteration_slope, congestion_per_iteration_slope);
-
- return false;
- }
- }
-#endif
- }
-
- //print_usage_by_wire_length();
-
-
- if (success) {
-
- if (timing_analysis_enabled) {
- load_timing_graph_net_delays(net_delay);
- do_timing_analysis(slacks, timing_inf, false, false);
- float critical_path_delay = get_critical_path_delay();
- vpr_printf_info("%9d %6.2f sec %8.5f ns %3.2e (%3.4f %)\n", itry, time, critical_path_delay, overused_ratio*num_rr_nodes, overused_ratio*100);
- vpr_printf_info("Critical path: %g ns\n", critical_path_delay);
- } else {
- vpr_printf_info("%9d %6.2f sec N/A %3.2e (%3.4f %)\n", itry, time, overused_ratio*num_rr_nodes, overused_ratio*100);
- }
-
- vpr_printf_info("Successfully routed after %d routing iterations.\n", itry);
-#ifdef DEBUG
- if (timing_analysis_enabled)
- timing_driven_check_net_delays(net_delay);
-#endif
- return (true);
- }
-
- if (itry == 1) {
- pres_fac = router_opts.initial_pres_fac;
- pathfinder_update_cost(pres_fac, 0.); /* Acc_fac=0 for first iter. */
- } else {
- pres_fac *= router_opts.pres_fac_mult;
-
- /* Avoid overflow for high iteration counts, even if acc_cost is big */
- pres_fac = min(pres_fac, static_cast<float>(HUGE_POSITIVE_FLOAT / 1e5));
-
- pathfinder_update_cost(pres_fac, router_opts.acc_fac);
- }
-
- if (timing_analysis_enabled) {
- /* Update slack values by doing another timing analysis.
- Timing_driven_route_net updated the net delay values. */
-
- load_timing_graph_net_delays(net_delay);
-
- do_timing_analysis(slacks, timing_inf, false, false);
-
- } else {
- /* If timing analysis is not enabled, make sure that the criticalities and the
- net_delays stay as 0 so that wirelength can be optimized. */
-
- for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
- for (unsigned int ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ++ipin) {
- slacks->timing_criticality[inet][ipin] = 0.;
-#ifdef PATH_COUNTING
- slacks->path_criticality[inet][ipin] = 0.;
-#endif
- net_delay[inet][ipin] = 0.;
- }
- }
- }
-
-
- if (timing_analysis_enabled) {
- float critical_path_delay = get_critical_path_delay();
- vpr_printf_info("%9d %6.2f sec %8.5f ns %3.2e (%3.4f %)\n", itry, time, critical_path_delay, overused_ratio*num_rr_nodes, overused_ratio*100);
- } else {
- vpr_printf_info("%9d %6.2f sec N/A %3.2e (%3.4f %)\n", itry, time, overused_ratio*num_rr_nodes, overused_ratio*100);
- }
-
-#ifdef PROFILE
- if (router_opts.congestion_analysis) congestion_analysis();
- if (router_opts.fanout_analysis) time_on_fanout_analysis();
- time_on_criticality_analysis();
-#endif
- fflush(stdout);
- }
- vpr_printf_info("Routing failed.\n");
-
- return (false);
-}
-
-// profiling per iteration functions
-#ifdef PROFILE
-void time_on_fanout_analysis() {
- // using the global time_on_fanout and itry_on_fanout
- vpr_printf_info("fanout low time (s) attemps heap build time (s)\n");
- for (size_t bin = 0; bin < time_on_fanout.size(); ++bin) {
- if (itry_on_fanout[bin]) { // avoid printing the many 0 bins
- vpr_printf_info("%4d %14.3f %12d %14.3f\n",bin*fanout_per_bin, time_on_fanout[bin], itry_on_fanout[bin], time_to_build_heap[bin]);
- }
- }
-}
-
-void time_on_criticality_analysis() {
- vpr_printf_info("congestion low time (s) attemps\n");
- for (size_t bin = 0; bin < time_on_criticality.size(); ++bin) {
- if (itry_on_criticality[bin]) { // avoid printing the many 0 bins
- vpr_printf_info("%4d %14.3f %12d\n",bin*criticality_per_bin, time_on_criticality[bin], itry_on_criticality[bin]);
- }
- }
-}
-// at the end of a routing iteration, profile how much congestion is taken up by each type of rr_node
-// efficient bit array for checking against congested type
-struct Congested_node_types {
- uint32_t mask;
- Congested_node_types() : mask{0} {}
- void set_congested(int rr_node_type) {mask |= (1 << rr_node_type);}
- void clear_congested(int rr_node_type) {mask &= ~(1 << rr_node_type);}
- bool is_congested(int rr_node_type) const {return mask & (1 << rr_node_type);}
- bool empty() const {return mask == 0;}
-};
-
-void congestion_analysis() {
- static const std::vector<const char*> node_typename {
- "SOURCE",
- "SINK",
- "IPIN",
- "OPIN",
- "CHANX",
- "CHANY",
- "ICE"
- };
- // each type indexes into array which holds the congestion for that type
- std::vector<int> congestion_per_type((size_t) NUM_RR_TYPES, 0);
- // print out specific node information if congestion for type is low enough
-
- int total_congestion = 0;
- for (int inode = 0; inode < num_rr_nodes; ++inode) {
- const t_rr_node& node = rr_node[inode];
- int congestion = node.get_occ() - node.get_capacity();
-
- if (congestion > 0) {
- total_congestion += congestion;
- congestion_per_type[node.type] += congestion;
- }
- }
-
- constexpr int specific_node_print_threshold = 5;
- Congested_node_types congested;
- for (int type = SOURCE; type < NUM_RR_TYPES; ++type) {
- float congestion_percentage = (float)congestion_per_type[type] / (float) total_congestion * 100;
- vpr_printf_info(" %6s: %10.6f %\n", node_typename[type], congestion_percentage);
- // nodes of that type need specific printing
- if (congestion_per_type[type] > 0 &&
- congestion_per_type[type] < specific_node_print_threshold) congested.set_congested(type);
- }
-
- // specific print out each congested node
- if (!congested.empty()) {
- vpr_printf_info("Specific congested nodes\nxlow ylow type\n");
- for (int inode = 0; inode < num_rr_nodes; ++inode) {
- const t_rr_node& node = rr_node[inode];
- if (congested.is_congested(node.type) && (node.get_occ() - node.get_capacity()) > 0) {
- vpr_printf_info("(%3d,%3d) %6s\n", node.get_xlow(), node.get_ylow(), node_typename[node.type]);
- }
- }
- }
-}
-#endif
-
-bool try_timing_driven_route_net(int inet, int itry, float pres_fac,
- struct s_router_opts router_opts,
- float* pin_criticality, int* sink_order,
- t_rt_node** rt_node_of_sink, float** net_delay, t_slack* slacks) {
-
- bool is_routed = false;
-
- if (g_clbs_nlist.net[inet].is_fixed) { /* Skip pre-routed nets. */
- is_routed = true;
- } else if (g_clbs_nlist.net[inet].is_global) { /* Skip global nets. */
- is_routed = true;
- } else if (should_route_net(inet) == false) {
- is_routed = true;
- } else{
- // track time spent vs fanout
-#ifdef PROFILE
- clock_t net_begin = clock();
-#endif
-
- is_routed = timing_driven_route_net(inet, itry, pres_fac,
- router_opts.max_criticality, router_opts.criticality_exp,
- router_opts.astar_fac, router_opts.bend_cost,
- pin_criticality, sink_order,
- rt_node_of_sink, net_delay[inet], slacks);
-
-#ifdef PROFILE
- float time_for_net = static_cast<float>(clock() - net_begin) / CLOCKS_PER_SEC;
- int net_fanout = g_clbs_nlist.net[inet].num_sinks();
- time_on_fanout[net_fanout / fanout_per_bin] += time_for_net;
- itry_on_fanout[net_fanout / fanout_per_bin] += 1;
-#endif
-
- /* Impossible to route? (disconnected rr_graph) */
- if (is_routed) {
- g_clbs_nlist.net[inet].is_routed = true;
- g_atoms_nlist.net[clb_to_vpack_net_mapping[inet]].is_routed = true;
- } else {
- vpr_printf_info("Routing failed.\n");
- }
- }
- return (is_routed);
-}
-
-/*
- * NOTE:
- * Suggest using a timing_driven_route_structs struct. Memory is managed for you
- */
-void alloc_timing_driven_route_structs(float **pin_criticality_ptr,
- int **sink_order_ptr, t_rt_node *** rt_node_of_sink_ptr) {
-
- /* Allocates all the structures needed only by the timing-driven router. */
-
- int max_pins_per_net = get_max_pins_per_net();
-
- float *pin_criticality = (float *) my_malloc((max_pins_per_net - 1) * sizeof(float));
- *pin_criticality_ptr = pin_criticality - 1; /* First sink is pin #1. */
-
- int *sink_order = (int *) my_malloc((max_pins_per_net - 1) * sizeof(int));
- *sink_order_ptr = sink_order - 1;
-
- t_rt_node **rt_node_of_sink = (t_rt_node **) my_malloc((max_pins_per_net - 1) * sizeof(t_rt_node *));
- *rt_node_of_sink_ptr = rt_node_of_sink - 1;
-
- alloc_route_tree_timing_structs();
-}
-
-/* This function gets ratio of overused nodes (overused_nodes / num_rr_nodes) */
-static double get_overused_ratio(){
- double overused_nodes = 0.0;
- int inode;
- for(inode = 0; inode < num_rr_nodes; inode++){
- if(rr_node[inode].get_occ() > rr_node[inode].get_capacity())
- overused_nodes += (rr_node[inode].get_occ() - rr_node[inode].get_capacity());
- }
- overused_nodes /= (double)num_rr_nodes;
- return overused_nodes;
-}
-
-/*
- * NOTE:
- * Suggest using a timing_driven_route_structs struct. Memory is managed for you
- */
-void free_timing_driven_route_structs(float *pin_criticality, int *sink_order,
- t_rt_node ** rt_node_of_sink) {
-
- /* Frees all the stuctures needed only by the timing-driven router. */
-
- free(pin_criticality + 1); /* Starts at index 1. */
- free(sink_order + 1);
- free(rt_node_of_sink + 1);
- free_route_tree_timing_structs();
-}
-
-timing_driven_route_structs::timing_driven_route_structs() {
- alloc_timing_driven_route_structs(
- &pin_criticality,
- &sink_order,
- &rt_node_of_sink
- );
-}
-
-timing_driven_route_structs::~timing_driven_route_structs() {
- free_timing_driven_route_structs(
- pin_criticality,
- sink_order,
- rt_node_of_sink
- );
-}
-
-static int get_max_pins_per_net(void) {
-
- /* Returns the largest number of pins on any non-global net. */
-
- unsigned int inet;
- int max_pins_per_net;
-
- max_pins_per_net = 0;
- for (inet = 0; inet < g_clbs_nlist.net.size(); inet++) {
- if (g_clbs_nlist.net[inet].is_global == false) {
- max_pins_per_net = max(max_pins_per_net,
- (int) g_clbs_nlist.net[inet].pins.size());
- }
- }
-
- return (max_pins_per_net);
-}
-
-bool timing_driven_route_net(int inet, int itry, float pres_fac, float max_criticality,
- float criticality_exp, float astar_fac, float bend_cost,
- float *pin_criticality, int *sink_order,
- t_rt_node ** rt_node_of_sink, float *net_delay, t_slack * slacks) {
-
- /* Returns true as long is found some way to hook up this net, even if that *
- * way resulted in overuse of resources (congestion). If there is no way *
- * to route this net, even ignoring congestion, it returns false. In this *
- * case the rr_graph is disconnected and you can give up. If slacks = NULL, *
- * give each net a dummy criticality of 0. */
-
- unsigned int ipin;
- int num_sinks, itarget, target_pin, target_node, inode;
- float target_criticality, old_total_cost, new_total_cost, largest_criticality,
- old_back_cost, new_back_cost;
- t_rt_node *rt_root;
-
- struct s_trace *new_route_start_tptr;
- int highfanout_rlim;
-
- /* Rip-up any old routing. */
-
- pathfinder_update_one_cost(trace_head[inet], -1, pres_fac);
- free_traceback(inet);
-
- for (ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ipin++) {
- if (!slacks) {
- /* Use criticality of 1. This makes all nets critical. Note: There is a big difference between setting pin criticality to 0
- compared to 1. If pin criticality is set to 0, then the current path delay is completely ignored during routing. By setting
- pin criticality to 1, the current path delay to the pin will always be considered and optimized for */
- pin_criticality[ipin] = 1.0;
- } else {
-#ifdef PATH_COUNTING
- /* Pin criticality is based on a weighted sum of timing and path criticalities. */
- pin_criticality[ipin] = ROUTE_PATH_WEIGHT * slacks->path_criticality[inet][ipin]
- + (1 - ROUTE_PATH_WEIGHT) * slacks->timing_criticality[inet][ipin];
-#else
- /* Pin criticality is based on only timing criticality. */
- pin_criticality[ipin] = slacks->timing_criticality[inet][ipin];
-#endif
- /* Currently, pin criticality is between 0 and 1. Now shift it downwards
- by 1 - max_criticality (max_criticality is 0.99 by default, so shift down
- by 0.01) and cut off at 0. This means that all pins with small criticalities
- (<0.01) get criticality 0 and are ignored entirely, and everything
- else becomes a bit less critical. This effect becomes more pronounced if
- max_criticality is set lower. */
- // assert(pin_criticality[ipin] > -0.01 && pin_criticality[ipin] < 1.01);
- pin_criticality[ipin] = max(pin_criticality[ipin] - (1.0 - max_criticality), 0.0);
-
- /* Take pin criticality to some power (1 by default). */
- pin_criticality[ipin] = pow(pin_criticality[ipin], criticality_exp);
-
- /* Cut off pin criticality at max_criticality. */
- pin_criticality[ipin] = min(pin_criticality[ipin], max_criticality);
- }
- }
-
- num_sinks = g_clbs_nlist.net[inet].num_sinks();
- heapsort(sink_order, pin_criticality, num_sinks, 0);
-
- /* Update base costs according to fanout and criticality rules */
-
- largest_criticality = pin_criticality[sink_order[1]];
- update_rr_base_costs(inet, largest_criticality);
-
- mark_ends(inet); /* Only needed to check for multiply-connected SINKs */
-
- rt_root = init_route_tree_to_source(inet);
-#ifdef PROFILE
- float build_heap_time = 0;
-#endif
- // explore in order of decreasing criticality
- for (itarget = 1; itarget <= num_sinks; itarget++) {
- target_pin = sink_order[itarget];
- target_node = net_rr_terminals[inet][target_pin];
-
- target_criticality = pin_criticality[target_pin];
-#ifdef PROFILE
- clock_t sink_criticality_start = clock();
-#endif
-
- highfanout_rlim = mark_node_expansion_by_bin(inet, target_node,
- rt_root);
-
- if (itarget > 1 && itry > 5) {
- /* Enough iterations given to determine opin, to speed up legal solution, do not let net use two opins */
- assert(rr_node[rt_root->inode].type == SOURCE);
- rt_root->re_expand = false;
- }
-
- // reexplore route tree from root to add any new nodes (buildheap afterwards)
-#ifdef PROFILE
- clock_t route_tree_start = clock();
-#endif
- add_route_tree_to_heap(rt_root, target_node, target_criticality,
- astar_fac);
- heap_::build_heap(); // via sifting down everything
- // if (itarget == num_sinks && itarget > 800) {
- // vpr_printf_info("heap for target %d: ", itarget);
- // heap_::verify_extract_top();
- // }
-#ifdef PROFILE
- build_heap_time += static_cast<float>(clock() - route_tree_start) / CLOCKS_PER_SEC;
-#endif
-
-
- // cheapest s_heap (gives index to rr_node) in current route tree to be expanded on
- struct s_heap* cheapest = get_heap_head();
-
- if (cheapest == NULL) { /* Infeasible routing. No possible path for net. */
- vpr_printf_info("Cannot route net #%d (%s) to sink #%d -- no possible path.\n",
- inet, g_clbs_nlist.net[inet].name, itarget);
- reset_path_costs();
- free_route_tree(rt_root);
- return (false);
- }
-
- inode = cheapest->index;
- while (inode != target_node) {
- old_total_cost = rr_node_route_inf[inode].path_cost;
- new_total_cost = cheapest->cost;
-
- if (old_total_cost > 0.99 * HUGE_POSITIVE_FLOAT) /* First time touched. */
- old_back_cost = HUGE_POSITIVE_FLOAT;
- else
- old_back_cost = rr_node_route_inf[inode].backward_path_cost;
-
- new_back_cost = cheapest->backward_path_cost;
-
- /* I only re-expand a node if both the "known" backward cost is lower *
- * in the new expansion (this is necessary to prevent loops from *
- * forming in the routing and causing havoc) *and* the expected total *
- * cost to the sink is lower than the old value. Different R_upstream *
- * values could make a path with lower back_path_cost less desirable *
- * than one with higher cost. Test whether or not I should disallow *
- * re-expansion based on a higher total cost. */
-
- if (old_total_cost > new_total_cost && old_back_cost > new_back_cost) {
- rr_node_route_inf[inode].prev_node = cheapest->u.prev_node;
- rr_node_route_inf[inode].prev_edge = cheapest->prev_edge;
- rr_node_route_inf[inode].path_cost = new_total_cost;
- rr_node_route_inf[inode].backward_path_cost = new_back_cost;
-
- if (old_total_cost > 0.99 * HUGE_POSITIVE_FLOAT) /* First time touched. */
- add_to_mod_list(&rr_node_route_inf[inode].path_cost);
-
- timing_driven_expand_neighbours(cheapest, inet, itry, bend_cost,
- target_criticality, target_node, astar_fac,
- highfanout_rlim);
- }
-
- free_heap_data(cheapest);
- cheapest = get_heap_head();
- // test heap property
- // if (!heap_::is_valid()) {vpr_printf_info("invalid heap: "); heap_::pop_heap();}
-
- if (cheapest == NULL) { /* Impossible routing. No path for net. */
- vpr_printf_info("Cannot route net #%d (%s) to sink #%d -- no possible path.\n",
- inet, g_clbs_nlist.net[inet].name, itarget);
- reset_path_costs();
- free_route_tree(rt_root);
- return (false);
- }
-
- inode = cheapest->index;
- }
-#ifdef PROFILE
- time_on_criticality[target_criticality / criticality_per_bin] += static_cast<float>(clock() - sink_criticality_start) / CLOCKS_PER_SEC;
- ++itry_on_criticality[target_criticality / criticality_per_bin];
-#endif
- /* NB: In the code below I keep two records of the partial routing: the *
- * traceback and the route_tree. The route_tree enables fast recomputation *
- * of the Elmore delay to each node in the partial routing. The traceback *
- * lets me reuse all the routines written for breadth-first routing, which *
- * all take a traceback structure as input. Before this routine exits the *
- * route_tree structure is destroyed; only the traceback is needed at that *
- * point. */
-
- rr_node_route_inf[inode].target_flag--; /* Connected to this SINK. */
- new_route_start_tptr = update_traceback(cheapest, inet);
- rt_node_of_sink[target_pin] = update_route_tree(cheapest);
- free_heap_data(cheapest);
- pathfinder_update_one_cost(new_route_start_tptr, 1, pres_fac);
-
- empty_heap();
- reset_path_costs();
- }
-#ifdef PROFILE
- if (!time_to_build_heap.empty()) time_to_build_heap[num_sinks / fanout_per_bin] += build_heap_time;
-#endif
- /* For later timing analysis. */
-
- update_net_delays_from_route_tree(net_delay, rt_node_of_sink, inet);
- free_route_tree(rt_root);
- return (true);
-}
-
-static void add_route_tree_to_heap(t_rt_node * rt_node, int target_node,
- float target_criticality, float astar_fac) {
-
- /* Puts the entire partial routing below and including rt_node onto the heap *
- * (except for those parts marked as not to be expanded) by calling itself *
- * recursively. */
-
- int inode;
- t_rt_node *child_node;
- t_linked_rt_edge *linked_rt_edge;
- float tot_cost, backward_path_cost, R_upstream;
-
- /* Pre-order depth-first traversal */
-
- if (rt_node->re_expand) {
- inode = rt_node->inode;
- backward_path_cost = target_criticality * rt_node->Tdel;
- R_upstream = rt_node->R_upstream;
- tot_cost = backward_path_cost
- + astar_fac
- * get_timing_driven_expected_cost(inode, target_node,
- target_criticality, R_upstream);
- heap_::push_back_node(inode, tot_cost, NO_PREVIOUS, NO_PREVIOUS,
- backward_path_cost, R_upstream);
-
- }
-
- linked_rt_edge = rt_node->u.child_list;
-
- while (linked_rt_edge != NULL) {
- child_node = linked_rt_edge->child;
- add_route_tree_to_heap(child_node, target_node, target_criticality,
- astar_fac);
- linked_rt_edge = linked_rt_edge->next;
- }
-}
-
-static void timing_driven_expand_neighbours(struct s_heap *current,
- int inet, int itry,
- float bend_cost, float criticality_fac, int target_node,
- float astar_fac, int highfanout_rlim) {
-
- /* Puts all the rr_nodes adjacent to current on the heap. rr_nodes outside *
- * the expanded bounding box specified in route_bb are not added to the *
- * heap. */
-
- float new_R_upstream;
-
- int inode = current->index;
- float old_back_pcost = current->backward_path_cost;
- float R_upstream = current->R_upstream;
- int num_edges = rr_node[inode].get_num_edges();
-
- int target_x = rr_node[target_node].get_xhigh();
- int target_y = rr_node[target_node].get_yhigh();
- bool high_fanout = g_clbs_nlist.net[inet].num_sinks() >= HIGH_FANOUT_NET_LIM;
-
- for (int iconn = 0; iconn < num_edges; iconn++) {
- int to_node = rr_node[inode].edges[iconn];
-
- if (high_fanout) {
- // since target node is an IPIN, xhigh and xlow are the same (same for y values)
- if (rr_node[to_node].get_xhigh() < target_x - highfanout_rlim
- || rr_node[to_node].get_xlow() > target_x + highfanout_rlim
- || rr_node[to_node].get_yhigh() < target_y - highfanout_rlim
- || rr_node[to_node].get_ylow() > target_y + highfanout_rlim){
- continue; /* Node is outside high fanout bin. */
- }
- }
- else if (rr_node[to_node].get_xhigh() < route_bb[inet].xmin
- || rr_node[to_node].get_xlow() > route_bb[inet].xmax
- || rr_node[to_node].get_yhigh() < route_bb[inet].ymin
- || rr_node[to_node].get_ylow() > route_bb[inet].ymax)
- continue; /* Node is outside (expanded) bounding box. */
-
-
- /* Prune away IPINs that lead to blocks other than the target one. Avoids *
- * the issue of how to cost them properly so they don't get expanded before *
- * more promising routes, but makes route-throughs (via CLBs) impossible. *
- * Change this if you want to investigate route-throughs. */
-
- t_rr_type to_type = rr_node[to_node].type;
- if (to_type == IPIN
- && (rr_node[to_node].get_xhigh() != target_x
- || rr_node[to_node].get_yhigh() != target_y))
- continue;
-
- /* new_back_pcost stores the "known" part of the cost to this node -- the *
- * congestion cost of all the routing resources back to the existing route *
- * plus the known delay of the total path back to the source. new_tot_cost *
- * is this "known" backward cost + an expected cost to get to the target. */
-
- float new_back_pcost = old_back_pcost
- + (1. - criticality_fac) * get_rr_cong_cost(to_node);
-
- int iswitch = rr_node[inode].switches[iconn];
- if (g_rr_switch_inf[iswitch].buffered) {
- new_R_upstream = g_rr_switch_inf[iswitch].R;
- } else {
- new_R_upstream = R_upstream + g_rr_switch_inf[iswitch].R;
- }
-
- float Tdel = rr_node[to_node].C * (new_R_upstream + 0.5 * rr_node[to_node].R);
- Tdel += g_rr_switch_inf[iswitch].Tdel;
- new_R_upstream += rr_node[to_node].R;
- new_back_pcost += criticality_fac * Tdel;
-
- if (bend_cost != 0.) {
- t_rr_type from_type = rr_node[inode].type;
- to_type = rr_node[to_node].type;
- if ((from_type == CHANX && to_type == CHANY)
- || (from_type == CHANY && to_type == CHANX))
- new_back_pcost += bend_cost;
- }
-
- float expected_cost = get_timing_driven_expected_cost(to_node, target_node,
- criticality_fac, new_R_upstream);
- float new_tot_cost = new_back_pcost + astar_fac * expected_cost;
-
- node_to_heap(to_node, new_tot_cost, inode, iconn, new_back_pcost,
- new_R_upstream);
-
- } /* End for all neighbours */
-}
-
-static float get_timing_driven_expected_cost(int inode, int target_node,
- float criticality_fac, float R_upstream) {
-
- /* Determines the expected cost (due to both delay and resouce cost) to reach *
- * the target node from inode. It doesn't include the cost of inode -- *
- * that's already in the "known" path_cost. */
-
- t_rr_type rr_type;
- int cost_index, ortho_cost_index, num_segs_same_dir, num_segs_ortho_dir;
- float expected_cost, cong_cost, Tdel;
-
- rr_type = rr_node[inode].type;
-
- if (rr_type == CHANX || rr_type == CHANY) {
-#ifdef INTERPOSER_BASED_ARCHITECTURE
- int num_interposer_hops = get_num_expected_interposer_hops_to_target(inode, target_node);
-#endif
-
- num_segs_same_dir = get_expected_segs_to_target(inode, target_node,
- &num_segs_ortho_dir);
- cost_index = rr_node[inode].get_cost_index();
- ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;
-
- cong_cost = num_segs_same_dir * rr_indexed_data[cost_index].base_cost
- + num_segs_ortho_dir
- * rr_indexed_data[ortho_cost_index].base_cost;
- cong_cost += rr_indexed_data[IPIN_COST_INDEX].base_cost
- + rr_indexed_data[SINK_COST_INDEX].base_cost;
-
- Tdel =
- num_segs_same_dir * rr_indexed_data[cost_index].T_linear
- + num_segs_ortho_dir
- * rr_indexed_data[ortho_cost_index].T_linear
- + num_segs_same_dir * num_segs_same_dir
- * rr_indexed_data[cost_index].T_quadratic
- + num_segs_ortho_dir * num_segs_ortho_dir
- * rr_indexed_data[ortho_cost_index].T_quadratic
- + R_upstream
- * (num_segs_same_dir
- * rr_indexed_data[cost_index].C_load
- + num_segs_ortho_dir
- * rr_indexed_data[ortho_cost_index].C_load);
-
- Tdel += rr_indexed_data[IPIN_COST_INDEX].T_linear;
-#ifdef INTERPOSER_BASED_ARCHITECTURE
- float interposer_hop_delay = (float)delay_increase * 1e-12;
- Tdel += num_interposer_hops * interposer_hop_delay;
-#endif
-
- expected_cost = criticality_fac * Tdel
- + (1. - criticality_fac) * cong_cost;
- return (expected_cost);
- }
-
- else if (rr_type == IPIN) { /* Change if you're allowing route-throughs */
- return (rr_indexed_data[SINK_COST_INDEX].base_cost);
- }
-
- else { /* Change this if you want to investigate route-throughs */
- return (0.);
- }
-}
-#ifdef INTERPOSER_BASED_ARCHITECTURE
-static int get_num_expected_interposer_hops_to_target(int inode, int target_node)
-{
- /*
- Description:
- returns the expected number of times you have to cross the
- interposer in order to go from inode to target_node.
- This does not include inode itself.
-
- Assumptions:
- 1- Cuts are horizontal
- 2- target_node is a terminal pin (hence its ylow==yhigh)
- 3- wires that go through the interposer are uni-directional
-
- --------- y=150
- | |
- --------- y=100
- | |
- --------- y=50
- | |
- --------- y=0
-
- num_cuts = 2, cut_step = 50, cut_locations = {50, 100}
- */
- int y_start; /* start point y-coordinate. (y-coordinate at the *end* of wire 'i') */
- int y_end; /* destination (target) y-coordinate */
- int cut_i, y_cut_location, num_expected_hops;
- t_rr_type rr_type;
-
- num_expected_hops = 0;
- y_end = rr_node[target_node].get_ylow();
- rr_type = rr_node[inode].type;
-
- if(rr_type == CHANX)
- { /* inode is a horizontal wire */
- /* the ylow and yhigh are the same */
- assert(rr_node[inode].get_ylow() == rr_node[inode].get_yhigh());
- y_start = rr_node[inode].get_ylow();
- }
- else
- { /* inode is a CHANY */
- if(rr_node[inode].direction == INC_DIRECTION)
- {
- y_start = rr_node[inode].get_yhigh();
- }
- else if(rr_node[inode].direction == DEC_DIRECTION)
- {
- y_start = rr_node[inode].get_ylow();
- }
- else
- {
- /* this means direction is BIDIRECTIONAL! Error out. */
- y_start = -1;
- assert(rr_node[inode].direction!=BI_DIRECTION);
- }
- }
-
- /* for every cut, is it between 'i' and 'target'? */
- for(cut_i=0 ; cut_i<num_cuts; ++cut_i)
- {
- y_cut_location = arch_cut_locations[cut_i];
- if( (y_start < y_cut_location && y_cut_location < y_end) ||
- (y_end < y_cut_location && y_cut_location < y_start))
- {
- ++num_expected_hops;
- }
- }
-
- /* Make there is no off-by-1 error.For current node i:
- if it's a vertical wire, node 'i' itself may be crossing the interposer.
- */
- if(rr_type == CHANY)
- {
- /* for every cut, does it cut wire 'i'? */
- for(cut_i=0 ; cut_i<num_cuts; ++cut_i)
- {
- y_cut_location = arch_cut_locations[cut_i];
- if(rr_node[inode].get_ylow() < y_cut_location && y_cut_location < rr_node[inode].get_yhigh())
- {
- ++num_expected_hops;
- }
- }
- }
-
- return num_expected_hops;
-}
-#endif
-
-/* Macro used below to ensure that fractions are rounded up, but floating *
- * point values very close to an integer are rounded to that integer. */
-#define ROUND_UP(x) (ceil (x - 0.001))
-
-static int get_expected_segs_to_target(int inode, int target_node,
- int *num_segs_ortho_dir_ptr) {
-
- /* Returns the number of segments the same type as inode that will be needed *
- * to reach target_node (not including inode) in each direction (the same *
- * direction (horizontal or vertical) as inode and the orthogonal direction).*/
-
- t_rr_type rr_type;
- int target_x, target_y, num_segs_same_dir, cost_index, ortho_cost_index;
- int no_need_to_pass_by_clb;
- float inv_length, ortho_inv_length, ylow, yhigh, xlow, xhigh;
-#ifdef INTERPOSER_BASED_ARCHITECTURE
- int num_expected_hops = get_num_expected_interposer_hops_to_target(inode, target_node);
-#endif
-
- target_x = rr_node[target_node].get_xlow();
- target_y = rr_node[target_node].get_ylow();
- cost_index = rr_node[inode].get_cost_index();
- inv_length = rr_indexed_data[cost_index].inv_length;
- ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;
- ortho_inv_length = rr_indexed_data[ortho_cost_index].inv_length;
- rr_type = rr_node[inode].type;
-
- if (rr_type == CHANX) {
- ylow = rr_node[inode].get_ylow();
- xhigh = rr_node[inode].get_xhigh();
- xlow = rr_node[inode].get_xlow();
-
- /* Count vertical (orthogonal to inode) segs first. */
-
- if (ylow > target_y) { /* Coming from a row above target? */
- *num_segs_ortho_dir_ptr =
- (int)(ROUND_UP((ylow - target_y + 1.) * ortho_inv_length));
- no_need_to_pass_by_clb = 1;
- } else if (ylow < target_y - 1) { /* Below the CLB bottom? */
- *num_segs_ortho_dir_ptr = (int)(ROUND_UP((target_y - ylow) *
- ortho_inv_length));
- no_need_to_pass_by_clb = 1;
- } else { /* In a row that passes by target CLB */
- *num_segs_ortho_dir_ptr = 0;
- no_need_to_pass_by_clb = 0;
- }
-#ifdef INTERPOSER_BASED_ARCHITECTURE
- (*num_segs_ortho_dir_ptr) = (*num_segs_ortho_dir_ptr) + 2*num_expected_hops;
-#endif
-
- /* Now count horizontal (same dir. as inode) segs. */
-
- if (xlow > target_x + no_need_to_pass_by_clb) {
- num_segs_same_dir = (int)(ROUND_UP((xlow - no_need_to_pass_by_clb -
- target_x) * inv_length));
- } else if (xhigh < target_x - no_need_to_pass_by_clb) {
- num_segs_same_dir = (int)(ROUND_UP((target_x - no_need_to_pass_by_clb -
- xhigh) * inv_length));
- } else {
- num_segs_same_dir = 0;
- }
- }
-
- else { /* inode is a CHANY */
- ylow = rr_node[inode].get_ylow();
- yhigh = rr_node[inode].get_yhigh();
- xlow = rr_node[inode].get_xlow();
-
- /* Count horizontal (orthogonal to inode) segs first. */
-
- if (xlow > target_x) { /* Coming from a column right of target? */
- *num_segs_ortho_dir_ptr = (int)(
- ROUND_UP((xlow - target_x + 1.) * ortho_inv_length));
- no_need_to_pass_by_clb = 1;
- } else if (xlow < target_x - 1) { /* Left of and not adjacent to the CLB? */
- *num_segs_ortho_dir_ptr = (int)(ROUND_UP((target_x - xlow) *
- ortho_inv_length));
- no_need_to_pass_by_clb = 1;
- } else { /* In a column that passes by target CLB */
- *num_segs_ortho_dir_ptr = 0;
- no_need_to_pass_by_clb = 0;
- }
-
- /* Now count vertical (same dir. as inode) segs. */
-
- if (ylow > target_y + no_need_to_pass_by_clb) {
- num_segs_same_dir = (int)(ROUND_UP((ylow - no_need_to_pass_by_clb -
- target_y) * inv_length));
- } else if (yhigh < target_y - no_need_to_pass_by_clb) {
- num_segs_same_dir = (int)(ROUND_UP((target_y - no_need_to_pass_by_clb -
- yhigh) * inv_length));
- } else {
- num_segs_same_dir = 0;
- }
-#ifdef INTERPOSER_BASED_ARCHITECTURE
- num_segs_same_dir = num_segs_same_dir + 2*num_expected_hops;
-#endif
- }
-
- return (num_segs_same_dir);
-}
-
-static void update_rr_base_costs(int inet, float largest_criticality) {
-
- /* Changes the base costs of different types of rr_nodes according to the *
- * criticality, fanout, etc. of the current net being routed (inet). */
-
- float fanout, factor;
- int index;
-
- fanout = g_clbs_nlist.net[inet].num_sinks();
-
- /* Other reasonable values for factor include fanout and 1 */
- factor = sqrt(fanout);
-
- for (index = CHANX_COST_INDEX_START; index < num_rr_indexed_data; index++) {
- if (rr_indexed_data[index].T_quadratic > 0.) { /* pass transistor */
- rr_indexed_data[index].base_cost =
- rr_indexed_data[index].saved_base_cost * factor;
- } else {
- rr_indexed_data[index].base_cost =
- rr_indexed_data[index].saved_base_cost;
- }
- }
-}
-
-/* Nets that have high fanout can take a very long time to route. Routing for sinks that are part of high-fanout nets should be
- done within a rectangular 'bin' centered around a target (as opposed to the entire net bounding box) the size of which is returned by this function. */
-static int mark_node_expansion_by_bin(int inet, int target_node,
- t_rt_node * rt_node) {
- int target_xlow, target_ylow, target_xhigh, target_yhigh;
- int rlim = 1;
- int inode;
- float area;
- bool success;
- t_linked_rt_edge *linked_rt_edge;
- t_rt_node * child_node;
-
- target_xlow = rr_node[target_node].get_xlow();
- target_ylow = rr_node[target_node].get_ylow();
- target_xhigh = rr_node[target_node].get_xhigh();
- target_yhigh = rr_node[target_node].get_yhigh();
-
- if (g_clbs_nlist.net[inet].num_sinks() < HIGH_FANOUT_NET_LIM) {
- /* This algorithm only applies to high fanout nets */
- return 1;
- }
- if (rt_node == NULL || rt_node->u.child_list == NULL) {
- /* If unknown traceback, set radius of bin to be size of chip */
- rlim = max(nx + 2, ny + 2);
- return rlim;
- }
-
- area = (route_bb[inet].xmax - route_bb[inet].xmin)
- * (route_bb[inet].ymax - route_bb[inet].ymin);
- if (area <= 0) {
- area = 1;
- }
-
- rlim = (int)(ceil(sqrt((float) area / (float) g_clbs_nlist.net[inet].num_sinks())));
-
- success = false;
- /* determine quickly a feasible bin radius to route sink for high fanout nets
- this is necessary to prevent super long runtimes for high fanout nets; in best case, a reduction in complexity from O(N^2logN) to O(NlogN) (Swartz fast router)
- */
- linked_rt_edge = rt_node->u.child_list;
- while (success == false && linked_rt_edge != NULL) {
- while (linked_rt_edge != NULL && success == false) {
- child_node = linked_rt_edge->child;
- inode = child_node->inode;
- if (!(rr_node[inode].type == IPIN || rr_node[inode].type == SINK)) {
- if (rr_node[inode].get_xlow() <= target_xhigh + rlim
- && rr_node[inode].get_xhigh() >= target_xhigh - rlim
- && rr_node[inode].get_ylow() <= target_yhigh + rlim
- && rr_node[inode].get_yhigh() >= target_yhigh - rlim) {
- success = true;
- }
- }
- linked_rt_edge = linked_rt_edge->next;
- }
-
- if (success == false) {
- if (rlim > max(nx + 2, ny + 2)) {
- vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
- "VPR internal error, net %s has paths that are not found in traceback.\n", g_clbs_nlist.net[inet].name);
- }
- /* if sink not in bin, increase bin size until fit */
- rlim *= 2;
- } else {
- /* Sometimes might just catch a wire in the end segment, need to give it some channel space to explore */
- rlim += 4;
- }
- linked_rt_edge = rt_node->u.child_list;
- }
-
- /* adjust rlim to account for width/height of block containing the target sink */
- int target_span = max( target_xhigh - target_xlow, target_yhigh - target_ylow );
- rlim += target_span;
-
- /* redetermine expansion based on rlim */
- linked_rt_edge = rt_node->u.child_list;
- while (linked_rt_edge != NULL) {
- child_node = linked_rt_edge->child;
- inode = child_node->inode;
- if (!(rr_node[inode].type == IPIN || rr_node[inode].type == SINK)) {
- if (rr_node[inode].get_xlow() <= target_xhigh + rlim
- && rr_node[inode].get_xhigh() >= target_xhigh - rlim
- && rr_node[inode].get_ylow() <= target_yhigh + rlim
- && rr_node[inode].get_yhigh() >= target_yhigh - rlim) {
- child_node->re_expand = true;
- } else {
- child_node->re_expand = false;
- }
- }
- linked_rt_edge = linked_rt_edge->next;
- }
- return rlim;
-}
-#define ERROR_TOL 0.0001
-
-static void timing_driven_check_net_delays(float **net_delay) {
-
- /* Checks that the net delays computed incrementally during timing driven *
- * routing match those computed from scratch by the net_delay.c module. */
-
- unsigned int inet, ipin;
- float **net_delay_check;
-
- t_chunk list_head_net_delay_check_ch = {NULL, 0, NULL};
-
- /*struct s_linked_vptr *ch_list_head_net_delay_check;*/
-
- net_delay_check = alloc_net_delay(&list_head_net_delay_check_ch, g_clbs_nlist.net,
- g_clbs_nlist.net.size());
- load_net_delay_from_routing(net_delay_check, g_clbs_nlist.net, g_clbs_nlist.net.size());
-
- for (inet = 0; inet < g_clbs_nlist.net.size(); inet++) {
- for (ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ipin++) {
- if (net_delay_check[inet][ipin] == 0.) { /* Should be only GLOBAL nets */
- if (fabs(net_delay[inet][ipin]) > ERROR_TOL) {
- vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
- "in timing_driven_check_net_delays: net %d pin %d.\n"
- "\tIncremental calc. net_delay is %g, but from scratch net delay is %g.\n",
- inet, ipin, net_delay[inet][ipin], net_delay_check[inet][ipin]);
- }
- } else {
- if (fabs(1.0 - net_delay[inet][ipin] / net_delay_check[inet][ipin]) > ERROR_TOL) {
- vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
- "in timing_driven_check_net_delays: net %d pin %d.\n"
- "\tIncremental calc. net_delay is %g, but from scratch net delay is %g.\n",
- inet, ipin, net_delay[inet][ipin], net_delay_check[inet][ipin]);
- }
- }
- }
- }
-
- free_net_delay(net_delay_check, &list_head_net_delay_check_ch);
- vpr_printf_info("Completed net delay value cross check successfully.\n");
-}
-
-
-/* Detect if net should be routed or not */
-static bool should_route_net(int inet) {
- t_trace * tptr = trace_head[inet];
-
- if (tptr == NULL) {
- /* No routing yet. */
- return true;
- }
-
- for (;;) {
- int inode = tptr->index;
- int occ = rr_node[inode].get_occ();
- int capacity = rr_node[inode].get_capacity();
-
- if (occ > capacity) {
- return true; /* overuse detected */
- }
-
- if (rr_node[inode].type == SINK) {
- tptr = tptr->next; /* Skip next segment. */
- if (tptr == NULL)
- break;
- }
-
- tptr = tptr->next;
-
- } /* End while loop -- did an entire traceback. */
-
- return false; /* Current route has no overuse */
-}
-
-static bool early_exit_heuristic(const t_router_opts& router_opts) {
- /* Early exit code for cases where it is obvious that a successful route will not be found
- Heuristic: If total wirelength used in first routing iteration is X% of total available wirelength, exit */
- int total_wirelength = 0;
- int available_wirelength = 0;
-
- for (int i = 0; i < num_rr_nodes; ++i) {
- if (rr_node[i].type == CHANX || rr_node[i].type == CHANY) {
- available_wirelength += 1 +
- rr_node[i].get_xhigh() - rr_node[i].get_xlow() +
- rr_node[i].get_yhigh() - rr_node[i].get_ylow();
- }
- }
-
- for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
- if (g_clbs_nlist.net[inet].is_global == false
- && g_clbs_nlist.net[inet].num_sinks() != 0) { /* Globals don't count. */
- int bends, wirelength, segments;
- get_num_bends_and_length(inet, &bends, &wirelength, &segments);
-
- total_wirelength += wirelength;
- }
- }
- vpr_printf_info("Wire length after first iteration %d, total available wire length %d, ratio %g\n",
- total_wirelength, available_wirelength,
- (float) (total_wirelength) / (float) (available_wirelength));
- if ((float) (total_wirelength) / (float) (available_wirelength)> FIRST_ITER_WIRELENTH_LIMIT) {
- vpr_printf_info("Wire length usage ratio exceeds limit of %g, fail routing.\n",
- FIRST_ITER_WIRELENTH_LIMIT);
- return true;
- }
- vpr_printf_info("--------- ---------- ----------- ---------------------\n");
- vpr_printf_info("Iteration Time Crit Path Overused RR Nodes\n");
- vpr_printf_info("--------- ---------- ----------- ---------------------\n");
- return false;
-}
-
+#include <cstdio>
+#include <ctime>
+#include <cmath>
+#include <assert.h>
+#include <vector>
+#include <algorithm>
+#include "vpr_utils.h"
+#include "util.h"
+#include "vpr_types.h"
+#include "globals.h"
+#include "route_export.h"
+#include "route_common.h"
+#include "route_tree_timing.h"
+#include "route_timing.h"
+#include "heapsort.h"
+#include "path_delay.h"
+#include "net_delay.h"
+#include "stats.h"
+#include "ReadOptions.h"
+
+
+using namespace std;
+
+
+/* Oleg's test code. This is an experimental/test measure to give the timing-driven router
+ look-ahead greater awareness of the different wire lengths in the FPGA.
+ Enabling this significantly increases routing time, but the router will
+ still be much faster than running it with astar_fac = 0. */
+//#define OP_STRONG_LOOKAHEAD
+
+
+/******************** Subroutines local to route_timing.c ********************/
+
+static int get_max_pins_per_net(void);
+
+static void add_route_tree_to_heap(t_rt_node * rt_node, int target_node,
+ float target_criticality, float astar_fac);
+
+static void timing_driven_expand_neighbours(struct s_heap *current,
+ int inet, int itry,
+ float bend_cost, float criticality_fac, int target_node,
+ float astar_fac, int highfanout_rlim);
+
+#ifndef OP_STRONG_LOOKAHEAD
+static float get_timing_driven_expected_cost(int inode, int target_node,
+ float criticality_fac, float R_upstream);
+#else
+static float get_timing_driven_multiple_wirelengths_expected_cost(int inode, int target_node,
+ float criticality_fac, float R_upstream);
+#endif
+
+#ifdef INTERPOSER_BASED_ARCHITECTURE
+static int get_num_expected_interposer_hops_to_target(int inode, int target_node);
+#endif
+
+#ifndef OP_STRONG_LOOKAHEAD
+static int get_expected_segs_to_target(int inode, int target_node,
+ int *num_segs_ortho_dir_ptr);
+#else
+static int get_expected_segs_to_target(int inode, int via_cost_index, int target_node,
+ int *num_segs_ortho_dir_ptr);
+#endif
+
+static void update_rr_base_costs(int inet, float largest_criticality);
+
+static void timing_driven_check_net_delays(float **net_delay);
+
+static int mark_node_expansion_by_bin(int inet, int target_node,
+ t_rt_node * rt_node);
+
+static double get_overused_ratio();
+
+static bool should_route_net(int inet);
+static bool early_exit_heuristic(const t_router_opts& router_opts);
+struct more_sinks_than {
+ inline bool operator() (const int& net_index1, const int& net_index2) {
+ return g_clbs_nlist.net[net_index1].num_sinks() > g_clbs_nlist.net[net_index2].num_sinks();
+ }
+};
+
+
+#ifdef PROFILE
+static void congestion_analysis();
+static void time_on_criticality_analysis();
+constexpr int fanout_per_bin = 4;
+constexpr float criticality_per_bin = 0.05;
+static vector<float> time_on_fanout;
+static vector<float> time_to_build_heap;
+static vector<int> itry_on_fanout;
+static vector<float> time_on_criticality;
+static vector<int> itry_on_criticality;
+#endif
+
+/************************ Subroutine definitions *****************************/
+bool try_timing_driven_route(struct s_router_opts router_opts,
+ float **net_delay, t_slack * slacks, t_ivec ** clb_opins_used_locally,
+ bool timing_analysis_enabled, const t_timing_inf &timing_inf) {
+
+ /* Timing-driven routing algorithm. The timing graph (includes slack) *
+ * must have already been allocated, and net_delay must have been allocated. *
+ * Returns true if the routing succeeds, false otherwise. */
+#ifdef PROFILE
+ const int max_fanout {get_max_pins_per_net()};
+ time_on_fanout.resize((max_fanout / fanout_per_bin) + 1, 0);
+ time_to_build_heap.resize((max_fanout / fanout_per_bin) + 1, 0);
+ itry_on_fanout.resize((max_fanout / fanout_per_bin) + 1, 0);
+ time_on_criticality.resize((1 / criticality_per_bin) + 1, 0);
+ itry_on_criticality.resize((1 / criticality_per_bin) + 1, 0);
+#endif
+
+ auto sorted_nets = vector<int>(g_clbs_nlist.net.size());
+
+ for (size_t i = 0; i < g_clbs_nlist.net.size(); ++i) {
+ sorted_nets[i] = i;
+ }
+
+ // sort so net with most sinks is first.
+ std::sort(sorted_nets.begin(), sorted_nets.end(), more_sinks_than());
+
+ timing_driven_route_structs route_structs{}; // allocs route strucs (calls default constructor)
+ // contains:
+ // float *pin_criticality; /* [1..max_pins_per_net-1] */
+ // int *sink_order; /* [1..max_pins_per_net-1] */;
+ // t_rt_node **rt_node_of_sink; /* [1..max_pins_per_net-1] */
+
+ /* First do one routing iteration ignoring congestion to get reasonable net
+ delay estimates. Set criticalities to 1 when timing analysis is on to
+ optimize timing, and to 0 when timing analysis is off to optimize routability. */
+
+ float init_timing_criticality_val = (timing_analysis_enabled ? 1.0 : 0.0);
+
+ /* Variables used to do the optimization of the routing, aborting visibly
+ * impossible Ws */
+ double overused_ratio;
+ vector<double> historical_overuse_ratio;
+ historical_overuse_ratio.reserve(router_opts.max_router_iterations + 1);
+
+ // for unroutable large circuits, the time per iteration seems to increase dramatically
+ vector<float> time_per_iteration;
+ time_per_iteration.reserve(router_opts.max_router_iterations + 1);
+
+ for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
+ if (g_clbs_nlist.net[inet].is_global == false) {
+ for (unsigned int ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ++ipin) {
+ slacks->timing_criticality[inet][ipin] = init_timing_criticality_val;
+ }
+#ifdef PATH_COUNTING
+ slacks->path_criticality[inet][ipin] = init_timing_criticality_val;
+#endif
+ } else {
+ /* Set delay of global signals to zero. Non-global net delays are set by
+ update_net_delays_from_route_tree() inside timing_driven_route_net(),
+ which is only called for non-global nets. */
+ for (unsigned int ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ++ipin) {
+ net_delay[inet][ipin] = 0.;
+ }
+ }
+ }
+
+ float pres_fac = router_opts.first_iter_pres_fac; /* Typically 0 -> ignore cong. */
+
+ for (int itry = 1; itry <= router_opts.max_router_iterations; ++itry) {
+ clock_t begin = clock();
+
+ /* Reset "is_routed" and "is_fixed" flags to indicate nets not pre-routed (yet) */
+ for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
+ g_clbs_nlist.net[inet].is_routed = false;
+ g_clbs_nlist.net[inet].is_fixed = false;
+ }
+
+ for (unsigned int i = 0; i < g_clbs_nlist.net.size(); ++i) {
+ bool is_routable = try_timing_driven_route_net(
+ sorted_nets[i],
+ itry,
+ pres_fac,
+ router_opts,
+ route_structs.pin_criticality,
+ route_structs.sink_order,
+ route_structs.rt_node_of_sink,
+ net_delay,
+ slacks
+ );
+
+ if (!is_routable) {
+ return (false);
+ }
+ }
+
+ clock_t end = clock();
+ float time = static_cast<float>(end - begin) / CLOCKS_PER_SEC;
+ time_per_iteration.push_back(time);
+
+ if (itry == 1 && early_exit_heuristic(router_opts)) return false;
+
+ /* Make sure any CLB OPINs used up by subblocks being hooked directly
+ to them are reserved for that purpose. */
+
+ bool rip_up_local_opins = (itry == 1 ? false : true);
+ reserve_locally_used_opins(pres_fac, router_opts.acc_fac, rip_up_local_opins, clb_opins_used_locally);
+
+ /* Pathfinder guys quit after finding a feasible route. I may want to keep
+ going longer, trying to improve timing. Think about this some. */
+
+ bool success = feasible_routing();
+
+ /* Verification to check the ratio of overused nodes, depending on the configuration
+ * may abort the routing if the ratio is too high. */
+ overused_ratio = get_overused_ratio();
+ historical_overuse_ratio.push_back(overused_ratio);
+
+ /* Determine when routing is impossible hence should be aborted */
+ if (itry > 5){
+
+ int expected_success_route_iter = predict_success_route_iter(historical_overuse_ratio, router_opts);
+ if (expected_success_route_iter == UNDEFINED) {
+ return false;
+ }
+
+#ifdef REGRESSION_EXIT
+ if (itry > 15) {
+ // compare their slopes over the last 5 iterations
+ double time_per_iteration_slope = linear_regression_vector(time_per_iteration, itry-5);
+ double congestion_per_iteration_slope = linear_regression_vector(historical_overuse_ratio, itry-5);
+ if (router_opts.congestion_analysis)
+ vpr_printf_info("%f s/iteration %f %/iteration\n", time_per_iteration_slope, congestion_per_iteration_slope);
+ // time is increasing and congestion is non-decreasing (grows faster than 10% per iteration)
+ if (congestion_per_iteration_slope > 0 && time_per_iteration_slope > 0.1*time_per_iteration.back()
+ && time_per_iteration_slope > 1) { // filter out noise
+ vpr_printf_info("Time per iteration growing too fast at slope %f s/iteration \n\
+ while congestion grows at %f %/iteration, unlikely to finish.\n",
+ time_per_iteration_slope, congestion_per_iteration_slope);
+
+ return false;
+ }
+ }
+#endif
+ }
+
+ //print_usage_by_wire_length();
+
+
+ if (success) {
+
+ if (timing_analysis_enabled) {
+ load_timing_graph_net_delays(net_delay);
+ do_timing_analysis(slacks, timing_inf, false, false);
+ float critical_path_delay = get_critical_path_delay();
+ vpr_printf_info("%9d %6.2f sec %8.5f ns %3.2e (%3.4f %)\n", itry, time, critical_path_delay, overused_ratio*num_rr_nodes, overused_ratio*100);
+ vpr_printf_info("Critical path: %g ns\n", critical_path_delay);
+ } else {
+ vpr_printf_info("%9d %6.2f sec N/A %3.2e (%3.4f %)\n", itry, time, overused_ratio*num_rr_nodes, overused_ratio*100);
+ }
+
+ vpr_printf_info("Successfully routed after %d routing iterations.\n", itry);
+#ifdef DEBUG
+ if (timing_analysis_enabled)
+ timing_driven_check_net_delays(net_delay);
+#endif
+ return (true);
+ }
+
+ if (itry == 1) {
+ pres_fac = router_opts.initial_pres_fac;
+ pathfinder_update_cost(pres_fac, 0.); /* Acc_fac=0 for first iter. */
+ } else {
+ pres_fac *= router_opts.pres_fac_mult;
+
+ /* Avoid overflow for high iteration counts, even if acc_cost is big */
+ pres_fac = min(pres_fac, static_cast<float>(HUGE_POSITIVE_FLOAT / 1e5));
+
+ pathfinder_update_cost(pres_fac, router_opts.acc_fac);
+ }
+
+ if (timing_analysis_enabled) {
+ /* Update slack values by doing another timing analysis.
+ Timing_driven_route_net updated the net delay values. */
+
+ load_timing_graph_net_delays(net_delay);
+
+ do_timing_analysis(slacks, timing_inf, false, false);
+
+ } else {
+ /* If timing analysis is not enabled, make sure that the criticalities and the
+ net_delays stay as 0 so that wirelength can be optimized. */
+
+ for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
+ for (unsigned int ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ++ipin) {
+ slacks->timing_criticality[inet][ipin] = 0.;
+#ifdef PATH_COUNTING
+ slacks->path_criticality[inet][ipin] = 0.;
+#endif
+ net_delay[inet][ipin] = 0.;
+ }
+ }
+ }
+
+
+ if (timing_analysis_enabled) {
+ float critical_path_delay = get_critical_path_delay();
+ vpr_printf_info("%9d %6.2f sec %8.5f ns %3.2e (%3.4f %)\n", itry, time, critical_path_delay, overused_ratio*num_rr_nodes, overused_ratio*100);
+ } else {
+ vpr_printf_info("%9d %6.2f sec N/A %3.2e (%3.4f %)\n", itry, time, overused_ratio*num_rr_nodes, overused_ratio*100);
+ }
+
+#ifdef PROFILE
+ if (router_opts.congestion_analysis) congestion_analysis();
+ if (router_opts.fanout_analysis) time_on_fanout_analysis();
+ time_on_criticality_analysis();
+#endif
+ fflush(stdout);
+ }
+ vpr_printf_info("Routing failed.\n");
+
+ return (false);
+}
+
+// profiling per iteration functions
+#ifdef PROFILE
+void time_on_fanout_analysis() {
+ // using the global time_on_fanout and itry_on_fanout
+ vpr_printf_info("fanout low time (s) attemps heap build time (s)\n");
+ for (size_t bin = 0; bin < time_on_fanout.size(); ++bin) {
+ if (itry_on_fanout[bin]) { // avoid printing the many 0 bins
+ vpr_printf_info("%4d %14.3f %12d %14.3f\n",bin*fanout_per_bin, time_on_fanout[bin], itry_on_fanout[bin], time_to_build_heap[bin]);
+ }
+ }
+}
+
+void time_on_criticality_analysis() {
+ vpr_printf_info("congestion low time (s) attemps\n");
+ for (size_t bin = 0; bin < time_on_criticality.size(); ++bin) {
+ if (itry_on_criticality[bin]) { // avoid printing the many 0 bins
+ vpr_printf_info("%4d %14.3f %12d\n",bin*criticality_per_bin, time_on_criticality[bin], itry_on_criticality[bin]);
+ }
+ }
+}
+// at the end of a routing iteration, profile how much congestion is taken up by each type of rr_node
+// efficient bit array for checking against congested type
+struct Congested_node_types {
+ uint32_t mask;
+ Congested_node_types() : mask{0} {}
+ void set_congested(int rr_node_type) {mask |= (1 << rr_node_type);}
+ void clear_congested(int rr_node_type) {mask &= ~(1 << rr_node_type);}
+ bool is_congested(int rr_node_type) const {return mask & (1 << rr_node_type);}
+ bool empty() const {return mask == 0;}
+};
+
+void congestion_analysis() {
+ static const std::vector<const char*> node_typename {
+ "SOURCE",
+ "SINK",
+ "IPIN",
+ "OPIN",
+ "CHANX",
+ "CHANY",
+ "ICE"
+ };
+ // each type indexes into array which holds the congestion for that type
+ std::vector<int> congestion_per_type((size_t) NUM_RR_TYPES, 0);
+ // print out specific node information if congestion for type is low enough
+
+ int total_congestion = 0;
+ for (int inode = 0; inode < num_rr_nodes; ++inode) {
+ const t_rr_node& node = rr_node[inode];
+ int congestion = node.get_occ() - node.get_capacity();
+
+ if (congestion > 0) {
+ total_congestion += congestion;
+ congestion_per_type[node.type] += congestion;
+ }
+ }
+
+ constexpr int specific_node_print_threshold = 5;
+ Congested_node_types congested;
+ for (int type = SOURCE; type < NUM_RR_TYPES; ++type) {
+ float congestion_percentage = (float)congestion_per_type[type] / (float) total_congestion * 100;
+ vpr_printf_info(" %6s: %10.6f %\n", node_typename[type], congestion_percentage);
+ // nodes of that type need specific printing
+ if (congestion_per_type[type] > 0 &&
+ congestion_per_type[type] < specific_node_print_threshold) congested.set_congested(type);
+ }
+
+ // specific print out each congested node
+ if (!congested.empty()) {
+ vpr_printf_info("Specific congested nodes\nxlow ylow type\n");
+ for (int inode = 0; inode < num_rr_nodes; ++inode) {
+ const t_rr_node& node = rr_node[inode];
+ if (congested.is_congested(node.type) && (node.get_occ() - node.get_capacity()) > 0) {
+ vpr_printf_info("(%3d,%3d) %6s\n", node.get_xlow(), node.get_ylow(), node_typename[node.type]);
+ }
+ }
+ }
+}
+#endif
+
+bool try_timing_driven_route_net(int inet, int itry, float pres_fac,
+ struct s_router_opts router_opts,
+ float* pin_criticality, int* sink_order,
+ t_rt_node** rt_node_of_sink, float** net_delay, t_slack* slacks) {
+
+ bool is_routed = false;
+
+ if (g_clbs_nlist.net[inet].is_fixed) { /* Skip pre-routed nets. */
+ is_routed = true;
+ } else if (g_clbs_nlist.net[inet].is_global) { /* Skip global nets. */
+ is_routed = true;
+ } else if (should_route_net(inet) == false) {
+ is_routed = true;
+ } else{
+ // track time spent vs fanout
+#ifdef PROFILE
+ clock_t net_begin = clock();
+#endif
+
+ is_routed = timing_driven_route_net(inet, itry, pres_fac,
+ router_opts.max_criticality, router_opts.criticality_exp,
+ router_opts.astar_fac, router_opts.bend_cost,
+ pin_criticality, sink_order,
+ rt_node_of_sink, net_delay[inet], slacks);
+
+#ifdef PROFILE
+ float time_for_net = static_cast<float>(clock() - net_begin) / CLOCKS_PER_SEC;
+ int net_fanout = g_clbs_nlist.net[inet].num_sinks();
+ time_on_fanout[net_fanout / fanout_per_bin] += time_for_net;
+ itry_on_fanout[net_fanout / fanout_per_bin] += 1;
+#endif
+
+ /* Impossible to route? (disconnected rr_graph) */
+ if (is_routed) {
+ g_clbs_nlist.net[inet].is_routed = true;
+ g_atoms_nlist.net[clb_to_vpack_net_mapping[inet]].is_routed = true;
+ } else {
+ vpr_printf_info("Routing failed.\n");
+ }
+ }
+ return (is_routed);
+}
+
+/*
+ * NOTE:
+ * Suggest using a timing_driven_route_structs struct. Memory is managed for you
+ */
+void alloc_timing_driven_route_structs(float **pin_criticality_ptr,
+ int **sink_order_ptr, t_rt_node *** rt_node_of_sink_ptr) {
+
+ /* Allocates all the structures needed only by the timing-driven router. */
+
+ int max_pins_per_net = get_max_pins_per_net();
+
+ float *pin_criticality = (float *) my_malloc((max_pins_per_net - 1) * sizeof(float));
+ *pin_criticality_ptr = pin_criticality - 1; /* First sink is pin #1. */
+
+ int *sink_order = (int *) my_malloc((max_pins_per_net - 1) * sizeof(int));
+ *sink_order_ptr = sink_order - 1;
+
+ t_rt_node **rt_node_of_sink = (t_rt_node **) my_malloc((max_pins_per_net - 1) * sizeof(t_rt_node *));
+ *rt_node_of_sink_ptr = rt_node_of_sink - 1;
+
+ alloc_route_tree_timing_structs();
+}
+
+/* This function gets ratio of overused nodes (overused_nodes / num_rr_nodes) */
+static double get_overused_ratio(){
+ double overused_nodes = 0.0;
+ int inode;
+ for(inode = 0; inode < num_rr_nodes; inode++){
+ if(rr_node[inode].get_occ() > rr_node[inode].get_capacity())
+ overused_nodes += (rr_node[inode].get_occ() - rr_node[inode].get_capacity());
+ }
+ overused_nodes /= (double)num_rr_nodes;
+ return overused_nodes;
+}
+
+/*
+ * NOTE:
+ * Suggest using a timing_driven_route_structs struct. Memory is managed for you
+ */
+void free_timing_driven_route_structs(float *pin_criticality, int *sink_order,
+ t_rt_node ** rt_node_of_sink) {
+
+ /* Frees all the stuctures needed only by the timing-driven router. */
+
+ free(pin_criticality + 1); /* Starts at index 1. */
+ free(sink_order + 1);
+ free(rt_node_of_sink + 1);
+ free_route_tree_timing_structs();
+}
+
+timing_driven_route_structs::timing_driven_route_structs() {
+ alloc_timing_driven_route_structs(
+ &pin_criticality,
+ &sink_order,
+ &rt_node_of_sink
+ );
+}
+
+timing_driven_route_structs::~timing_driven_route_structs() {
+ free_timing_driven_route_structs(
+ pin_criticality,
+ sink_order,
+ rt_node_of_sink
+ );
+}
+
+static int get_max_pins_per_net(void) {
+
+ /* Returns the largest number of pins on any non-global net. */
+
+ unsigned int inet;
+ int max_pins_per_net;
+
+ max_pins_per_net = 0;
+ for (inet = 0; inet < g_clbs_nlist.net.size(); inet++) {
+ if (g_clbs_nlist.net[inet].is_global == false) {
+ max_pins_per_net = max(max_pins_per_net,
+ (int) g_clbs_nlist.net[inet].pins.size());
+ }
+ }
+
+ return (max_pins_per_net);
+}
+
+bool timing_driven_route_net(int inet, int itry, float pres_fac, float max_criticality,
+ float criticality_exp, float astar_fac, float bend_cost,
+ float *pin_criticality, int *sink_order,
+ t_rt_node ** rt_node_of_sink, float *net_delay, t_slack * slacks) {
+
+ /* Returns true as long is found some way to hook up this net, even if that *
+ * way resulted in overuse of resources (congestion). If there is no way *
+ * to route this net, even ignoring congestion, it returns false. In this *
+ * case the rr_graph is disconnected and you can give up. If slacks = NULL, *
+ * give each net a dummy criticality of 0. */
+
+ unsigned int ipin;
+ int num_sinks, itarget, target_pin, target_node, inode;
+ float target_criticality, old_total_cost, new_total_cost, largest_criticality,
+ old_back_cost, new_back_cost;
+ t_rt_node *rt_root;
+
+ struct s_trace *new_route_start_tptr;
+ int highfanout_rlim;
+
+ /* Rip-up any old routing. */
+
+ pathfinder_update_one_cost(trace_head[inet], -1, pres_fac);
+ free_traceback(inet);
+
+ for (ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ipin++) {
+ if (!slacks) {
+ /* Use criticality of 1. This makes all nets critical. Note: There is a big difference between setting pin criticality to 0
+ compared to 1. If pin criticality is set to 0, then the current path delay is completely ignored during routing. By setting
+ pin criticality to 1, the current path delay to the pin will always be considered and optimized for */
+ pin_criticality[ipin] = 1.0;
+ } else {
+#ifdef PATH_COUNTING
+ /* Pin criticality is based on a weighted sum of timing and path criticalities. */
+ pin_criticality[ipin] = ROUTE_PATH_WEIGHT * slacks->path_criticality[inet][ipin]
+ + (1 - ROUTE_PATH_WEIGHT) * slacks->timing_criticality[inet][ipin];
+#else
+ /* Pin criticality is based on only timing criticality. */
+ pin_criticality[ipin] = slacks->timing_criticality[inet][ipin];
+#endif
+ /* Currently, pin criticality is between 0 and 1. Now shift it downwards
+ by 1 - max_criticality (max_criticality is 0.99 by default, so shift down
+ by 0.01) and cut off at 0. This means that all pins with small criticalities
+ (<0.01) get criticality 0 and are ignored entirely, and everything
+ else becomes a bit less critical. This effect becomes more pronounced if
+ max_criticality is set lower. */
+ // assert(pin_criticality[ipin] > -0.01 && pin_criticality[ipin] < 1.01);
+ pin_criticality[ipin] = max(pin_criticality[ipin] - (1.0 - max_criticality), 0.0);
+
+ /* Take pin criticality to some power (1 by default). */
+ pin_criticality[ipin] = pow(pin_criticality[ipin], criticality_exp);
+
+ /* Cut off pin criticality at max_criticality. */
+ pin_criticality[ipin] = min(pin_criticality[ipin], max_criticality);
+ }
+ }
+
+ num_sinks = g_clbs_nlist.net[inet].num_sinks();
+ heapsort(sink_order, pin_criticality, num_sinks, 0);
+
+ /* Update base costs according to fanout and criticality rules */
+
+ largest_criticality = pin_criticality[sink_order[1]];
+ update_rr_base_costs(inet, largest_criticality);
+
+ mark_ends(inet); /* Only needed to check for multiply-connected SINKs */
+
+ rt_root = init_route_tree_to_source(inet);
+#ifdef PROFILE
+ float build_heap_time = 0;
+#endif
+ // explore in order of decreasing criticality
+ for (itarget = 1; itarget <= num_sinks; itarget++) {
+ target_pin = sink_order[itarget];
+ target_node = net_rr_terminals[inet][target_pin];
+
+ target_criticality = pin_criticality[target_pin];
+#ifdef PROFILE
+ clock_t sink_criticality_start = clock();
+#endif
+
+ highfanout_rlim = mark_node_expansion_by_bin(inet, target_node,
+ rt_root);
+
+ if (itarget > 1 && itry > 5) {
+ /* Enough iterations given to determine opin, to speed up legal solution, do not let net use two opins */
+ assert(rr_node[rt_root->inode].type == SOURCE);
+ rt_root->re_expand = false;
+ }
+
+ // reexplore route tree from root to add any new nodes (buildheap afterwards)
+#ifdef PROFILE
+ clock_t route_tree_start = clock();
+#endif
+ add_route_tree_to_heap(rt_root, target_node, target_criticality,
+ astar_fac);
+ heap_::build_heap(); // via sifting down everything
+ // if (itarget == num_sinks && itarget > 800) {
+ // vpr_printf_info("heap for target %d: ", itarget);
+ // heap_::verify_extract_top();
+ // }
+#ifdef PROFILE
+ build_heap_time += static_cast<float>(clock() - route_tree_start) / CLOCKS_PER_SEC;
+#endif
+
+
+ // cheapest s_heap (gives index to rr_node) in current route tree to be expanded on
+ struct s_heap* cheapest = get_heap_head();
+
+ if (cheapest == NULL) { /* Infeasible routing. No possible path for net. */
+ vpr_printf_info("Cannot route net #%d (%s) to sink #%d -- no possible path.\n",
+ inet, g_clbs_nlist.net[inet].name, itarget);
+ reset_path_costs();
+ free_route_tree(rt_root);
+ return (false);
+ }
+
+ inode = cheapest->index;
+ while (inode != target_node) {
+ old_total_cost = rr_node_route_inf[inode].path_cost;
+ new_total_cost = cheapest->cost;
+
+ if (old_total_cost > 0.99 * HUGE_POSITIVE_FLOAT) /* First time touched. */
+ old_back_cost = HUGE_POSITIVE_FLOAT;
+ else
+ old_back_cost = rr_node_route_inf[inode].backward_path_cost;
+
+ new_back_cost = cheapest->backward_path_cost;
+
+ /* I only re-expand a node if both the "known" backward cost is lower *
+ * in the new expansion (this is necessary to prevent loops from *
+ * forming in the routing and causing havoc) *and* the expected total *
+ * cost to the sink is lower than the old value. Different R_upstream *
+ * values could make a path with lower back_path_cost less desirable *
+ * than one with higher cost. Test whether or not I should disallow *
+ * re-expansion based on a higher total cost. */
+
+ if (old_total_cost > new_total_cost && old_back_cost > new_back_cost) {
+ rr_node_route_inf[inode].prev_node = cheapest->u.prev_node;
+ rr_node_route_inf[inode].prev_edge = cheapest->prev_edge;
+ rr_node_route_inf[inode].path_cost = new_total_cost;
+ rr_node_route_inf[inode].backward_path_cost = new_back_cost;
+
+ if (old_total_cost > 0.99 * HUGE_POSITIVE_FLOAT) /* First time touched. */
+ add_to_mod_list(&rr_node_route_inf[inode].path_cost);
+
+ timing_driven_expand_neighbours(cheapest, inet, itry, bend_cost,
+ target_criticality, target_node, astar_fac,
+ highfanout_rlim);
+ }
+
+ free_heap_data(cheapest);
+ cheapest = get_heap_head();
+ // test heap property
+ // if (!heap_::is_valid()) {vpr_printf_info("invalid heap: "); heap_::pop_heap();}
+
+ if (cheapest == NULL) { /* Impossible routing. No path for net. */
+ vpr_printf_info("Cannot route net #%d (%s) to sink #%d -- no possible path.\n",
+ inet, g_clbs_nlist.net[inet].name, itarget);
+ reset_path_costs();
+ free_route_tree(rt_root);
+ return (false);
+ }
+
+ inode = cheapest->index;
+ }
+#ifdef PROFILE
+ time_on_criticality[target_criticality / criticality_per_bin] += static_cast<float>(clock() - sink_criticality_start) / CLOCKS_PER_SEC;
+ ++itry_on_criticality[target_criticality / criticality_per_bin];
+#endif
+ /* NB: In the code below I keep two records of the partial routing: the *
+ * traceback and the route_tree. The route_tree enables fast recomputation *
+ * of the Elmore delay to each node in the partial routing. The traceback *
+ * lets me reuse all the routines written for breadth-first routing, which *
+ * all take a traceback structure as input. Before this routine exits the *
+ * route_tree structure is destroyed; only the traceback is needed at that *
+ * point. */
+
+ rr_node_route_inf[inode].target_flag--; /* Connected to this SINK. */
+ new_route_start_tptr = update_traceback(cheapest, inet);
+ rt_node_of_sink[target_pin] = update_route_tree(cheapest);
+ free_heap_data(cheapest);
+ pathfinder_update_one_cost(new_route_start_tptr, 1, pres_fac);
+
+ empty_heap();
+ reset_path_costs();
+ }
+#ifdef PROFILE
+ if (!time_to_build_heap.empty()) time_to_build_heap[num_sinks / fanout_per_bin] += build_heap_time;
+#endif
+ /* For later timing analysis. */
+
+ update_net_delays_from_route_tree(net_delay, rt_node_of_sink, inet);
+ free_route_tree(rt_root);
+ return (true);
+}
+
+static void add_route_tree_to_heap(t_rt_node * rt_node, int target_node,
+ float target_criticality, float astar_fac) {
+
+ /* Puts the entire partial routing below and including rt_node onto the heap *
+ * (except for those parts marked as not to be expanded) by calling itself *
+ * recursively. */
+
+ int inode;
+ t_rt_node *child_node;
+ t_linked_rt_edge *linked_rt_edge;
+ float tot_cost, backward_path_cost, R_upstream;
+
+ /* Pre-order depth-first traversal */
+
+ if (rt_node->re_expand) {
+ inode = rt_node->inode;
+ backward_path_cost = target_criticality * rt_node->Tdel;
+ R_upstream = rt_node->R_upstream;
+#ifndef OP_STRONG_LOOKAHEAD
+ tot_cost = backward_path_cost
+ + astar_fac
+ * get_timing_driven_expected_cost(inode, target_node,
+ target_criticality, R_upstream);
+#else
+ tot_cost = backward_path_cost
+ + astar_fac
+ * get_timing_driven_multiple_wirelengths_expected_cost(inode, target_node,
+ target_criticality, R_upstream);
+#endif
+ heap_::push_back_node(inode, tot_cost, NO_PREVIOUS, NO_PREVIOUS,
+ backward_path_cost, R_upstream);
+
+ }
+
+ linked_rt_edge = rt_node->u.child_list;
+
+ while (linked_rt_edge != NULL) {
+ child_node = linked_rt_edge->child;
+ add_route_tree_to_heap(child_node, target_node, target_criticality,
+ astar_fac);
+ linked_rt_edge = linked_rt_edge->next;
+ }
+}
+
+static void timing_driven_expand_neighbours(struct s_heap *current,
+ int inet, int itry,
+ float bend_cost, float criticality_fac, int target_node,
+ float astar_fac, int highfanout_rlim) {
+
+ /* Puts all the rr_nodes adjacent to current on the heap. rr_nodes outside *
+ * the expanded bounding box specified in route_bb are not added to the *
+ * heap. */
+
+ float new_R_upstream;
+
+ int inode = current->index;
+ float old_back_pcost = current->backward_path_cost;
+ float R_upstream = current->R_upstream;
+ int num_edges = rr_node[inode].get_num_edges();
+
+ int target_x = rr_node[target_node].get_xhigh();
+ int target_y = rr_node[target_node].get_yhigh();
+ bool high_fanout = g_clbs_nlist.net[inet].num_sinks() >= HIGH_FANOUT_NET_LIM;
+
+ for (int iconn = 0; iconn < num_edges; iconn++) {
+ int to_node = rr_node[inode].edges[iconn];
+
+ if (high_fanout) {
+ // since target node is an IPIN, xhigh and xlow are the same (same for y values)
+ if (rr_node[to_node].get_xhigh() < target_x - highfanout_rlim
+ || rr_node[to_node].get_xlow() > target_x + highfanout_rlim
+ || rr_node[to_node].get_yhigh() < target_y - highfanout_rlim
+ || rr_node[to_node].get_ylow() > target_y + highfanout_rlim){
+ continue; /* Node is outside high fanout bin. */
+ }
+ }
+ else if (rr_node[to_node].get_xhigh() < route_bb[inet].xmin
+ || rr_node[to_node].get_xlow() > route_bb[inet].xmax
+ || rr_node[to_node].get_yhigh() < route_bb[inet].ymin
+ || rr_node[to_node].get_ylow() > route_bb[inet].ymax)
+ continue; /* Node is outside (expanded) bounding box. */
+
+
+ /* Prune away IPINs that lead to blocks other than the target one. Avoids *
+ * the issue of how to cost them properly so they don't get expanded before *
+ * more promising routes, but makes route-throughs (via CLBs) impossible. *
+ * Change this if you want to investigate route-throughs. */
+
+ t_rr_type to_type = rr_node[to_node].type;
+ if (to_type == IPIN
+ && (rr_node[to_node].get_xhigh() != target_x
+ || rr_node[to_node].get_yhigh() != target_y))
+ continue;
+
+ /* new_back_pcost stores the "known" part of the cost to this node -- the *
+ * congestion cost of all the routing resources back to the existing route *
+ * plus the known delay of the total path back to the source. new_tot_cost *
+ * is this "known" backward cost + an expected cost to get to the target. */
+
+ float new_back_pcost = old_back_pcost
+ + (1. - criticality_fac) * get_rr_cong_cost(to_node);
+
+ int iswitch = rr_node[inode].switches[iconn];
+ if (g_rr_switch_inf[iswitch].buffered) {
+ new_R_upstream = g_rr_switch_inf[iswitch].R;
+ } else {
+ new_R_upstream = R_upstream + g_rr_switch_inf[iswitch].R;
+ }
+
+ float Tdel = rr_node[to_node].C * (new_R_upstream + 0.5 * rr_node[to_node].R);
+ Tdel += g_rr_switch_inf[iswitch].Tdel;
+ new_R_upstream += rr_node[to_node].R;
+ new_back_pcost += criticality_fac * Tdel;
+
+ if (bend_cost != 0.) {
+ t_rr_type from_type = rr_node[inode].type;
+ to_type = rr_node[to_node].type;
+ if ((from_type == CHANX && to_type == CHANY)
+ || (from_type == CHANY && to_type == CHANX))
+ new_back_pcost += bend_cost;
+ }
+
+#ifndef OP_STRONG_LOOKAHEAD
+ float expected_cost = get_timing_driven_expected_cost(to_node, target_node,
+ criticality_fac, new_R_upstream);
+#else
+ float expected_cost = get_timing_driven_multiple_wirelengths_expected_cost(to_node, target_node,
+ criticality_fac, new_R_upstream);
+#endif
+ float new_tot_cost = new_back_pcost + astar_fac * expected_cost;
+
+ node_to_heap(to_node, new_tot_cost, inode, iconn, new_back_pcost,
+ new_R_upstream);
+
+ } /* End for all neighbours */
+}
+
+#ifndef OP_STRONG_LOOKAHEAD
+static float get_timing_driven_expected_cost(int inode, int target_node,
+ float criticality_fac, float R_upstream) {
+
+ /* Determines the expected cost (due to both delay and resouce cost) to reach *
+ * the target node from inode. It doesn't include the cost of inode -- *
+ * that's already in the "known" path_cost. */
+
+ t_rr_type rr_type;
+ int cost_index, ortho_cost_index, num_segs_same_dir, num_segs_ortho_dir;
+ float expected_cost, cong_cost, Tdel;
+
+ rr_type = rr_node[inode].type;
+
+ if (rr_type == CHANX || rr_type == CHANY) {
+
+#ifdef INTERPOSER_BASED_ARCHITECTURE
+ int num_interposer_hops = get_num_expected_interposer_hops_to_target(inode, target_node);
+#endif
+
+ num_segs_same_dir = get_expected_segs_to_target(inode, target_node,
+ &num_segs_ortho_dir);
+ cost_index = rr_node[inode].get_cost_index();
+ ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;
+
+ cong_cost = num_segs_same_dir * rr_indexed_data[cost_index].base_cost
+ + num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].base_cost;
+ cong_cost += rr_indexed_data[IPIN_COST_INDEX].base_cost
+ + rr_indexed_data[SINK_COST_INDEX].base_cost;
+
+ Tdel =
+ num_segs_same_dir * rr_indexed_data[cost_index].T_linear
+ + num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].T_linear
+ + num_segs_same_dir * num_segs_same_dir
+ * rr_indexed_data[cost_index].T_quadratic
+ + num_segs_ortho_dir * num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].T_quadratic
+ + R_upstream
+ * (num_segs_same_dir
+ * rr_indexed_data[cost_index].C_load
+ + num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].C_load);
+
+ Tdel += rr_indexed_data[IPIN_COST_INDEX].T_linear;
+
+#ifdef INTERPOSER_BASED_ARCHITECTURE
+ float interposer_hop_delay = (float)delay_increase * 1e-12;
+ Tdel += num_interposer_hops * interposer_hop_delay;
+#endif
+
+ expected_cost = criticality_fac * Tdel
+ + (1. - criticality_fac) * cong_cost;
+ return (expected_cost);
+ }
+
+ else if (rr_type == IPIN) { /* Change if you're allowing route-throughs */
+ return (rr_indexed_data[SINK_COST_INDEX].base_cost);
+ }
+
+ else { /* Change this if you want to investigate route-throughs */
+ return (0.);
+ }
+}
+
+#else
+static float get_timing_driven_multiple_wirelengths_expected_cost(int inode, int target_node,
+ float criticality_fac, float R_upstream) {
+
+ /* Determines the expected cost (due to both delay and resouce cost) to reach *
+ * the target node from inode. It doesn't include the cost of inode -- *
+ * that's already in the "known" path_cost. */
+
+ t_rr_type rr_type;
+ int cost_index, ortho_cost_index, num_segs_same_dir, num_segs_ortho_dir;
+ float expected_cost, cong_cost, Tdel;
+
+ rr_type = rr_node[inode].type;
+
+ if (rr_type == CHANX || rr_type == CHANY) {
+
+ /* OP: Want to account for multiple wirelengths by breaking the assumption that
+ a route will stay on the same kind of node that it's currently on. So here I
+ get the minimum expected cost across all CHANX cost indices. This significantly
+ drives up routing time, but is still much faster than running VPR with
+ astar_fac = 0.
+ */
+
+ float minimum_cost = -1.0;
+ for (cost_index = CHANX_COST_INDEX_START; cost_index < CHANX_COST_INDEX_START + (num_rr_indexed_data - CHANX_COST_INDEX_START)/2; cost_index++){
+
+ num_segs_same_dir = get_expected_segs_to_target(inode, cost_index, target_node,
+ &num_segs_ortho_dir);
+ ortho_cost_index = cost_index;
+
+ cong_cost = num_segs_same_dir * rr_indexed_data[cost_index].base_cost
+ + num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].base_cost;
+ cong_cost += rr_indexed_data[IPIN_COST_INDEX].base_cost
+ + rr_indexed_data[SINK_COST_INDEX].base_cost;
+
+ Tdel =
+ num_segs_same_dir * rr_indexed_data[cost_index].T_linear
+ + num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].T_linear
+ + num_segs_same_dir * num_segs_same_dir
+ * rr_indexed_data[cost_index].T_quadratic
+ + num_segs_ortho_dir * num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].T_quadratic
+ + R_upstream
+ * (num_segs_same_dir
+ * rr_indexed_data[cost_index].C_load
+ + num_segs_ortho_dir
+ * rr_indexed_data[ortho_cost_index].C_load);
+
+ Tdel += rr_indexed_data[IPIN_COST_INDEX].T_linear;
+
+ expected_cost = criticality_fac * Tdel
+ + (1. - criticality_fac) * cong_cost;
+
+ if (expected_cost < minimum_cost || minimum_cost < 0){
+ minimum_cost = expected_cost;
+ }
+ }
+ //assert( minimum_cost >= 0 );
+ return (minimum_cost);
+ }
+
+ else if (rr_type == IPIN) { /* Change if you're allowing route-throughs */
+ return (rr_indexed_data[SINK_COST_INDEX].base_cost);
+ }
+
+ else { /* Change this if you want to investigate route-throughs */
+ return (0.);
+ }
+}
+#endif
+
+#ifdef INTERPOSER_BASED_ARCHITECTURE
+static int get_num_expected_interposer_hops_to_target(int inode, int target_node)
+{
+ /*
+ Description:
+ returns the expected number of times you have to cross the
+ interposer in order to go from inode to target_node.
+ This does not include inode itself.
+
+ Assumptions:
+ 1- Cuts are horizontal
+ 2- target_node is a terminal pin (hence its ylow==yhigh)
+ 3- wires that go through the interposer are uni-directional
+
+ --------- y=150
+ | |
+ --------- y=100
+ | |
+ --------- y=50
+ | |
+ --------- y=0
+
+ num_cuts = 2, cut_step = 50, cut_locations = {50, 100}
+ */
+ int y_start; /* start point y-coordinate. (y-coordinate at the *end* of wire 'i') */
+ int y_end; /* destination (target) y-coordinate */
+ int cut_i, y_cut_location, num_expected_hops;
+ t_rr_type rr_type;
+
+ num_expected_hops = 0;
+ y_end = rr_node[target_node].get_ylow();
+ rr_type = rr_node[inode].type;
+
+ if(rr_type == CHANX)
+ { /* inode is a horizontal wire */
+ /* the ylow and yhigh are the same */
+ assert(rr_node[inode].get_ylow() == rr_node[inode].get_yhigh());
+ y_start = rr_node[inode].get_ylow();
+ }
+ else
+ { /* inode is a CHANY */
+ if(rr_node[inode].direction == INC_DIRECTION)
+ {
+ y_start = rr_node[inode].get_yhigh();
+ }
+ else if(rr_node[inode].direction == DEC_DIRECTION)
+ {
+ y_start = rr_node[inode].get_ylow();
+ }
+ else
+ {
+ /* this means direction is BIDIRECTIONAL! Error out. */
+ y_start = -1;
+ assert(rr_node[inode].direction!=BI_DIRECTION);
+ }
+ }
+
+ /* for every cut, is it between 'i' and 'target'? */
+ for(cut_i=0 ; cut_i<num_cuts; ++cut_i)
+ {
+ y_cut_location = arch_cut_locations[cut_i];
+ if( (y_start < y_cut_location && y_cut_location < y_end) ||
+ (y_end < y_cut_location && y_cut_location < y_start))
+ {
+ ++num_expected_hops;
+ }
+ }
+
+ /* Make there is no off-by-1 error.For current node i:
+ if it's a vertical wire, node 'i' itself may be crossing the interposer.
+ */
+ if(rr_type == CHANY)
+ {
+ /* for every cut, does it cut wire 'i'? */
+ for(cut_i=0 ; cut_i<num_cuts; ++cut_i)
+ {
+ y_cut_location = arch_cut_locations[cut_i];
+ if(rr_node[inode].get_ylow() < y_cut_location && y_cut_location < rr_node[inode].get_yhigh())
+ {
+ ++num_expected_hops;
+ }
+ }
+ }
+
+ return num_expected_hops;
+}
+#endif
+
+/* Macro used below to ensure that fractions are rounded up, but floating *
+ * point values very close to an integer are rounded to that integer. */
+#define ROUND_UP(x) (ceil (x - 0.001))
+
+#ifndef OP_STRONG_LOOKAHEAD
+static int get_expected_segs_to_target(int inode, int target_node,
+ int *num_segs_ortho_dir_ptr) {
+
+ /* Returns the number of segments the same type as inode that will be needed *
+ * to reach target_node (not including inode) in each direction (the same *
+ * direction (horizontal or vertical) as inode and the orthogonal direction).*/
+
+ t_rr_type rr_type;
+ int target_x, target_y, num_segs_same_dir, cost_index, ortho_cost_index;
+ int no_need_to_pass_by_clb;
+ float inv_length, ortho_inv_length, ylow, yhigh, xlow, xhigh;
+
+ #ifdef INTERPOSER_BASED_ARCHITECTURE
+ int num_expected_hops = get_num_expected_interposer_hops_to_target(inode, target_node);
+ #endif
+
+ target_x = rr_node[target_node].get_xlow();
+ target_y = rr_node[target_node].get_ylow();
+ cost_index = rr_node[inode].get_cost_index();
+ inv_length = rr_indexed_data[cost_index].inv_length;
+ ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;
+ ortho_inv_length = rr_indexed_data[ortho_cost_index].inv_length;
+ rr_type = rr_node[inode].type;
+
+ if (rr_type == CHANX) {
+ ylow = rr_node[inode].get_ylow();
+ xhigh = rr_node[inode].get_xhigh();
+ xlow = rr_node[inode].get_xlow();
+
+ /* Count vertical (orthogonal to inode) segs first. */
+
+ if (ylow > target_y) { /* Coming from a row above target? */
+ *num_segs_ortho_dir_ptr =
+ (int)(ROUND_UP((ylow - target_y + 1.) * ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else if (ylow < target_y - 1) { /* Below the CLB bottom? */
+ *num_segs_ortho_dir_ptr = (int)(ROUND_UP((target_y - ylow) *
+ ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else { /* In a row that passes by target CLB */
+ *num_segs_ortho_dir_ptr = 0;
+ no_need_to_pass_by_clb = 0;
+ }
+
+#ifdef INTERPOSER_BASED_ARCHITECTURE
+ (*num_segs_ortho_dir_ptr) = (*num_segs_ortho_dir_ptr) + 2*num_expected_hops;
+#endif
+
+ /* Now count horizontal (same dir. as inode) segs. */
+
+ if (xlow > target_x + no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((xlow - no_need_to_pass_by_clb -
+ target_x) * inv_length));
+ } else if (xhigh < target_x - no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((target_x - no_need_to_pass_by_clb -
+ xhigh) * inv_length));
+ } else {
+ num_segs_same_dir = 0;
+ }
+ }
+
+ else { /* inode is a CHANY */
+ ylow = rr_node[inode].get_ylow();
+ yhigh = rr_node[inode].get_yhigh();
+ xlow = rr_node[inode].get_xlow();
+
+ /* Count horizontal (orthogonal to inode) segs first. */
+
+ if (xlow > target_x) { /* Coming from a column right of target? */
+ *num_segs_ortho_dir_ptr = (int)(
+ ROUND_UP((xlow - target_x + 1.) * ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else if (xlow < target_x - 1) { /* Left of and not adjacent to the CLB? */
+ *num_segs_ortho_dir_ptr = (int)(ROUND_UP((target_x - xlow) *
+ ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else { /* In a column that passes by target CLB */
+ *num_segs_ortho_dir_ptr = 0;
+ no_need_to_pass_by_clb = 0;
+ }
+
+ /* Now count vertical (same dir. as inode) segs. */
+
+ if (ylow > target_y + no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((ylow - no_need_to_pass_by_clb -
+ target_y) * inv_length));
+ } else if (yhigh < target_y - no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((target_y - no_need_to_pass_by_clb -
+ yhigh) * inv_length));
+ } else {
+ num_segs_same_dir = 0;
+ }
+
+#ifdef INTERPOSER_BASED_ARCHITECTURE
+ num_segs_same_dir = num_segs_same_dir + 2*num_expected_hops;
+#endif
+ }
+
+ return (num_segs_same_dir);
+}
+
+#else
+static int get_expected_segs_to_target(int inode, int via_cost_index, int target_node,
+ int *num_segs_ortho_dir_ptr) {
+
+ /* Returns the number of segments the same type as inode that will be needed *
+ * to reach target_node (not including inode) in each direction (the same *
+ * direction (horizontal or vertical) as inode and the orthogonal direction).*/
+
+ /* OP: 'via_cost_index' is the cost index representing the type of node that we
+ will stay on for teh remainder of the routing */
+
+ t_rr_type rr_type;
+ int target_x, target_y, num_segs_same_dir, cost_index;
+ int no_need_to_pass_by_clb;
+ float inv_length, ortho_inv_length, ylow, yhigh, xlow, xhigh;
+
+ target_x = rr_node[target_node].get_xlow();
+ target_y = rr_node[target_node].get_ylow();
+ cost_index = via_cost_index;
+ inv_length = rr_indexed_data[cost_index].inv_length;
+ ortho_inv_length = inv_length;
+ rr_type = rr_node[inode].type;
+
+ if (rr_type == CHANX) {
+ ylow = rr_node[inode].get_ylow();
+ xhigh = rr_node[inode].get_xhigh();
+ xlow = rr_node[inode].get_xlow();
+
+ /* Count vertical (orthogonal to inode) segs first. */
+
+ if (ylow > target_y) { /* Coming from a row above target? */
+ *num_segs_ortho_dir_ptr =
+ (int)(ROUND_UP((ylow - target_y + 1.) * ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else if (ylow < target_y - 1) { /* Below the CLB bottom? */
+ *num_segs_ortho_dir_ptr = (int)(ROUND_UP((target_y - ylow) *
+ ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else { /* In a row that passes by target CLB */
+ *num_segs_ortho_dir_ptr = 0;
+ no_need_to_pass_by_clb = 0;
+ }
+
+ /* Now count horizontal (same dir. as inode) segs. */
+
+ if (xlow > target_x + no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((xlow - no_need_to_pass_by_clb -
+ target_x) * inv_length));
+ } else if (xhigh < target_x - no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((target_x - no_need_to_pass_by_clb -
+ xhigh) * inv_length));
+ } else {
+ num_segs_same_dir = 0;
+ }
+ }
+
+ else { /* inode is a CHANY */
+ ylow = rr_node[inode].get_ylow();
+ yhigh = rr_node[inode].get_yhigh();
+ xlow = rr_node[inode].get_xlow();
+
+ /* Count horizontal (orthogonal to inode) segs first. */
+
+ if (xlow > target_x) { /* Coming from a column right of target? */
+ *num_segs_ortho_dir_ptr = (int)(
+ ROUND_UP((xlow - target_x + 1.) * ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else if (xlow < target_x - 1) { /* Left of and not adjacent to the CLB? */
+ *num_segs_ortho_dir_ptr = (int)(ROUND_UP((target_x - xlow) *
+ ortho_inv_length));
+ no_need_to_pass_by_clb = 1;
+ } else { /* In a column that passes by target CLB */
+ *num_segs_ortho_dir_ptr = 0;
+ no_need_to_pass_by_clb = 0;
+ }
+
+ /* Now count vertical (same dir. as inode) segs. */
+
+ if (ylow > target_y + no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((ylow - no_need_to_pass_by_clb -
+ target_y) * inv_length));
+ } else if (yhigh < target_y - no_need_to_pass_by_clb) {
+ num_segs_same_dir = (int)(ROUND_UP((target_y - no_need_to_pass_by_clb -
+ yhigh) * inv_length));
+ } else {
+ num_segs_same_dir = 0;
+ }
+ }
+
+ return (num_segs_same_dir);
+}
+#endif
+
+static void update_rr_base_costs(int inet, float largest_criticality) {
+
+ /* Changes the base costs of different types of rr_nodes according to the *
+ * criticality, fanout, etc. of the current net being routed (inet). */
+
+ float fanout, factor;
+ int index;
+
+ fanout = g_clbs_nlist.net[inet].num_sinks();
+
+ /* Other reasonable values for factor include fanout and 1 */
+ factor = sqrt(fanout);
+
+ for (index = CHANX_COST_INDEX_START; index < num_rr_indexed_data; index++) {
+ if (rr_indexed_data[index].T_quadratic > 0.) { /* pass transistor */
+ rr_indexed_data[index].base_cost =
+ rr_indexed_data[index].saved_base_cost * factor;
+ } else {
+ rr_indexed_data[index].base_cost =
+ rr_indexed_data[index].saved_base_cost;
+ }
+ }
+}
+
+/* Nets that have high fanout can take a very long time to route. Routing for sinks that are part of high-fanout nets should be
+ done within a rectangular 'bin' centered around a target (as opposed to the entire net bounding box) the size of which is returned by this function. */
+static int mark_node_expansion_by_bin(int inet, int target_node,
+ t_rt_node * rt_node) {
+ int target_xlow, target_ylow, target_xhigh, target_yhigh;
+ int rlim = 1;
+ int inode;
+ float area;
+ bool success;
+ t_linked_rt_edge *linked_rt_edge;
+ t_rt_node * child_node;
+
+ target_xlow = rr_node[target_node].get_xlow();
+ target_ylow = rr_node[target_node].get_ylow();
+ target_xhigh = rr_node[target_node].get_xhigh();
+ target_yhigh = rr_node[target_node].get_yhigh();
+
+ if (g_clbs_nlist.net[inet].num_sinks() < HIGH_FANOUT_NET_LIM) {
+ /* This algorithm only applies to high fanout nets */
+ return 1;
+ }
+ if (rt_node == NULL || rt_node->u.child_list == NULL) {
+ /* If unknown traceback, set radius of bin to be size of chip */
+ rlim = max(nx + 2, ny + 2);
+ return rlim;
+ }
+
+ area = (route_bb[inet].xmax - route_bb[inet].xmin)
+ * (route_bb[inet].ymax - route_bb[inet].ymin);
+ if (area <= 0) {
+ area = 1;
+ }
+
+ rlim = (int)(ceil(sqrt((float) area / (float) g_clbs_nlist.net[inet].num_sinks())));
+
+ success = false;
+ /* determine quickly a feasible bin radius to route sink for high fanout nets
+ this is necessary to prevent super long runtimes for high fanout nets; in best case, a reduction in complexity from O(N^2logN) to O(NlogN) (Swartz fast router)
+ */
+ linked_rt_edge = rt_node->u.child_list;
+ while (success == false && linked_rt_edge != NULL) {
+ while (linked_rt_edge != NULL && success == false) {
+ child_node = linked_rt_edge->child;
+ inode = child_node->inode;
+ if (!(rr_node[inode].type == IPIN || rr_node[inode].type == SINK)) {
+ if (rr_node[inode].get_xlow() <= target_xhigh + rlim
+ && rr_node[inode].get_xhigh() >= target_xhigh - rlim
+ && rr_node[inode].get_ylow() <= target_yhigh + rlim
+ && rr_node[inode].get_yhigh() >= target_yhigh - rlim) {
+ success = true;
+ }
+ }
+ linked_rt_edge = linked_rt_edge->next;
+ }
+
+ if (success == false) {
+ if (rlim > max(nx + 2, ny + 2)) {
+ vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
+ "VPR internal error, net %s has paths that are not found in traceback.\n", g_clbs_nlist.net[inet].name);
+ }
+ /* if sink not in bin, increase bin size until fit */
+ rlim *= 2;
+ } else {
+ /* Sometimes might just catch a wire in the end segment, need to give it some channel space to explore */
+ rlim += 4;
+ }
+ linked_rt_edge = rt_node->u.child_list;
+ }
+
+ /* adjust rlim to account for width/height of block containing the target sink */
+ int target_span = max( target_xhigh - target_xlow, target_yhigh - target_ylow );
+ rlim += target_span;
+
+ /* redetermine expansion based on rlim */
+ linked_rt_edge = rt_node->u.child_list;
+ while (linked_rt_edge != NULL) {
+ child_node = linked_rt_edge->child;
+ inode = child_node->inode;
+ if (!(rr_node[inode].type == IPIN || rr_node[inode].type == SINK)) {
+ if (rr_node[inode].get_xlow() <= target_xhigh + rlim
+ && rr_node[inode].get_xhigh() >= target_xhigh - rlim
+ && rr_node[inode].get_ylow() <= target_yhigh + rlim
+ && rr_node[inode].get_yhigh() >= target_yhigh - rlim) {
+ child_node->re_expand = true;
+ } else {
+ child_node->re_expand = false;
+ }
+ }
+ linked_rt_edge = linked_rt_edge->next;
+ }
+ return rlim;
+}
+#define ERROR_TOL 0.0001
+
+static void timing_driven_check_net_delays(float **net_delay) {
+
+ /* Checks that the net delays computed incrementally during timing driven *
+ * routing match those computed from scratch by the net_delay.c module. */
+
+ unsigned int inet, ipin;
+ float **net_delay_check;
+
+ t_chunk list_head_net_delay_check_ch = {NULL, 0, NULL};
+
+ /*struct s_linked_vptr *ch_list_head_net_delay_check;*/
+
+ net_delay_check = alloc_net_delay(&list_head_net_delay_check_ch, g_clbs_nlist.net,
+ g_clbs_nlist.net.size());
+ load_net_delay_from_routing(net_delay_check, g_clbs_nlist.net, g_clbs_nlist.net.size());
+
+ for (inet = 0; inet < g_clbs_nlist.net.size(); inet++) {
+ for (ipin = 1; ipin < g_clbs_nlist.net[inet].pins.size(); ipin++) {
+ if (net_delay_check[inet][ipin] == 0.) { /* Should be only GLOBAL nets */
+ if (fabs(net_delay[inet][ipin]) > ERROR_TOL) {
+ vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
+ "in timing_driven_check_net_delays: net %d pin %d.\n"
+ "\tIncremental calc. net_delay is %g, but from scratch net delay is %g.\n",
+ inet, ipin, net_delay[inet][ipin], net_delay_check[inet][ipin]);
+ }
+ } else {
+ if (fabs(1.0 - net_delay[inet][ipin] / net_delay_check[inet][ipin]) > ERROR_TOL) {
+ vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
+ "in timing_driven_check_net_delays: net %d pin %d.\n"
+ "\tIncremental calc. net_delay is %g, but from scratch net delay is %g.\n",
+ inet, ipin, net_delay[inet][ipin], net_delay_check[inet][ipin]);
+ }
+ }
+ }
+ }
+
+ free_net_delay(net_delay_check, &list_head_net_delay_check_ch);
+ vpr_printf_info("Completed net delay value cross check successfully.\n");
+}
+
+
+/* Detect if net should be routed or not */
+static bool should_route_net(int inet) {
+ t_trace * tptr = trace_head[inet];
+
+ if (tptr == NULL) {
+ /* No routing yet. */
+ return true;
+ }
+
+ for (;;) {
+ int inode = tptr->index;
+ int occ = rr_node[inode].get_occ();
+ int capacity = rr_node[inode].get_capacity();
+
+ if (occ > capacity) {
+ return true; /* overuse detected */
+ }
+
+ if (rr_node[inode].type == SINK) {
+ tptr = tptr->next; /* Skip next segment. */
+ if (tptr == NULL)
+ break;
+ }
+
+ tptr = tptr->next;
+
+ } /* End while loop -- did an entire traceback. */
+
+ return false; /* Current route has no overuse */
+}
+
+static bool early_exit_heuristic(const t_router_opts& router_opts) {
+ /* Early exit code for cases where it is obvious that a successful route will not be found
+ Heuristic: If total wirelength used in first routing iteration is X% of total available wirelength, exit */
+ int total_wirelength = 0;
+ int available_wirelength = 0;
+
+ for (int i = 0; i < num_rr_nodes; ++i) {
+ if (rr_node[i].type == CHANX || rr_node[i].type == CHANY) {
+ available_wirelength += 1 +
+ rr_node[i].get_xhigh() - rr_node[i].get_xlow() +
+ rr_node[i].get_yhigh() - rr_node[i].get_ylow();
+ }
+ }
+
+ for (unsigned int inet = 0; inet < g_clbs_nlist.net.size(); ++inet) {
+ if (g_clbs_nlist.net[inet].is_global == false
+ && g_clbs_nlist.net[inet].num_sinks() != 0) { /* Globals don't count. */
+ int bends, wirelength, segments;
+ get_num_bends_and_length(inet, &bends, &wirelength, &segments);
+
+ total_wirelength += wirelength;
+ }
+ }
+ vpr_printf_info("Wire length after first iteration %d, total available wire length %d, ratio %g\n",
+ total_wirelength, available_wirelength,
+ (float) (total_wirelength) / (float) (available_wirelength));
+ if ((float) (total_wirelength) / (float) (available_wirelength)> FIRST_ITER_WIRELENTH_LIMIT) {
+ vpr_printf_info("Wire length usage ratio exceeds limit of %g, fail routing.\n",
+ FIRST_ITER_WIRELENTH_LIMIT);
+ return true;
+ }
+ vpr_printf_info("--------- ---------- ----------- ---------------------\n");
+ vpr_printf_info("Iteration Time Crit Path Overused RR Nodes\n");
+ vpr_printf_info("--------- ---------- ----------- ---------------------\n");
+ return false;
+}
+
