Class Tdm¶

Defined in File tdm.h

Class Documentation¶

class Tdm¶

TDM 分配器及其算法实验集合。

对象引用 Routing 产生的布线树、割线网和割时序路径，先构建内部时序 DAG，再求连续 ratio、投影容量、选择 GIO/MGT、离散合法化和关键路径后处理。最终结果保存在 timing_edges[*].tdm_ratio_assign，并由 export_tdm_solution() 写入结果文件。

Routing 与平台输入

const flat_hash_map<int, set<pair<int, int>>> &route_trees¶: 布线树。

vector<vector<int>> die_physical_links¶: Die 间物理 link 总量矩阵。

vector<vector<int>> die_gio_links¶: Die/FPGA 间 GIO 容量矩阵。

vector<vector<int>> die_mgt_links¶: Die/FPGA 间 MGT 容量矩阵。

vector<vector<int>> die_graph¶: 布线使用的 Die 容量图。

vector<cut_timing_path> &cut_timing_paths¶: 可写的割时序路径集合。

const vector<cut_net> &cut_nets¶: Routing 产生的割线网。

vector<vector<int>> cut_mat¶: 有向逻辑边占用矩阵副本。

const shared_ptr<mulClockAttr> &mul_clock_attr¶: 多时钟归一化信息。

const unordered_map<cut_timing_path, double> &cut_to_tp_id¶: 路径 ID 映射。

const graph &finest¶: 原始超图。

std::vector<int> node_to_route_part¶: 原图节点到布线分区编号。

vector<DieConnection> die_connections¶: 物理 socket/link 描述。

vector<std::vector<int>> board_capacity¶: FPGA 级有向容量矩阵。

const flat_hash_map<int, vector<RouteTreeEdge>> *route_trees_edges¶: 带端口名的布线边。

延迟库与 ratio 查询

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¶

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, const std::vector<double> &edge_mu, const std::vector<uint8_t> &edge_in_path)¶

inline RatioLib lib_from_ratio(int r) const¶

std::vector<int> choices_for(RatioLib lib) const¶

端到端分配策略

统一入口之外保留的当前、历史和实验分配算法。

早期基础分配算法；新流程通常不直接调用。

void tdm_assign()¶

void tdm_assign_optimized_legacy()¶: 保留旧求解器行为的优化版本。

void tdm_assign_optimized()¶: 连续优化、候选策略比较与后处理的主优化器。

void tdm_assign_optimized_contest()¶: 以最坏 net delay 为目标并按比赛格式导出的优化器。

void tdm_assign_avg_only()¶: 非时序基线：仅按割边数量和容量均分 ratio。

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()¶

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)¶

GIO/MGT 混合离散化辅助函数

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¶: 判断 tdm_opt_mode 是否启用 GIO root 方向拆分。

bool tdm_final_polish_enabled() const¶: 判断 tdm_opt_mode 是否启用最终局部打磨。

bool tdm_postprocess_enabled() const¶: 判断是否允许最终 winner 后处理；no_postprocess 返回 false。

bool tdm_mu_slack_enabled() const¶: 判断是否使用以最差 slack 更新的边权重。

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)¶

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()¶: 导出标准 tdmDelayReport.json 与 routing.out。

void export_contest_outputs(const std::string &route_filename, const std::string &tdm_filename) const¶: 导出比赛要求的 route 与 TDM 文本文件。

void assign_group_sockets(const vector<DieConnection> &die_connections, bool has_die)¶: 从物理连接描述为各分配组绑定可用 socket 和方向容量。

时序 DAG 构建与分析

从布线树创建真实 TDM 边和物理分配组。

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)¶: 将割时序路径接入 DAG，并补充源/汇 dummy 边。

vector<int> topological_sort_kahn(const vector<vector<int>> &in_edges, const vector<vector<int>> &out_edges, int node_count)¶: 对内部 DAG 执行 Kahn 拓扑排序。

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()¶

容量投影与关键路径修复

将一组连续 ratio 严格投影到双向物理容量约束。

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¶

Public Functions

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 = {})¶: 构造分配器；参数通常由 tdm::executeTDM() 从 Routing 和配置组装。

Note

多个输入以引用或非拥有指针保存，其生命周期必须覆盖本对象。

Public Members

bidir_map tdm_group_map¶: {min(part), max(part)} 到组 ID。

bidir_map node_maps¶: {local_net_id, physical_part} 到 DAG 节点 ID。

bidir_map edge_map¶: {src_node, dst_node} 到时序边 ID。

vector<tdm_group> tdm_groups¶: 共享物理容量的分配组。

vector<timing_edge> timing_edges¶: 优化和分析使用的时序 DAG 边。

set<int> tdm_choices¶: GIO 离散 ratio 候选。

set<int> mgt_ratios¶: MGT 离散 ratio 候选。

double cut_delay¶: 无延迟库/比赛模型的固定跨分区延迟。

double tdm_delay¶: 无延迟库/比赛模型的 ratio 线性系数。

double die_delay¶: 同 FPGA 跨 Die 固定延迟。

double clock_period¶: Routing 提供的默认时钟周期。

bool enable_net¶: 是否输出/分析 net 级时序信息。

int channel_grouping_capacity¶: 单根 GIO 折算的逻辑通道数，默认 23。

bool is_directed¶: 物理容量是否按方向解释。

bool delayLibReady = false¶: 延迟库是否成功加载。

bool has_die = false¶: 是否使用展平 Die 级拓扑。

bool has_timing = false¶: 是否存在可用时序路径/周期信息。

bool contest = false¶: 比赛模式：以最坏 net delay 为目标。

bool debug_mode = false¶: 是否生成调试文件和详细日志。

int solver_threads = 1¶: 并行策略评估线程上限。

int log_topk = 1¶: 输出的最差时序路径数量。

bool tdm_fast_mode = false¶: 是否只评估精简策略集合。

bool use_worst_slack_objective = false¶: 连续阶段是否以 worst slack 代替 arrival time 为目标。

bool allow_mgt_on_non_timing_edges = false¶: 是否允许非时序路径上的 TDM 边使用 MGT。

bool use_hierarchy_delay = false¶: 是否启用分层 scope 延迟模型。

std::string tdm_opt_mode = "legacy"¶: 后处理/消融模式选择。

int board_count_hint = -1¶: 导出使用的板数量提示。

int fpga_per_board_hint = -1¶: 导出使用的每板 FPGA 数提示。

vector<vector<int>> fpga_hierarchy_paths¶: FPGA 的 rack/cluster/board 路径。

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¶: ratio 数值稳定常量。

double min_ratio¶: 当前模式下最小 ratio。

double max_ratio¶: 当前模式下最大 ratio。

const double R_STEP = 2¶: 默认候选 ratio 倍增步长。

const double R_MAX = 256¶: 无库时默认 GIO ratio 上限。

const double R_MIN = 1¶: ratio 的绝对下限。

const DelayLibrary *delayLib = nullptr¶: 非拥有型延迟库指针。

Private Functions

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)¶: 对边集执行带上下界的 sum(1/ratio)=capacity 投影。

inline RatioLib edge_lib(int u, int v)¶: 根据物理拓扑为有向边选择初始 GIO/MGT 类型。

Private Members

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¶: 指数衰减速率。