整理日期：2026-10-17。
适用范围：筛法的算术与访存成本、批量内积、并行更新、低精度筛选，以及实验比较的基本口径。
前置笔记：23 多层分桶的参数选择与优化、24 重复配对、去重与有效覆盖、26 G6K 与 Pump。
沿用当前筛法维数 \(s\) 和池大小 \(N\)。\(F\)、\(C\)、\(U\) 沿用第 23–24 篇：分别表示向量与中心的过滤测试次数、包含重复与无效对的候选对检查次数，以及至少被检查一次的不同有效源对数量。讨论 \(U\) 时，应固定输入池和有效性判据。
本篇关注：算法产生的工作量，怎样通过数据组织与硬件执行转化为实际耗时。
1. 从操作次数到运行成本#
如果每次过滤与候选检查都计算一个完整的 \(s\) 维内积，仅内积部分就约需
次标量算术操作，这里乘法与加法各计一次。若加入预筛，应改用实际执行的完整内积数量。
但相同的 \(F,C\) 可以对应不同的运行时间：连续扫描与随机读取、逐对计算与批量计算，以及不同的数据表示，都可能改变每次检查的成本。
还应区分两个量：
- 峰值驻留内存 \(M_{\mathrm{peak}}\)： 同时需要存放多少数据。
- 访存流量 \(Q_{\mathrm{mem}}\)： 在指定阶段中，跨某一存储层边界累计传输了多少字节。
同一向量池反复读取，容量可以不变，流量却持续增加。估计容量时，也要计入向量的派生表示、桶索引、候选缓冲和并行副本。
例如，G6K 会同时维护整数系数、用于内积的浮点表示、压缩信息等，并使用连续存储与压缩条目组织访问。参见 G6K，EUROCRYPT 2019，§5.3，PDF 第 20–21 页。
2. 一个简化的算术—访存模型#
固定一个计算阶段及其数值精度，记：
- \(K\)：按约定口径统计的算术操作数。
- \(Q_{\mathrm{mem}}\)：跨指定存储边界的读写字节数。
- \(R_{\mathrm{op}}\)、\(R_{\mathrm{mem}}\)：模型中的计算吞吐上限和带宽上限，单位分别为操作/秒与字节/秒。
定义运算强度
它表示每搬运一个字节，完成多少次算术操作。在上述资源上限模型中，
这是 Roofline 思路对应的时间下界，用于识别可能的瓶颈；实际时间还受延迟、调度、同步和负载不均衡影响。参见 Williams–Waterman–Patterson，Roofline 技术报告，2008，§3，PDF 第 3–4 页。
由这个模型可直接看出：当访存项占主导时，只提高算力不会降低该项；通过复用数据减少 \(Q_{\mathrm{mem}}\)，才可能继续获益。
存储边界必须明确。 CPU 主存与缓存之间、GPU 显存与片上存储之间、CPU 与 GPU 之间，应分别统计流量与带宽。某一层的流量不能直接代入另一层的带宽。
3. 批量内积为什么可能更快#
把两组向量在当前正交归一坐标系中的坐标按行排列为
这里仅规定批处理的数据布局，仍沿用前文的列基约定。所有交叉内积组成
\(Y\) 可以是一批过滤中心，也可以是另一块待比较向量。同一桶内部配对时，还应排除自身配对并避免对称重复。
下面直接估算一个理想的数据复用模型。若每个坐标占 \(b\) 字节，两个输入块各从所考察的存储层读取一次，暂不计输出，则
一次读入的向量可以参与多次内积，因此批量处理能够提高输入数据的复用程度。
这只是输入流量模型。实际还要计入重复加载、表示转换、索引和候选输出；若把完整的 \(G\) 写回，还会增加与 \(mk\) 成正比的输出空间和流量。
筛法通常只需要通过判据的候选。因此，可以分块计算内积并立即筛选，只输出少量候选信息。Ducas–Stevens–van Woerden 的 GPU 筛法采用了这种计算与筛选结合的方式。参见 Advanced Lattice Sieving on GPUs, with Tensor Cores，EUROCRYPT 2021，§5，PDF 第 18–20 页。
批量也受容量约束：过小难以摊薄搬运和启动开销，过大则可能增加工作集与缓冲需求。第 23 篇的批量参数 \(g_\ell\)，正是在控制这种执行粒度。
多层分桶还可以逐步缩小工作集，使后续阶段利用更快的缓存。《Sieving with Streaming Memory Access》对各层过滤与末层约化的工作集、算术吞吐和运行时间进行了分别统计。参见 Zhao–Ding–Yang，TCHES 2025，§4.2、Table 2，PDF 第 9–11 页。
因此，参数选择需要同时考虑有效覆盖、检查数量与执行效率。单独减少 \(C\)，并不能确定总时间下降。
4. 并行搜索与向量池更新#
筛法中的候选搜索容易划分成多个任务，但共享向量池的更新会产生依赖：多个任务可能找到相同候选，也可能同时尝试替换同一个条目。
为理解这些依赖，可以先使用下面的分批模型：
固定当前基、窗口和本批输入
并行执行过滤与候选搜索
各工作线程保存局部候选信息
汇总并重构候选，复核长度与重复
按当前池的接纳规则批量更新
同步派生表示，进入下一批在这个模型中，源向量被覆盖之前，应完成依赖它的读取和候选重构；更新时还要处理同批候选之间的重复。
批量提交可以减少共享状态的争用，但会推迟新向量参与搜索，也会改变更新顺序。因此，批量大小可能同时影响硬件效率与筛法进展。
G6K 使用线程局部缓冲、批量更新以及相应的同步机制；上面的流程只是便于分析的分批模型。参见 G6K §5.4，PDF 第 21–22 页。
还需区分两种并行目标：
- 同一任务内部并行： 多个线程或设备合作处理一个筛法任务，关注该任务完成时间。
- 多个独立任务并发： 分别维护状态，关注单位时间完成的任务数，并计入各任务的内存占用。
G6K 的并行实验也分别考察了这两种方式。参见 G6K，Appendix B，PDF 第 33–35 页。
增加并行资源后，收益可能受共享带宽、同步或串行阶段限制，需要结合整段运行测量。
5. 低精度筛选与候选复核#
低精度表示可以减少数据量，并利用相应的矩阵计算单元，但会影响接近阈值的约化判断。
一种常见组织方式是：批量内积使用较低精度，对筛出的候选再用更高精度复核。GPU 筛法论文明确把低精度计算作为候选过滤，并讨论其误差与漏检。参见 Ducas–Stevens–van Woerden，§5 的 Precision 部分及 Appendix C。
这里有两种不同的影响：
- 误报： 本来不满足判据的候选通过筛选，增加复核与去重成本。
- 漏检： 本来有效的候选被筛掉，降低有效覆盖，并可能增加后续迭代。
复核只能检查进入候选集的结果，不能补回已漏掉的候选。给筛选阈值留余量可以减少漏检；若要保证不漏检，需要适用的误差上界。
向量表示也应区分用途：整数系数用于确定候选所代表的格向量，几何表示用于快速估计内积与长度。更高精度的复核仍是数值检查；严格的长度保证需要相应的误差控制或精确计算。
因此，评价低精度方案时，要同时考察吞吐、有效覆盖和达到同一目标的总时间。
6. 怎样比较一个实现是否更快#
实验应说明计时覆盖的范围：
- 内核时间： 输入已准备好时，批量内积或过滤本身的耗时。
- 一轮筛法时间： 包括数据准备、分桶、搬运、搜索、候选复核与池更新。
- 完整任务时间： 包括预处理、提升、基插入，以及达到目标所需的多次调用。
第 26 篇的 Pump 成本属于第三层。某个内核变快，只有在完整任务中仍保留收益，才说明它改善了相应的约化流程。
GPU 操作可能异步执行，计时应覆盖已完成的工作；传输与计算存在重叠时，各阶段独立计时之和也不一定等于总耗时。参见 NVIDIA CUDA Best Practices Guide，Timing 与 传输和计算重叠。
最少记录以下信息：
- 问题与目标： 输入实例、维数、初始状态、长度或基质量目标、停止条件。
- 实现与平台： 代码版本、参数、数值精度、CPU/GPU、线程数与设备数。
- 成本与效果： 分阶段耗时、总耗时、峰值内存，以及与当前实验对应的覆盖或最终质量。
- 随机波动： 重复次数、随机种子、成功率和耗时分布。
固定输入实验可以使用 \(F,C,U\) 解释工作量与覆盖；完整筛法则需要在一致的目标和成功率要求下比较。资源配置不同时，也应同时说明运行时间与资源用量。
本篇属于筛法专题基础。后续关于 GPU、流式访存或外存筛法的研究增量，可以据此说明：相对哪个基线，改变了哪些计算或数据访问，收益在什么条件下成立，并由什么实验支持。
本文按上述论文版本核对，NVIDIA 在线文档访问日期为 2026-10-17。