Routing 模块技术手册

1. Routing 在完整流程中的位置

Partition 决定逻辑节点属于哪个 FPGA/Die；Routing 在固定划分结果上选择跨分区线网的物理互连；TDM 再在已选共享链路上分配最终复用比例和延迟。

图 1：从 Partition 输出到 TDM 输入的七阶段 Routing 流程。

2. 算法总览

2.1 布线闭环

默认时序布线是一个“投影—排序—增量布线—全局评估—拆线重布”的闭环，不是一次固定权重最短路。

cut_nets, cut_paths = reform_timing_paths()
order = timing_order(zero_load_shortest_distance)

baseline   = route_all(common_cost, order)
timingSeed = route_all(timing_externality_cost, order)
current    = discrete_score_and_choose(baseline, timingSeed)

repeat:
    targets = nets_on_lowest_slack_paths(current)
    backup_all_incremental_state()
    rip_up(targets)
    reroute(targets)
    if discrete_global_score() improves: commit
    else: rollback; break

2.2 板级与 Die 级布线

2.3 多层级拓扑处理

fpga_hierarchy_paths[i] 描述第 i 个 FPGA 从高层容器到本地位置的层级路径。典型结构如下：

Rack
└── Cluster
    └── Board
        └── FPGA
            └── Die

四级路径可区分 Rack、Cluster、Board；三级路径可区分 Cluster、Board；二级路径可区分 Board。缺少有效层级路径或分范围延迟模型时使用 Default 模型。

3. 核心数据结构

3.1 cut_net

3.2 cut_timing_path

operator== 与哈希均比较 path 和 arcs，它们共同定义当前压缩等价类。

3.3 两种布线树

flat_hash_map<int, set<pair<int,int>>> route_trees;
flat_hash_map<int, vector<RouteTreeEdge>> route_trees_edges;

前者服务算法与 TDM；后者带稳定端口名和分区端点，服务结果回写。

4. 割线网提取与时序路径压缩

4.1 割线网提取

reform_timing_paths() 只保留端点跨越两个及以上物理分区的 net。fpga_nodes[0] 为源分区，其余为去重汇分区；net_id 保留原始 net ID，new_net_id 建立它到局部 cut-net ID 的映射。

4.2 路径投影与折叠

逻辑节点: a0 -> a1 -> b0 -> b1 -> c0
物理分区: A  -> A  -> B  -> B  -> C
投影路径: A  --------> B  --------> C
割线网弧:      net_x        net_y

连续落在同一物理分区的逻辑节点被折叠，只保留真实割事件。全程同分区、映射无效、没有有效割边或缺失必要时钟信息的路径不会进入时序布线。

4.3 等价类与最坏代表

Routing 以 (path, arcs) 为压缩键。键相同的路径只保留 slack 较小者，并保存其原始路径 ID。

图 2：先折叠连续同分区节点，再按物理节点序列和割线网序列去重。

key = (projected_physical_nodes, projected_cut_net_arcs)
if key is new:
    representative[key] = path
else if path.slack < representative[key].slack:
    representative[key] = path

压缩只减少布线阶段的重复计算；最终签核仍应在完整原始路径集合上进行。

5. 时序路径与线网排序

5.1 零负载延迟预测

统一板级布线先在零负载拓扑上计算最短距离。压缩路径的预测 slack 为原始裕量减去所有割事件的预计物理延迟：

cut_slack 越小，路径越先布线。各算法分支的平局规则略有不同，调试和性能记录应同时保存实际模式参数。

5.2 路径顺序转换为 net 顺序

P0: n3 -> n8 -> n5     (最关键)
P1: n8 -> n2
P2: n7 -> n3

首次出现顺序: n3, n8, n5, n2, n7

扫描路径时，同一 net 只加入一次。没有出现在压缩路径中的剩余割线网按静态 routing_cost 从大到小追加。

• d_max：最远汇端距离；
• d_avg：所有汇端平均距离；
• γ：routing_cost_factor；
• η_clock：相应分支启用的多时钟归一化项。

6. 候选边的容量、延迟与时序外部性

对候选有向边 (u,v)，布线器检查方向、GIO/MGT 容量、bypass 类型、离散 TDM 档位、候选自身延迟以及它对既有关键流量造成的延迟增长。不可行候选直接设为无穷大。

6.1 异构链路估计

new demand
   |-- GIO split q_gio -> ratio r_gio -> delay D_gio
   `-- MGT split q_mgt -> ratio r_mgt -> delay D_mgt

check direction / capacity / clock / bypass
choose minimum-delay feasible split

estimate_link 会在离散选择边界附近试探负载拆分。新增一条线网可能让比例从 r 跳到 r+1，从而同时提高已在该边上的连接延迟。

6.2 代价模式

图 3：短路径若触发拥塞链路的 TDM 档位跃迁，可能劣于较长但低外部性的路径。

7. Dijkstra 选择与多汇布线树

统一板级布线从 fpga_nodes[0] 执行一次动态边权 Dijkstra，得到 prev[]，随后从每个汇端回溯到源端。共享树干通过 visited 去重，回溯边并集构成布线树。

source S
  |\
  | `---- X ---- sink B
  `------ Y ---- sink A
          `----- sink C

7.1 增量状态更新

1. 增加有向 route_load[u][v]；
2. 更新兼容统计使用的 cut_mat；
3. 登记关键链路使用；
4. 立即刷新受影响的 cost_mat。

因此后布线 net 会看到前面 net 已造成的拥塞和 ratio 变化，避免大量线网同时抢占一条静态“便宜边”。

7.2 不可达的常见原因

• 方向容量为零或拓扑断开；
• GIO/MGT 离散选择均不可行；
• bypass 类型与边不匹配；
• 容量矩阵尺寸或节点映射错误。

8. 离散全局评估与初始种子

Dijkstra 使用局部边代价，而最终 TDM 比例由整张布线共同决定。统一布线会执行 dry-run 离散打包，并用同一口径评分 common baseline 和 timing seed。

两个初始解都经过离散全局评分后再选优，避免局部时序估计破坏整体可行性。

9. 关键路径拆线重布

9.1 目标选择

板级统一布线执行至多 K 轮重布，候选不再改善时提前结束。每轮选择一组当前 slack 最差的压缩路径，取其 arcs 并集作为目标线网；路径内线网按最差 slack 优先，其余按 routing_cost 排序。K 和关键路径数量目前由对应布线分支内部的迭代上限控制，尚未接入顶层配置参数。

图 4：拆线重布是带全状态备份、提交与回滚的事务。

9.2 全状态事务

backup:
  route_trees, route_graph, route_load,
  cut_mat, cost_mat, critical_link_usage

rip-up -> decrement loads -> refresh costs
reroute -> update loads/costs after each edge
evaluate -> discrete global RouteScore

improved: commit
otherwise: restore every backed-up structure

只恢复布线树而不恢复负载或代价会污染下一轮，因此回滚必须覆盖全部增量状态。

9.3 板级验收

• 候选必须可行；
• min_slack 改善超过 1e-3 时提交；
• 在 critical_minmax 系列中，slack 精确持平时依次比较最差路径跳数、层次跨度、总边数、最大利用率；
• 否则回滚并结束本轮重布循环。

9.4 Die 级差异

die_routing() 使用相同的迭代上限与提前终止框架，但每轮围绕单条最差路径。候选需要 slack 改善超过 1e-3，且不能同时让 TDM cut 和 die cut 变坏。

10. 参数速查与流程分支

10.1 顶层开关

10.2 test 分支

test=1..5 用于实验对照；常规流程建议使用 test=0。

10.3 代价参数

11. 输入、构造与调用

11.1 流程调用

vector<CutConnection> cutConnections;

routing_flow::routingFlow(
    finest, parts, die_parts, fpgas, cutweights,
    para, router, pFlow, &delayLib, cutConnections);

if (para.route) {
    tdm::executeTDM(router, fpgas, para, delayLib);
}

有 Die 模式必须保证 die_parts.size() == finest.nodes.size()，展平编号为 fpga_id * dies_per_fpga + die_id。

12. 输出检查与调试顺序

routingFlow() 会写出 routing_cut_info.json；其中 top_port_connection 保存参与布线的跨分区端口，route_graph 保存有效父节点图。

1. 检查投影：cut_net.net_id/fpga_nodes 与 cut_timing_path.path/arcs；
2. 检查可达：方向容量、GIO/MGT 类型、bypass 限制；
3. 检查树：每个汇端是否能沿父节点回到源端；
4. 检查负载：每条树边是否只在 route_load/cut_mat 计数一次；
5. 检查离散可行性：ratio 档位、方向超限和延迟库；
6. 检查 slack 口径：压缩、多时钟归一化和 TDM 延迟是否一致；
7. 检查回滚：失败候选后所有备份结构是否同时恢复。

13. 算法环节与代码位置

14. 常见问题与调优

Q1：只设置 route=true，为什么没有进入无 Die 布线？

无 Die 分支还要求 IO 约束有效且 cutweights 非空。检查平台容量解析和 Partition 是否产生跨 FPGA 线网。

Q2：为什么有空布线树？

可能是投影后仅剩一个物理端点，也可能是方向、类型或离散容量使汇端不可达。先区分“无需布线”和“布线失败”。

Q3：没有延迟库能否运行？

可以退回默认延迟模型，但异构 GIO/MGT 的档位延迟可能不够准确。性能比较和时序回归应固定延迟库版本。

Q4：为什么最短跳数路径没有被选中？

时序模式优化插入后的延迟和对既有关键流量的影响，而不是纯 hop count。TDM 档位跳变或层级范围变化可能让更长路径具有更低全局代价。

Q5：为什么拆线后 slack 没改善就立即回滚？

当前实现采用保守的单调验收，避免用暂时恶化 WNS 的中间状态换取不确定的后续收益。