| #include <cstdio> |
| #include <cstring> |
| #include <cmath> |
| #include <time.h> |
| #include <limits> |
| |
| #include "vtr_assert.h" |
| #include "vtr_ndmatrix.h" |
| #include "vtr_log.h" |
| #include "vtr_util.h" |
| #include "vtr_math.h" |
| #include "vtr_memory.h" |
| #include "vtr_time.h" |
| #include "vtr_geometry.h" |
| |
| #include "arch_util.h" |
| |
| #include "vpr_types.h" |
| #include "globals.h" |
| #include "place_and_route.h" |
| #include "route_common.h" |
| #include "route_tree_timing.h" |
| #include "route_timing.h" |
| #include "route_export.h" |
| #include "rr_graph.h" |
| #include "timing_place_lookup.h" |
| #include "read_xml_arch_file.h" |
| #include "echo_files.h" |
| #include "atom_netlist.h" |
| #include "rr_graph2.h" |
| #include "place_util.h" |
| // all functions in profiling:: namespace, which are only activated if PROFILE is defined |
| #include "route_profiling.h" |
| #include "router_delay_profiling.h" |
| #include "place_delay_model.h" |
| |
| /*To compute delay between blocks we calculate the delay between */ |
| /*different nodes in the FPGA. From this procedure we generate |
| * a lookup table which tells us the delay between different locations in*/ |
| /*the FPGA */ |
| |
| /*the delta arrays are used to contain the best case routing delay */ |
| /*between different locations on the FPGA. */ |
| |
| //#define VERBOSE |
| |
| constexpr float UNINITIALIZED_DELTA = -1; //Indicates the delta delay value has not been calculated |
| constexpr float EMPTY_DELTA = -2; //Indicates delta delay from/to an EMPTY block |
| constexpr float IMPOSSIBLE_DELTA = std::numeric_limits<float>::infinity(); //Indicates there is no valid delta delay |
| |
| struct t_profile_loc { |
| t_profile_loc(int x, int y, std::vector<vtr::Point<int>> delta_values) |
| : root(x, y) |
| , deltas(delta_values) {} |
| |
| vtr::Point<int> root; |
| std::vector<vtr::Point<int>> deltas; |
| }; |
| |
| struct t_profile_info { |
| std::vector<t_profile_loc> locations; |
| |
| int max_delta_x; |
| int max_delta_y; |
| }; |
| |
| /*** Function Prototypes *****/ |
| static t_chan_width setup_chan_width(const t_router_opts& router_opts, |
| t_chan_width_dist chan_width_dist); |
| |
| static float route_connection_delay( |
| const RouterDelayProfiler& route_profiler, |
| int source_x_loc, |
| int source_y_loc, |
| int sink_x_loc, |
| int sink_y_loc, |
| const t_router_opts& router_opts, |
| bool measure_directconnect); |
| |
| static void generic_compute_matrix( |
| const RouterDelayProfiler& route_profiler, |
| vtr::Matrix<std::vector<float>>& matrix, |
| int source_x, |
| int source_y, |
| int start_x, |
| int start_y, |
| int end_x, |
| int end_y, |
| const t_router_opts& router_opts, |
| bool measure_directconnect); |
| |
| static vtr::Matrix<float> compute_delta_delays( |
| const RouterDelayProfiler& route_profiler, |
| const t_placer_opts& palcer_opts, |
| const t_router_opts& router_opts, |
| bool measure_directconnect, |
| size_t longest_length); |
| |
| float delay_reduce(std::vector<float>& delays, e_reducer reducer); |
| |
| static vtr::Matrix<float> compute_delta_delay_model( |
| const RouterDelayProfiler& route_profiler, |
| const t_placer_opts& placer_opts, |
| const t_router_opts& router_opts, |
| bool measure_directconnect, |
| int longest_length); |
| |
| static bool find_direct_connect_sample_locations(const t_direct_inf* direct, |
| t_physical_tile_type_ptr from_type, |
| int from_pin, |
| int from_pin_class, |
| t_physical_tile_type_ptr to_type, |
| int to_pin, |
| int to_pin_class, |
| int* src_rr, |
| int* sink_rr); |
| |
| static bool verify_delta_delays(const vtr::Matrix<float>& delta_delays); |
| |
| static int get_longest_segment_length(std::vector<t_segment_inf>& segment_inf); |
| |
| static void fix_empty_coordinates(vtr::Matrix<float>& delta_delays); |
| static void fix_uninitialized_coordinates(vtr::Matrix<float>& delta_delays); |
| |
| static float find_neightboring_average(vtr::Matrix<float>& matrix, int x, int y, int max_distance); |
| |
| /******* Globally Accessible Functions **********/ |
| |
| std::unique_ptr<PlaceDelayModel> compute_place_delay_model(const t_placer_opts& placer_opts, |
| const t_router_opts& router_opts, |
| t_det_routing_arch* det_routing_arch, |
| std::vector<t_segment_inf>& segment_inf, |
| t_chan_width_dist chan_width_dist, |
| const t_direct_inf* directs, |
| const int num_directs) { |
| vtr::ScopedStartFinishTimer timer("Computing placement delta delay look-up"); |
| |
| init_placement_context(); |
| |
| t_chan_width chan_width = setup_chan_width(router_opts, chan_width_dist); |
| |
| alloc_routing_structs(chan_width, router_opts, det_routing_arch, segment_inf, |
| directs, num_directs); |
| |
| const RouterLookahead* router_lookahead = get_cached_router_lookahead( |
| router_opts.lookahead_type, |
| router_opts.write_router_lookahead, |
| router_opts.read_router_lookahead, |
| segment_inf); |
| RouterDelayProfiler route_profiler(router_lookahead); |
| |
| int longest_length = get_longest_segment_length(segment_inf); |
| |
| /*now setup and compute the actual arrays */ |
| std::unique_ptr<PlaceDelayModel> place_delay_model; |
| if (placer_opts.delay_model_type == PlaceDelayModelType::DELTA) { |
| place_delay_model = std::make_unique<DeltaDelayModel>(); |
| } else if (placer_opts.delay_model_type == PlaceDelayModelType::DELTA_OVERRIDE) { |
| place_delay_model = std::make_unique<OverrideDelayModel>(); |
| } else { |
| VTR_ASSERT_MSG(false, "Invalid placer delay model"); |
| } |
| |
| if (placer_opts.read_placement_delay_lookup.empty()) { |
| place_delay_model->compute(route_profiler, placer_opts, router_opts, longest_length); |
| } else { |
| place_delay_model->read(placer_opts.read_placement_delay_lookup); |
| } |
| |
| if (!placer_opts.write_placement_delay_lookup.empty()) { |
| place_delay_model->write(placer_opts.write_placement_delay_lookup); |
| } |
| |
| /*free all data structures that are no longer needed */ |
| free_routing_structs(); |
| |
| return place_delay_model; |
| } |
| |
| void DeltaDelayModel::compute( |
| const RouterDelayProfiler& route_profiler, |
| const t_placer_opts& placer_opts, |
| const t_router_opts& router_opts, |
| int longest_length) { |
| router_opts_ = router_opts; |
| delays_ = compute_delta_delay_model( |
| route_profiler, |
| placer_opts, router_opts, /*measure_directconnect=*/true, |
| longest_length); |
| } |
| |
| void OverrideDelayModel::compute( |
| const RouterDelayProfiler& route_profiler, |
| const t_placer_opts& placer_opts, |
| const t_router_opts& router_opts, |
| int longest_length) { |
| router_opts_ = router_opts; |
| auto delays = compute_delta_delay_model( |
| route_profiler, |
| placer_opts, router_opts, /*measure_directconnect=*/false, |
| longest_length); |
| |
| base_delay_model_ = std::make_unique<DeltaDelayModel>(delays, router_opts); |
| |
| compute_override_delay_model(route_profiler); |
| } |
| |
| /******* File Accessible Functions **********/ |
| |
| std::vector<int> get_best_classes(enum e_pin_type pintype, t_physical_tile_type_ptr type) { |
| /* |
| * This function tries to identify the best pin classes to hook up |
| * for delay calculation. The assumption is that we should pick |
| * the pin class with the largest number of pins. This makes |
| * sense, since it ensures we pick commonly used pins, and |
| * removes order dependence on how the pins are specified |
| * in the architecture (except in the case were the two largest pin classes |
| * of a particular pintype have the same number of pins, in which case the |
| * first pin class is used). |
| */ |
| |
| std::vector<int> best_classes; |
| |
| //Collect all classes of matching type which do not have all their pins ignored |
| for (int i = 0; i < type->num_class; i++) { |
| if (type->class_inf[i].type == pintype) { |
| bool all_ignored = true; |
| for (int ipin = 0; ipin < type->class_inf[i].num_pins; ++ipin) { |
| int pin = type->class_inf[i].pinlist[ipin]; |
| if (!type->is_ignored_pin[pin]) { |
| all_ignored = false; |
| break; |
| } |
| } |
| if (!all_ignored) { |
| best_classes.push_back(i); |
| } |
| } |
| } |
| |
| //Sort classe so largest pin class is first |
| auto cmp_class = [&](int lhs, int rhs) { |
| return type->class_inf[lhs].num_pins > type->class_inf[rhs].num_pins; |
| }; |
| |
| std::stable_sort(best_classes.begin(), best_classes.end(), cmp_class); |
| |
| return best_classes; |
| } |
| |
| static int get_longest_segment_length(std::vector<t_segment_inf>& segment_inf) { |
| int length; |
| |
| length = 0; |
| for (size_t i = 0; i < segment_inf.size(); i++) { |
| if (segment_inf[i].length > length) |
| length = segment_inf[i].length; |
| } |
| return (length); |
| } |
| |
| static t_chan_width setup_chan_width(const t_router_opts& router_opts, |
| t_chan_width_dist chan_width_dist) { |
| /*we give plenty of tracks, this increases routability for the */ |
| /*lookup table generation */ |
| |
| int width_fac; |
| |
| if (router_opts.fixed_channel_width == NO_FIXED_CHANNEL_WIDTH) { |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| auto type = physical_tile_type(find_most_common_block_type(device_ctx.grid)); |
| |
| width_fac = 4 * type->num_pins; |
| /*this is 2x the value that binary search starts */ |
| /*this should be enough to allow most pins to */ |
| /*connect to tracks in the architecture */ |
| } else { |
| width_fac = router_opts.fixed_channel_width; |
| } |
| |
| return init_chan(width_fac, chan_width_dist); |
| } |
| |
| static float route_connection_delay( |
| const RouterDelayProfiler& route_profiler, |
| int source_x, |
| int source_y, |
| int sink_x, |
| int sink_y, |
| const t_router_opts& router_opts, |
| bool measure_directconnect) { |
| //Routes between the source and sink locations and calculates the delay |
| |
| float net_delay_value = IMPOSSIBLE_DELTA; /*set to known value for debug purposes */ |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| bool successfully_routed = false; |
| |
| //Get the rr nodes to route between |
| auto best_driver_ptcs = get_best_classes(DRIVER, device_ctx.grid[source_x][source_y].type); |
| auto best_sink_ptcs = get_best_classes(RECEIVER, device_ctx.grid[sink_x][sink_y].type); |
| |
| for (int driver_ptc : best_driver_ptcs) { |
| VTR_ASSERT(driver_ptc != OPEN); |
| |
| int source_rr_node = get_rr_node_index(device_ctx.rr_node_indices, source_x, source_y, SOURCE, driver_ptc); |
| |
| VTR_ASSERT(source_rr_node != OPEN); |
| |
| for (int sink_ptc : best_sink_ptcs) { |
| VTR_ASSERT(sink_ptc != OPEN); |
| |
| int sink_rr_node = get_rr_node_index(device_ctx.rr_node_indices, sink_x, sink_y, SINK, sink_ptc); |
| |
| VTR_ASSERT(sink_rr_node != OPEN); |
| |
| if (!measure_directconnect && directconnect_exists(source_rr_node, sink_rr_node)) { |
| //Skip if we shouldn't measure direct connects and a direct connect exists |
| continue; |
| } |
| |
| { |
| successfully_routed = route_profiler.calculate_delay( |
| source_rr_node, sink_rr_node, |
| router_opts, |
| &net_delay_value); |
| } |
| |
| if (successfully_routed) break; |
| } |
| if (successfully_routed) break; |
| } |
| |
| if (!successfully_routed) { |
| VTR_LOG_WARN("Unable to route between blocks at (%d,%d) and (%d,%d) to characterize delay (setting to %g)\n", |
| source_x, source_y, sink_x, sink_y, net_delay_value); |
| } |
| |
| return (net_delay_value); |
| } |
| |
| static void generic_compute_matrix( |
| const RouterDelayProfiler& route_profiler, |
| vtr::Matrix<std::vector<float>>& matrix, |
| int source_x, |
| int source_y, |
| int start_x, |
| int start_y, |
| int end_x, |
| int end_y, |
| const t_router_opts& router_opts, |
| bool measure_directconnect) { |
| int delta_x, delta_y; |
| int sink_x, sink_y; |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| for (sink_x = start_x; sink_x <= end_x; sink_x++) { |
| for (sink_y = start_y; sink_y <= end_y; sink_y++) { |
| delta_x = abs(sink_x - source_x); |
| delta_y = abs(sink_y - source_y); |
| |
| t_physical_tile_type_ptr src_type = device_ctx.grid[source_x][source_y].type; |
| t_physical_tile_type_ptr sink_type = device_ctx.grid[sink_x][sink_y].type; |
| |
| bool src_or_target_empty = (src_type == device_ctx.EMPTY_TYPE |
| || sink_type == device_ctx.EMPTY_TYPE); |
| |
| if (src_or_target_empty) { |
| if (matrix[delta_x][delta_y].empty()) { |
| //Only set empty target if we don't already have a valid delta delay |
| matrix[delta_x][delta_y].push_back(EMPTY_DELTA); |
| #ifdef VERBOSE |
| VTR_LOG("Computed delay: %12s delta: %d,%d (src: %d,%d sink: %d,%d)\n", |
| "EMPTY", |
| delta_x, delta_y, |
| source_x, source_y, |
| sink_x, sink_y); |
| #endif |
| } |
| } else { |
| //Valid start/end |
| |
| float delay = route_connection_delay(route_profiler, source_x, source_y, sink_x, sink_y, router_opts, measure_directconnect); |
| |
| #ifdef VERBOSE |
| VTR_LOG("Computed delay: %12g delta: %d,%d (src: %d,%d sink: %d,%d)\n", |
| delay, |
| delta_x, delta_y, |
| source_x, source_y, |
| sink_x, sink_y); |
| #endif |
| if (matrix[delta_x][delta_y].size() == 1 && matrix[delta_x][delta_y][0] == EMPTY_DELTA) { |
| //Overwrite empty delta |
| matrix[delta_x][delta_y][0] = delay; |
| } else { |
| //Collect delta |
| matrix[delta_x][delta_y].push_back(delay); |
| } |
| } |
| } |
| } |
| } |
| |
| static vtr::Matrix<float> compute_delta_delays( |
| const RouterDelayProfiler& route_profiler, |
| const t_placer_opts& placer_opts, |
| const t_router_opts& router_opts, |
| bool measure_directconnect, |
| size_t longest_length) { |
| //To avoid edge effects we place the source at least 'longest_length' away |
| //from the device edge |
| //and route from there for all possible delta values < dimension |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& grid = device_ctx.grid; |
| |
| vtr::Matrix<std::vector<float>> sampled_delta_delays({grid.width(), grid.height()}); |
| |
| size_t mid_x = vtr::nint(grid.width() / 2); |
| size_t mid_y = vtr::nint(grid.height() / 2); |
| |
| size_t low_x = std::min(longest_length, mid_x); |
| size_t low_y = std::min(longest_length, mid_y); |
| size_t high_x = std::max(grid.width() - longest_length, mid_x); |
| size_t high_y = std::max(grid.height() - longest_length, mid_y); |
| |
| // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| // + | | + |
| // + A | B | C + |
| // + | | + |
| // +-----------------\-----------------------.---------------+ |
| // + | | + |
| // + | | + |
| // + | | + |
| // + | | + |
| // + D | E | F + |
| // + | | + |
| // + | | + |
| // + | | + |
| // + | | + |
| // +-----------------*-----------------------/---------------+ |
| // + | | + |
| // + G | H | I + |
| // + | | + |
| // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| // |
| // * = (low_x, low_y) |
| // . = (high_x, high_y) |
| // / = (high_x, low_y) |
| // \ = (low_x, high_y) |
| // + = device edge |
| |
| //Find the lowest y location on the left edge with a non-empty block |
| size_t y = 0; |
| size_t x = 0; |
| t_physical_tile_type_ptr src_type = nullptr; |
| for (x = 0; x < grid.width(); ++x) { |
| for (y = 0; y < grid.height(); ++y) { |
| auto type = grid[x][y].type; |
| |
| if (type != device_ctx.EMPTY_TYPE) { |
| src_type = type; |
| break; |
| } |
| } |
| if (src_type) { |
| break; |
| } |
| } |
| VTR_ASSERT(src_type != nullptr); |
| |
| #ifdef VERBOSE |
| VTR_LOG("Computing from lower left edge (%d,%d):\n", x, y); |
| #endif |
| generic_compute_matrix(route_profiler, sampled_delta_delays, |
| x, y, |
| x, y, |
| grid.width() - 1, grid.height() - 1, |
| router_opts, |
| measure_directconnect); |
| |
| //Find the lowest x location on the bottom edge with a non-empty block |
| src_type = nullptr; |
| for (y = 0; y < grid.height(); ++y) { |
| for (x = 0; x < grid.width(); ++x) { |
| auto type = grid[x][y].type; |
| |
| if (type != device_ctx.EMPTY_TYPE) { |
| src_type = type; |
| break; |
| } |
| } |
| if (src_type) { |
| break; |
| } |
| } |
| VTR_ASSERT(src_type != nullptr); |
| #ifdef VERBOSE |
| VTR_LOG("Computing from left bottom edge (%d,%d):\n", x, y); |
| #endif |
| generic_compute_matrix(route_profiler, sampled_delta_delays, |
| x, y, |
| x, y, |
| grid.width() - 1, grid.height() - 1, |
| router_opts, |
| measure_directconnect); |
| |
| //Since the other delta delay values may have suffered from edge effects, |
| //we recalculate deltas within regions B, C, E, F |
| #ifdef VERBOSE |
| VTR_LOG("Computing from low/low:\n"); |
| #endif |
| generic_compute_matrix(route_profiler, sampled_delta_delays, |
| low_x, low_y, |
| low_x, low_y, |
| grid.width() - 1, grid.height() - 1, |
| router_opts, |
| measure_directconnect); |
| |
| //Since the other delta delay values may have suffered from edge effects, |
| //we recalculate deltas within regions D, E, G, H |
| #ifdef VERBOSE |
| VTR_LOG("Computing from high/high:\n"); |
| #endif |
| generic_compute_matrix(route_profiler, sampled_delta_delays, |
| high_x, high_y, |
| 0, 0, |
| high_x, high_y, |
| router_opts, |
| measure_directconnect); |
| |
| //Since the other delta delay values may have suffered from edge effects, |
| //we recalculate deltas within regions A, B, D, E |
| #ifdef VERBOSE |
| VTR_LOG("Computing from high/low:\n"); |
| #endif |
| generic_compute_matrix(route_profiler, sampled_delta_delays, |
| high_x, low_y, |
| 0, low_y, |
| high_x, grid.height() - 1, |
| router_opts, |
| measure_directconnect); |
| |
| //Since the other delta delay values may have suffered from edge effects, |
| //we recalculate deltas within regions E, F, H, I |
| #ifdef VERBOSE |
| VTR_LOG("Computing from low/high:\n"); |
| #endif |
| generic_compute_matrix(route_profiler, sampled_delta_delays, |
| low_x, high_y, |
| low_x, 0, |
| grid.width() - 1, high_y, |
| router_opts, |
| measure_directconnect); |
| |
| vtr::Matrix<float> delta_delays({grid.width(), grid.height()}); |
| for (size_t dx = 0; dx < sampled_delta_delays.dim_size(0); ++dx) { |
| for (size_t dy = 0; dy < sampled_delta_delays.dim_size(1); ++dy) { |
| delta_delays[dx][dy] = delay_reduce(sampled_delta_delays[dx][dy], placer_opts.delay_model_reducer); |
| } |
| } |
| |
| return delta_delays; |
| } |
| |
| float delay_reduce(std::vector<float>& delays, e_reducer reducer) { |
| if (delays.size() == 0) { |
| return IMPOSSIBLE_DELTA; |
| } else if (delays.size() == 1) { |
| return delays[0]; |
| } |
| |
| VTR_ASSERT(delays.size() > 1); |
| |
| float delay; |
| |
| if (reducer == e_reducer::MIN) { |
| auto itr = std::min_element(delays.begin(), delays.end()); |
| delay = *itr; |
| } else if (reducer == e_reducer::MAX) { |
| auto itr = std::max_element(delays.begin(), delays.end()); |
| delay = *itr; |
| } else if (reducer == e_reducer::MEDIAN) { |
| std::sort(delays.begin(), delays.end()); |
| delay = vtr::median(delays.begin(), delays.end()); |
| } else if (reducer == e_reducer::ARITHMEAN) { |
| delay = vtr::arithmean(delays.begin(), delays.end()); |
| } else if (reducer == e_reducer::GEOMEAN) { |
| delay = vtr::geomean(delays.begin(), delays.end()); |
| } else { |
| VPR_FATAL_ERROR(VPR_ERROR_PLACE, "Unrecognized delta delay reducer"); |
| } |
| |
| return delay; |
| } |
| |
| /* We return the average placement estimated delay for a routing spanning (x,y). |
| * We start with an averaging distance of 1 (i.e. from (x-1,y-1) to (x+1,y+1)) |
| * and look for legal delay values to average; if some are found we return the |
| * average and if none are found we increase the distance to average over. |
| * |
| * If no legal values are found to average over with a range of max_distance, |
| * we return IMPOSSIBLE_DELTA. |
| */ |
| static float find_neightboring_average( |
| vtr::Matrix<float>& matrix, |
| int x, |
| int y, |
| int max_distance) { |
| float sum = 0; |
| int counter = 0; |
| int endx = matrix.end_index(0); |
| int endy = matrix.end_index(1); |
| |
| int delx, dely; |
| |
| for (int distance = 1; distance <= max_distance; ++distance) { |
| for (delx = x - distance; delx <= x + distance; delx++) { |
| for (dely = y - distance; dely <= y + distance; dely++) { |
| // Check distance constraint |
| if (abs(delx - x) + abs(dely - y) > distance) { |
| continue; |
| } |
| |
| //check out of bounds |
| if (delx < 0 || dely < 0 || delx >= endx || dely >= endy || (delx == x && dely == y)) { |
| continue; |
| } |
| |
| if (matrix[delx][dely] == EMPTY_DELTA || matrix[delx][dely] == IMPOSSIBLE_DELTA) { |
| continue; |
| } |
| counter++; |
| sum += matrix[delx][dely]; |
| } |
| } |
| if (counter != 0) { |
| return sum / (float)counter; |
| } |
| } |
| |
| return IMPOSSIBLE_DELTA; |
| } |
| |
| static void fix_empty_coordinates(vtr::Matrix<float>& delta_delays) { |
| // Set any empty delta's to the average of it's neighbours |
| // |
| // Empty coordinates may occur if the sampling location happens to not have |
| // a connection at that location. However a more through sampling likely |
| // would return a result, so we fill in the empty holes with a small |
| // neighbour average. |
| constexpr int kMaxAverageDistance = 2; |
| for (size_t delta_x = 0; delta_x < delta_delays.dim_size(0); ++delta_x) { |
| for (size_t delta_y = 0; delta_y < delta_delays.dim_size(1); ++delta_y) { |
| if (delta_delays[delta_x][delta_y] == EMPTY_DELTA) { |
| delta_delays[delta_x][delta_y] = find_neightboring_average(delta_delays, delta_x, delta_y, kMaxAverageDistance); |
| } |
| } |
| } |
| } |
| |
| static void fix_uninitialized_coordinates(vtr::Matrix<float>& delta_delays) { |
| // Set any empty delta's to the average of it's neighbours |
| for (size_t delta_x = 0; delta_x < delta_delays.dim_size(0); ++delta_x) { |
| for (size_t delta_y = 0; delta_y < delta_delays.dim_size(1); ++delta_y) { |
| if (delta_delays[delta_x][delta_y] == UNINITIALIZED_DELTA) { |
| delta_delays[delta_x][delta_y] = IMPOSSIBLE_DELTA; |
| } |
| } |
| } |
| } |
| |
| static void fill_impossible_coordinates(vtr::Matrix<float>& delta_delays) { |
| // Set any impossible delta's to the average of it's neighbours |
| // |
| // Impossible coordinates may occur if an IPIN cannot be reached from the |
| // sampling OPIN. This might occur if the IPIN or OPIN used for sampling |
| // is specialized, and therefore cannot be reached via the by the pins |
| // sampled. Leaving this value in the delay matrix will result in invalid |
| // slacks if the delay matrix uses this value. |
| // |
| // A max average distance of 5 is used to provide increased effort in |
| // filling these gaps. It is more important to have a poor predication, |
| // than a invalid value and causing a slack assertion. |
| constexpr int kMaxAverageDistance = 5; |
| for (size_t delta_x = 0; delta_x < delta_delays.dim_size(0); ++delta_x) { |
| for (size_t delta_y = 0; delta_y < delta_delays.dim_size(1); ++delta_y) { |
| if (delta_delays[delta_x][delta_y] == IMPOSSIBLE_DELTA) { |
| delta_delays[delta_x][delta_y] = find_neightboring_average( |
| delta_delays, delta_x, delta_y, kMaxAverageDistance); |
| } |
| } |
| } |
| } |
| |
| static vtr::Matrix<float> compute_delta_delay_model( |
| const RouterDelayProfiler& route_profiler, |
| const t_placer_opts& placer_opts, |
| const t_router_opts& router_opts, |
| bool measure_directconnect, |
| int longest_length) { |
| vtr::ScopedStartFinishTimer timer("Computing delta delays"); |
| vtr::Matrix<float> delta_delays = compute_delta_delays(route_profiler, |
| placer_opts, router_opts, measure_directconnect, longest_length); |
| |
| fix_uninitialized_coordinates(delta_delays); |
| |
| fix_empty_coordinates(delta_delays); |
| |
| fill_impossible_coordinates(delta_delays); |
| |
| verify_delta_delays(delta_delays); |
| |
| return delta_delays; |
| } |
| |
| //Finds a src_rr and sink_rr appropriate for measuring the delay of the current direct specification |
| static bool find_direct_connect_sample_locations(const t_direct_inf* direct, |
| t_physical_tile_type_ptr from_type, |
| int from_pin, |
| int from_pin_class, |
| t_physical_tile_type_ptr to_type, |
| int to_pin, |
| int to_pin_class, |
| int* src_rr, |
| int* sink_rr) { |
| VTR_ASSERT(from_type != nullptr); |
| VTR_ASSERT(to_type != nullptr); |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& grid = device_ctx.grid; |
| |
| //Search the grid for an instance of from/to blocks which satisfy this direct connect offsets, |
| //and which has the appropriate pins |
| int from_x = 0, from_y = 0, from_z = 0; |
| int to_x = 0, to_y = 0, to_z = 0; |
| bool found = false; |
| for (from_x = 0; from_x < (int)grid.width(); ++from_x) { |
| to_x = from_x + direct->x_offset; |
| if (to_x < 0 || to_x >= (int)grid.width()) continue; |
| |
| for (from_y = 0; from_y < (int)grid.height(); ++from_y) { |
| if (grid[from_x][from_y].type != from_type) continue; |
| |
| //Check that the from pin exists at this from location |
| //(with multi-width/height blocks pins may not exist at all locations) |
| bool from_pin_found = false; |
| if (direct->from_side != NUM_SIDES) { |
| int from_pin_rr = get_rr_node_index(device_ctx.rr_node_indices, from_x, from_y, OPIN, from_pin, direct->from_side); |
| from_pin_found = (from_pin_rr != OPEN); |
| } else { |
| std::vector<int> from_pin_rrs = get_rr_node_indices(device_ctx.rr_node_indices, from_x, from_y, OPIN, from_pin); |
| from_pin_found = !from_pin_rrs.empty(); |
| } |
| if (!from_pin_found) continue; |
| |
| to_y = from_y + direct->y_offset; |
| |
| if (to_y < 0 || to_y >= (int)grid.height()) continue; |
| if (grid[to_x][to_y].type != to_type) continue; |
| |
| //Check that the from pin exists at this from location |
| //(with multi-width/height blocks pins may not exist at all locations) |
| bool to_pin_found = false; |
| if (direct->to_side != NUM_SIDES) { |
| int to_pin_rr = get_rr_node_index(device_ctx.rr_node_indices, to_x, to_y, IPIN, to_pin, direct->to_side); |
| to_pin_found = (to_pin_rr != OPEN); |
| } else { |
| std::vector<int> to_pin_rrs = get_rr_node_indices(device_ctx.rr_node_indices, to_x, to_y, IPIN, to_pin); |
| to_pin_found = !to_pin_rrs.empty(); |
| } |
| if (!to_pin_found) continue; |
| |
| for (from_z = 0; from_z < from_type->capacity; ++from_z) { |
| to_z = from_z + direct->z_offset; |
| |
| if (to_z < 0 || to_z >= to_type->capacity) continue; |
| |
| found = true; |
| break; |
| } |
| if (found) break; |
| } |
| if (found) break; |
| } |
| |
| if (!found) { |
| return false; |
| } |
| |
| //Now have a legal instance of this direct connect |
| VTR_ASSERT(grid[from_x][from_y].type == from_type); |
| VTR_ASSERT(from_z < from_type->capacity); |
| |
| VTR_ASSERT(grid[to_x][to_y].type == to_type); |
| VTR_ASSERT(to_z < to_type->capacity); |
| |
| VTR_ASSERT(from_x + direct->x_offset == to_x); |
| VTR_ASSERT(from_y + direct->y_offset == to_y); |
| VTR_ASSERT(from_z + direct->z_offset == to_z); |
| |
| // |
| //Find a source/sink RR node associated with the pins of the direct |
| // |
| |
| auto source_rr_nodes = get_rr_node_indices(device_ctx.rr_node_indices, from_x, from_y, SOURCE, from_pin_class); |
| VTR_ASSERT(source_rr_nodes.size() > 0); |
| |
| auto sink_rr_nodes = get_rr_node_indices(device_ctx.rr_node_indices, to_x, to_y, SINK, to_pin_class); |
| VTR_ASSERT(sink_rr_nodes.size() > 0); |
| |
| *src_rr = source_rr_nodes[0]; |
| *sink_rr = sink_rr_nodes[0]; |
| |
| return true; |
| } |
| |
| static bool verify_delta_delays(const vtr::Matrix<float>& delta_delays) { |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& grid = device_ctx.grid; |
| |
| for (size_t x = 0; x < grid.width(); ++x) { |
| for (size_t y = 0; y < grid.height(); ++y) { |
| float delta_delay = delta_delays[x][y]; |
| |
| if (delta_delay < 0.) { |
| VPR_ERROR(VPR_ERROR_PLACE, |
| "Found invaild negative delay %g for delta (%d,%d)", |
| delta_delay, x, y); |
| } |
| } |
| } |
| |
| return true; |
| } |
| |
| void OverrideDelayModel::compute_override_delay_model(const RouterDelayProfiler& route_profiler) { |
| t_router_opts router_opts2 = router_opts_; |
| router_opts2.astar_fac = 0.; |
| |
| //Look at all the direct connections that exist, and add overrides to delay model |
| auto& device_ctx = g_vpr_ctx.device(); |
| for (int idirect = 0; idirect < device_ctx.arch->num_directs; ++idirect) { |
| const t_direct_inf* direct = &device_ctx.arch->Directs[idirect]; |
| |
| InstPort from_port = parse_inst_port(direct->from_pin); |
| InstPort to_port = parse_inst_port(direct->to_pin); |
| |
| t_physical_tile_type_ptr from_type = find_block_type_by_name(from_port.instance_name(), device_ctx.physical_tile_types); |
| t_physical_tile_type_ptr to_type = find_block_type_by_name(to_port.instance_name(), device_ctx.physical_tile_types); |
| |
| int num_conns = from_port.port_high_index() - from_port.port_low_index() + 1; |
| VTR_ASSERT_MSG(num_conns == to_port.port_high_index() - to_port.port_low_index() + 1, "Directs must have the same size to/from"); |
| |
| //We now walk through all the connections associated with the current direct specification, measure |
| //their delay and specify that value as an override in the delay model. |
| // |
| //Note that we need to check every connection in the direct to cover the case where the pins are not |
| //equivalent. |
| // |
| //However, if the from/to ports are equivalent we could end up sampling the same RR SOURCE/SINK |
| //paths multiple times (wasting CPU time) -- we avoid this by recording the sampled paths in |
| //sampled_rr_pairs and skipping them if they occur multiple times. |
| int missing_instances = 0; |
| int missing_paths = 0; |
| std::set<std::pair<int, int>> sampled_rr_pairs; |
| for (int iconn = 0; iconn < num_conns; ++iconn) { |
| //Find the associated pins |
| int from_pin = find_pin(logical_block_type(from_type), from_port.port_name(), from_port.port_low_index() + iconn); |
| int to_pin = find_pin(logical_block_type(to_type), to_port.port_name(), to_port.port_low_index() + iconn); |
| |
| VTR_ASSERT(from_pin != OPEN); |
| VTR_ASSERT(to_pin != OPEN); |
| |
| int from_pin_class = find_pin_class(logical_block_type(from_type), from_port.port_name(), from_port.port_low_index() + iconn, DRIVER); |
| VTR_ASSERT(from_pin_class != OPEN); |
| |
| int to_pin_class = find_pin_class(logical_block_type(to_type), to_port.port_name(), to_port.port_low_index() + iconn, RECEIVER); |
| VTR_ASSERT(to_pin_class != OPEN); |
| |
| int src_rr = OPEN; |
| int sink_rr = OPEN; |
| bool found_sample_points = find_direct_connect_sample_locations(direct, from_type, from_pin, from_pin_class, to_type, to_pin, to_pin_class, &src_rr, &sink_rr); |
| |
| if (!found_sample_points) { |
| ++missing_instances; |
| continue; |
| } |
| |
| //If some of the source/sink ports are logically equivalent we may have already |
| //sampled the associated source/sink pair and don't need to do so again |
| if (sampled_rr_pairs.count({src_rr, sink_rr})) continue; |
| |
| VTR_ASSERT(src_rr != OPEN); |
| VTR_ASSERT(sink_rr != OPEN); |
| |
| float direct_connect_delay = std::numeric_limits<float>::quiet_NaN(); |
| bool found_routing_path = route_profiler.calculate_delay(src_rr, sink_rr, router_opts2, &direct_connect_delay); |
| |
| if (found_routing_path) { |
| set_delay_override(from_type->index, from_pin_class, to_type->index, to_pin_class, direct->x_offset, direct->y_offset, direct_connect_delay); |
| } else { |
| ++missing_paths; |
| } |
| |
| //Record that we've sampled this pair of source and sink nodes |
| sampled_rr_pairs.insert({src_rr, sink_rr}); |
| } |
| |
| VTR_LOGV_WARN(missing_instances > 0, "Found no delta delay for %d bits of inter-block direct connect '%s' (no instances of this direct found)\n", missing_instances, direct->name); |
| VTR_LOGV_WARN(missing_paths > 0, "Found no delta delay for %d bits of inter-block direct connect '%s' (no routing path found)\n", missing_paths, direct->name); |
| } |
| } |
| |
| bool directconnect_exists(int src_rr_node, int sink_rr_node) { |
| //Returns true if there is a directconnect between the two RR nodes |
| // |
| //This is checked by looking for a SOURCE -> OPIN -> IPIN -> SINK path |
| //which starts at src_rr_node and ends at sink_rr_node |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& rr_nodes = device_ctx.rr_nodes; |
| |
| VTR_ASSERT(rr_nodes[src_rr_node].type() == SOURCE && rr_nodes[sink_rr_node].type() == SINK); |
| |
| //TODO: This is a constant depth search, but still may be too slow |
| for (t_edge_size i_src_edge = 0; i_src_edge < rr_nodes[src_rr_node].num_edges(); ++i_src_edge) { |
| int opin_rr_node = rr_nodes[src_rr_node].edge_sink_node(i_src_edge); |
| |
| if (rr_nodes[opin_rr_node].type() != OPIN) continue; |
| |
| for (t_edge_size i_opin_edge = 0; i_opin_edge < rr_nodes[opin_rr_node].num_edges(); ++i_opin_edge) { |
| int ipin_rr_node = rr_nodes[opin_rr_node].edge_sink_node(i_opin_edge); |
| |
| if (rr_nodes[ipin_rr_node].type() != IPIN) continue; |
| |
| for (t_edge_size i_ipin_edge = 0; i_ipin_edge < rr_nodes[ipin_rr_node].num_edges(); ++i_ipin_edge) { |
| if (sink_rr_node == rr_nodes[ipin_rr_node].edge_sink_node(i_ipin_edge)) { |
| return true; |
| } |
| } |
| } |
| } |
| return false; |
| } |
