A Survey on Algorithm and Hardware Optimization to LWE-Based Fully Homomorphic Encryption
-
摘要:
随着云计算、量子计算等技术的飞速发展, 数据隐私面临严峻威胁. 越来越多的用户将数据和应用程序存储在云端，但传统的安全技术难以保障云计算环境中的数据安全. 在此背景下，引入全同态加密算法成为有效的解决方案之一. 同时，基于格理论的全同态加密技术具有天然的抗量子攻击能力，能够在加密状态下对数据进行任意计算,有效为量子计算时代数据安全提供保障. 尽管全同态加密有广阔的应用前景, 但它存在计算和存储巨额开销的问题. 为了推动全同态加密算法的应用和落地, 算法和硬件领域的研究人员提出了多种解决方案并取得显著进展. 归纳了主流的全同态加密技术、分析整理算法计算库和全同态硬件加速的相关工作近5年的进展, 最后展望了全同态加密技术的未来发展.
-
关键词:
- 全同态加密 /
- 同态加密算法 /
- 全同态加密算法库 /
- 全同态加密硬件加速器 /
- 容错学习问题
Abstract:With the rapid development of cloud computing, quantum computing and other advanced technologies, data privacy is facing increasingly severe threats. Especially in recent years, more and more users have been storing their sensitive data and applications in the cloud to take advantage of convenient services and powerful computing capabilities. However, traditional security technologies can not fully guarantee the security of cloud computing. Introducing fully homomorphic encryption algorithms is one of the effective ways to address this issue. At the same time, fully homomorphic encryption technology based on lattice theory has the capabilities of natural resistance to quantum attacks and arbitrary calculations on data in an encrypted state, effectively guaranteeing data security in the quantum computing era. Although fully homomorphic encryption shows significant potential, it suffers the problem of the volume explosion of computing and storage. To address the above problem and speed up the widespread adoption of fully homomorphic encryption algorithms, researchers from the fields of algorithms and hardware have been proposed a variety of solutions, and significant progress has been made. This work summarizes the progress of mainstream fully homomorphic encryption technology, analysis and compilation of algorithm libraries and fully homomorphic hardware accelerator in the past five years, and finally provides perspective of fully homomorphic encryption technology future development.
-
随着人工智能（AI）技术的快速发展，大语言模型（large language model，LLM）[1]、多模态大模型[2]等先进AI模型不断涌现，工业界和学术界对AI计算的算力需求也在持续攀升. 具体而言，一方面，当前AI的训练与推理不仅对算力设备的数量提出了更高要求[3]，同时对算力性能的特性也有不同需求[4]. 因此，基于异构计算的计算系统已成为当今业界构建智算集群的主要方式. 另一方面，内存限制成为了制约AI计算的重要问题[5]. 对于训练过程，现有计算架构已无法支撑该过程中产生的激活、优化器状态等内存数据，因此才产生了如Zero[6]、重计算[7]、数据并行训练[8]等折中的内存瓶颈缓解技术. 对于推理过程，KVcache[9]、MoE[10]等技术也对现有内存容量带来了巨大挑战. 缓存一致性技术被认为有望解决计算卡内存受限的问题[11]，诸如英伟达等厂商均提出了高效的缓存一致性互连技术[12-13]，形成紧耦合的融合计算系统[14]，以提升算力资源在并行AI计算中的协同执行效率. CXL协议[15]的提出也论证了一致性互连技术对内存池化、管理、调度等方面的优势. 因此，在未来，结合异构计算与缓存一致性互连技术的异构一致性融合计算系统，将成为AI算力基础设施的重要发展方向.
异构一致性融合计算系统结合类型多样的异构算力，如CPU、GPU、FPGA等，不仅能够充分发挥不同计算架构的优势，还能够通过高效的内存管理和缓存一致性协议协调不同异构算力之间的数据访问与处理. 然而，由于异构计算和一致性互连等关键技术尚未完全成熟，异构一致性融合计算系统的性能预测与评估仍然是当前亟待解决的问题. 例如，如何在建设异构一致性融合计算系统之前以低成本快速地估算其性能，如何评测LLM训练任务在该系统中的执行效率，以及如何发现并优化计算系统中的性能瓶颈，都是异构一致性融合计算系统研究中待解决的核心挑战.
但是，在实际应用中，该计算系统的性能涉及算力的分布、算力与内存的互连架构、任务负载的部署方式、互连拓扑的时延带宽参数等多个复杂变量和指标，因此在实际硬件系统中进行测评的难度和成本往往较高，难以实现. 为此，使用建模与仿真方法对异构一致性融合计算系统进行性能评估，成为一种较为理想的解决方案.
然而，现有的建模与仿真研究大多集中于同构计算系统和非一致性计算系统，难以有效地对异构计算、一致性互连等关键技术进行建模. 目前，建模异构一致性融合计算系统时，主要面临2个挑战：
1）异构一致性融合计算系统的拓扑架构建模具有较大难度. 模型中不仅需要构建异构算力、内存设备等各类器部件之间的互连拓扑，还需考虑异构算力之间的计算性能差异. 以往的建模与仿真工作往往难以同时满足这些需求.
2）引入缓存一致性协议后，计算负载的执行方式会与传统的非一致性系统有所不同. 尽管一致性系统解决了算力主存空间的限制，但算力对远程内存的直接访问开销成为需要特别考虑的因素[16]，这也使得以往的工作难以进行合理建模.
为了解决以上问题，本文研究提出了一种面向异构一致性融合计算系统的性能建模工具HCSim （heterogeneous coherent simulator）. HCSim集成了成熟的分布式系统仿真器SimGrid[17-18]，充分利用其互连拓扑描述能力以及SimGrid-S4U[19]的高效网络仿真能力，从而有效解决了异构一致性融合计算系统的拓扑架构建模难题. 此外，HCSim针对一致性系统的工作特性，设计了结合内存访问特性的负载建模与负载运行模拟方法，使用户能够模拟一致性系统下的工作负载执行方式，并生成可观测的执行轨迹. 进一步地，基于所设计的HCSim，本文研究对异构一致性融合计算系统与LLM训练任务进行了建模，探究了多种变量参数对该系统性能的影响，并提出优化方案以缓解该系统中的通信瓶颈，提高计算系统的整体性能. 本文的贡献有3点：
1）提出了面向异构一致性融合计算系统的性能建模工具HCSim，解决了拓扑架构建模困难以及一致性计算系统负载执行方式存在差异的问题，为异构一致性融合计算系统的性能建模、评估和优化提供了高效的仿真分析工具.
2）基于HCSim构建了在异构一致性融合计算系统下执行LLM训练负载的仿真，并探究了异构算力分布、并行计算规模、时延、带宽等参数对计算系统性能的影响.
3）面向异构一致性融合计算系统中的通信性能优化问题，提出了一致性下的ring-allreduce参数同步方法，并使用HCSim验证了该优化方式对计算系统性能的提升.
本文研究旨在面向新型异构一致性融合计算系统，提出高效、可用的建模仿真分析工具，为工业界和学术界提供低成本的新型计算系统性能与优化方案的评估手段，从而助力新一代AI基础设施与AI应用的创新与发展.
1. 相关工作
1.1 高精度的计算、内存、网络仿真器
计算系统通常涉及处理器计算、内存访存和网络通信等过程[20]，以往已有许多成熟的研究能够对上述3种过程进行高精度的建模与仿真. 对于计算过程的建模与仿真，经典的体系结构仿真器包括高度可配置的开源微架构仿真器Gem5[21]，兼具指令级和全系统仿真的操作系统开发与嵌入式系统仿真器QEMU[22]，以及专门用于GPGPU计算和并行程序性能分析与优化的GPGPU-Sim[23]等；对于内存访存过程的建模与仿真，较为成熟的仿真器包括专注于DRAM访问时序和性能分析的DRAMSim3[24]，以及支持较新内存标准（如DDR4、HBM）的仿真器Ramulator[25]等；在网络仿真器方面，较为广泛使用的是离散事件网络仿真器NS-3[26]，还有支持无线网络、物联网、车联网和数据中心网络的模块化仿真器OMNeT++[27]等.
然而，以上仿真器通常面临计算复杂度高和仿真耗时较大的问题. 例如，使用GPGPU-Sim仿真单个GPU计算任务可能需要长达几天的时间[28]，而NS-3仿真64个节点执行1MB的all-reduce操作可能需要20 min以上[29]. 因此，直接使用这些成熟的高精度仿真器，往往难以在有效时间内对规模较大的计算系统进行仿真与分析，无法满足建模异构一致性融合计算系统的需求.
1.2 面向分布式AI计算系统的性能建模
随着分布式AI计算技术的飞速发展，业界和学界涌现了一系列面向分布式AI计算系统与AI计算任务的性能建模仿真研究，表1中展示了近几年提出的相关工作.
表 1 面向分布式AI计算系统的性能建模工作Table 1. Performance Modeling Work for Distributed AI Computing Systems工作名称 工作简介 AMPeD[30] 针对Transformer神经网络架构的分布式训练任务进行数学建模的研究. Calculon[31] 针对LLM的分布式训练过程进行数学建模的工作. Paleo[32] 早期使用数学模型与有向无环图（DAG）模型建模数据并行、模型并行等AI分布式训练任务的研究. FlexFlow[33] 一个开源的深度学习编译器和运行时系统，其中提供了一个基于图模型的模块，用于建模与优化分布式AI计算任务. Daydream[34] 使用细粒度的基于图的模型描述分布式训练，主要针对基于all-reduce的分布式并行任务进行建模与仿真. Dpro replayer[35] 基于图模型预测和优化数据并行分布式训练的性能. DistSim[36] 用于预测每个参与分布式训练的算力节点的详细工作时间线. DistIR[37] 一种基于MLIR[38]的中间表示，用于以伪代码的形式模拟分布式训练的执行过程. Proteus[39] 使用策略树描述并行策略，并依赖执行图来建模分布式训练. 该研究考虑了分布式训练的运行时特征. TAG[40] 使用图模型建模并预测分布式训练任务的耗时，同时基于图神经网络搜索并优化分布式训练的执行策略. SMSG[41] 一种无需进行实际性能采集分析（profiling）的分布式训练数学建模方法，仅需输入AI加速器的实际计算性能和系统通信能力，即可对分布式系统中的AI训练任务进行建模. Astra-sim[29,42] 一个帮助研究人员理解并探索分布式训练中多种软硬件协同设计空间的模拟器. 然而，这些已有的研究对于异构计算与一致性互连技术的支持能力较为有限. 具体而言，现有工作面临的主要问题包括以下4点：
1）通常假设所有算力的计算能力一致，难以模拟异构算力差异对计算系统性能的影响.
2）依赖于在特定硬件上运行AI模型训练的前几个训练步骤，并通过性能分析工具获取执行轨迹，导致应用成本较高，无法适用于尚未实际部署的计算系统.
3）对于计算系统中互连拓扑建模的灵活性较弱，无法描述异构一致性融合计算系统中复杂的互连架构.
4）缺乏对一致性建模仿真的支持，无法建模一致性条件下AI计算任务的工作负载与执行方式.
由此可见，现有的建模仿真研究难以解决上述拓扑架构建模困难和引入一致性后计算负载建模困难的两大挑战，难以实现对异构一致性融合计算系统的性能建模，也无法在缺乏实际软硬件的情况下评估系统优化方案的效果. 这些正是本文研究所提出的HCSim所要解决的问题.
1.3 相对精度的系统性能建模
随着计算系统的变量、规模和复杂性逐渐增加，保证性能建模与仿真工作高精度的技术难度不断提升，搭建实际计算系统软硬件平台对仿真器进行校准的成本也在逐步增加，这使得建模与仿真工具的设计与实现变得愈加困难. 因此，近年来，许多建模与仿真工作不再专注于提升仿真的绝对精度，而是更多地关注模拟计算系统的功能与原理，并输出用于参考的相对指标.
例如，SMSG[41]在其研究中指出，重要的不是估计分布式训练的实际执行时间，而是对比不同策略的相对执行耗时. 在Scale-sim[43]仿真器中，研究人员仿真了脉冲阵列微架构[44]的工作流程，但其仿真器仅输出了仿真中定义的周期（cycle），并没有将仿真输出结果与真实系统进行对比. 同样地，在近期提出的Astra-sim[29,42]中，研究者也仅使用仿真中定义的时间对比了不同计算系统软硬件协同设计方式的差异，未探究仿真器建模的具体精度.
对于异构一致性融合计算系统的性能建模与仿真，由于异构软硬件之间通常存在兼容性问题，实际部署计算系统并对仿真进行校准需要付出巨大的工程量与成本，这与建模仿真的初衷相悖. 因此，与诸多近期的研究工作一致，本文研究提出的HCSim采用相对精度，旨在对比不同算力与内存的互连架构、任务负载的部署方式、互连拓扑时延带宽等多种变量对系统性能的相对影响，从而为异构一致性融合计算系统的设计与优化提供指导建议.
2. HCSim的设计实现与工作原理
HCSim的建设目标是对异构一致性融合计算系统的性能进行建模，解决以往建模仿真工作对该系统进行建模的挑战. 根据输入的计算系统互连架构和AI计算负载，HCSim用于模拟仿真AI计算负载的执行流程，最终输出AI计算负载在计算系统中的执行耗时和运行轨迹，为研究者在异构一致性融合计算系统的设计与优化过程中提供相对指标的参考.
2.1 HCSim的架构
为了实现上述目标，本文研究提出HCSim的系统架构如图1所示，主要包括3个核心层的设计：
1）平台层. 用于接收和解析用户输入的异构一致性融合计算系统的互连拓扑配置，并支持用户对互连拓扑以及拓扑中的算力、内存节点进行自定义，进而对算力节点、内存节点、拓扑结构以及节点之间的互连进行建模与仿真.
2）负载层. 接收用户定义的AI计算任务描述，并将计算任务转化为HCSim所定义的负载图，用于描述计算系统中的分布式AI计算任务. 随后，负载层根据转化后的负载图，驱动执行层对计算任务的执行过程进行仿真模拟，并在执行过程中不断输出细粒度的执行轨迹.
3）执行层. 在负载层的驱动下，执行层用于仿真AI计算负载在平台层所定义的计算系统中的执行过程. 该层基于SimGrid[17]实现，包括通信建模和计算建模2个部分，能够模拟算子级别的执行流程，输出AI计算任务的细粒度执行耗时.
HCSim依赖于这3层的相互协作，实现对异构一致性融合计算系统的性能建模.
2.2 异构一致性融合计算系统的拓扑架构建模
为了满足对异构一致性融合计算系统拓扑架构进行建模的需求，HCSim的平台层支持灵活自定义算力节点、内存节点和互连拓扑，并支持定义相关的核心参数. 平台层所定义的互连拓扑会被传递至执行层所集成的SimGrid仿真器[17]，从而实现计算系统互连拓扑的模型构建.
与绝大多数建模工作类似，HCSim仿真平台采用图的方式对互连拓扑进行建模. 表2展示了HCSim在平台层支持构建的图节点与边等元素，以及它们相应的属性参数. 在HCSim中，所构建的图上的节点分为交换节点、异构算力节点和内存节点. 其中，交换节点主要用于描述计算系统中的数据交换节点，如PCIE Switch，NVSwtich，L1 Switch，ToR Switch等，其节点上没有必要的属性. 异构算力节点用于描述计算系统中的异构算力，这些节点需要定义与计算能力相关的属性信息. 对于内存节点，HCSim支持定义内存的容量，也可以将内存设置为无穷大. 对于所构建图中用于连接节点的边，在HCSim中设计用边来表示节点之间的物理链路连接，因此需要定义带宽、时延等与数据传输相关的属性信息.
表 2 拓扑图的元素定义Table 2. Element Definitions of Topology Graph元素名称 属性名 属性含义 交换节点 无需定义属性 异构算力节点 fp16算力/ FLOPS fp16计算精度下的计算性能 fp32算力/ FLOPS fp32计算精度下的计算性能 内存节点 内存容量 包含可用的内存空间有多少 边 时延 所连接节点之间的通信时延 带宽 所连接节点之间的通信带宽 基于平台层的设计，图2展示了HCSim可以构建的异构一致性融合计算系统拓扑的抽象表示. 在一致性互连技术的帮助下，对于任意异构算力（图2中的XPU），不仅可以直接以高带宽低时延访问本地主存，还可以通过一致性互连网络直接访问远端其他XPU的内存或扩展内存，实现缓存一致性. 在图2中，HCSim可以自由修改计算系统和一致性互连网络的互连拓扑，也可以自由定义每个异构算力节点的计算能力、每个内存节点的存储容量，从而实现对异构一致性融合计算系统拓扑架构的灵活建模. 另外，值得注意的是，HCSim对异构算力的定义要求较低，这使HCSim不仅可以建模常用的异构算力，而且可以对诸如FPGA，ASIC等定制化算力进行性能建模. 研究者只需通过测试的方式获得异构算力的计算能力、内存容量等信息，便可以利用HCSim对不同的异构算力开展建模仿真.
2.3 一致性系统中的AI计算负载建模
在异构一致性融合计算系统中，由于XPU可以直接对非本地内存进行访存操作，因此AI计算负载的工作方式与传统非一致性计算系统存在差异，这也导致以往的建模仿真工作难以直接应用.
以往绝大多数建模仿真工作并未考虑内存对计算负载的影响. 即便较新的Astra-sim 2.0[29]提出了面向分离式内存的负载模型，它仍然难以有效描述异构一致性融合计算系统下的负载计算流程. 图3（a）展示了基于Astra-sim 2.0的负载模型构建的计算任务负载图，其中描述了2个异构算力采用数据并行训练带有3个神经层的神经网络. 在图3（a）中，每个顶点代表一个执行过程，边代表执行过程之间的依赖关系，即对于图中的任一个顶点，只有所有指向该顶点的顶点完成后，该顶点才能启动执行. 图3（a）中灰色顶点代表访存的通信过程，黄色顶点代表计算过程，蓝色顶点代表集合通信过程，FP代表前向传播，BP代表反向传播，FP1代表第一个神经层的前向传播过程，以此类推. 可以看出，尽管Astra-sim 2.0考虑了访存过程对AI计算任务的影响，但其建模中仍然仅模拟了将远端内存搬运到本地显存，再进行计算的过程，这与一致性系统的实际情况不符.
![]()
图 3 HCSim中异构一致性融合计算系统拓扑的抽象表示Figure 3. Abstract representation of the heterogeneous consistency integrated computing systems topology in HCSim图3（b）和图3（c）分别展示了HCSim的负载层为上述相同AI计算任务在非一致性系统和一致性系统中构建的负载图，其中黄色顶点代表计算过程，蓝色顶点代表通信过程. 在一致性系统中，由于XPU可以直接访问远端内存，因此远端访存过程可以与计算过程形成流水线执行. 在这种情况下，神经层的计算耗时可能会受到异构算力计算能力的限制，也可能会受到访存速度的限制. 因此，如图3（c）所示，HCSim构建的负载图将计算过程与访存过程描述为并行执行，可以近似表达访存与计算的流水执行过程，进而挖掘每个神经层在一致性系统中的性能瓶颈，以实现更准确地表达AI计算负载在一致性系统中的执行流程. 相比之下，3（b）则展示了HCSim所建模的非一致性系统中异构算力先进行内存搬运，再进行主存访存与计算的过程.
表3展示了HCSim的负载图中所有顶点以及可定义的属性. 可以看出，除了需要在负载图中绑定计算顶点和通信顶点的执行位置之外，HCSim的任务负载图与互连拓扑图几乎解耦，这使得HCSim的使用者能够更快捷地定义不同的计算任务负载. 此外，区别于以往建模工作中常用的有向无环图（DAG），HCSim采用有向有环图对AI计算负载进行建模，从而帮助HCSim更准确地模拟AI训练任务反复迭代循环的过程. 对于AI推理计算、分布式数据分析等其他计算负载，使用者也可以在HCSim中用同样的方式进行定义与仿真模拟.
表 3 负载图的元素定义Table 3. Element Definitions in the Workload Graph元素
名称属性名 属性含义 计算
顶点计算量/ FLOPs 该计算顶点所代表的计算任务的计算量 访存量 该计算顶点所执行的任务需要的访存数据量 执行位置 该计算顶点所执行的异构算力位置 是否为起始顶点 该计算顶点是不是计算任务的起始顶点 通信
顶点通信量 该通信顶点的总通信量 通信方式 该通信顶点的通信方式（例如集合通信、点对点通信） 通信范围 根据通信顶点的通信方式，定义源节点、目的节点，或通信节点范围等 是否为起始顶点 该通信顶点是不是计算任务的起始顶点 连接顶
点的边是否需要在第1次执行考虑 在计算任务第1次执行迭代时，不需要考虑有些边到顶点执行的依赖关系中 2.4 HCSim的工作流程与实现方式
基于构建的互连拓扑和负载图，HCSim可以对分布式AI计算进行建模与仿真. 整体的工作流程如图4所示，图中展示的每个具体步骤以及实现方式将在本节中逐一进行介绍.
1）互连拓扑图与负载图生成
如图4中的①所示，为了构建2.2节和2.3节中描述的互连拓扑图和负载图，HCSim在负载层和平台层分别构建了负载图描述与生成模块、互连拓扑描述与生成模块，并集成了NetworkX[45]的接口. NetworkX是一个非常实用的Python库，专门用于创建、操作和研究图与网络. 该库提供了丰富的功能，使得用户能够方便地构建有向图或无向图，添加或删除节点和边，或为这些节点和边赋予属性. 此外，NetworkX还支持多种图的遍历算法，如深度优先搜索和广度优先搜索，这使得在复杂的网络结构中查找路径、修改路由等方面变得更加简便. 另一个优势是，NetworkX提供了与Matplotlib集成的绘图工具，使得使用者能够将构建的网络拓扑可视化，从而直观地验证所构建的拓扑是否符合需求. 借助NetworkX，HCSim的使用者只需按照表2和表3的要求定义图与属性，即可将所生成的互连拓扑图、负载图作为HCSim建模与仿真的输入.
2）NetworkX-SimGrid拓扑编译
NetworkX本身只能进行图的构建与分析，并不具备仿真能力. 因此，如图4中的②所示，HCSim在平台层进一步构建了NetworkX-SimGrid编译器，使得NetworkX构建的图模型能够被SimGrid加载，并通过SimGrid-S4U[18]模型进行仿真执行.
具体来说，NetworkX-SimGrid编译器的功能是遍历NetworkX所生成的图模型中的节点和边，并将它们逐一转换为SimGrid支持的XML文件格式. 同时，编译器还会使用NetworkX中的Dijkstra算法计算所有节点之间的最短路径，并将这些最短路径作为路由信息，与图模型一同存储为SimGrid可读的XML文件. 此外，路由信息也可以由用户自行定义，从而进一步提升仿真的灵活性.
3）负载执行引擎
如图4中的③所示，在HCSim的负载层中，负载执行引擎的作用是结合所构建的负载图，驱动执行层进行仿真，从而完成对AI分布式计算任务的模拟执行.
具体而言，负载执行引擎采用事件驱动的方式进行仿真. 如图5所示，负载执行引擎首先将负载图中的所有起始顶点（表3中定义为起始顶点的所有顶点）放入一个执行容器中，并启动这些顶点的执行，将其送入执行层进行仿真. 如果执行顶点是计算顶点，该顶点的计算任务信息将被发送到执行层的计算模型进行仿真；如果执行顶点是通信顶点，该顶点则会被发送至执行层的网络模型进行仿真. 随后，负载层还包含一个事件触发器. 一旦执行容器中的某个顶点完成计算或通信，事件触发器会被激活，从执行容器中移除该完成的顶点，并检查该完成顶点在负载图中所指向的所有顶点是否满足所有依赖. 如果有满足所有依赖条件的顶点，这些顶点将被加入到执行容器中. 这样，负载图便可以在执行容器中不断循环执行，并根据仿真平台使用者定义的执行迭代次数生成相应的执行轨迹，直到所有初始顶点被重新加入容器的次数达到定义的迭代次数. 最后，负载执行引擎将收集并汇总整个模拟执行过程，并将分布式AI计算的执行时间与执行轨迹返回给仿真平台的使用者.
4）执行层的计算与网络顶点仿真
如图4中的④所示，当接收到计算顶点或通信顶点的信息时，执行层需要结合平台层的信息对这些顶点进行模拟. 对于计算顶点，HCSim直接使用SimGrid中的计算模型进行耗时计算，即：
tcomp=FLOPsFLOPS, (1) 其中，FLOPs（floating point operations）是计算顶点的浮点运算次数，FLOPS（floating point operations per second）是计算顶点所分配的异构算力的计算能力. 对于通信节点，HCSim采用SimGrid的CM02模型[46]，并设置TCP-gamma为0，从而获得经典的通信耗时模型：
tcomm=tlatency+LdatasizeHbandwidth. (2) 值得注意的是，以上所有SimGrid模型均采用线性最大-最小求解器进行模拟，即不断根据输入到仿真器中的执行任务的执行速度和剩余工作量计算最早完成的操作，并更新求解器与其他未完成的执行任务. 基于这种仿真方式，SimGrid可以更好地权衡仿真精度与仿真速度，从而高效地仿真分布式计算系统的执行流程.
一旦有顶点执行完毕，执行层会转发SimGrid输出的完成信息，并将其反馈给负载执行引擎的事件触发器. 最终，负载执行引擎根据收到的反馈信息，输出AI计算任务的执行时间与执行轨迹，完成对异构一致性融合计算系统的性能建模.
3. 仿真与分析
借助HCSim的仿真能力，本节从计算系统互连架构、异构算力分布、任务规模，以及计算系统互连拓扑的时延、带宽等参数出发，研究与分析了异构一致性融合计算系统的构建方式与性能瓶颈. 随后，针对异构一致性融合计算系统的通信瓶颈问题提出了优化方法，并使用HCSim仿真验证了该优化方法的效果.
3.1 仿真配置
1）互连拓扑配置
为了更好地对比与分析引入一致性数据访问之前计算系统的局限性，以及引入一致性数据访问后计算系统的优势，仿真首先构建了传统未引入一致性数据访问的互连拓扑. 如图6（a）所示，在构建的传统互连拓扑中，服务器内的互连架构借鉴了IEIT 5468服务器的架构[47]. 该架构采用Balance拓扑，每颗CPU下连接1个PCIe switch，每个PCIe switch连接4块异构算力（XPU）. 此外，考虑到诸如英伟达等厂商提供了NVSwitch[48]等高效的异构算力互连能力，本文研究在该拓扑中引入了XPU switch，以表达算力间的高效互连能力. 基于XPU switch，服务器内的异构算力之间可以实现比PCIe switch更强大的互连互访能力. 对于服务器之间的互连架构，整体计算系统的拓扑采用leaf-spine架构. 具体来说，所有服务器对外的互连采用以太网互连，且同一个机架上的所有服务器会被连接到机顶交换机（ToR switch）上. 所有机顶交换机最终连接到一个核心交换机（Core switch）上，从而实现所有服务器和异构算力之间的互连互访. 由于缺乏一致性互连技术，扩展内存只能与服务器中的CPU互连. 本文研究构建了包含
4096 个XPU的计算系统，其中共有32个ToR，每个ToR包含16个服务器，每个服务器中挂载8个XPU，并设定每个ToR内的128个XPU类型相同.![]()
图 6 未引入一致性互连技术与引入了一致性互连技术CXL的互连拓扑架构图对比Figure 6. Comparison of interconnect topology without and with the introduction of the consistent interconnect technology CXL在图6（a）的拓扑基础之上，进一步构建了图6（b）所示的引入一致性数据访问技术CXL[49-51]后的互连拓扑. 该拓扑与图6（a）中拓扑的主要区别在于，该拓扑中额外引入了基于CXL 3.0[15]特性的CXL switch，构建了一致性互连网络（CXL Fabric），用于建模一致性数据访问. 在该系统架构中，一致性互连网络不仅为异构算力之间（CXL Type 2设备）的内存互访提供了快速通路，而且为异构算力提供了额外的内存扩展（CXL Type 3设备）. 如图6所示，所有通过蓝色箭头连接的内存设备之间都可以使用高速的CXL链路进行一致性访问. 此外，由于CXL switch具备级联能力，因此每个机架中的CXL switch 还可以进行级联扩展. 本文研究基于CXL 3.0的能力，将
4096 个XPU通过CXL switch互连. 外置的扩展内存也可以直接连接到一致性互连网络中，供XPU使用.为了公平对比图6（a）与图6（b）的拓扑，仿真中设计为2个拓扑中的每个XPU都配置了可以无阻塞访问的扩展内存. 对于未引入一致性数据访问的互连拓扑，如图6（a）所示，仿真配置了CPU与PCIe之间的4条PCIe连接，保证每个XPU有充足的带宽访问CPU下的外置内存. 对于引入一致性数据访问的互连拓扑，如图6（b）所示，仿真为每个XPU都配置了唯一可访问且不冲突的CXL Type 3内存设备. 通过以上配置，在XPU主存不足时，仿真中每个XPU都可以无阻塞地访问扩展内存，并按照负载图的定义执行相应的数据读取等过程.
2）AI计算负载配置
本文研究通过建模与分析异构一致性融合计算系统在处理LLM训练任务时的性能表现评估该计算系统的性能，因此建立了如图7所示的LLAMA2-13B[52]的负载图. 由于训练LLAMA2-13B的主要耗时集中在计算其模型架构中的40个LLaMA decoder，因此该负载图描述了这些LLaMA decoder的并行训练过程. 其中，在XPU本地内存有剩余时，橙色顶点代表在本地内存的计算过程；在XPU本地内存不足时，对于非一致性系统，橙色顶点代表如图3（b）所示的先内存搬运再计算过程，而对于一致性系统，橙色顶点代表如图3（c）所示的直接访问远端内存进行计算过程. 为了构建HCSim的负载图，本文研究根据矩阵乘法、self-attention、layer normalization、concat、dropout、GeLU等神经层的计算特征，估计了如表4所示的每个神经层的计算量和访存量，并将其记录到负载图中相应的计算与通信顶点中，其中本文研究使用FP32训练精度. 然后，结合每个神经层在反向传播过程中所需同步的梯度数据量，将其记录到表示参数同步过程的相应通信顶点中，从而完成了LLAMA2-13B负载图的所有参数配置，使其能够被HCSim读取并用于模拟执行.
![]()
图 7 LLAMA2-13B的分布式训练负载图Figure 7. Workload graph for distributed training of LLAMA2-13B表 4 LLaMA Decoder中每个神经层的计算量与访存量Table 4. Computational Load and Memory Access of Each Neural Layer in LLaMA Decoder神经层 前传计算量/
GFLOPs前传访存量/
GB反传计算量/
GFLOPs反传访存量/
GBlayer norm 可忽略 0.00002 +0.039×b可忽略 0.00015 + 0.156blinear (K) b×195 0.0488 +0.039×bb×390 0.39 + 0.156b linear (Q) b×195 0.0488 +0.039×bb×390 0.39 + 0.156b linear (V) b×195 0.0488 +0.039×bb×390 0.39 + 0.156b self-attention b×312.5 3.242×b b×625 0.234b concat 可忽略 可忽略 可忽略 可忽略 linear b×195 0.0488 +0.039×bb×390 0.39 + 0.156b dropout 可忽略 0.0195 ×b可忽略 0.0195 add 可忽略 0.078×b 可忽略 0.039 layer norm 可忽略 0.00002 +0.039×b可忽略 0.00015 + 0.156blinear b×780 0.195 + 0.039×b b× 1560 1.562GB + 0.39b GeLU 可忽略 0.156×b 可忽略 0.078 linear b×780 0.195 + 0.156×b b× 1560 1.562GB + 0.39b dropout 可忽略 0.0195 ×b可忽略 0.0195 add 可忽略 0.078×b 可忽略 0.156 3）仿真参数
由于现有仿真工作缺乏对异构一致性融合计算系统中互连拓扑、计算负载的合理建模，因此，本文研究的仿真聚焦于探究HCSim本身的仿真能力.
对于拓扑架构和AI计算负载的其他参数，仿真中的设定如表5所示，其中参考了当前构建计算集群的主流性能参数. 对于表5里未标记为变量的参数，在仿真中配置为定值，不会发生变化. 对于标记为变量的参数，如CXL_link的时延、带宽等，仿真中将对其进行调整，用于对比不同参数对系统性能和任务执行效率的影响. 仿真使用的服务器配置了Intel Xeon Platinum 8168 @ 2.70 GHz处理器，内存为DDR4
2666 MHz.表 5 仿真参数设定Table 5. Simulation Parameter Settings异构一致性融合计算系统 LLaMA2-13B任务配置 算力节点 带宽 时延变量 ToR_to_L1 12.5 GB/s 5 μs 训练时每个XPU
输入的batch_size1 NIC_to_ToR 12.5 GB/s 5 μs seq_len 4096 UPI 62.4 GB/s 100 ns 隐藏层维度 5120 PCIE_link 128 GB/s 250 ns 使用算力节点
数量（scale）变量 XPU_link 900 GB/s 100 ns CXL_link 3.2 仿真结果分析
1）对比引入/不引入一致性的计算系统性能
首先，给定CXL_link的带宽与时延分别为128 GB/s和200 ns，本文研究对比了在使用不同数量的算力节点时，引入或不引入一致性的计算系统性能. 本文研究通过整个计算系统每秒处理的batch数量来对比不同参数配置下的系统性能，并针典型的英伟达H100、A100、V100算力，仿真了H100同构计算系统和H100+A100，H100+V100两种异构计算系统. 对于FPGA，ASIC等异构算力的仿真，也可以通过在HCSim中自定义算力节点实现建模仿真. 图8展示了仿真结果. 仿真记录HCSim仅用756.6 s便完成了包含
1024 个算力节点的一个训练迭代的仿真，这也充分说明了HCSim在对异构一致性融合计算系统性能进行仿真时具有优秀的执行效率.![]()
图 8 对比引入/不引入一致性的计算系统性能的仿真结果Figure 8. Simulation result on the computing system performance with and without introducing consistency从图8看出，无论是在同构还是异构的情况下，引入一致性后的计算系统性能明显优于不引入一致性的计算系统性能. 为了分析性能差异的原因，本文研究提取了如图9所示的仿真输出执行轨迹，其中包含了HCSim中每个计算过程和通信过程在完成时的仿真时间. 经过对执行轨迹的分析，以上性能差异的原因主要包括2点：
![]()
图 9 HCSim对同一个算子输出的执行轨迹Figure 9. Execution trace of HCSim for the same operator output①在不引入一致性的计算系统中，一旦XPU本地内存不足，就需要引入额外的内存搬运过程，导致训练耗时增加. 相比之下，从图9（b）的反向传播过程轨迹可以明显看出，由于一致性互连技术CXL的引入，反传过程可以省略如图3所示的额外本地内存搬运步骤，从而节约训练耗时.
②对比图9（a）中的参数同步过程轨迹可以发现，在不引入一致性的计算系统中，参数同步过程明显耗时更长，这是由于在该系统中异构算力节点之间的梯度同步仍需要通过以太网进行，效率较低. 相比之下，如图6所示，引入一致性后算力之间可以通过一致性互连网络进行通信，从而显著提升参数同步过程的执行效率.
另外，值得注意的是，对于H100+A100、H100+V100两种异构计算系统，在节点数量从128增加至256时，计算系统的性能出现了明显跳变. 这应该是由于在每个ToR内的XPU类型相同的仿真条件下，在128个节点以下时，计算系统仍然保持着同构. 而当节点数量从128提升至256时，系统引入了低性能的异构计算卡，降低了系统的整体计算性能. 这个仿真结果充分说明了对于异构计算系统，一味地增加XPU的数量并不一定会带来计算系统性能的提升，还需考虑XPU之间是否存在计算性能的差异.
2）探究带宽对计算系统性能的影响
进一步地，本节探究带宽对异构一致性融合计算系统性能的影响. 仿真采用图6（b）中的互连架构，并固定CXL_link的时延为200 ns，通过修改CXL_link的带宽与算力节点规模，对LLAMA2-13B的并行训练进行仿真，并观察不同计算系统性能的变化. 图10展示了这部分的仿真结果，经过分析可以得到以下结论：
![]()
图 10 带宽对异构一致性融合计算系统性能的影响Figure 10. Impact of bandwidth on the performance of heterogeneous consistency-integrated computing systems①在算力节点规模不变时，随着CXL_link一致性互连带宽的提升，计算系统的性能会逐渐提升，但提升的效果逐渐减缓. 这是因为带宽的提升缓解了带宽瓶颈，直接加速了内存访问与参数同步过程，从而提升了计算系统的整体性能. 而随着带宽的增加，系统的瓶颈逐渐从带宽转移到了算力，最终导致提升效果不再显著.
②在带宽不变的情况下，参与计算任务的XPU数量的增加显著提升了计算系统的性能. 这应该是由于一致性互连为XPU之间带来了高效的通信能力，提升了计算系统的可扩展性.
③引入异构算力同样会带来计算系统性能的波动，导致提升系统带宽的性能收益减弱.
3）探究时延对计算系统性能的影响
固定CXL_link带宽为128 GB/s，本文研究通过修改CXL_link时延与算力节点规模，从而观察不同计算系统性能的变化. 仿真结果如图11所示，经过分析，可以得到以下结论：
![]()
图 11 时延对异构一致性融合计算系统性能的影响Figure 11. Impact of latency on the performance of heterogeneous consistency-integrated computing systems①在时延较小时，时延略微增加并不会影响计算系统的性能. 这应该是由于在时延较小时，时延对通信影响的比重较低，不会明显影响系统性能.
②随着一致性互连时延的增大，特别是在时延大于10 μs后，时延逐渐成为影响系统性能的关键因素. 这是因为参数同步过程中有大量的通信过程，这些过程受时延影响较大，而时延增加时该影响也会更加显著.
③在时延变化时，计算节点数量更多的计算任务会受到更大的影响. 这是由于计算节点较多时，参数同步过程中通信的次数也会随之增加，造成时延的影响更加显著.
3.3 面向异构一致性融合计算系统的通信优化与仿真分析
进一步地，针对异构一致性融合计算系统的通信优化问题，本文研究提出了基于一致性ring-allreduce的通信优化方法，并利用HCSim的仿真能力，验证了所提方法的有效性.
具体而言，在参与分布式训练任务的节点规模较大或模型参数量较多时，由于节点之间需要通过通信同步模型参数，节点之间的通信将影响任务执行效率. 本文研究提出了一致性ring-allreduce，借助一致性系统的特性，降低了参数同步的通信次数，缓解了通信对AI计算任务的影响. 图12展示了传统ring-allreduce和本文研究所提出的一致性ring-allreduce之间参数同步运作流程的区别. 如图12（a）所示，在传统的ring-allreduce中，受制于异构算力节点内存之间访问的隔离（即图12（a）的虚线），每个异构算力节点都需要将同步后的梯度放置到本地内存，才能实现参数同步更新. 对于N个需要同步参数的异构算力节点，总共需要2×(N−1)次通信. 相比之下，如图12（b）所示，一致性ring-allreduce只需要进行(N−1)次通信便可完成梯度同步，减少了一半的梯度同步的通信步骤. 这是因为在一致性系统中，由于XPU之间的内存可以互相访问，因此只需要在一致性系统中保证平均后的梯度存在（即图12（b）的a0+a1+a2、b0+b1+b2、c0+c1+c2），而不再需要使用额外的all-gather集合通信将同步后的梯度发送到所有的XPU内存上.
![]()
图 12 传统ring-allreduce和一致性ring-allreduce的对比Figure 12. Comparison between traditional ring-allreduce and consistent ring-allreduce基于这一思路，本文研究在HCSim中调整了负载图中对ring-allreduce的执行定义，在给定CXL_link的带宽时延分别为128 GB/s和200 μs的情况下，获得的仿真结果如表6所示. 仿真结果表明，虽然一致性ring-allreduce可以提升系统性能，但提升并不显著. 对于整体算力性能较强，或系统规模较大的计算系统，应用一致性ring-allreduce可以带来相对更大的收益. 总结来看，虽然提升的幅度较小，一致性ring-allreduce可以在没有额外性能损失的情况下合理利用一致性互连的特性，实现在异构一致性融合计算系统中提升AI训练任务的执行效率.
表 6 优化前后对比结果Table 6. Comparison Results Before and After Optimization计算系统架构 传统ring-allreduce 一致性ring-allreduce 64个H100 同构 7.98 batch/s 8.12 batch/s 256个H100 同构 31.97 batch/s 32.53 batch/s 128个H100+128个 A100异构 10.65 batch/s 10.71 batch/s 128个H100+128个 V100异构 12.86 batch/s 12.93 batch/s 3.4 仿真小节
针对异构一致性融合计算系统，本文研究利用HCSim的仿真能力，不仅建模分析了引入一致性技术的效果，而且建模探究了一致性互连网络中带宽、时延对系统性能的影响，最终进一步模拟仿真了所提出的一致性ring-allreduce对该系统性能的提升. 这充分说明了HCSim不仅可以用于异构一致性融合计算系统的性能建模，而且可以通过少量修改完成对异构一致性融合计算系统的优化方案验证.
4. 结论与展望
针对新型异构一致性融合计算系统的性能建模和优化困难等问题，本文研究提出了一种全新的建模仿真工具HCSim. 该工具解决了以往研究中异构一致性融合计算系统拓扑架构建模困难和计算负载建模偏差的问题，并集成了SimGrid仿真器，实现了可以对异构一致性融合计算系统进行灵活高效的性能建模与仿真. 本文研究利用HCSim模拟构建了一致性互连拓扑架构，并建模了LLAMA2-13B的训练负载. 基于HCSim，仿真分析了异构算力分布、带宽、时延和计算规模等变量对异构一致性融合计算系统性能和AI计算任务执行效率的影响. 此外，还针对该系统的通信问题，提出了基于一致性ring-allreduce的通信优化方法，并使用HCSim进行了仿真验证. 通过仿真可以看出，HCSim不仅可以低成本、高效地实现对异构一致性融合计算系统的性能建模，而且能够对异构一致性融合计算系统的优化方案进行仿真验证. 在未来，我们将继续扩展HCSim的仿真能力，包括加入对时间局部性、空间局部性等算子的建模以及加入对一致性维护开销的建模以及加入对更多典型互连拓扑建模的支持，并在仿真能力更加完整后进行开源. 希望本文研究提出的HCSim能为工业界和学术界提供低成本的异构一致性融合计算系统性能评估手段，并为未来新型计算系统的仿真建模提供一些新的思路.
作者贡献声明：李仁刚提出了性能建模的核心思路，撰写仿真器核心代码和论文的主要章节；唐轶男修改与校对论文；郭振华提出了一致性ring-allreduce的思路；王丽实现了一致性ring-allreduce的仿真代码；宗瓒进行了实验部分数据的汇总与论文相关部分的撰写；杨广文负责论文的整体指导.
-
![]()
图 3 典型的全同态加密方案发展过程
Figure 3. The development process of typical fully homomorphic encryption scheme
![]()
图 4 部分全同态加密ASIC加速架构
Figure 4. Partial fully homomorphic encryption ASIC acceleration architecture
表 1 符号说明
Table 1 Symbol Explanation
符号 含义 KeyGenε 加密方案ε的密钥生成算法 Encε 加密方案ε的加密算法 Decε 加密方案ε的解密算法 Evalε 加密方案ε的密文计算算法 λ 安全参数 pk 公钥 sk 私钥 P 公钥为矩阵时用P表示 s 私钥为向量时用 \boldsymbol{s} 表示 evk 评估密钥 \boldsymbol{c}=\left({c}_{1},{c}_{2},… ,{c}_{t}\right) 密文 f 密文函数 {\boldsymbol{c}}_{f} 密文计算后获得的密文 \boldsymbol{m}=({m}_{1},{m}_{2},… ,{m}_{t}) 明文 m 当明文为单比特明文时写作 m e 噪声 q,q\in \mathbb{Z} 模数 q {\mathbb{Z}}_{q} 以 q 为模的整数集合 {\mathbb{Z}}_{q}^{n} {\mathbb{Z}}_{q} 上的 n 维向量 R=\mathbb{Z}\left[x\right]/\left\langle{f\left(x\right)}\right\rangle 多项式环, 其整数系数以（单次）多项式 f\left(x\right) 为模 {R}_{q}={\mathbb{Z}}_{q}\left[x\right]/\left\langle{g\left(x\right)}\right\rangle 多项式的系数是模 q 的多项式环 
下载: 导出CSV
表 2 不同全同态方案的特点
Table 2 Characteristics of Different Fully Homomorphic Encryption Schemes
共同特点 FHE方案 重要突破与特点 以算术电路为主，用于控制密文维数增加的
技术BV[20] 模数变换，重线性化技术 BGV[4] 免自举的LHE方案，带有模数变换的同态乘法 BFV[5-6] 比例不变性技术以减缓噪声增长速度 RNS FV[25] 提出FV的RNS变体 HPS[26] 提出了有效的缩放和CRT基础扩展程序，为RNS FV的优化改进 CKKS[10] 将加密噪声视为近似计算误差，重缩放技术以减低噪声 文献[21] CKKS的FHE方案，利用缩放正弦函数近似和加速模归约运算 文献[27] CKKS的Full-RNS变体，快速基转化 文献[28] 减少了密钥变换中临时模数的数量 快速自举, 以布尔电路为主, 密文是自然相加和相乘的矩阵, 避免了密文维数膨胀的问题 GSW[7] 提出近似特征向量方法，提出了新的构造同态乘法的方法 文献[29] 构建了第一个加密矩阵并支持同态矩阵运算的FHE方案 FHEW[8] 使用累加器做自举 TFHE[9] 提出了非对称输入的同态乘法 文献[30] 提出了新的打包方法和电路自举方法，无填充可编程自举 文献[31] 提出可编程自举的多输出版本
下载: 导出CSV
表 3 全同态方案自举过程特点
Table 3 Characteristics of Bootstrapping Process in Fully Homomorphic Encryption Schemes
下载: 导出CSV
表 4 全同态加密算法库程序语言及其支持方案
Table 4 Programming Language and Supported Schemes for FHE library
库 语言 方案 HElib[39] C++ BGV, CKKS PALISADE[40] C++ BGV, BFV, FHEW, TFHE, CKKS HEAAN[41] C++ CKKS OpenFHE[23] C++ BGV, BFV, FHEW, TFHE, CKKS FV-NFLlib[45] C++ BFV SEAL[42] C++/C# BFV, CKKS TenSEAL[49] python BFV, CKKS pyFHE[36] python BFV, CKKS PySEAL[37] python BFV, CKKS Pyfhel[38] python BFV, CKKS Lattigo[35] Go BFV, CKKS FHEW[43] C++ FHEW TFHE[44] C++/C TFHE CONCRETE[50] Rust TFHE TFHEpp[51] C++ TFHE cuFHE[46] Cuda/C++ TFHE nuFHE[47] python TFHE
下载: 导出CSV
表 5 整数、二进制和浮点算术的密文大小以及乘法和旋转操作的延迟
Table 5 Ciphertext Size of Integer, Binary and Floating-Point Arithmetic and the Delay of Multiplication and Rotation Operations
库 编码 二进制① 整数② 浮点数② 延迟时间/s 时间④/s 密文大小③/
MB延迟时间/s 时间⑤/s 密文大小③/
MB延迟时间/s 时间⑤/s 密文大小/
MBMult ROT Mult ROT Mult ROT HElib v2.2.1 < 1\;000 < 0.1 12.1 49.4 < 10 < 0.1 1.5 6.2 < 1 < 0.1 1.58 9.5 Lattigo v3.0.2 < 1\;000 < 0.1 58.7 50.3 < 1 < 0.1 0.2 6.3 < 1 < 0.1 0.25 9.4 PALISADE v1.11.6 < 10\;000 < 0.1 36.4/125 14.7 < 1 < 0.1 0.2 1.8 < 10 < 0.1 0.46 5.8 SEAL v4.0 < 1\;000 < 0.1 109 14.6 < 1 < 0.1 0.4 1.8 < 1 < 0.1 0.65 4.5 TFHE v1.0.1 < 100 < 0.1 4.0 0.02 - - 3083 - - - - - 最快⑦ T [44] T [44] T [44] N/A P [40] P [40]
L [35]P [40]
L [35]N/A P [40] P [40]
L[35]L [35] N/A 注：①二进制运算（除TFHE）使用32 k次分圆多项式 ，TFHE使用1 024次. ②整数和浮点域运算，使用16 k次分圆多项式. ③使用每个库的最小参数来加密8位数字并在128 b安全性下实现深度10. ④使用二进制编码测量字大小为8 B的CRC-8基准测试在二进制域中的FHE总执行时间，PALISADE第1个时间为多线程实现的执行时间，第2个时间为单核执行时间. ⑤针对整数和浮点域测量LR基准测试的总执行时间，且基准测试主要包括低深度的加法和乘法，TFHE使用字长 w=16\;\mathrm{b} . ⑥-：暂无数据. ⑦所有算法库库名仅保留原算法库英文名称的首字母.
下载: 导出CSV
表 6 2020―2023年部分硬件加速器关于NTT的优化工作
Table 6 Optimization Work on NTT for Partial Hardware Accelerators from 2020 to 2023
硬件
类型加速器 NTT优化方向 GPU TensorFHE[53] 充分利用TCU（tensor core unit） FPGA HEAX[54] 实现吞吐量可调,全流水线架构 HEAWS[55] 为实现蝶形计算优化架构, 避免内存访问冲突 Poseidon[56] 减少模计算 FAB[57] 针对NTT数据路径进行优化 Medha[58] 使用迭代NTT的方法, 消除了部分系数排列的需要 ASIC F1[24] 产生向量友好的分解, 实现全流水线的NTT单元 CraterLake[59] 在F1工作的基础上, 优化向量分解, 优化数据流 BTS[60] 使用系数级并行, 优化了数据路径 PIM MeNTT[61] 减少数据流 CryptoPIM[62] 更快的内存乘法,高吞吐量
下载: 导出CSV
表 7 全同态加密硬件加速器支持加密方案及其特点
Table 7 Supported Encryption Schemes and Their Characteristics for FHE Hardware Accelerators
类型 加速器 支持的加密方案 特点 GPU Wang等人[63] Gentry等人[64] 优化的FFT加速百亿比特级模乘 Badawi等人[65] BFV 基于CRT，DGT，RNS多项式乘法的GPU实现 Over 100x[66] CKKS 算子融合和主函数重排的内存优化技术 TensorFHE[53] CKKS, BGV, BFV 有效利用TCU, 优化NTT GME[67] CKKS 微架构扩展与优化 FPGA Roy等人[68] FV BFV算子优化和多项式乘的并行优化技术 HEAX[54] CKKS 模计算和NTT优化技术 HEAWS[55] FV 面向云FGPA的实现; 软硬件接口通信优化技术 XHEC[69] TFHE 对多比特计算优化加速, 提出布尔门之间的并行技术 Poseidon[56] CKKS 计算算子拆分, 算子的分时复用和重组合 FAB[57] CKKS 关键路径的计算并行, 计算调度已提高数据重用 FxHENN[70] CKKS 资源限制下的设计空间探索技术, 在低功耗FPGA上验证 Medha[58] CKKS RNS多项式计算单元; 通过最少数量网络实现并行单元之间的互连 ASIC F1[24] BGV，GSW，CKKS 基于静态调度策略并减少数据移动, 仅适用于浅乘法深度的子集 CraterLake[59] BGV，GSW，CKKS 解决了深度计算的开销 BTS[60] BGV，BFV，CKKS 第1个以自举为目标的加速器, 可以实现无限的乘法深度 MATCHA[71] TFHE 快速且节能的加速器, 通过近似方法加速多项式乘法 ARK[72] CKKS 软硬协同设计,大大提升自举效率 SHARP[73] CKKS 首次设计了短字长加速器缓解FHE中内存瓶颈和数据通信问题 PIM CiM-HE[74] BGV，BFV，GSW，TFHE，CKKS 第1个支持BFV SHE方案所有基本评估操作 MemFHE[75] FHEW 第1个客户端和服务器加速器; 第1个以内存为中心的架构
下载: 导出CSV
表 10 部分全同态加速器硬件性能比较 ms
Table 10 Comparison of Partially Homomorphic Accelerator for Hardware Performace
类别 工作 年份 自举
时间LR ResNet-20 GPU Over 100x[66] 2021 328.25 775 -② TensorFHE[53] 2023 157 178 3793 GME[67] 2023 33.63 54.5 982 FPGA Poseidon[56] 2023 -② 72.98 2661 FAB[57] 2023 92.4 103 -② ASIC F1[24] 2021 -① 1024 2693 CraterLake[59] 2022 4.5 119.62 321 BTS[60] 2022 58.9 39.9 1910 ARK[72] 2022 3.7 7.717 125 SHARP[73] 2023 -② 2.53 99 注：①F1仅支持单槽自举，不支持打包自举. ②-表示暂无数据.
下载: 导出CSV
-
[1] Cyberlands. IO. Top 14 cybersecuity breaches in China[EB/OL]. [2023-12-01]. https://www.cyberlands.io/topsecuritybreacheschina
[2] Gentry C. Fully homomorphic encryption using ideal lattices[C]//Proc of the 41st Annual ACM Symp on Theory of Computing. New York: ACM, 2009: 169−178
[3] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169−180
[4] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1−36
[5] Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]//Proc of the 32nd Annual Cryptology Conf. Berlin: Springer, 2012: 868−886
[6] Fan Junfeng, Vercauteren F. Somewhat practical fully homomorphic encryption[J/OL]. Cryptology ePrint Archive. [2012-03-22]. https://eprint.iacr.org/2012/144
[7] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[G]//LNCS: 8042: Proc of the 33rd Annual Cryptology Conf on Advances in Cryptology(CRYPTO 2013). Berlin: Springer, 2013: 75−92
[8] Ducas L, Micciancio D. FHEW: Bootstrapping homomorphic encryption in less than a second[G]//LNCS 9056: Proc of the 34th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2015: 617−640
[9] Chillotti I, Gama N, Georgieva M, et al. TFHE: Fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34−91
[10] Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[G]//LNCS 10624: Proc of the 23rd Int Conf on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2017). Berlin: Springer, 2017: 409−437
[11] Dathathri R, Saarikivi O, Chen Hao, et al. CHET: An optimizing compiler for fully-homomorphic neural-network inferencing[C]//Proc of the 40th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2019: 142−156
[12] Shaikh M U, Adnan W A W, Ahmad S A. Sensitivity and positive prediction of secured electrocardiograph (ecg) transmission using fully homomorphic encryption technique (fhe)[C]//Proc of the 6th IEEE-EMBS Conf on Biomedical Engineering and Sciences (IECBES). Piscataway, NJ: IEEE, 2021: 292−297
[13] Kocabas O, Soyata T. Towards privacy-preserving medical cloud computing using homomorphic encryption[M]//Virtual and Mobile Healthcare: Breakthroughs in Research and Practice. Hershey, PA: IGI Global, 2020: 93−125
[14] Sun Xiaoqiang, Zhang Peng, Liu J K, et al. Private machine learning classification based on fully homomorphic encryption[J]. IEEE Transactions on Emerging Topics in Computing, 2018, 8(2): 352−364
[15] 刘明洁,王安. 全同态加密研究动态及其应用概述[J]. 计算机研究与发展,2014,51(12):2593−2603 doi: 10.7544/issn1000-1239.2014.20131168 Liu Mingjie, Wang An. Fully homomorphic encryption and its applications[J]. Journal of Computer Research and Development, 2014, 51(12): 2593−2603 (in Chinese) doi: 10.7544/issn1000-1239.2014.20131168
[16] 白利芳,祝跃飞,李勇军,等. 全同态加密研究进展[J]. 计算机研究与发展,2024,61(12):3069−3087 doi: 10.7544/issn1000-1239.202221052 Bai Lifang, Zhu Yuefei, Li Yongjun, et al. Research progress of fully homomorphic encryption[J]. Journal of Computer Research and Development, 2024, 61(12): 3069−3087 (in Chinese) doi: 10.7544/issn1000-1239.202221052
[17] Marcolla C, Sucasas V, Manzano M, et al. Survey on fully homomorphic encryption, theory, and applications[J]. Proceedings of the IEEE, 2022, 110(10): 1572−1609 doi: 10.1109/JPROC.2022.3205665
[18] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1−40
[19] Stehlé D, Steinfeld R, Tanaka K, et al. Efficient public key encryption based on ideal lattices[G]//LNCS 5912: Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 617−635
[20] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE[J]. SIAM Journal on Computing, 2014, 43(2): 831−871 doi: 10.1137/120868669
[21] Cheon J H, Kim A, Kim M, et al. Bootstrapping for approximate homomorphic encryption[G]//LNCS 10820: Advances in Cryptology (EUROCRYPT 2018). Berlin: Springer, 2018: 360–384
[22] Boura C, Gama N, Georgieva M, et al. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes[J]. Journal of Mathematical Cryptology, 2020, 14(1): 316−338 doi: 10.1515/jmc-2019-0026
[23] Al Badawi A, Bates J, Bergamaschi F, et al. Openfhe: Open-source fully homomorphic encryption library[C]//Proc of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography. New York: ACM, 2022: 53−63
[24] Samardzic N, Feldmann A, Krastev A, et al. F1: A fast and programmable accelerator for fully homomorphic encryption[C]//Proc of the 54th Annual IEEE/ACM Int Symp on Microarchitecture (MICRO−54). New York: ACM, 2021: 238−252
[25] Bajard J C, Eynard J, Hasan M A, et al. A full RNS variant of FV like somewhat homomorphic encryption schemes[G]///LNCS 10532: Proc of the 23rd Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2016: 423−442
[26] Halevi S, Polyakov Y, Shoup V. An improved RNS variant of the BFV homomorphic encryption scheme[G]//LNCS 11405: Proc of the Cryptographers’ Track at the RSA Conf on Topics in Cryptology(CT-RSA). Berlin: Springer, 2019: 83−105
[27] Cheon J H, Han K, Kim A, et al. A full RNS variant of approximate homomorphic encryption[G]//LNCS 11349: Proc of the 25th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2019: 347−368
[28] Han K, Ki D. Better bootstrapping for approximate homomorphic encryption[G]//LNCS 12006: Proc of the Cryptographers’ Track at the RSA Conf on Topics in Cryptology(CT-RSA). Berlin: Springer, 2020: 364−390
[29] Hiromasa R, Abe M, Okamoto T. Packing messages and optimizing bootstrapping in GSW-FHE[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2016, 99(1): 73−82
[30] Chillotti I, Gama N, Georgieva M, et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[G]//LNCS 10624: Proc of the 23rd Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2017: 377−408
[31] Guimarães A, Borin E, Aranha D F. Revisiting the functional bootstrap in TFHE[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021: 229−253
[32] Alperin-Sheriff J, Peikert C. Faster bootstrapping with polynomial error[G]//LNCS 8616: Proc of the 34th Annual Cryptology Conf on Advances in Cryptology(CRYPTO 2014). Berlin: Springer, 2014: 297−314
[33] Bergerat L, Boudi A, Bourgerie Q, et al. Parameter optimization and larger precision for (T) FHE[J]. Journal of Cryptology, 2023, 36(3): 28 doi: 10.1007/s00145-023-09463-5
[34] Doröz Y, Hoffstein J, Pipher J, et al. Fully homomorphic encryption from the finite field isomorphism problem[G]//LNCS 10769: Proc of the 21st IACR Int Workshop on Public Key Cryptography. Berlin: Springer, 2018: 125−155
[35] EPFL-LDS, Tune Insight SA. Lattigo v5.0. 2[EB/OL]. (2023-11-28)[2024-03-20]. https://github.com/tuneinsight/lattigo
[36] Erabelli S. pyFHE-A Python library for fully homomorphic encryption[D]. Cambridge, MA: MIT Press, 2020
[37] Titus A J, Kishore S, Stavish T, et al. PySEAL: A Python wrapper implementation of the SEAL homomorphic encryption library[J]. arXiv preprint, arXiv: 1803.01891, 2018
[38] Ibarrondo A, Viand A. Pyfhel: Python for homomorphic encryption libraries[C]//Proc of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography. New York: ACM, 2021: 11−16
[39] Shai H, Victor S. HElib 2.3. 0[EB/OL]. (2023-07-18)[2024-03-20]. https://github.com/homenc/HElib
[40] Dave C, Kurt R, Yuriy P. PALISADE[EB/OL]. (2022-11-02)[2024-03-20]. https://gitlab.com/palisade/palisade-release
[41] Kim A. HEAAN v2.1[EB/OL]. (2017-09-05)[2024-03-20]. https://github.com/snucrypto/HEAAN
[42] Microsoft Research. Microsoft SEAL v4.1. 1[EB/OL]. (2023-01-11)[2024-03-20]. https://github.com/Microsoft/SEAL
[43] Leo D, Daniele Mi. FHEW v2.0-beta[EB/OL]. (2017-05-31)[2023-04-25]. https://github.com/lducas/FHEW
[44] Ilaria C, Nicolas G, Mariya G et al. TFHE v1.0. 1[EB/OL]. (2017-08-16)[2023-05-27]. https://github.com/tfhe/tfhe
[45] CryptoExperts. FV-NFLlib[EB/OL]. (2016-07-26)[2023-04-06]. https://github.com/CryptoExperts/FV-NFLlib
[46] Wei Dai. cuFHE v1.0_beta[EB/OL]. (2018-03-14)[2023-09-11]. https://github.com/vernamlab/cuFHE
[47] NuCypher. nuFHE v0.0. 3[EB/OL]. (2019-07-20)[2023-07-14]. https://github.com/nucypher/nufhe
[48] Victor S. NTL v11.5. 1[EB/OL]. (2021-06-24)[2023-04-07]. https://github.com/libntl/ntl
[49] Benaissa A, Retiat B, Cebere B, et al. Tenseal: A library for encrypted tensor operations using homomorphic encryption[J]. arXiv preprint, arXiv: 2104.03152, 2021
[50] Zama. Concrete: TFHE compiler that converts python programs into FHE equivalent v2.5. 0[EB/OL]. (2024-01-23)[2024-03-20]. https://github.com/zama-ai/concrete
[51] Kotaro M. TFHEpp v8[EB/OL]. (2023-10-01)[2023-08-07]. https://github.com/virtualsecureplatform/TFHEpp
[52] Gouert C, Mouris D, Tsoutsos N. Sok: New insights into fully homomorphic encryption libraries via standardized benchmarks[J/OL]. Proceedings on Privacy Enhancing Technologies, 2023, 2023(3): 154−172[2025-02-20]. https://petsymposium.org/popets/2023/popets-2023-0075.php
[53] Fan Shengyu, Wang Zhiwei, Xu Weizhi, et al. Tensorfhe: Achieving practical computation on encrypted data using gpgpu[C]//Proc of the 29th IEEE Int Symp on High-Performance Computer Architecture (HPCA−29). Piscataway, NJ: IEEE, 2023: 922−934
[54] Riazi M S, Laine K, Pelton B, et al. HEAX: An architecture for computing on encrypted data[C]//Proc of the 25th Int Conf on Architectural support for Programming Languages and Operating Systems. New York: ACM, 2020: 1295−1309
[55] Turan F, Roy S S, Verbauwhede I. HEAWS: An accelerator for homomorphic encryption on the Amazon AWS FPGA[J]. IEEE Transactions on Computers, 2020, 69(8): 1185−1196
[56] Yang Yinghao, Zhang Huaizhi, Fan Shengyu, et al. Poseidon: Practical homomorphic encryption accelerator[C]//Proc of the 29th IEEE Int Symp on High-Performance Computer Architecture (HPCA−29). Piscataway, NJ: IEEE, 2023: 870−881
[57] Agrawal R, de Castro L, Yang Guowei, et al. FAB: An FPGA-based accelerator for bootstrappable fully homomorphic encryption[C]//Proc of the 29th IEEE Int Symp on High-Performance Computer Architecture (HPCA−29). Piscataway, NJ: IEEE, 2023: 882−895
[58] Mert A C, Kwon S, Shin Y, et al. Medha: Microcoded hardware accelerator for computing on encrypted data[J/OL]. Cryptology ePrint Archive[2022-10-12]. https://eprint.iacr.org/2022/480
[59] Samardzic N, Feldmann A, Krastev A, et al. Craterlake: A hardware accelerator for efficient unbounded computation on encrypted data[C]//Proc of the 49th Annual Int Symp on Computer Architecture. New York: ACM, 2022: 173−187
[60] Kim S, Kim J, Kim M J, et al. Bts: An accelerator for bootstrappable fully homomorphic encryption[C]//Proc of the 49th Annual Int Symp on Computer Architecture. New York: ACM, 2022: 711−725
[61] Li Dai, Pakala A, Yang Kaiyuan. MeNTT: A compact and efficient processing-in-memory number theoretic transform (NTT) accelerator[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2022, 30(5): 579−588
[62] Nejatollahi H, Gupta S, Imani M, et al. Cryptopim: In-memory acceleration for lattice-based cryptographic hardware[C/OL]//Proc of the 57th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2020[2024-08-21]. https://ieeexplore.ieee.org/abstract/document/9218730
[63] Wang Wang, Hu Yin, Chen Lianmu, et al. Exploring the feasibility of fully homomorphic encryption[J]. IEEE Transactions on Computers, 2013, 64(3): 698−706
[64] Gentry C, Halevi S. Implementing gentry’s fully-homomorphic encryption scheme[G]//LNVC 6632: Proc of the 30th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011: 129−148
[65] Al Badawi A, Veeravalli B, Mun C F, et al. High-performance FV somewhat homomorphic encryption on GPUs: An implementation using CUDA[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(2): 70−95
[66] Jung W, Kim S, Ahn J H, et al. Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with GPUs[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(4): 114−148
[67] Shivdikar K, Bao Yuhui, Agrawal R, et al. GME: GPU-based microarchitectural extensions to accelerate homomorphic encryption[C]//Proc of the 56th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2023: 670−684
[68] Roy S S, Turan F, Jarvinen K, et al. FPGA-based high-performance parallel architecture for homomorphic computing on encrypted data[C]//Proc of the 25th IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2019: 387−398
[69] Nam K, Oh H, Moon H, et al. Accelerating n-bit operations over TFHE on commodity CPU-FPGA[C/OL]//Proc of the 41st IEEE/ACM Int Conf on Computer-Aided Design. New York: ACM, 2022[2024-08-31]. https://dl.acm.org/doi/10.1145/3508352.3549413
[70] Zhu Yilan, Wang Xinyao, Ju Lei, et al. FxHENN: FPGA-based acceleration framework for homomorphic encrypted CNN inference[C]//Proc of the 29th IEEE Int Symp on High-Performance Computer Architecture (HPCA−29). Piscataway, NJ: IEEE, 2023: 896−907
[71] Jiang L, Lou Q, Joshi N. Matcha: A fast and energy-efficient accelerator for fully homomorphic encryption over the torus[C]//Proc of the 59th ACM/IEEE Design Automation Conf. New York: ACM, 2022: 235−240
[72] Kim J, Lee G, Kim S, et al. Ark: Fully homomorphic encryption accelerator with runtime data generation and inter-operation key reuse[C]//Proc of the 55th IEEE/ACM Int Symp on Microarchitecture (MICRO). Piscataway, NJ: IEEE, 2022: 1237−1254
[73] Kim J, Kim S, Choi J, et al. SHARP: A short-word hierarchical accelerator for robust and practical fully homomorphic encryption[C/OL]//Proc of the 50th Annual Int Symp on Computer Architecture. New York: ACM, 2023[2024-08-31]. https://dl.acm.org/doi/10.1145/3579371.3589053
[74] Reis D, Niemier M T, Hu X S. A computing-in-memory engine for searching on homomorphically encrypted data[J]. IEEE Journal on Exploratory Solid-State Computational Devices and Circuits, 2019, 5(2): 123−131 doi: 10.1109/JXCDC.2019.2931889
[75] Gupta S, Cammarota R, Šimunić T. Memfhe: End-to-end computing with fully homomorphic encryption in memory[J]. ACM Transactions on Embedded Computing Systems, 2024, 23(2): 1−23
[76] Roy S S, Järvinen K, Vliegen J, et al. HEPCloud: An FPGA-based multicore processor for FV somewhat homomorphic function evaluation[J]. IEEE Transactions on Computers, 2018, 67(11): 1637−1650
[77] Agrawal R, De Castro L, Juvekar C, et al. MAD: Memory-aware design techniques for accelerating fully homomorphic encryption[C]//Proc of the 56th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2023: 685−697
[78] Martins P, Sousa L. A methodical FHE-based cloud computing model[J]. Future Generation Computer Systems, 2019, 95: 639−648 doi: 10.1016/j.future.2019.01.046
计量
- 文章访问数: 50
- HTML全文浏览量: 1
- PDF下载量: 10
