TDM 模块技术手册

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

Partition 确定逻辑节点所属的 FPGA/Die，Routing 生成跨分区布线树，TDM 再在已经选定的物理连接上分配 GIO/MGT 类型、离散复用比和实际通道位置。

图 1：从 Partition 与 Routing 结果到稳定 TDM 输出的六阶段流程。

2. 算法总览

2.1 六阶段分配闭环

默认流程使用连续时序优化确定分配方向，再由离散合法化保证结果可实现。

build_tdm() + buildGraphEdges()
        ↓
initialize ratio / lib choice / capacity
        ↓
arrival + slack → edge criticality μ
        ↓
continuous capacity projection
        ↓
GIO/MGT selection + discrete choices
        ↓
direction/socket/root/lane/clock legalization
        ↓
discrete global score → commit or rollback

2.2 板级与 Die 级编号

executeTDM() 从 die_parts 生成 node_to_route_part。存在非零 Die ID 或 has_die=true 时使用展平 Die 编号，否则保留 FPGA ID。

2.3 多层级拓扑如何参与 TDM

图 2：层级路径决定 delay scope，并贯穿边状态、连续斜率和离散延迟查询。

四级路径可区分 Rack、Cluster、Board；三级路径可区分 Cluster、Board；二级路径可区分 Board。缺少层级路径、缺少分范围模型或处于 contest 模式时使用基础延迟语义。

3. 核心数据结构

3.1 timing_edge

timing_edge 表示内部时序 DAG 的一条有向边，真实物理布线段和连接路径使用的 dummy 边共用该结构。

3.2 tdm_group

tdm_group 聚合同一无向物理分区对之间的全部 TDM 边。规范化后 left_part < right_part；edges[0, backward_id) 为正向，余下为反向。组内保存双向容量、socket/root/lane、连续容量、乘子及关联边。

图 3：同一物理分区对的双向边共享容量组，但两个方向分别受约束。

3.3 bidir_map 与内部 DAG

bidir_map::operator[] 具有插入语义；只读检查使用 contains() 或 try_get()。

3.4 DelayLibrary

统一提供 PWL delay(ratio) 与 slope(ratio)、ratio 边界、离散 choices、bypass 语义及多层级 scope 覆盖。

4. 阶段 1：输入投影、构图与容量分组

4.1 executeTDM() 组装输入

先复用 Routing 已加载的延迟库；若尚未加载且配置了 delay_lib_path，再读取 JSON。随后生成 node_to_route_part，把布线树、割线网、割时序路径、容量矩阵、时钟信息和求解参数传入 Tdm。

4.2 build_tdm() 创建真实边

1. 把原始 net ID 映射为局部 cut-net 索引；
2. 为布线树物理段创建或复用 DAG 节点；
3. 区分片内固定延迟与跨 FPGA TDM 边；
4. 将跨 FPGA 边加入规范化容量组；
5. 记录方向、容量、端口、clock 和 delay_scope；
6. 用 backward_id 分隔两个方向。

4.3 buildGraphEdges() 串接时序路径

按 cut_timing_paths 串接相邻 cut-net，将路径段映射到真实布线树父节点链；同时加入超级源、超级汇 dummy 边，生成入边、出边和拓扑顺序，使 arrival、slack 与关键权重能在完整 DAG 上传播。

5. 阶段 2：ratio 初始化与连续优化

5.1 ratio 的容量含义

ratio 表示一条物理通道时分承载的逻辑信号数。ratio 越小通常延迟越低，但消耗的物理容量份额越大。

r_e 是连续 ratio，C 是对应方向的 GIO channel 或 MGT lane 容量。

5.2 初始化

初值由方向负载、容量、延迟库边界和 bypass 约束决定，默认优先 GIO；无 GIO 但有 MGT 时直接选 MGT。

5.3 时序权重

arrival/slack 分析把物理边延迟传播到完整路径，并为关键边产生权重 μ。关键程度越高、delay slope 越大，连续优化越倾向于分配更小 ratio。

5.4 拉格朗日松弛模型

连续阶段暂时移除离散档位和物理装箱，只保留时序代价与共享容量。令 μ_e 为关键权重、s_e 为当前延迟曲线局部斜率，并定义 w_e=max(μ_e·s_e, ε)，容量组子问题为：

为容量约束引入非负乘子 λ_g：

对未触及边界的 ratio 应用 KKT 条件，可直接得到：

μ_e·s_e 越大，边越关键，ratio 越小；容量越紧张，λ_g 越大，组内 ratio 整体增大。因此 λ_g 可以理解为容量组的“拥塞价格”。ratio 触及上下界时，投影固定越界边、扣除其占用，再为自由边重算乘子和 ratio；有方向容量时 forward/backward 分别处理。

5.5 当前实现的连续迭代

1. 建立初始权重：在 DAG 上计算 arrival，由超级汇沿逆拓扑传播 μ，并结合 preceding TDM edge 延迟形成初始关键度。
2. 计算容量价格：每组汇总 √(μ_es_e)，按容量计算 λ_g。
3. 更新 ratio：使用闭式关系生成浮点候选，对零权重和数值异常使用安全上界。
4. 恢复容量可行性：限制 ratio 范围，再按 cap_cont 缩放或投影，并检查方向容量。
5. 刷新时序：更新 delay，沿拓扑顺序重算 edge/node arrival 与 arrival gap。
6. 重新分配关键权重：增加临界入边的 μ、减少非关键入边的 μ，并通过逆拓扑传播保持权重流量一致。
7. 保存最优连续解：仅在目的节点 arrival 改善时更新 ratio 快照。
8. 判断收敛：改善小于阈值或连续达到稳定次数时提前结束，否则至多执行 max_iters 次。

代码中的 lambda_velocity 保留容量惩罚的动量状态，但当前 ratio 主更新采用 KKT 闭式容量价格。浮点解只作为 GIO/MGT 选择和离散合法化的高质量起点，不直接导出。

6. 阶段 3：GIO/MGT 选择与离散化

6.1 类型选择

混合分配综合关键边权重与 slack 收益、scope ratio-delay 曲线、双向容量、GIO root/socket、MGT link/lane 及 clock domain 可行性选择 GIO 或 MGT。

默认不允许未出现在 cut_timing_path 上的边占用 MGT；allow_mgt_on_non_timing_edges=true 可放宽限制。

6.2 离散 choices

连续 ratio 必须映射到所选类型的离散 choices。类型或 ratio 改变后立即用 scoped_lib_delay() 刷新延迟。

continuous ratio 37.4
        │ GIO choices: 32, 64, 128
        │ MGT choices: 62, 124, 248
        ↓
select lib + feasible discrete ratio + scope delay

7. 阶段 4：物理合法化、评价与后处理

连续容量可行并不等于实际通道可装箱。离散合法化还检查双向 GIO/MGT 容量、真实 channel 桶、socket 与 GIO root、MGT lane 与 clock domain、bypass 语义，以及 signal slot 重复或越界。

图 4：连续解经离散档位、物理装箱和全局时序评分后提交或回滚。

7.1 离散全局评价

候选合法化后，在完整 DAG 上重算离散 delay、arrival 与 slack，并检查方向容量和装箱。只有可行且评分不退化的候选才保留，否则恢复快照。

7.2 后处理

tdm_opt_mode 可控制 GIO root 方向拆分、final/score polish、worst-path rescue、winner 后处理和容量补齐。局部后处理按策略上限执行，没有改善或候选不可行时提前结束。

8. 延迟库 JSON

8.1 data/delay.json 的标准结构

{
  "gio": {
    "points": [
      [2, 4.57], [8, 58], [16, 62], [24, 67], [32, 72],
      [40, 77], [48, 81], [56, 86], [64, 90], [72, 95],
      [80, 100], [88, 105], [96, 110], [104, 115],
      [112, 120], [120, 125], [128, 130], [136, 135],
      [144, 140], [152, 145], [160, 150], [168, 155],
      [176, 160], [184, 165], [192, 170], [200, 175],
      [208, 180], [216, 185], [224, 190], [232, 195],
      [240, 200], [248, 205], [256, 210]
    ]
  },
  "mgt": {
    "points": [
      [62, 96], [124, 104], [248, 124], [496, 154], [992, 216]
    ]
  }
}

points 中每项依次为 [ratio, delay_ns]。根对象必须同时包含可用的 gio 和 mgt，每类至少提供两个不同 ratio 的采样点。

8.2 buildFromJson() 的自动推导

• min_ratio 和 max_ratio 缺省时使用首尾采样 ratio；
• choices 缺省时使用全部采样 ratio；
• GIO bypass 缺省时使用最小采样点 [2, 4.57]；
• 采样点会按 ratio 排序、合并重复值并构造 PWL 与回退模型；
• delay_detail.json 的对象形式采样点和根级 bypass 同样可解析，但当前不读取其中的 fit、fallback_linear 和 low_range_linear 字段。

8.3 scope 覆盖

"scopes": {
  "board":         { "mgt": { "offset_ns": 0.0 } },
  "inter_board":   { "mgt": { "offset_ns": 38.79 } },
  "inter_cluster": { "offset_ns": 128.007 },
  "inter_rack":    { "offset_ns": 160.0 }
}

scope 可提供独立 points，也可继承基础模型并叠加 offset_ns、delay_offset_ns 或 add_delay_ns。只覆盖一种链路时，另一类型回退到基础模型。

9. 输出文件

9.1 tdmDelayReport.json

按物理分区 pair 输出两端 FPGA/Die 与层级路径、双向容量、socket pair、物理 channel 的类型/ratio/delay/signal slots，以及原始 net_id、端口和 ratio_index。

9.2 routing.out

逐 hyperedge 输出拓扑规模、类型数量，以及各 net 的 source、sinks、物理路径、ratio、delay、类型和端口布线段。

9.3 条件输出

固定相对路径的文件多为覆盖写入；多实例并发运行应使用不同工作目录。

10. 参数速查与流程分支

10.1 调度优先级

10.2 TDMParams

10.3 tdm_opt_mode

contest 模式优先于该参数：无论配置哪个值，都会关闭普通流程的 root split、final polish、winner 后处理和 slack μ 特性，使用 contest 自身的处理语义。

11. 输入、构造与流程调用

11.1 前置状态

• 布线树、割线网与原始 net ID 可互相对应；
• cut_mat 覆盖全部展平节点；
• 时序模式下割时序路径与 route_graph 完整；
• Die 模式下 die_parts、die_graph 与 dies_per_fpga 一致；
• 延迟库可解析，或明确接受 fallback；
• 输入对象生命周期覆盖求解过程。

11.2 流程调用

DelayLibrary delayLib;

// routing_flow::routingFlow(...) 已填充 router。
if (para.route) {
    tdm::executeTDM(router, fpgas, para, delayLib);
}

executeTDM() 完成延迟库复用/加载、Tdm 构造、模式选择和标准结果导出。

12. 输出检查与调试顺序

1. 编号一致：局部 net ID 正确映射到 cut_nets；
2. DAG 闭合：拓扑排序覆盖有效节点，source 到 sink 可达；
3. 组方向正确：backward_id 准确分隔方向；
4. 连续容量可行：每方向、每类型的 Σ1/r 不超过容量；
5. ratio 可实现：最终 ratio 属于对应 choices；
6. 物理装箱可行：socket/root、方向桶、lane/clock 满足约束；
7. 延迟已刷新：离散化或切换类型后重新查询；
8. 全局评分一致：离散 WNS 与 winner 日志一致；
9. 输出完整：JSON slot 无重复，文本报告覆盖所有 sink。

13. 算法环节与代码位置

14. 常见问题与调优

Q1：为什么 delay library 加载失败后仍继续？

流程记录可降级告警并使用 fallback ratio 和线性延迟。生产运行应将告警视为配置错误。

Q2：为什么离散 ratio 不在预期集合？

choices 缺省时从 PWL 横坐标推断；加载失败也会进入 fallback。检查加载日志、delayLibReady 和 scope choices。

Q3：为什么某个方向仍然容量溢出？

Σ1/r 可行不保证真实 channel/socket 可装箱。检查方向容量、GIO root、socket、MGT lane/clock 和合法化告警。

Q4：为什么 MGT 分配很少？

默认保护非时序边不使用 MGT；lane、clock domain 或离散 ratio 也可能使候选不可装箱。

Q5：为什么 test=3/4/5 没有标准 JSON？

这些分析型分支完成分析后直接返回。需要标准输出时使用默认流程、avg_only 或 contest 流程。

Q6：为什么层次 scope 没有启用？

需要延迟库加载成功、JSON 含 scopes、层级路径非空，并且当前不是 contest 基础延迟语义。

Q7：为什么连续优化采用拉格朗日松弛法？

直接同时枚举全部边的 GIO/MGT、离散 ratio 和物理通道会形成很大的组合搜索；平均分配又无法区分关键路径。拉格朗日松弛提供了更合适的连续层：

• 容量组可分解：固定时序权重后，各 tdm_group 独立计算容量价格和 ratio，核心更新具有闭式形式，单轮代价主要随边数增长；
• 时序与拥塞统一：μ_e·s_e 表示减少 ratio 的时序收益，λ_g 表示共享容量的稀缺程度；
• 关注关键路径：关键边获得较小 ratio，非关键边主动让出容量；
• 连续方向更平滑：浮点解避免频繁档位跳变，并为后续离散策略缩小搜索范围；
• 适配多层级延迟：替换不同 scope 的局部 slope 后，模型与求解形式保持不变。

该方法只解决连续容量分配，不替代离散合法化；最终仍须经过 choices、GIO/MGT、socket/root/lane/clock 装箱和离散全局 WNS 验收。

调优优先级

1. 先确保延迟库、方向容量和真实装箱可行；
2. 校验 Die 展平编号、层级路径和 scope；
3. 用 avg_only 建立容量与导出基线；
4. 对比 root split、final polish 和 v2；
5. 再调整迭代上限、收敛阈值和学习率；
6. 同时观察离散 WNS、利用率、GIO/MGT 使用和可装箱性。