.. _program_listing_file_src_tdm_tdm.h: Program Listing for File tdm.h ============================== |exhale_lsh| :ref:`Return to documentation for file ` (``src/tdm/tdm.h``) .. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS .. code-block:: cpp #ifndef TDM_H #define TDM_H #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "delay_lib.h" #include "routing.h" #include "tool.h" class bidir_map { int _size = 0; public: flat_hash_map, int> node_map; vector> reverse_node_map; int operator[](const pair &key) { if (node_map.find(key) == node_map.end()) { node_map[key] = _size++; reverse_node_map.push_back(key); } return node_map[key]; } int size() const { return _size; } const pair &at(int id) const { return reverse_node_map[id]; } bool contains(const pair &key) const { return node_map.find(key) != node_map.end(); } bool try_get(const pair &key, int &value) const { auto it = node_map.find(key); if (it != node_map.end()) { value = it->second; return true; } return false; } }; struct timing_edge { int src; int dst; int net_id; int src_node; int dst_node; bool is_tdm; double delay; double tdm_ratio; double tdm_ratio_assign; int group_idx; double tdm_delay; double die_delay; double cut_delay; double clock_period; RatioLib lib_choice; std::string port_name; std::string left_port_name; std::string right_port_name; DelayScope delay_scope = DelayScope::Default; string get_port_name() const; }; struct hash_pair { template std::size_t operator()(const std::pair &p) const { return std::hash()(p.first) ^ (std::hash()(p.second) << 1); } }; struct CutTimingPathInfo { int index; double cp; double old_slack; vector ratios; int die_hop; double new_slack; double delay_real_sum; double delay_sum; }; struct EdgeStat { int id = -1; double crit = 0.0; // criticality (0~1) double r_cont = 1.0; // continuous ratio (floating) int r_disc = 1; // discrete ratio (int, multiple of 4) }; struct EdgeSnap { int eid; double ratio_assign; double tdm_ratio; double delay; RatioLib lib_choice; }; struct TypedSockets { vector left_gio, right_gio; vector left_mgt, right_mgt; }; struct MgtSubChannel { double clock; int used; }; struct DomainStat { double cp = 0.0; double slack_min = std::numeric_limits::max(); }; static inline double saturate(double v, double lo, double hi) { return std::max(lo, std::min(v, hi)); } class tdm_group { public: int left_part; int right_part; int backward_id; int capacity; int cap_cont = 0; vector edges; vector left_sockets; vector right_sockets; int forward_capacity; int backward_capacity; double lambda = 0.0; double learning_rate = 0.5; bool is_mgt = false; int gio_links = 0; int mgt_links = 0; bool channel_capacity_mode = false; int gio_channel_capacity = 0; int mgt_channel_capacity = 0; int fwd_cap_gio = 0, bwd_cap_gio = 0; int fwd_cap_mgt = 0, bwd_cap_mgt = 0; double cap_cont_gio; double cap_cont_mgt; double cap_cont_gio_fwd = 0, cap_cont_gio_bwd = 0; double cap_cont_mgt_fwd = 0, cap_cont_mgt_bwd = 0; }; class Tdm { public: bidir_map tdm_group_map; bidir_map node_maps; bidir_map edge_map; vector tdm_groups; vector timing_edges; set tdm_choices; set mgt_ratios; const flat_hash_map>> &route_trees; vector> die_physical_links; vector> die_gio_links; vector> die_mgt_links; vector> die_graph; vector &cut_timing_paths; const vector &cut_nets; vector> cut_mat; const shared_ptr &mul_clock_attr; const unordered_map &cut_to_tp_id; const graph &finest; std::vector node_to_route_part; vector die_connections; vector> board_capacity; const flat_hash_map> *route_trees_edges; double cut_delay; double tdm_delay; double die_delay; double clock_period; bool enable_net; int channel_grouping_capacity; bool is_directed; bool delayLibReady = false; bool has_die = false; bool has_timing = false; bool contest = false; bool debug_mode = false; int solver_threads = 1; int log_topk = 1; bool tdm_fast_mode = false; bool use_worst_slack_objective = false; bool allow_mgt_on_non_timing_edges = false; bool use_hierarchy_delay = false; std::string tdm_opt_mode = "legacy"; int board_count_hint = -1; int fpga_per_board_hint = -1; vector> fpga_hierarchy_paths; const double INIT_LR = 0.5; const double MAX_LR = 5.0; const double MIN_LR = 1e-3; const double TDM_RATIO_EPS = 1e-6; double min_ratio; double max_ratio; const double R_STEP = 2; const double R_MAX = 256; const double R_MIN = 1; const DelayLibrary *delayLib = nullptr; double lib_delay(RatioLib lib, double r) const; double lib_slope(RatioLib lib, double r) const; DelayScope delay_scope_for_parts(int src_part, int dst_part) const; double scoped_lib_delay(DelayScope scope, RatioLib lib, double r) const; double scoped_lib_slope(DelayScope scope, RatioLib lib, double r) const; double lib_rmin(RatioLib lib) const; double lib_rmax(RatioLib lib) const; bool is_mgt_ratio(int r) const; // 判断是否为MGT ratio bool is_bypass_ratio(int r) const; double mgt_benefit_from_ratio(int base_ratio, double mu) const; void relief_pack_one_dir(const tdm_group &g_dir, const std::vector &dir_edges, int gio_cap_channels, int mgt_cap_lanes, // = 8 * mgt_links (lanes) const std::vector &edge_mu, const std::vector &edge_in_path); inline RatioLib lib_from_ratio(int r) const { return is_mgt_ratio(r) ? RatioLib::MGT : RatioLib::GIO; } std::vector choices_for(RatioLib lib) const; // 候选离散比率 Tdm(const vector> &die_graph, vector> die_physical_links, vector> die_gio_links, vector> die_mgt_links, vector &cut_timing_paths, const vector &cut_nets, const vector> &cut_mat, const flat_hash_map>> &route_trees, const flat_hash_map> *route_trees_edges, double cut_delay, double tdm_delay, double die_delay, double clock_period, const shared_ptr &mul_clock_attr, const graph &finest, const std::vector &node_to_route_part, const unordered_map &cut_to_tp_id, int max_iters, double convergence_threshold, double convergence_num, double decay_factor, double initial_learning_rate, double decay_base, double decay_rate, vector die_connections, double stable_num, bool enable_net, vector> board_capacity, const DelayLibrary *delayLib, bool delayLibReady, bool has_die, bool has_timing, bool debug_mode, int solver_threads, int log_topk, bool tdm_fast_mode, bool use_worst_slack_objective, bool allow_mgt_on_non_timing_edges, const std::string &tdm_opt_mode, bool contest, int board_count_hint = -1, int fpga_per_board_hint = -1, vector> fpga_hierarchy_paths = {}); void tdm_assign(); void tdm_assign_optimized_legacy(); void tdm_assign_optimized(); void tdm_assign_optimized_contest(); void tdm_assign_avg_only(); void tdm_assign_optimized_1(); void tdm_assign_optimized_2(); void tdm_assign_optimized_3(); void init_average(); vector build_try_ratios_from_lib(RatioLib lib) const; void tdm_continuous_assignment_optimized(); void assign_continuous_paper(); void discretise_dp_paper(); std::pair> compute_RW_net(); void legalize_per_group(); void tdm_discretization_dp(); double compute_RW(); void init_net_criticality(); void tdm_assign_paper(); void refine_continuous_paper(); // Experimental branches selected by para.test=4/5. They do not export a // standard solution and run the common cut-timing-path slack analyzer last. void tdm_assign_synergistic_paper(); void tdm_assign_near_optimal_paper(); void enter_paper_experiment_mode(); void build_paper_timing_path_edges(const std::string &tag); void legalize_paper_wire_assignment(bool delay_aware); double mgt_benefit(int eid, double mu) const; tdm_group make_subgroup_single_dir(const tdm_group &g, const std::vector &edges) const; int required_roots_bestcase(const tdm_group &g_sub, RatioLib lib, double max_bound); void pack_subset_assign(const tdm_group &g_sub, RatioLib lib, int cap_roots); vector build_try_ratios_from_lib(RatioLib lib, double focus_ratio, int max_out) const; void select_and_pack_one_dir(const tdm_group &g_dir, const std::vector &dir_edges, int gio_cap_roots, int mgt_cap_roots, const std::vector &edge_mu); void discretize_group_separate_libs(tdm_group &g, const std::vector &edge_mu); void discretize_group_gio_baseline(tdm_group &g); void discretize_pure_gio_then_sequential_mgt( const std::vector &edge_mu); void improve_all_groups_with_mgt_slack_guided( const std::vector &edge_mu); bool improve_one_dir_slack_guided(const tdm_group &g_dir, const std::vector &dir_edges, int gio_cap_channels, int mgt_cap_lanes, const std::vector &edge_mu, const std::vector &edge_in_path, double &best_min_slack); void set_continuous_capacity_baseline(); std::vector build_edge_in_any_cut_path(int edge_count) const; void log_timing_vs_non_timing_tdm_usage( const std::string &tag, bool append_to_pair_stats_file = false) const; int mgt_lanes_needed_same_clock(const std::vector &mgt_edges, int r_mgt) const; bool mgt_assign_feasible_same_clock(const std::vector &mgt_edges, int r_mgt, int mgt_cap_lanes) const; int mgt_lanes_needed_mixed_ratio(const std::vector &mgt_edges) const; bool mgt_channel_packable_dir(const std::vector &mgt_edges, int mgt_cap_lanes) const; void pack_dir_by_sets(const tdm_group &g_dir, const std::vector &gio_set, const std::vector &mgt_set, int gio_cap_channels, int mgt_cap_lanes); bool repack_dir_by_lib_sets(const tdm_group &g_dir, const std::vector &dir_edges, const std::vector &gio_set, const std::vector &mgt_set, int gio_cap_channels, int mgt_cap_lanes); void split_group_base(tdm_group &group, double *forward_usage = nullptr, double *backward_usage = nullptr); void split_group(tdm_group &group); void apply_gio_root_split(tdm_group &group, int fwd_gio_roots); bool optimize_group_gio_root_split(tdm_group &group, const std::vector &edge_mu, bool mixed_lib); bool apply_final_polish(const std::vector &edge_mu, int max_rounds = 3); bool apply_gio_capacity_fill(int max_rounds = 3, double active_window = 5.0); bool apply_mgt_channel_polish(int max_rounds = 3, double active_window = 5.0); bool legalize_all_gio_dir_bucket_overflow(const std::string &tag, int max_moves = 10000); bool apply_score_batch_reallocation(int max_rounds = 2, double active_cut_window = 5.0, int critical_topk = 50, int protected_topk = 200); bool apply_score_polish(int max_rounds = 3, double active_window = 2.0, double tau = 1.0); bool socket_packable_dir(const tdm_group &g, bool is_forward, const std::vector &dir_edges); bool socket_packable_dir_with_map( const tdm_group &g, bool is_forward, const std::vector &dir_edges, const std::unordered_map &ratio_map); bool socket_packable_dir(const tdm_group &g, bool is_fwd) const; bool update_edge_mu_for_worst_slack(std::vector &edge_mu) const; bool tdm_root_split_enabled() const; bool tdm_final_polish_enabled() const; bool tdm_postprocess_enabled() const; bool tdm_mu_slack_enabled() const; int pick_choice(int base, double bound, RatioLib lib); double get_min_bound_typed(const tdm_group &group, double max_bound, bool is_forward, RatioLib lib, int capacity_groups); int get_min_wire_typed(const tdm_group &group, int idx, double bound, bool assign_ratio, bool is_forward, RatioLib lib, int capacity_groups, int &next_idx); int get_min_wire_common(const tdm_group &group, int idx, double bound, bool assign_ratio, bool is_forward, const std::vector &choices, int capacity_groups, int &next_idx); double get_min_bound_common(const tdm_group &group, double max_bound, bool is_forward, const std::vector &choices, int capacity_groups); // 获取group中从idx开始，选择choice个元素的最大索引 int get_end_idx(const tdm_group &group, int idx, int choice, double bound); int get_min_wire(const tdm_group &group, int idx, double bound, bool assign_ratio, bool is_forward); double get_min_bound(const tdm_group &group, double max_bound, bool is_forward); double get_min_bound_lib(const tdm_group &group, double max_bound, bool is_forward, RatioLib lib, int capacity_channels); int get_min_wire_lib(const tdm_group &group, int idx, double bound, bool assign_ratio, bool is_forward, RatioLib lib); double eval_worst_delay_discrete() const; double eval_worst_net_rw_current() const; double eval_worst_net_rw_discrete() const; void log_contest_worst_nets(const std::string &stage, bool use_discrete_delay, int top_k) const; double eval_min_slack_discrete() const; void export_tdm_solution(); void export_contest_outputs(const std::string &route_filename, const std::string &tdm_filename) const; void assign_group_sockets(const vector &die_connections, bool has_die); void build_tdm(int &edge_id, const shared_ptr &mul_clock_attr); void buildGraphEdges(vector> &inEdges, vector> &outEdges, int nodeCount, int &edgeCount); vector topological_sort_kahn(const vector> &in_edges, const vector> &out_edges, int node_count); void tdm_local_search(vector &topo_order, vector &edge_tdm_ratio, vector &edge_arrival_time, vector &node_arrival_time, vector &node_critical_prev, vector &arrival_time_gap, double &best_discrete_arrival_time, const vector> &in_edges, const vector> &out_edges, int dst_node, int node_count, int edge_count); void compute_arrival_times(const vector &topo_order, const vector> &out_edges, vector &node_arrival, vector &edge_arrival, bool reset_arrays = true); void log_worst_slack_path(); void log_cut_worst_slack_path(int top_k = 1); void log_ratio_comparison(const std::string &filename); std::string format_fpga_die(int die_id, int die_per_fpga) const; TypedSockets collect_group_sockets_from_connections( const tdm_group &group, const std::vector &conns); void populate_timing_edge_ports(); void project_group_ratios_exact(int g, const std::vector &edge_mu, double r_min, double r_max); void seed_base_ratio_by_mu(const tdm_group &g, const std::vector &edge_mu); double edge_delay_from_assign(const timing_edge &e) const; void refresh_all_tdm_delay_from_assign(); void log_worst_cut_path_brief(const std::string &tag, int max_edges_to_print = 8, bool use_current_edge_delay = false) const; std::vector get_worst_cut_path_eids( bool use_current_edge_delay = false) const; bool try_reduce_critical_edge_ratio(int critical_eid, double &best_min_slack, const std::vector &edge_in_path); bool try_reduce_critical_edge_ratio_to_target( int critical_eid, int target_ratio, const std::vector &edge_in_path, double &out_min_slack); bool rescue_single_tdm_edge_worst_path( const std::vector &edge_in_path, double &best_min_slack); bool rescue_worst_path_edge_ratio(); void export_contest_route_result(const std::string &filename) const; void export_contest_tdm_result(const std::string &filename, const std::string &route_filename) const; int count_dir_bypass_channels_need(const tdm_group &group, bool is_forward) const; int gio_cap_channels_from_roots(int roots, int bypass_extra) const; private: int max_iters; double convergence_threshold; double convergence_num; double stable_num; double decay_factor; double initial_learning_rate; double decay_base; double decay_rate; void prepare_graph_and_topology(int &edge_count, int &node_count, int &dst_node, vector> &in_edges, vector> &out_edges, vector &topo_order); double analyze_arrival_and_trace(const vector &topo_order, const vector> &out_edges, int node_count, int dst_node, vector &node_arrival_time); void init_dual_state_from_topology( const vector &topo_order, const vector> &in_edges, const vector> &out_edges, int node_count, int edge_count, int dst_node, vector &lambda, vector &learning_rate, vector &node_critical_prev, vector &edge_arrival_time, vector &arrival_time_gap, vector &edge_tdm_ratio, vector &node_pte, vector &edge_pte, vector &node_mu, vector &edge_mu, vector &lambda_velocity); void normalize_and_rescue_tdm_assignments(); double compute_dst_arrival_from_current_delay( const vector &topo_order, const vector> &out_edges, int node_count, int dst_node) const; RatioLib choose_lib_continuous_for_group(const tdm_group &g) const; void project_edges_with_capacity_(const std::vector &E, double capacity, const std::vector &edge_mu, double r_min, double r_max); inline RatioLib edge_lib(int u, int v); }; namespace tdm { void executeTDM(Routing &router, const fpga &fpgas, const params ¶, DelayLibrary &delayLib); } // namespace tdm #endif