BGJ 筛法的流式访存组织

前置笔记：BGJ 递归分桶与多层筛选、多层分桶的参数选择与优化、重复配对、去重与有效覆盖、筛法的并行化与平台成本模型。

《Sieving with Streaming Memory Access》围绕多层 BGJ 筛法研究流式访存组织 [1]。

本篇沿用 $F,C,U$ 的过滤、检查与覆盖计数，以及 $Q_{\mathrm{mem}}$ 的访存流量含义。新增符号在使用时定义。

1. 已有基线与本篇增量

BGJ 递归分桶、分桶参数优化与去重与有效覆盖已经建立多层分桶、参数选择和去重的分析框架；并行筛法与平台成本说明，同样的检查次数可以对应不同的运行时间。

已有 GPU 筛法也重视数据复用，并指出 CPU 与 GPU 之间的带宽会限制小桶处理的效率 [2, pp. 12–13]。

Zhao–Ding–Yang 进一步围绕多层 BGJ 组织访存：大父桶顺序读入，同时服务多个过滤中心；子桶逐层缩小，使后续计算转入更小的存储区域 [1, pp. 9–10]。

相对前文的操作计数基线，本篇增加的是对数据读取、复用与写出的具体分析。评价对象包括过滤工作量，也包括执行这些工作所需的数据移动。

2. 固定过滤任务，改变父桶的扫描方式

先建立一个便于比较的模型。固定父桶、中心集合与过滤判据，记：

$m$ ：父桶中的向量数。
$t$ ：本次需要测试的中心总数。
$g$ ：每批处理的中心数， $1\le g\le t$ ，对应分桶参数优化的批量参数。
$w$ ：每个输入向量在当前表示下占用的字节数。

无论逐中心处理还是批量处理，都要完成

F_{\mathrm{parent}}=mt

次向量—中心测试。

假设每次扫描都需要跨越所考察的存储边界，且一批中心能够留在本地。只计算父桶输入的读取量，有

Q_{\mathrm{read}}^{(1)}\approx wmt, \qquad \boxed{ Q_{\mathrm{read}}^{(g)} \approx wm\left\lceil\frac{t}{g}\right\rceil. }

因此，批量处理可以在保持过滤测试数量的同时，减少父桶的重复读取。上述公式是本篇固定任务模型的直接计数，不是论文对完整筛法的性能保证。

示意流程为：

将固定的 t 个中心分成若干批，每批至多 g 个

对每批中心：
    初始化本批子桶的输出缓冲
    顺序读取父桶中的向量：
        对本批所有中心执行过滤测试
        将通过测试的成员追加到对应子桶
    递归处理或转存本批子桶

在输入不变、判据计算结果相同且全部任务完成时，改变这种遍历次序不会改变桶成员及其后续候选集合，因而可以单独比较数据组织的成本。

如果父桶本来就能被缓存复用，逐中心扫描未必会反复访问主存；此时应按实际跨层流量修正模型。

3. 把子桶输出与数据库更新计入成本

减少父桶读取，只解决了访问链条中的一部分。

设生成的子桶为 $D_1,\ldots,D_t$ ，每条输出记录占 $w_{\mathrm{out}}$ 字节，则直接物化这些子桶需要的输出量为

Q_{\mathrm{out}} = w_{\mathrm{out}}\sum_{j=1}^{t}|D_j|.

同一向量进入多个子桶时，每次出现都计入。若输出记录只保存索引，后续根据索引读取完整向量的流量还需另计。

因此，读取连续的索引数组，不意味着被索引的向量也连续。把成员重新整理为紧凑的数据块可以改善后续访问，但需要计入整理和复制成本。增大 $g$ 时，也应检查本批子桶及缓冲的峰值驻留空间。

数据库更新还有一项需要区分：论文 §4.2 提出通过归并排序处理重复与过长向量，但 §6.2 描述的实际实现仍维护 UID 哈希表 [1, pp. 10, 13–14]。

这意味着“可以组织成流式处理的方案”和“当前实现具体执行的更新流程”应分别记录。结果去重也不等于已经消除重复源对的内积检查，计数继续沿用去重与有效覆盖的区分。

4. 论文主张与实验证据的范围

访存分析。 在分层存储、局部处理及流式带宽假设下，作者主张对最大主数据库的流式访问量可以保持在与池规模相同的指数阶。沿用前文符号表示为

A_{\mathrm{main}}=N\,2^{o(s)}, \qquad N=(4/3)^{s/2+o(s)}.

这里 $A_{\mathrm{main}}$ 表示主库访问量的渐近计数，不是并行筛法与平台成本按字节统计的 $Q_{\mathrm{mem}}$ ，也不是完整运行时间。

附录 A 使用 $O(\log s)$ 层及沿路径正交的中心，并理想化末层中心的分布；中心非均匀性是否只造成次指数损失，论文仍留有未解决的问题 [1, pp. 9–10, 19]。

因此，使用这个主张时，需要保留存储模型和分布条件。它不能替代对各层读写、局部计算和完整筛法成功条件的分析。

实现观察。 Table 2 在 140 维、112 线程、双 Intel Xeon Platinum 8479 平台上记录：最外层工作集为 278.8 GB，位于 RAM；末层约化工作集为 556.7 KB，位于 L2 缓存 [1, p. 11]。

这组数据展示了该实现中“逐层缩小工作集并利用缓存”的执行方式。仅凭这张分阶段表，不能把全部性能收益归因于流式访存；隔离这一因素，还需要控制数值表示、内积内核、筛选参数和更新策略进行比较。

5. 对后续研究的用法

把选参问题分成两个相互关联的层次：

搜索层： 层数、阈值和中心数怎样影响 $F,C,U$ 。
执行层： 中心批量、桶布局和处理顺序怎样影响读写流量、峰值空间及运行时间。

评估自己的实现时，可以先固定输入、中心与判据，只改变访问组织，核对桶成员、候选集合和流量变化；再放开参数调整，比较达到同一长度或基质量目标的总时间。

这一增量提供的研究视角是：把多层分桶同时看作搜索结构与数据访问结构。几何上的减少检查，与实现上的减少数据移动，应分别计数，再放到完整任务中评价。

参考文献

1. Ziyu Zhao, Jintai Ding, and Bo-Yin Yang. Sieving with streaming memory access. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2025. DOI.

2. Léo Ducas, Marc Stevens, and Wessel P. J. van Woerden. Advanced lattice sieving on GPUs, with tensor cores. Advances in cryptology – EUROCRYPT 2021, part II. 2021. DOI.

BGJ 筛法的流式访存组织#

#1. 已有基线与本篇增量

#2. 固定过滤任务，改变父桶的扫描方式

#3. 把子桶输出与数据库更新计入成本

#4. 论文主张与实验证据的范围

#5. 对后续研究的用法