# 27 筛法的并行化与平台成本模型

整理日期：2026-10-17。  
适用范围：筛法的算术与访存成本、批量内积、并行更新、低精度筛选，以及实验比较的基本口径。  
前置笔记：[23 多层分桶的参数选择与优化](/knowledge/multilevel-bucketing-optimization/)、[24 重复配对、去重与有效覆盖](/knowledge/duplicate-pairs-and-effective-coverage/)、[26 G6K 与 Pump](/knowledge/g6k-and-pump/)。

沿用当前筛法维数 $s$ 和池大小 $N$。$F$、$C$、$U$ 沿用第 23–24 篇：分别表示向量与中心的过滤测试次数、包含重复与无效对的候选对检查次数，以及至少被检查一次的不同有效源对数量。讨论 $U$ 时，应固定输入池和有效性判据。

本篇关注：算法产生的工作量，怎样通过数据组织与硬件执行转化为实际耗时。

## 1. 从操作次数到运行成本

如果每次过滤与候选检查都计算一个完整的 $s$ 维内积，仅内积部分就约需

$$
2s(F+C)
$$

次标量算术操作，这里乘法与加法各计一次。若加入预筛，应改用实际执行的完整内积数量。

但相同的 $F,C$ 可以对应不同的运行时间：连续扫描与随机读取、逐对计算与批量计算，以及不同的数据表示，都可能改变每次检查的成本。

还应区分两个量：

- **峰值驻留内存 $M_{\mathrm{peak}}$：** 同时需要存放多少数据。
- **访存流量 $Q_{\mathrm{mem}}$：** 在指定阶段中，跨某一存储层边界累计传输了多少字节。

同一向量池反复读取，容量可以不变，流量却持续增加。估计容量时，也要计入向量的派生表示、桶索引、候选缓冲和并行副本。

例如，G6K 会同时维护整数系数、用于内积的浮点表示、压缩信息等，并使用连续存储与压缩条目组织访问。参见 [G6K，EUROCRYPT 2019，§5.3，PDF 第 20–21 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

## 2. 一个简化的算术—访存模型

固定一个计算阶段及其数值精度，记：

- $K$：按约定口径统计的算术操作数。
- $Q_{\mathrm{mem}}$：跨指定存储边界的读写字节数。
- $R_{\mathrm{op}}$、$R_{\mathrm{mem}}$：模型中的计算吞吐上限和带宽上限，单位分别为操作/秒与字节/秒。

定义运算强度

$$
I=\frac{K}{Q_{\mathrm{mem}}}.
$$

它表示每搬运一个字节，完成多少次算术操作。在上述资源上限模型中，

$$
\boxed{
T_{\mathrm{stage}}
\ge
\max\left\{
\frac{K}{R_{\mathrm{op}}},
\frac{Q_{\mathrm{mem}}}{R_{\mathrm{mem}}}
\right\}.
}
$$

这是 Roofline 思路对应的时间下界，用于识别可能的瓶颈；实际时间还受延迟、调度、同步和负载不均衡影响。参见 [Williams–Waterman–Patterson，Roofline 技术报告，2008，§3，PDF 第 3–4 页](https://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-134.pdf)。

由这个模型可直接看出：当访存项占主导时，只提高算力不会降低该项；通过复用数据减少 $Q_{\mathrm{mem}}$，才可能继续获益。

**存储边界必须明确。** CPU 主存与缓存之间、GPU 显存与片上存储之间、CPU 与 GPU 之间，应分别统计流量与带宽。某一层的流量不能直接代入另一层的带宽。

## 3. 批量内积为什么可能更快

把两组向量在当前正交归一坐标系中的坐标按行排列为

$$
X\in\mathbb R^{m\times s},
\qquad
Y\in\mathbb R^{k\times s}.
$$

这里仅规定批处理的数据布局，仍沿用前文的列基约定。所有交叉内积组成

$$
G=XY^{\mathsf T}.
$$

$Y$ 可以是一批过滤中心，也可以是另一块待比较向量。同一桶内部配对时，还应排除自身配对并避免对称重复。

下面直接估算一个理想的数据复用模型。若每个坐标占 $b$ 字节，两个输入块各从所考察的存储层读取一次，暂不计输出，则

$$
K\approx2mks,
\qquad
Q_{\mathrm{in}}=bs(m+k),
\qquad
\boxed{
I_{\mathrm{in}}\approx\frac{2mk}{b(m+k)}.
}
$$

一次读入的向量可以参与多次内积，因此批量处理能够提高输入数据的复用程度。

这只是输入流量模型。实际还要计入重复加载、表示转换、索引和候选输出；若把完整的 $G$ 写回，还会增加与 $mk$ 成正比的输出空间和流量。

筛法通常只需要通过判据的候选。因此，可以分块计算内积并立即筛选，只输出少量候选信息。Ducas–Stevens–van Woerden 的 GPU 筛法采用了这种计算与筛选结合的方式。参见 [Advanced Lattice Sieving on GPUs, with Tensor Cores，EUROCRYPT 2021，§5，PDF 第 18–20 页](https://ir.cwi.nl/pub/31045/31045.pdf)。

批量也受容量约束：过小难以摊薄搬运和启动开销，过大则可能增加工作集与缓冲需求。第 23 篇的批量参数 $g_\ell$，正是在控制这种执行粒度。

多层分桶还可以逐步缩小工作集，使后续阶段利用更快的缓存。《Sieving with Streaming Memory Access》对各层过滤与末层约化的工作集、算术吞吐和运行时间进行了分别统计。参见 [Zhao–Ding–Yang，TCHES 2025，§4.2、Table 2，PDF 第 9–11 页](https://csrc.nist.gov/csrc/media/events/2025/sixth-pqc-standardization-conference/sieving%20with%20streaming%20memory%20access.pdf)。

因此，参数选择需要同时考虑有效覆盖、检查数量与执行效率。单独减少 $C$，并不能确定总时间下降。

## 4. 并行搜索与向量池更新

筛法中的候选搜索容易划分成多个任务，但共享向量池的更新会产生依赖：多个任务可能找到相同候选，也可能同时尝试替换同一个条目。

为理解这些依赖，可以先使用下面的分批模型：

~~~text
固定当前基、窗口和本批输入
并行执行过滤与候选搜索
各工作线程保存局部候选信息

汇总并重构候选，复核长度与重复
按当前池的接纳规则批量更新
同步派生表示，进入下一批
~~~

在这个模型中，源向量被覆盖之前，应完成依赖它的读取和候选重构；更新时还要处理同批候选之间的重复。

批量提交可以减少共享状态的争用，但会推迟新向量参与搜索，也会改变更新顺序。因此，批量大小可能同时影响硬件效率与筛法进展。

G6K 使用线程局部缓冲、批量更新以及相应的同步机制；上面的流程只是便于分析的分批模型。参见 [G6K §5.4，PDF 第 21–22 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

还需区分两种并行目标：

- **同一任务内部并行：** 多个线程或设备合作处理一个筛法任务，关注该任务完成时间。
- **多个独立任务并发：** 分别维护状态，关注单位时间完成的任务数，并计入各任务的内存占用。

G6K 的并行实验也分别考察了这两种方式。参见 [G6K，Appendix B，PDF 第 33–35 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

增加并行资源后，收益可能受共享带宽、同步或串行阶段限制，需要结合整段运行测量。

## 5. 低精度筛选与候选复核

低精度表示可以减少数据量，并利用相应的矩阵计算单元，但会影响接近阈值的约化判断。

一种常见组织方式是：批量内积使用较低精度，对筛出的候选再用更高精度复核。GPU 筛法论文明确把低精度计算作为候选过滤，并讨论其误差与漏检。参见 [Ducas–Stevens–van Woerden，§5 的 Precision 部分及 Appendix C](https://ir.cwi.nl/pub/31045/31045.pdf)。

这里有两种不同的影响：

- **误报：** 本来不满足判据的候选通过筛选，增加复核与去重成本。
- **漏检：** 本来有效的候选被筛掉，降低有效覆盖，并可能增加后续迭代。

复核只能检查进入候选集的结果，不能补回已漏掉的候选。给筛选阈值留余量可以减少漏检；若要保证不漏检，需要适用的误差上界。

向量表示也应区分用途：整数系数用于确定候选所代表的格向量，几何表示用于快速估计内积与长度。更高精度的复核仍是数值检查；严格的长度保证需要相应的误差控制或精确计算。

因此，评价低精度方案时，要同时考察吞吐、有效覆盖和达到同一目标的总时间。

## 6. 怎样比较一个实现是否更快

实验应说明计时覆盖的范围：

1. **内核时间：** 输入已准备好时，批量内积或过滤本身的耗时。
2. **一轮筛法时间：** 包括数据准备、分桶、搬运、搜索、候选复核与池更新。
3. **完整任务时间：** 包括预处理、提升、基插入，以及达到目标所需的多次调用。

第 26 篇的 Pump 成本属于第三层。某个内核变快，只有在完整任务中仍保留收益，才说明它改善了相应的约化流程。

GPU 操作可能异步执行，计时应覆盖已完成的工作；传输与计算存在重叠时，各阶段独立计时之和也不一定等于总耗时。参见 [NVIDIA CUDA Best Practices Guide，Timing](https://docs.nvidia.com/cuda/cuda-c-best-practices-guide/index.html#timing) 与 [传输和计算重叠](https://docs.nvidia.com/cuda/cuda-c-best-practices-guide/index.html#asynchronous-and-overlapping-transfers-with-computation)。

最少记录以下信息：

- **问题与目标：** 输入实例、维数、初始状态、长度或基质量目标、停止条件。
- **实现与平台：** 代码版本、参数、数值精度、CPU/GPU、线程数与设备数。
- **成本与效果：** 分阶段耗时、总耗时、峰值内存，以及与当前实验对应的覆盖或最终质量。
- **随机波动：** 重复次数、随机种子、成功率和耗时分布。

固定输入实验可以使用 $F,C,U$ 解释工作量与覆盖；完整筛法则需要在一致的目标和成功率要求下比较。资源配置不同时，也应同时说明运行时间与资源用量。

本篇属于筛法专题基础。后续关于 GPU、流式访存或外存筛法的研究增量，可以据此说明：相对哪个基线，改变了哪些计算或数据访问，收益在什么条件下成立，并由什么实验支持。

本文按上述论文版本核对，NVIDIA 在线文档访问日期为 2026-10-17。

## 引用此笔记

- [28 BGJ 筛法的流式访存组织](/knowledge/bgj-streaming-memory-organization/)