#MOSAIC-Sieve 架构设计

#目标：从向量池中不断寻找更短的向量

给定一个格基，我们希望找到格中较短的非零向量，供格基约化及相关应用使用。问题背景可参见基本计算格问题：SVP、CVP 与 SIVP。

筛法维护一个向量池，尝试用已有向量的加减构造更短的候选。例如，两条长度接近、方向相近的向量，相减后可能得到更短的向量。将有效候选去重并纳入池，再继续搜索，就能逐步改善池中的向量。基本原理见筛法的基本框架与两向量约化。

直接比较池中的所有向量对，成本很高。项目采用分桶与桶内搜索，把更有希望产生短向量的组合集中起来。MOSAIC-Sieve 要处理的工程问题，就是让这个反复读取数据、执行搜索、更新向量池的过程，能够使用外存和不同的并行硬件。

#模块划分与协作

框架由管理与编排侧的五个模块，以及计算后端组成：

• 工作流（Workflow）：组织初始化、阶段推进，并根据算法返回的结果安排后续操作。
• 算法（Algorithm）：组织分桶、搜索和格基更新，判断当前筛法阶段是否完成。
• 数据池（Pool）：管理向量、候选及其存储，在数据更新时维护去重信息和统计。
• 基础结构（Core）：提供格基、向量表示、标识和筛块上下文等共同的数据基础。
• 运行支持（Runtime）：提供计算资源管理、文件读写与进程通信能力。
• 计算后端（Backend）：面向 CPU 多线程、CUDA GPU、神威从核等平台实现具体计算。

基础结构与运行支持由多个模块共享。数据池维护跨越多轮计算的状态，计算后端处理具体任务；算法与执行适配负责组织两者之间的协作。

下面以上升阶段的一次升维及随后的一轮筛法迭代为例。上一维筛法达到所需的饱和条件后，工作流推进升维。图中每一行对应一个模块，事件用于说明职责与主要状态变化。

eventmodeling
    rf 01 evt Workflow.ExtendPlanned
    tf 02 evt Algorithm.SaturationConfirmed
    tf 03 evt Pool.ExtensionStarted
    tf 04 evt Core.ContextPrepared
    tf 05 evt Runtime.TransformSubmitted
    tf 06 evt Backend.VectorsExtended
    tf 07 evt Pool.PoolExtended
    tf 08 evt Workflow.SieveStarted
    tf 09 evt Algorithm.CentersSelected
    tf 10 evt Runtime.BatchesSubmitted
    tf 11 evt Backend.BucketsBuilt
    tf 12 evt Backend.CandidatesFound ->> 11
    tf 13 evt Pool.PoolUpdated
    tf 14 evt Algorithm.RoundChecked

extend 向左扩大筛块，将已有向量池转换到新的筛维度。工作流安排操作，数据池利用基础结构准备变换，再借助运行支持和计算后端执行；变换结束后，数据池更新相关状态。这样可以在扩大搜索范围时继续利用已有成果，背景见渐进筛法与向量池复用。

随后，算法模块选择中心，组织分桶和桶内搜索。计算后端产生候选，候选经过恢复、检查和去重后纳入数据池，再由算法模块依据更新后的统计判断是否继续。图中只展示一轮迭代；当前维度通常需要多轮筛法，完成后才由工作流推进下一阶段。

#存储与计算之间的数据通路

向量存放在哪里、由什么硬件计算，是两个可以分别调整的选择。框架通过数据块、视图和索引组织任务输入，将存储读写与后端执行衔接起来。下面以筛法搜索为例，展示数据如何从存储进入计算，再回到向量池。

flowchart LR
    subgraph S["Storage"]
        M["Memory"]
        F["Files"]
    end
    M -->|View or copy| I["Task inputs<br/>Batches / views / indices"]
    F -->|Read into buffers| I
    I --> A["Execution adaptation"]
    subgraph B["Compute backend"]
        C["CPU threads"]
        G["CUDA GPU"]
        W["Sunway CPE"]
    end
    A --> C
    A --> G
    A --> W
    C --> R["Candidate results"]
    G --> R
    W --> R
    R --> U["Check + deduplicate<br/>Merge into pool"]
    U -.->|Store updates| S

存储侧负责提供数据。 内存模式可以借用已有数据的只读视图，也可以按任务需要复制、整理；外存模式则先将所需数据读入内存缓冲。两种方式都围绕数据块组织访问，上层据此准备本次计算所需的向量、桶或索引，减少对全量向量池常驻内存的依赖。

执行侧负责适配硬件。 任务输入交给执行适配，由相应的 CPU、CUDA 或神威后端处理。适配过程负责衔接数据布局、任务提交和结果收集；需要设备传输时，也在这一侧组织。部分路径可以复用已有向量，只传递索引来组织新的搜索，减少重复复制或上传。图中的三个后端表示不同执行选择。

结果回到统一的池更新流程。 后端返回候选结果，经必要的恢复、检查和去重后，再合并到向量池，并按存储方式完成相应更新。这样，存储方式的变化主要由数据读取与准备环节承接，计算平台的变化主要由执行适配承接，上层仍围绕任务、候选和池更新组织算法。

解耦的收益是可以分别优化存储和计算；需要协调的部分则是数据布局、缓冲容量和使用期限。外存访问与设备传输仍有成本，借用的数据也必须保留到相关任务使用结束。

#从局部操作到完整 Pump

Pump 将筛法与窗口变化组织成一次格基改进过程：先在逐渐扩大的筛块中积累短向量，再利用合适的短向量更新格基，并调整向量池以继续计算。

flowchart LR
    I["Initialize<br/>Sample + initial sieve"] --> U["Pump-up<br/>Extend + sieve"]
    U -->|Repeat to target dimension| U
    U --> D["Pump-down<br/>Basis update + pool transform"]
    D --> R["Optional extend<br/>Optional sieve"]
    R -->|Next update| D
    D -->|Stop condition| O["Output basis"]

• 初始化：建立较小筛块中的向量池，完成初始采样与筛法。
• 上升阶段（Pump-up）：反复扩展筛块，并在新的筛维度继续筛法，直到达到计划的目标维度。
• 下降阶段（Pump-down）：扫描可用于格基更新的候选，选择合适的短向量插入格基，同时将池转换到较小的筛块；没有合适候选时直接缩小筛块。当前实现也允许按配置穿插再次扩展与筛法，随后继续更新，直到满足结束条件并输出格基。

因此，筛法迭代改善向量池，Pump 则将这些局部计算组织成格基更新流程。相关背景见G6K 与 Pump。

《实践经验》进一步讨论异步批次如何交叠、缓冲何时能够复用，以及如何根据瓶颈调整批次组织。

资料依据：MOSAIC-Sieve v3 的工作流、池变换、筛法、格基更新及后端实现。核对版本：1b22e06cceed；整理日期：2026-10-20。

#引用此笔记

• 项目概览
• 实践经验
• CUDA 与 Tensor Core 编程