102 lines
5.2 KiB
Markdown
102 lines
5.2 KiB
Markdown
# 50 MHz 时序收敛分析与修复方案
|
||
|
||
> 报告来源:`synth_timing.tcl`（OOC 综合 `mlkem_top`，器件 `xc7a200tfbg676-1`，
|
||
> `sysclk` 20 ns / 50 MHz）。生成 `timing.rpt` / `timing_worst.rpt` / `util.rpt`。
|
||
|
||
## 一、现状
|
||
|
||
| 指标 | 值 |
|
||
|:---|:---|
|
||
| WNS | **-32.206 ns**（目标 20 ns，实际关键路径 ~52 ns） |
|
||
| TNS | -37879 ns，失败端点 3132 / 44689 |
|
||
| Hold (WHS) | +0.134 ns ✅（无 hold 违例） |
|
||
| 关键路径 | `u_pmul/mem_A_reg[239][2]` → `u_pmul/c0_reg_reg[0]` |
|
||
| 路径延迟 | 52.055 ns（逻辑 21.9 ns / 布线 30.1 ns），**70 逻辑级**（CARRY4×26 + LUT×43 + MUXF×3） |
|
||
| 面积 | LUT 25.5%、FF 8.6%、BRAM ~5 片、**DSP 0 / 740（完全没用）** |
|
||
|
||
之前那份 `timing.rpt`（WNS -17.7 ns，关键路径在 comp_decomp 的组合除法器）已经过时——
|
||
`717a992` 用 Barrett 乘法替换了组合除法器,comp_decomp 不再是瓶颈。本次重新综合后,
|
||
**瓶颈转移到 `poly_mul` 的 basecase 乘法器 `u_pmul`**。
|
||
|
||
## 二、根因
|
||
|
||
`basecase_mul`（NTT 域 degree-1 乘法）单周期组合计算 c0/c1:
|
||
|
||
```
|
||
c0 = (a0·b0 + (a1·b1)·zeta) mod Q
|
||
c1 = (a0·b1 + a1·b0) mod Q
|
||
```
|
||
|
||
c0 这条路径**串联了两级 Barrett 模乘**:先 `t2 = a1·b1 mod Q`,再 `t2_zeta = t2·zeta mod Q`,
|
||
最后再做一次模加。每级 `barrett_mul` 含 12×12 乘 + ×K 乘 + ×Q 移位加 + 两次条件减,
|
||
而且全局带 `(* use_dsp = "no" *)` —— 所有乘法都摊成 LUT+CARRY4 阵列。两级串联 ⇒ 70 级、52 ns。
|
||
|
||
**两个叠加的放大因素:**
|
||
1. **串联两次 Barrett 模乘**(t2 → t2·zeta)挤在一个组合周期。
|
||
2. **`use_dsp="no"`** 把每个乘法变成进位链,本可用的 740 个 DSP48 一个没用。
|
||
|
||
> 注:此前给乘法器加 `use_dsp="no"` 多半是为了规避 XSIM 仿真问题;但综合时这逼着工具
|
||
> 用 LUT 搭乘法,正是当前 52 ns 关键路径的主因。
|
||
|
||
## 三、修复方案（约束:**不允许使用 DSP**，纯 LUT/CARRY4 流水化）
|
||
|
||
> 实测细节(timing_worst.rpt 逐级):一个 `barrett_mul` 单独就要 **~24 ns**
|
||
> (t2 = a1·b1 走到 ~28 ns,其中乘法本体 + ×K + ×Q 约简占大头),c0 又把
|
||
> **两个 Barrett 串联**(t2 → t2·zeta)+ 模加 ⇒ 52 ns。
|
||
> 关键结论:**单级 Barrett(~24 ns)本身就超 20 ns**,所以光在两次乘法之间插一拍
|
||
> (26 ns/级)不够,必须**在 `barrett_mul` 内部也切流水**。
|
||
|
||
### 推荐方案:三段式流水的 Barrett 模乘 + basecase 重构
|
||
|
||
把 `a·b mod Q` 拆成 3 个寄存级,每级 < ~12 ns:
|
||
|
||
```
|
||
级1: p = a * b (12×12 → 24b 乘法,纯 LUT/CARRY4) → 寄存 p
|
||
级2: qe = (p * K) >> 24 (24×13 乘法 + 移位) → 寄存 qe、p
|
||
级3: r = p - qe*Q; 两次条件减 Q → 寄存 product
|
||
```
|
||
|
||
- 单个乘法(12×12 或 24×13)在 LUT 上约 ~10–12 ns,加约简一拍单独走,各级都能压到 20 ns 内。
|
||
- `barrett_mul` 从纯组合改成 **3 拍流水**(加 `clk`/`valid` 端口或用上层节拍计数)。
|
||
|
||
basecase 的 c0 双乘串联(`a1·b1` 再 `·zeta`)= 两个 3 级流水级联 = **6 拍**;
|
||
c1 只有单乘 = 3 拍。让两条对齐到 6 拍输出。`poly_mul_sync` 现有
|
||
`S_COMP_CALC → S_COMP_C0 → S_COMP_C1` 节拍改为:CALC 阶段等待乘法流水排空(固定 N 拍),
|
||
再依次输出 c0/c1。**吞吐**:逐点乘本就 1 系数/多拍,加深流水只增加固定启动延迟(~6 拍/128 次
|
||
basecase = 几百拍),相对 KeyGen ~22.9k、Decaps ~50.8k 周期可忽略。
|
||
|
||
### 同源风险:comp_decomp 的 Barrett
|
||
|
||
`comp_decomp_sync` 也用同样的 Barrett 结构(compress 路径 `dividend*5039>>24` + ×Q 约简),
|
||
单条也可能逼近 20 ns。修好 basecase 后若它冒头,同样按“Barrett 内部 3 级流水”处理。
|
||
其 5-phase 微序列(cd_valid 脉冲 + ph 等待)很容易吸收额外流水拍。
|
||
|
||
### 备选:更激进的乘法器结构（若 3 级仍不够）
|
||
|
||
- 12×12 乘法本身用 **2 级流水**(部分积分两半累加),把 Barrett 拉成 4–5 级;
|
||
- 或对乘法做 **基-4/基-8 部分积 + 进位保存加法器(CSA)树**,减少 CARRY4 链深度。
|
||
改动大,仅在 3 级流水实测仍 > 20 ns 时再考虑。
|
||
|
||
## 四、建议路线（不用 DSP）
|
||
|
||
1. 把 `barrett_mul` 改成 3 级流水版(带 clk/valid),单独综合确认单级 < 20 ns。
|
||
2. 重构 `basecase_mul`:c0 路径两级 Barrett 级联(6 拍),c1 对齐;`poly_mul_sync` 节拍
|
||
按固定流水深度调整(CALC 等 N 拍再出 c0/c1)。
|
||
3. 全量 KAT 复测(`run_tb.sh top/enc/dec` + `hello`)确认功能不变 —— 流水加深会改变
|
||
`poly_mul`/`ntt`/`comp_decomp` 的拍数,各 FSM 的 done/valid 判定需同步更新。
|
||
4. 重综合看 WNS;若 comp_decomp 成新瓶颈,同法流水化。
|
||
5. 迭代直到 WNS ≥ 0 @ 20 ns。
|
||
|
||
> 注意:本项目所有时序验证目前靠 XSIM 功能仿真 + KAT,**没有跑过布局布线后时序**。
|
||
> 加流水属于改时序行为的大改,务必每步重跑全部 KAT,确保 ek/dk/ss/ct 仍逐字节正确。
|
||
|
||
|
||
## 五、复现命令
|
||
|
||
```bash
|
||
source /opt/Xilinx/Vivado/2019.2/settings64.sh
|
||
export LD_PRELOAD=/usr/lib64/libtinfo.so.5
|
||
vivado -mode batch -source synth_timing.tcl # 器件在脚本里:xc7a200tfbg676-1
|
||
# 读 timing.rpt(摘要) / timing_worst.rpt(逐路径) / util.rpt(面积、DSP 占用)
|
||
```
|