Program Listing for File tdm.h¶
↰ Return to documentation for file (src/tdm/tdm.h)
#ifndef TDM_H
#define TDM_H
#include <spdlog/sinks/basic_file_sink.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <future>
#include <iomanip>
#include <iostream>
#include <list>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <thread>
#include <unordered_set>
#include <vector>
#include "delay_lib.h"
#include "routing.h"
#include "tool.h"
class bidir_map {
int _size = 0;
public:
flat_hash_map<pair<int, int>, int> node_map;
vector<pair<int, int>> reverse_node_map;
int operator[](const pair<int, int> &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<int, int> &at(int id) const
{
return reverse_node_map[id];
}
bool contains(const pair<int, int> &key) const
{
return node_map.find(key) != node_map.end();
}
bool try_get(const pair<int, int> &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 <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const
{
return std::hash<T1>()(p.first) ^ (std::hash<T2>()(p.second) << 1);
}
};
struct CutTimingPathInfo {
int index;
double cp;
double old_slack;
vector<int> 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<string> left_gio, right_gio;
vector<string> left_mgt, right_mgt;
};
struct MgtSubChannel {
double clock;
int used;
};
struct DomainStat {
double cp = 0.0;
double slack_min = std::numeric_limits<double>::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<int> edges;
vector<string> left_sockets;
vector<string> 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_group> tdm_groups;
vector<timing_edge> timing_edges;
set<int> tdm_choices;
set<int> mgt_ratios;
const flat_hash_map<int, set<pair<int, int>>> &route_trees;
vector<vector<int>> die_physical_links;
vector<vector<int>> die_gio_links;
vector<vector<int>> die_mgt_links;
vector<vector<int>> die_graph;
vector<cut_timing_path> &cut_timing_paths;
const vector<cut_net> &cut_nets;
vector<vector<int>> cut_mat;
const shared_ptr<mulClockAttr> &mul_clock_attr;
const unordered_map<cut_timing_path, double>
&cut_to_tp_id;
const graph &finest;
std::vector<int> node_to_route_part;
vector<DieConnection> die_connections;
vector<std::vector<int>> board_capacity;
const flat_hash_map<int, vector<RouteTreeEdge>>
*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<vector<int>>
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<int> &dir_edges,
int gio_cap_channels,
int mgt_cap_lanes, // = 8 * mgt_links (lanes)
const std::vector<double> &edge_mu,
const std::vector<uint8_t> &edge_in_path);
inline RatioLib lib_from_ratio(int r) const
{
return is_mgt_ratio(r) ? RatioLib::MGT : RatioLib::GIO;
}
std::vector<int> choices_for(RatioLib lib) const; // 候选离散比率
Tdm(const vector<vector<int>> &die_graph,
vector<vector<int>> die_physical_links, vector<vector<int>> die_gio_links,
vector<vector<int>> die_mgt_links,
vector<cut_timing_path> &cut_timing_paths,
const vector<cut_net> &cut_nets, const vector<vector<int>> &cut_mat,
const flat_hash_map<int, set<pair<int, int>>> &route_trees,
const flat_hash_map<int, vector<RouteTreeEdge>> *route_trees_edges,
double cut_delay, double tdm_delay, double die_delay, double clock_period,
const shared_ptr<mulClockAttr> &mul_clock_attr, const graph &finest,
const std::vector<int> &node_to_route_part,
const unordered_map<cut_timing_path, double> &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<DieConnection> die_connections, double stable_num, bool enable_net,
vector<std::vector<int>> 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<vector<int>> 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<int> build_try_ratios_from_lib(RatioLib lib) const;
void tdm_continuous_assignment_optimized();
void assign_continuous_paper();
void discretise_dp_paper();
std::pair<double, std::vector<double>> 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<int> &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<int> 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<int> &dir_edges,
int gio_cap_roots, int mgt_cap_roots,
const std::vector<double> &edge_mu);
void discretize_group_separate_libs(tdm_group &g,
const std::vector<double> &edge_mu);
void discretize_group_gio_baseline(tdm_group &g);
void discretize_pure_gio_then_sequential_mgt(
const std::vector<double> &edge_mu);
void improve_all_groups_with_mgt_slack_guided(
const std::vector<double> &edge_mu);
bool improve_one_dir_slack_guided(const tdm_group &g_dir,
const std::vector<int> &dir_edges,
int gio_cap_channels, int mgt_cap_lanes,
const std::vector<double> &edge_mu,
const std::vector<uint8_t> &edge_in_path,
double &best_min_slack);
void set_continuous_capacity_baseline();
std::vector<uint8_t> 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<int> &mgt_edges,
int r_mgt) const;
bool mgt_assign_feasible_same_clock(const std::vector<int> &mgt_edges,
int r_mgt, int mgt_cap_lanes) const;
int mgt_lanes_needed_mixed_ratio(const std::vector<int> &mgt_edges) const;
bool mgt_channel_packable_dir(const std::vector<int> &mgt_edges,
int mgt_cap_lanes) const;
void pack_dir_by_sets(const tdm_group &g_dir, const std::vector<int> &gio_set,
const std::vector<int> &mgt_set, int gio_cap_channels,
int mgt_cap_lanes);
bool repack_dir_by_lib_sets(const tdm_group &g_dir,
const std::vector<int> &dir_edges,
const std::vector<int> &gio_set,
const std::vector<int> &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<double> &edge_mu,
bool mixed_lib);
bool apply_final_polish(const std::vector<double> &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<int> &dir_edges);
bool socket_packable_dir_with_map(
const tdm_group &g, bool is_forward, const std::vector<int> &dir_edges,
const std::unordered_map<int, int> &ratio_map);
bool socket_packable_dir(const tdm_group &g, bool is_fwd) const;
bool update_edge_mu_for_worst_slack(std::vector<double> &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<int> &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<int> &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<DieConnection> &die_connections,
bool has_die);
void build_tdm(int &edge_id, const shared_ptr<mulClockAttr> &mul_clock_attr);
void buildGraphEdges(vector<std::vector<int>> &inEdges,
vector<std::vector<int>> &outEdges, int nodeCount,
int &edgeCount);
vector<int> topological_sort_kahn(const vector<vector<int>> &in_edges,
const vector<vector<int>> &out_edges,
int node_count);
void tdm_local_search(vector<int> &topo_order, vector<double> &edge_tdm_ratio,
vector<double> &edge_arrival_time,
vector<double> &node_arrival_time,
vector<int> &node_critical_prev,
vector<double> &arrival_time_gap,
double &best_discrete_arrival_time,
const vector<vector<int>> &in_edges,
const vector<vector<int>> &out_edges, int dst_node,
int node_count, int edge_count);
void compute_arrival_times(const vector<int> &topo_order,
const vector<vector<int>> &out_edges,
vector<double> &node_arrival,
vector<double> &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<DieConnection> &conns);
void populate_timing_edge_ports();
void project_group_ratios_exact(int g, const std::vector<double> &edge_mu,
double r_min, double r_max);
void seed_base_ratio_by_mu(const tdm_group &g,
const std::vector<double> &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<int> 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<uint8_t> &edge_in_path);
bool try_reduce_critical_edge_ratio_to_target(
int critical_eid, int target_ratio,
const std::vector<uint8_t> &edge_in_path, double &out_min_slack);
bool rescue_single_tdm_edge_worst_path(
const std::vector<uint8_t> &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<vector<int>> &in_edges,
vector<vector<int>> &out_edges,
vector<int> &topo_order);
double analyze_arrival_and_trace(const vector<int> &topo_order,
const vector<vector<int>> &out_edges,
int node_count, int dst_node,
vector<double> &node_arrival_time);
void init_dual_state_from_topology(
const vector<int> &topo_order, const vector<vector<int>> &in_edges,
const vector<vector<int>> &out_edges, int node_count, int edge_count,
int dst_node, vector<double> &lambda, vector<double> &learning_rate,
vector<int> &node_critical_prev, vector<double> &edge_arrival_time,
vector<double> &arrival_time_gap, vector<double> &edge_tdm_ratio,
vector<double> &node_pte, vector<double> &edge_pte,
vector<double> &node_mu, vector<double> &edge_mu,
vector<double> &lambda_velocity);
void normalize_and_rescue_tdm_assignments();
double compute_dst_arrival_from_current_delay(
const vector<int> &topo_order, const vector<vector<int>> &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<int> &E, double capacity,
const std::vector<double> &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