Class Routing¶

Defined in File routing.h

Class Documentation¶

class Routing¶

多 FPGA/多 Die 互连的路由器与时序驱动重路由状态容器。

路由器根据划分结果和物理连接建立容量/代价矩阵，为每个割线网生成路由树，并可结合 TDM 延迟库和时序路径反复执行拥塞协商与关键线网重路由。输入对象以引用形式保存，因此其生命周期必须覆盖 Routing 实例。

Public Types

enum class LinkType : uint8_t¶

路由边使用的物理链路类型。

Values:

enumerator INTRA¶

enumerator GIO¶

enumerator MGT¶

Public Functions

Routing(const graph &finest, const vector<pair<int, int>> &die_parts, fpga &fpgas, const vector<DieConnection> &die_connections, double cut_delay, double tdm_delay, double die_delay, bool tdm_aware, const shared_ptr<mulClockAttr> &mul_clock_attr, bool has_die, double routing_cost_factor, vector<SimpleTiming> simpleTimings, const DelayLibrary *delayLib)¶

构造路由器并绑定划分、平台、时序及延迟模型输入。

Parameters:

finest – 最细层超图。
die_parts – 节点到 FPGA/Die 的划分映射。
fpgas – 目标硬件平台；路由过程中会更新其相关状态。
die_connections – 物理 Die 连接及方向容量。
cut_delay – 跨 FPGA 固定延迟。
tdm_delay – TDM 延迟系数。
die_delay – 片内跨 Die 固定延迟。
tdm_aware – 是否启用 TDM 感知代价。
mul_clock_attr – 多时钟域归一化属性。
has_die – 是否执行多 Die 层级路由。
routing_cost_factor – 路由代价的外部缩放系数。
simpleTimings – 简化时序路径集合。
delayLib – GIO/MGT 延迟库指针；调用方负责其生命周期。

inline RatioLib edge_lib(int u, int v)¶: 根据物理边上可用的链路类型选择相应的 TDM 延迟库。

void die_routing()¶: 执行当前默认的多 Die 路由与时序驱动重路由流程。

void die_routing_1()¶: 执行保留的第一版多 Die 路由流程，用于实验对照。

void die_routing_huang()¶: 执行 Huang 路由策略的 Die 级版本。

void board_routing_huang(const vector<int> &parts)¶

执行 Huang 路由策略的 FPGA 板级版本。

Parameters:: parts – 节点到 FPGA 的划分映射。

void die_routing_old()¶: 执行旧版多 Die 路由流程，用于兼容与回归对照。

void die_routing_direction()¶: 在调整链路方向后执行多 Die 路由。

void die_routing_synergistic_paper()¶: 执行论文中的协同式 Die 级基线算法。

void die_routing_near_optimal_paper()¶: 执行论文中的近最优 Die 级基线算法。

void board_routing_synergistic_paper(const vector<int> &parts)¶

执行论文中的协同式 FPGA 板级基线算法。

Parameters:: parts – 节点到 FPGA 的划分映射。

void board_routing_near_optimal_paper(const vector<int> &parts)¶

执行论文中的近最优 FPGA 板级基线算法。

Parameters:: parts – 节点到 FPGA 的划分映射。

void die_routing_negotiation_paper(const std::string &tag, const vector<int> *board_parts = nullptr)¶

执行论文基线共用的协商拥塞路由实现。

Parameters:

tag – 日志中标识当前基线策略的标签。
board_parts – 非空时执行板级路由并使用该 FPGA 划分；为空时执行 Die 级路由。

void export_routing_trees(flat_hash_map<int, vector<RouteTreeEdge>> &trees)¶

将内部拓扑边集转换为带端口名称的路由树。

Parameters:: trees – [out] 原始线网编号到命名路由边列表的映射。

void die_graph_from_connections()¶: 根据物理 Die 连接建立容量矩阵及 GIO/MGT 链路矩阵。

void build_board_capacity_from_connections()¶: 根据物理连接或平台通道配置建立 FPGA 级有向容量矩阵。

void init_mat(bool board_level = false)¶

初始化链路占用、代价、增量和 TDM 矩阵。

Parameters:: board_level – true 时按 FPGA 板级节点初始化，否则按展平 Die 节点初始化。

void ensure_type_aware_mats()¶: 确保 GIO/MGT 类型感知负载矩阵与当前拓扑尺寸一致。

double typed_edge_weight(int u, int v, LinkType tp) const¶

计算指定物理链路类型在当前负载下的边代价。

Returns:: 链路不可用时返回 INF_COST，否则返回固定代价与边际延迟之和。

void dijkstra_typed(int s, std::vector<double> &dist, std::vector<int> &parent_node, std::vector<LinkType> &parent_type) const¶

执行同时区分片内、GIO 和 MGT 并行边的单源最短路。

Parameters:

s – 源拓扑节点。
dist – [out] 源点到各节点的最短代价。
parent_node – [out] 最短路径树中的父节点。
parent_type – [out] 到达各节点所使用的链路类型。

void apply_path_and_update(int src, int dst, const std::vector<int> &parent_node, const std::vector<LinkType> &parent_type, std::set<std::pair<int, int>> &route_tree)¶: 回溯一条类型感知最短路径，并提交其负载和动态代价更新。

void route_one_net_gio_mgt(int net_local_id)¶

使用 GIO/MGT 类型感知最短路路由一个局部割线网。

Parameters:: net_local_id – 线网在 cut_nets 中的局部编号。

void route_nets_gio_mgt_min_delay(const std::vector<int> &net_order)¶: 按给定顺序批量执行 GIO/MGT 最小时延路由。

void adjust_die_graph_direction(bool board_level = false)¶

根据双向流量和容量调整可用方向。

Parameters:: board_level – true 表示处理 FPGA 板级拓扑，否则处理展平 Die 拓扑。

void adjust_die_graph_direction_old()¶: 使用旧版规则调整 Die 链路方向。

void adjust_die_graph_direction_contest()¶: 使用比赛版本规则调整 Die 链路方向。

void adjust_die_graph_direction_update()¶: 根据当前路由占用增量更新链路方向。

void check_cut(vector<vector<int>> &cut_weights)¶: 统计路由树在各拓扑边上的割线数量并记录诊断信息。

void calc_die_dist(bool board_level = false)¶

计算全部拓扑节点对之间的最短路距离。

Parameters:: board_level – true 表示按 FPGA 节点判断跨板边，否则按展平 Die 节点判断。

void routing_huang_impl(const vector<int> *board_parts)¶

Huang 路由策略的板级/Die 级共享实现。

Parameters:: board_parts – 非空时使用 FPGA 划分执行板级路由，为空时执行 Die 级路由。

void export_cut_info()¶: 将跨 FPGA 路由端口连接信息写入 die_cut_info.json。

vector<int> build_target_net_order(const unordered_set<int> &target_nets, const vector<cut_timing_path> &cut_timing_paths, const vector<cut_net> &cut_nets, bool isMultiClock)¶

为待重路由线网生成时序优先的处理顺序。

Returns:: cut_nets 中的局部线网编号序列；路径内线网优先，随后按路由代价排序。

SlackStat recompute_cut_slack(const vector<cut_timing_path> &cut_timing_paths, const vector<cut_net> &cut_nets, const vector<vector<double>> &cost_mat, const vector<vector<int>> &cut_mat, bool tdm_aware, bool update)¶

根据当前路由代价重新计算全部割时序路径的 slack。

Parameters:: update – true 时将结果写回每条路径的 cut_slack。
Returns:: 最小 slack 以及对应路径的 TDM/Die 割边计数。

void classify_critical_nets(const vector<cut_net> &cut_nets, vector<int> &critical_nets, vector<int> &non_critical_nets)¶

按线网引脚规模的数量级差异划分关键与非关键线网。

Parameters:

critical_nets – [out] 关键线网的局部编号。
non_critical_nets – [out] 非关键线网的局部编号。

void routing(const graph &finest, const vector<int> &parts, const fpga &fpgas, const shared_ptr<mulClockAttr> &mul_clock_attr, double tdm_delay, float &cut_delay, flat_hash_map<int, set<pair<int, int>>> &route_trees, vector<SimpleTiming> &simpleTimings)¶

在 FPGA 级拓扑上执行基础时序/TDM 感知路由。

Parameters:

route_trees – 输出的原始线网编号到路由树边集映射。
cut_delay – 输入并回传流程使用的跨 FPGA 固定延迟。

inline double lib_delay(RatioLib lib, double r) const¶: 查询指定链路库在 TDM 比例 r 下的延迟。

inline double lib_slope(RatioLib lib, double r) const¶: 查询指定链路库在 TDM 比例 r 附近的延迟斜率。

DelayScope delay_scope_for_parts(int src_part, int dst_part) const¶: 根据两个分区编号判断延迟库查询所需的互连层级。

inline double scoped_lib_delay(DelayScope scope, RatioLib lib, double r) const¶: 按互连层级查询延迟；层级模型不可用时退化到通用模型。

inline double scoped_lib_slope(DelayScope scope, RatioLib lib, double r) const¶: 按互连层级查询延迟斜率；层级模型不可用时退化到通用模型。

Public Members

const graph &finest¶: 待路由的最细层超图。

const vector<pair<int, int>> &die_parts¶: 节点到 {FPGA, Die} 的划分映射。

fpga &fpgas¶: 目标硬件平台的资源、拓扑和通道容量。

const vector<DieConnection> &die_connections¶: FPGA/Die 间物理连接及方向容量。

const shared_ptr<mulClockAttr> &mul_clock_attr¶: 多时钟域归一化属性，可为空。

vector<SimpleTiming> simpleTimings¶: 输入的简化时序路径集合。

flat_hash_map<int, set<pair<int, int>>> route_trees¶: 原始线网编号到拓扑路由树边集的映射。

flat_hash_map<int, vector<RouteTreeEdge>> route_trees_edges¶: 可供后续网表处理使用的命名路由边。

vector<cut_timing_path> cut_timing_paths¶: 投影到路由拓扑后的割时序路径。

vector<cut_net> cut_nets¶: 需要跨分区路由的线网列表。

vector<vector<int>> cut_mat¶: 当前每条有向拓扑边上的线网使用量。

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

vector<vector<int>> die_graph¶: 展平 Die 拓扑的有效容量矩阵。

vector<vector<int>> die_physical_links¶: 各拓扑边的物理链路总数。

vector<vector<int>> die_gio_links¶: 各拓扑边的 GIO 链路数。

vector<vector<int>> die_mgt_links¶: 各拓扑边的 MGT 链路数。

vector<vector<double>> cost_mat¶: 随占用动态变化的当前路由代价矩阵。

vector<vector<double>> inc_mat¶: 每增加一个线网时的边际代价矩阵。

vector<vector<double>> die_dist¶: 拓扑节点间的最短路距离矩阵。

vector<vector<int>> routing_graph¶: 路由过程使用的父节点或邻接状态。

unordered_map<cut_timing_path, double> cut_to_tp_id¶: 割时序路径到原始路径编号的映射。

const DelayLibrary *delayLib = nullptr¶: GIO/MGT TDM 比例到延迟的查表模型，不拥有对象。

vector<vector<double>> tdm_mat¶: 每条拓扑边的当前 TDM 比例。

vector<vector<int>> cutweights¶: 路由后统计得到的链路割线权重。

double cut_delay¶: 跨 FPGA 互连的固定延迟分量。

double tdm_delay¶: TDM 比例对应的延迟系数。

double die_delay¶: 片内跨 Die 互连的固定延迟。

bool tdm_aware¶: 是否在路由代价和时序评估中考虑 TDM 拥塞。

string timing_routing_cost_mode = "critical_minmax_hop"¶: 时序驱动路由的代价组合模式。

double timing_hop_penalty_multiplier = 0.5¶: 关键路径额外跳数的惩罚倍率。

bool has_die¶: 是否启用 FPGA 内多 Die 层级路由。

double clock_period¶: 单时钟模式使用的全局时钟周期。

int channel_grouping_capacity¶: 一个 GIO 通道组折算的可路由容量。

vector<Edge> disabled_edges¶: 方向调整后被部分或完全关闭的物理边。

vector<vector<int>> load_gio¶: GIO 链路的当前占用矩阵。

vector<vector<int>> load_mgt¶: MGT 链路的当前占用矩阵。

bool delayLibReady = false¶: 延迟库是否已成功加载并可供查询。

double a = 1.0¶: 路由代价模型的一次项系数。

double b = 0.0¶: 路由代价模型的附加系数。

double c = 0.0¶: 路由代价模型的常数或高阶修正系数。

const int max_negotiation_iter = 1¶: 协商拥塞路由的最大迭代轮数。

int free = 0¶: 当前路由策略使用的自由容量修正量。

double cong_alpha = 9.0¶: 拥塞代价的幂指数。

double cong_lambda = 0.0¶: 拥塞惩罚项权重。

double lambda_jump = 0¶: TDM 档位跳变惩罚权重。

const double INF = numeric_limits<double>::infinity()¶: 通用不可达代价值。

int Wtotal = 0¶: 当前拓扑的通道总数。

double improve_eps = 1e-5¶: 接受重路由改进时使用的数值容差。

bool contest = false¶: 是否启用比赛数据专用的代价和调整逻辑。

bool use_hierarchy_delay = false¶: 是否按片内、板内和板间层级查询延迟库。

Public Static Attributes

static constexpr double INF_COST = 1e100¶: 类型感知最短路使用的不可达代价。

Private Functions

inline int flatten_id(const pair<int, int> &id) const¶: 将 {FPGA, Die} 编号转换为展平拓扑节点编号。

inline pair<int, int> unflatten_id(int id) const¶: 将展平拓扑节点编号还原为 {FPGA, Die} 编号。

Private Members

double routing_cost_factor¶: Die 级路由代价的缩放系数。