基于寿命优化的新一代神威超级计算机量子电路仿真

基于寿命优化的新一代神威超级计算机量子电路仿真陈耀健清华大学中国北京宋家伟中国无锡国家超级计算中心楚国信息工程大学中国郑州勇刘国家超级计算无锡中心浙江实验室，杭州，中国辛六国家超级计算无锡中心浙江实验室，杭州，中国傅浩桓清华大学国家超级计算中心在中国新民市信息工程大学中国郑州林干清华大学国家超级计算中心在中国姐告国家并行工程技术研究中心中国北京摘要陈德勋中国无锡国家超级计算中心杨广文清华大学国家超级计算中心无锡浙江实验室，杭州，中国，这是最常用的图路径优化软件-高性能的量子电路经典模拟器，特别是张量网络收缩算法，已成为验证有噪量子计算的重要工具。 为了解决内存限制，切片技术用于减少张量维度，但它也可能导致额外的计算开销，大大降低整体性能。 本文提出了基于生命周期的新方法来减少切片开销，提高计算效率，包括处理切片开销的解释方法、寻找最小切片集的就地切片策略和为Sunway架构定制的自适应张量网络收缩路径再细化器。实验表明，在大多数情况下，我们的就地切片策略的切片开销将小于cotengra允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。必须尊重本作品第三方组件的版权。对于所有其他用途，请联系所有者/作者。PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577529目前的洁具最后，Sycamore量子处理器RQC的仿真时间缩短至96. 1秒，单精度性能达到308. 6Pflops，使用超过41M个内核生成1M个相关样本，与2021年Gordon BellPrize工作的60. 4Pflops相比，性能提升超过5倍。关键词：量子计算，电路模拟器，张量网络收缩，Sunway架构，切片，直接存储器访问，融合设计1介绍量子计算机有潜力在特定任务中提供比经典计算机更快的速度“量子优势”是指那些只能通过使用量子计算机在合理的然而，尽管在计算能力方面具有这些优势，但低保真度仍然是量子计算机的主要挑战[4]。因此，经典模拟器对于为量子计算机设计提供验证非常重要[5]。此外，在严重依赖可靠计算资源的领域，如量子算法、量子编程语言和量子计算机，PPoPPChen等人→.（）下一页（）下一页（）下一页（）下一页{∈ ∈ }（）∈编译器，可以在经典的模拟器上工作，并获得接近的性能[6]。考虑到模拟器的指数复杂性和需求的迫切性，提高现有经典模拟器的效率是非常重要的。在经典计算机上直接存储任意的量子态需要相对于量子比特数的指数级的存储量因此，使用传统的状态矢量方法来模拟量子电路目前被限制在小于50个量子比特[7]。 近年来，张量网络收缩（TNC）[8]算法已经显示出很有前途的潜力，特别是在模拟随机量子电路（RQC）方面。 结合切片技术，TNC算法可以在有限的存储空间内有效地模拟更大的量子电路。在TNC算法中，量子比特和量子门被表示为张量，整个量子电路被视为张量网络[9]。将计算输出量子态振幅的问题转化为收缩相应的张量网络的问题。跨国公司的绩效主要取决于跨国公司的路径。在具有数百个张量的网络中，与坏的收缩路径相比，好的收缩路径可以很容易地将复杂性降低几个数量级同时，在收缩过程中，可能出现巨大的中间张量切片技术可以减少内存需求[10][11]，但代价是一些计算开销。这项工作的目的是减少切片所造成的计算开销。与以前的努力，主要使用的是并行算法，这项工作引入了一个新的概念，生命周期，以提供更好的解释张量网络收缩切片优化。寿命通过分析它所涉及的所有张量和收缩来描述边如何影响TNC过程。通过使用寿命，可以将计算转换为具有更少内存需求的等价形式切片工作在多级存储系统上的每两个 对于Sunway体系结构（目前国内最先进的超级计算系统）来说，无论是从硬盘到主存的数据交换，还是从主存到本地数据存储器（LDM）的数据交换（即从主存到本地数据存储器的数据交换），都是一个复杂的过程。进程级和线程级）可以通过切片来优化。 在进程级，我们对张量进行切片以实现分布式存储和并行化，并应用基于生命周期的切片查找器来减少进程划分的开销。 在线程级，切片有助于设计一种融合算法，以减少内存访问，并将内存密集型内核转换为计算密集型内核。案例，从而提高优化能力。这项工作的主要贡献包括：提出了图边生存期（张量维数）的概念，解释了图边生存期对切片的影响、切片如何消除这种影响、切片开销的来源以及如何避免这种开销.提出了一种以生命周期为指导的动态切片方法，该方法引入了一个新的目标函数，可以在较小的切片开销下找到较小的切片集以寿命为指标，提出了一种适合于Sunway体系结构的高性能TNC算法2背景2.1张量网络收缩和切片2.1.1记法。张量网络可以被视为无向图，其中张量和维度分别由顶点和边表示。 我们定义的符号类似的工作cotengra[12]：我们把一个图记为n=n，n。 是顶点集， 一条边的关联集包含该边所连接的两个顶点地图预览：表示 边权重以及每个维度上的大小。尤其是在经典模拟中，是2的幂顶点的关联集定义为 ：顶点收缩通过删除共享边并保留其余边将两个顶点合并为一个顶点。在生成的图形���"，则收缩的顶点“00，���”01“被替换为新的在新的边集中，将删除顶点n2和n0到n1之间的边图10中的未收缩边和用户1将由用户2继承。如果我们按顺序执行成对收缩，直到只剩下一个顶点，则顺序将形成收缩路径。事实上，等价类可以通过对一些独立的步骤进行重新排序来组成，所有等价路径都可以用树结构唯一地描述。收缩树定义为：=，其中每条边用原始图的一个顶点或由收缩生成的一个中间顶点表示。特别地，连接到叶节点的边由中的顶点 表示。节点表示为三联体=1,2,3refer to contractions.特别地，叶节点诸如1、1、1可以被视为具有标量1的乘法。然后叶节点可以表示读取过程。一定的收缩路径决定了每次收缩的方向通过添加最后的收缩作为根，如图所示1，得到一棵有根二叉树。对于给定的收缩树，相应的收缩过程的时间和空间复杂度可以定量地评估。 空间代价是最大的中间张量，即max ���∈���∈ ������（ ）。和···基于寿命优化的新一代神威超级计算机量子电路仿真PPoPP（−）（）∈×图1.张量网络及其收缩树。当形成某个收缩路径时，应添加最终标量的附加收缩。时间复杂度是：图2.一个直观的切片例子后半部分用图形表示，作为平行线.2.1.2相关工作。原材料切片的需求-���（ ）=∑Σ���（1）nates从相当大的内存成本的高秩（1，2，3）∈ ∈（ 123 ）��� ���������为了最小化内存和时间成本，通常将上述两个实例视为目标函数。对于大型张量网络，内存限制始终是一个严重的问题。因此，在找到一条路径后，有必要决定是否需要切片来降低张量的维数 沿着维度（TN中的边）切片张量可以将 一维张量转换为 不同 的 一维子张量。 切片暂时取消这些子张量之间的相关性，并提供并行性。图2示出了切片的简单示例。在这项工作中，切片是在原始图像上进行的，其中有= 2为所有。因此， 切片边组成2 个独立的任务，并且结果将在其单独计算后累积。在某些情况下，切片后总时间复杂度可能会增加，则切片开销定义为：������������������ （ ）×2|���|张量在一些量子优势电路中，存在维度超过60的张量[12]。它们可以占用高达1000 PB的空间，这超过了大多数存储系统。 切片有助于将内存需求降低到TB甚至GB的水平，从而使仿真变得可行。Cotengra[12]集成了几种随时随地的方法，并声称与Google[1]的估计相比，加速超过10000。它引入了一系列有效的启发式算法来搜索收缩路径，如社区[13]和图划分[14]。在[ 15 ]中实现的预处理之后，秩1和秩2张量被吸收，并且张量网络被大大简化。一个基于贪婪的切片策略内置在contengra中。它反复选择一个导致最小开销的维度进行切片，直到满足内存需求。像大多数贪婪方法一样，这种切片策略存在局部最小值在我们的工作中，congra被应用于找到一个合适的收缩路径。阿里巴巴提出了一个基于观察到的结构的模拟器，称为“茎”[16 ]。主干是收缩树中的计算密集型区域，包括大多数高阶张量便宜的部分被称为（（二）（）树枝在一个茎中，一个更大的张量序列-基本上吸收了较小的，大约99%的计算其中，n表示切片边缘的集合切片开销来自于由于任务分割而产生的冗余计算 从更高的角度来看，切片提供了一种分布式存储策略和自然的流式设计，因为大张量被切片以分别在多个进程中存储和计算。 与传统的基于大量通信的方法相比，切片通过独立的子任务显示出其优势。然而，作为价格，切片开销决定了效果，所以这项工作的主要目标之一是解释和减少这种开销。在这些收缩过程中发生了成本 对于切片，使用类似的贪婪策略，在切片拾取的两个步骤之间执行收缩树的局部调整。这种动态设计大大减少了收缩树的固有切片开销然而，如果不满足局部调整的条件，则该策略可能无法找到最优切片集。 这项工作可以提供10 18。8倍复杂度，切片开销为4，14。7%的FLOPS效率。由于效率高PPoPPChen等人××动 态 设 计 被 许 多 其 他 软 件 应 用 或 更 新 ， 如cotengra[12]。至于新神威系统，有几项工作研究了TNC的高性能算法。Sw_Qsim[17]提供了一系列矩阵乘法和张量置换的 方法， 特别 是对于 窄张量 。获 得2021年ACMGordon Bell 奖 [6] 的工作在 Sunway 架 构 上 实 现 了Transpose Transpose GEMM Transpose（TTGT）算法，这是一种融合了张量置换和矩阵乘法的设计，以减少内存访问。 这些努力显著提高了FLOPS效率，但都集中在整个路径的一个步骤上，而不是采取整体观点。根据Roofline模型[18]，优化将很快达到带宽约束问题的上限。对于极深的电路，其他基于张量的方法（如矩阵乘积状态）也在Sunway架构上实现[19]。在这项工作中，我们专注于硬件驱动和高度纠缠的电路，具有清晰的2D几何形状，相对较浅。2.2双威26010Pro处理器作为消耗大量时间和内存的部分，执行实际收缩通常需要复杂的超级计算机的支持。一个新的Sunway超级计算机被选中进行这项工作。新一代神威超级计算机与神威太湖之光[20]具有类似的架构，主要计算能力由核心组（CG）提供。为这台超级计算机设计了一款异构众核处理器SW26010pro。图3示出了芯片的结构。每个处理器芯片有6个CG。每个CG的计算处理元件（CPE）被布置为8乘8网格。每个CG包含一个16 GB的主内存，每个CPE包含256 KB的本地数据内存（LDM）。LDM和主存储器之间提供带宽为51.2 GB/s的直接存储器访问（DMA）由于计算强度大，内存访问瓶颈往往成为优化的关键问题 。 峰 值 带 宽 超 过 800 GB/s 的 远 程 内 存 访 问（RMA）专为数据交换而设计图3.SW26010pro处理器。6个CG的主要备忘录联合起来形成交叉转储，16 6 GB在这项工作中，为了容纳大的十个。切片的边缘，并保持原来的复杂性然而，从右边开始，子任务中的第一个收缩和最后两个收缩在切片边缘后没有改变 ，那么它们将被计算两次。 这些多余的计算构成了开销。图4.一个例子来说明切片开销的起源。左半部分是用图表示的张量网络，箭头给出收缩顺序。右边的部分显示了切片之前和之后的切片后，总复杂度是所有子任务的总和。实际上，切片边缘的冗余决定了哪些收缩将被冗余地执行。考虑到切片之前的收缩，边缘 涉及四个收缩：[，，]× [，，]���→ [������，]在一个CG内的CPE之间3寿命[，]���× [���， ]→ [������，][，������] × [，]→ [���，]���������[，������] × [，���，]→ [，，]（三）3.1定义这里有一个简单的例子，显示了在头上的切片从何而来图 4表示4 2张量网络上的收缩过程，目标秩限制为3。理想的情况是，一个子任务中所有收缩的时间复杂度在一个子任务完成后仅为2−1。这些收缩正好在图4中的虚线框内，这将不会被冗余地计算。在此基础上，本文提出了一个新的概念，即寿命，来描述切片过程中切片尺寸的影响范围。 符号来自第2.1.1节。基于寿命优化的新一代神威超级计算机量子电路仿真PPoPP+（）（−）（−）（）下一页定义1. 给定一个张量网络���=（���，���）和一个收缩树���=（���，������），边索引的概念生命周期���∈���指的是一组张量{ ���1，������2，. . . ，���������}������，如果���∈������������，对所有1 ≤ ���≤���.通过定义寿命，清晰地表示了切片边的影响范围 我们可以得出这样的结论，从张量网络中切割一条边后，生命周期中张量的大小 将减半，而其他张量的大小不会改变。 对应于这些张量的收缩的时间复杂度将不会改变，而其他收缩的时间复杂度将加倍。不仅在整个收缩树上，在收缩过程中，通过简单地替换定义中的收缩树，可以方便地在每个子树或中间生成的树上递归地定义寿命。这里的优点是我们可以更专注于密集计算的区域。3.2寿命和切片开销在大型张量网络中，需要将数十条边切成可接受的大小，这些张量这使得多边切片成为复杂性分析的关键问题考虑到不同条边的寿命是相互独立的，我们可以顺序分析每条切片边的寿命。图 5提供了一个示例，说明如何使用索引和索引对两条边进行切片- 是的收缩树从左到右分为5个部分，索引的生命周期经历了第2部分和第3部分，而索引的生命周期经历了第3部分和第4部分。分别������对部分1、4、5和部分1、2、5的时间复杂度进行索引和加倍，使冗余计算的整数倍如图所示。5、作为一种生产方式。扩展到更一般的情况，如果一个张量包含���的切片索引总数为���，它将被分成2���个更小的张量。对于所有2个子任务，将有2个冗余数据的1/2-1/2倍 然后时间复杂度将乘以2− 倍。因此，寿命密度在区域的存储和计算复杂度中起着决定性的作用。更多的切片边往往会导致更高的开销。作为一个简单的条件，当给定切片集时，如果我们额外地挑选更多的边进行切片，那么开销将增加，除非所添加的边的生命周期跨越整个收缩树，这很少发生。然而，对于一个任意的有 边和 1边的切片集，我们能否找到它们的开销之间的偏序关系？我们可以用给定的目标大小证明下面的定理它为冗余切片提供了更深刻的解释，为我们的切片策略奠定了理论基石 它表明，在大多数情况下，有效的较小切片集表示较低的切片开销。图5.间接费用的叠加法则。在切片之前（上半部分）和之后（下半部分）从左到右示出收缩顺序每个分支表示一个张量，收缩发生在交点处。张量中具有不同颜色的线表示边，并且所有具有相同颜色的线的集合自然是这些边的寿命定理1. 对于张量网络、收缩树和 边切片集1，如果 找到1-边切片集2，并且1和2不为空，则必然存在 1-边切片集3，其开销小于1。图 6. 时 间 复 杂 度 和 通 过 对 茎 切 片 的 倍 数（Sycamore（λ=20）用作示例）。图 6比较了Sycamore电路[1]的一个公共收缩树上切片前后的整体时间复杂度。从图中，我们可以得出结论，低开销的关键是保持主要计算密集型部分的时间复杂度，这意味着大张量包含在与切片边一样多的生命周期中。理想情况下，时间复杂度和多重性导致的切片是负相关的。PPoPPChen等人（）下一页（）下一页≪≪+∈|∩|≥|| −3.3切片优化路线由于内存限制，我们必须进行切片，并保持一定的开销。然而，在多级存储系统上，在某些情况下，计算开销可以转化为数据移动。对于TNC，我们将介绍两种主要的方法来处理开销，即，为了通过搜索更好的切片集合来减少开销，或者为了通过经由堆叠的数据移动来替换开销，在以下部分中，将重新描述。 堆叠是切片的逆操作，当低存储器或分布式存储器的容量足以满足整个存储器需求时，堆叠是可行的。例如，我们可以将rank-53张量存储在硬盘中，通过IO在收缩步骤中获得rank-30切片，然后在计算后将其放回。这个过程执行切片的获取和堆叠的自然放。 如果在切片边的生存期结束后立即进行堆叠，则该边的开销自然会消除，并且内存需求也会得到解决。尽管如此，在数据访问（使用低级存储）或通信（对于分布式内存）期间，数据交换将产生巨大的成本。寻找更好的切片图7.按成本分配不同存储级别的开销（以Sycamore为例，原始内存成本为几十PB。 对于Sunway架构 ， 每 个 CPE 都 有 一 个 96GB 的 主 内 存 和 一 个256KB的LDM）最小化内存开销描述了一个带约束的优化问题。 对于收缩树 =，，目标函数可以通过切片后的总时间复杂度来描述。set可以避免内存访问和通信，但它引入了来自冗余计算的开销选择取决于带宽的具体值（���∑∈������2|| |���−|∩|���∩������|（四）和开销。 在低带宽和低开销的情况下，切片优化具有更好的性能，而在高带宽和高开销的情况下，堆叠更适合。图图7示出了不同目标大小的典型开销分布 数据访问成本通过不同层次的算术强度（AI）转化为相等的开销。等开销线和存储容量将图分成几个部分。最常见的手动控制的存储级别包括硬盘，主内存和LDM（双威架构）。对于内存访问，������������������������������������������������������������������������������-��������� 是���������������������������的从硬盘到LDM，堆栈技术的潜力越来越大，而切片优化技术则越来越有应用价值。这些方法不是为特定的体系结构定制的。实际上，我们需要的只是一个多级存储系统。4切片开销减少4.1切片优化IO的低带宽限制了堆栈，切片开销直接影响并行可扩展性.如Theorem所示1、切片的优化可以分为两步：寻找更小的切片集，并对所选切片集进行调优，以达到更低的开销。下面两个小节分别讨论这两个步骤。其中，n是切片边的集合，并且n是涉及TN中n的收缩的边的集合不超过存储器容量的目标大小表示为“0”。对于每一个人来说，没关系目标函数和公式一起可以确定优化问题。4.2切片策略在这里，我们将寿命定义在茎上[16]，而茎的定义有些不同。在这项工作中，干被定义为最计算密集的路径上的收缩树。根据图论，在路径上，每个收缩步骤与其下一步骤具有数据依赖性。 由于大多数分支与内存约束无关，因此它们是预收缩的，只有主干保留下来进行优化。经过预处理后的主干成为一棵新的收缩树，我们可以检测其上每条边的生存期。假设切片集的最佳尺寸为1/2，则茎被分成两个连续部分：1 对于1，多个候选集合共享相同的大小1。 根据上面的讨论，1通过2的张量寿命越多，更新后的2中被切片的边就越少。严格地说，更长的生命周期不一定会导致更低的切片开销。然而，生命的包容关系却可以。减少记忆的效果也是如此。特别是，对于基于寿命优化的新一代神威超级计算机量子电路仿真PPoPP[客户端]≤（）下一页−∈]1（）←（）∈[客户端]（）下一页（[]））//）收缩树只有一个延伸方向，那么它的长度决定了包含关系。 所以我们从词干的两端开始搜索，每次选择一个张量为1，左边的部分为2。因此，具有较长寿命的边缘将更好。如果我们迭代地执行这个过程则预期会有更小的切片集我们提出了算法。1详情算法1程序切片查找器输入：收缩树的主干 ，目标模糊度=对于所有边缘索引，计算时间重复结束������ =（ [0].���������<���[ -1].���������）？ [0]：���[ −将具有最长生存期的索引添加到索引中对于所有人 来说，如果....end ifendforUpdate更新结束，直到==0输出：切片集虽然上述策略并不总是提供具有最低开销的切片集，有时甚至比contengra发现的更差，但我们已经成功地满足了上述定理的所有先决条件。上面的方法可以为给定的收缩树找到尽可能小的切片集。结合路径搜索的动态过程，开销可以降低。然后，细化器将找到更好的切片集以减少开销。4.3基于模拟退火的切片细化算法我们的切片查找器不能保证找到最佳切片集，它会寻找尽可能小的切片集因此，本节的主要任务是在给定一定数量的切片边的情况下找到最佳考虑到切片集的大小是固定的，从前者到后者的置换可以描述为边替换。切片后，有一些张量的维数正好等于目标维数，它们被称为“临界张量”。 如果切片边的生命周期不包含任何临界张量，则该边不会有助于内存减少，并且可以从切片集中移除。而且，从另一个角度来看，要用index代替sliced edge ，一个直接的方法是找到另一个unsliced index ，它的生存期包含生命期内的所有临界张量 。简单地替换索引greatly有时会导致局部最小值。例如，最优集合包含index 和index ，而我们找到的集合包含 和 ，但是替换 from 可能会增加开销，或者无法匹配内存限制。 穷尽搜索或动态规划将导致最优解，但遭受搜索空间的组合爆炸。于是，随机算法成为一种平衡搜索时间和搜索质量的选择。模拟退火算法可以避免局部最小值，并提供了一个实用的速度，因为算法的复杂性暂时增加。2场演出。算法2程序切片细化器输入：目标尺寸、切片设置、收缩树 、最终温度、参数初始化温度范围对于所有边缘索引，计算时间重复结束随机选择_=___为了所有你想要的将改为计算时间复杂度如果你不知道， <更新日志其他用prob更新数据库��������� ���������=如果结束，则结束直到2009 年<输出：切片集5二次切片融合设计5.1线程级优化的难点对于线程级，如果在CPE上组织整个路径，考虑到256-KB的LDM，将存在巨大的开销。因此，以前的工作在线程级逐步优化[17][6]以避免它，转向内存访问而不是大量冗余计算。然而，频繁的内存访问也限制了FLOP的效率。张量之间的收缩是通过乘法实现的[17]。 基于此策略，对于类正方形矩阵，可以获得70%以上的峰值性能。然而，对于窄矩阵乘法，特别是当，，中的两个小于16时，这支配了许多模拟任务[1]，我们可以PPoPPChen等人×−（）（++）/（）下一页/（）下一页（）下一页（）下一页（）下一页（）下一页容易地推导出Θ���������Θ������������������，使得GEMM将从计算强度问题变为带宽约束问题。另一个约束来自每个CPE上的256-KB LDM，其只能容纳用于乘法的秩13张量。那么，对于CG，通过秩为31的张量计算收缩至少需要212倍的低效率GEMM。为了充分利用512位的单指令多数据（SIMD），一个4 4复杂GEMM内核的应用。当一个线程中的数据量和数据量都小于4时，对数据长度的要求会导致高性能内核和二维数据分布之间的冲突相比之下，1D分布避免了大多数填充，并将GEMM过程切片为简单的子任务。最重要的是，嵌入在数据分布中的隐式切片作为一种克服LDM内存限制的方法，与进程级切片存在类似的问题。我们提出了一个更有效的切片堆栈策略指导的生命周期，这可以大大降低数据移动的成本。 具体到线程级别，它被命名为第二层切片（第一层切片发生在进程级别）。LDM和主存之间的二次切片将提供一个融合算子来组织CPE上的收缩路径的部分，并大大节省存储器访问成本。5.2叠片设计如果我们在整个收缩路径上进行切片，则可以在没有中间通信和IO的情况下在进程上执行子任务，同时承受计算开销。相比之下，如果我们接受通信或内存访问，则可以避免计算开销。由于IO的低带宽和低计算开销，这种策略在进程级上不起作用，但在LDM和主存之间可用。 由于新的Sunway超级计算机上的LDM仅适用于秩为13的张量，如果收缩是逐步进行的，我们应该在每两步之间频繁地进行DMA-get和DMA-put。 考虑到上面的算术强度，内存访问将占主导地位。为了减少LDM和主存之间频繁的数据交换，在一个计算内核中连续执行收缩路径的并行化步骤有助于减少LDM和主存之间频繁的数据交换。 在这些步骤的开始，我们执行一次DMA-get以获得更大的张量，并且在n步计算之后，结果将由DMA-put写回。然后， 减 少 了 1次DMA-get和DMA-put。作为图的顶部部分图8显示，CPE每次都可以从主存中的张量中获得一个较低秩的张量，从而丢弃一些维度。在一个特殊的收缩中，通常有部分维度被吸收了，其他人也被吸收了。 根据这一观察，在计算开始时，如果我们选择将在下面被吸收的所有维度，步骤形成一个张量，并通过DMA以步幅将其送入LDM，然后每个CPE可以独立地进行计算，如图的下半部分。8场演出。对于记忆界，我们调整参数 来确定所形成的张量的秩。在这种策略中，选择的索引保留，其他索引被切片。不同的CPE执行切片产生的不同的主要的问题是如何选择切片，并找到合适的 。切片集的基本前提是切片索引不会逐步���收缩，幸运的是，这样的条件只是生存期的定义。 因此，对于路径上的特定起始位置，我们对具有最长生命周期的索引进行切片，并遍历主干，直到任何一个切片索引的生命周期结束。 如果切片集的大小加上13（LDM的容量）小于子路径上的每个张量，则融合计算完成。 使用这种策略，没有切片开销，最后一个DMA-put扮演堆叠的角色，没有额外的通信。5.3深度优化5.3.1用递推公式实现置换映射约简。 原位计算图和预计算图是张量置换的两种主要方法。 在原位计算地图需要一个������������������时间复杂度的大小 张量的秩���������������，和���1的空间复杂度。相比之下，后者提供������������������了第一次计算和������下一次计算的时间复杂度和空间复杂度������。在我们的融合算法中，每一步收缩之前的排列成为热点之一。即使使用短类型，但预先计算的地图太大而无法存储。然而，对于基于原位映射的策略，张量的秩约为10，这导致成本超过10倍。一个可行的解决方案是将两种策略。对于一个特定的收缩，= ，其中 表示置换，置换后秩为9的典型索引顺序 为0，1，2，4，5，7，8，3，6，需要吸收的索引将被组织在最后，即。，3， 6.与下标相反，这些下标放在开头，如3、 8、 0、 1、 2、 4、 5、 6、 7。显然 ，对于图1，前3个维度将不参与排列，所以只有18个维度的地图就足够了。 而对于 ，最后4个维度在置换过程中是相同的，因此由4，5，6，7形成的4个元素的相邻性将被保持，并且映射的大小被减小到116。有了偏移量，对应的映射可以通过以下方式计算：当处于以下情况时，[+ ]=[]+������������������<������������������������基于寿命优化的新一代神威超级计算机量子电路仿真PPoPP−（/）（）下一页图8.线程级优化的融合设计。上半部分显示了分步策略在以前的作品，和底部是融合的设计。我们的策略在LDM上组织一条子路径，对于一条长度为λ的子路径，将DMA-get和DMA-put的次数减少到λ1倍，上标λ表示置换，张量的下标表示切片维数。图9.二次切片的一个例子。有5条边的寿命贯穿整个过程。切片后，这些边缘，最大的内存需求从2 8减少到2 3，并产生2 5线程级并行的子任务。只有虚线框内的计算将在每个核心中执行，并且存储器访问发生在计算的开始和结束处。1、与预算图相同 空间复杂度将减少到2 ，其中m是在结束或开始处的连续索引的数目。5.3.2通过通信消除离散存储器访问。 虽然融合策略大大减少了DMA，但DMA的效率成为一个障碍。由于我们已经从原始张量中切出了一些边，因此我们需要的子张量通常离散分布在主内存。 如果我们想得到一个没有最后一个索引的子张量（假设它已经被切片），那么我们需要的每两个元素之间都有一个空间间隔。因此，DMA的粒度将非常小，这会损害带宽。在实践中，切片边缘分散在不同的位置。在这种情况下，DMA的带宽只能达到0. 1%的峰值性能，并进行负优化。为了提高带宽，64个CPE的合作变得至关重要。在我们的并行框架下，最后6个切片索引在64个CPE之间组织。通过远程内存访问（RMA），CPE之间的数据交换速度更快，整个CG的峰值性能可达800 GB/s。然后，我们把64个CPE的子张量作为一个整体，让每个CPE连续访问内存。 此策略保证了DMA的基本粒度为512 B，可提供超过50%的峰值性能。在存储器访问之后，RMA被应用于在CPE之间重新排列数据为了提高RMA的粒度和保证效率，增加了一个额外的置换对于其他架构，我们可以通过简单地划分通信组来实现此策略。PPoPPChen等人6结果相关工作（例如： ，Cotengra[12]， Alibaba[16]和[6]）都模拟了Sycamore RQC[1]。为了进行适当的比较，除非另有说明，否则本工作中使用的收缩树也来自Sycamore的张量网络。6.1切片开销和缩放结果图10.切片大小和开销与cotengra比较红色的点显示cotengra与我们相比的额外切片边的数量;绿色的点显示开销的比例。当差值为0且比值为100%时，两种方法的性能相同。根据第4节中的切片策略，给定一条收缩路径，我们可以找到一个预期开销较低的切片集。图 10显示了我们的工作和cotengra之间的比较。 我们用contentra找到了400条收缩路径，并分别用我们的方法和cotengra搜索切片集。与cotengra相比，我们发现的切片集可能更小，并且导致更低的开销。 具体到每一条路径，我们的策略在98%以上的情况下表现更好。 对于几种例外情况，观察到的现象是路径的计算密集区域是分散的。同时，由于模拟退火是一种随机方法，不能保证一定能找到最优解.我们发现的最佳开销结果小于1.05，我们综合选择一条复杂度进行线程级优化。由于切片，进程彼此高度独立，并且只会在程序结束时执行一次allReduce。 强标度结果和弱标度结果如图所示。十一岁图11.（强缩放结果（总共65536个子任务）和弱缩放结果（每个节点上有16个子任务）。图12.在线程级别通过二次切片进行优化在390核的单节点上进行了优化，并对收缩路径上不同大小的任务进行了性能测试。使用逐步策略进行比较。6.2计算效率图12表明我们的工作能够显著提高计算效率。使用1024个节点，可以在10098.5s内生成完美样本或1M个相关样本。 考虑到扩展的结果，我们预计，我们可以减少使用107520个节点（41，932，800个核心）的整体时间成本为96.1秒。可持续的单精度性能预计为308.6Pflops。根据图12，通过二次切片，存储器访问的时间大大减少，并且置换和GEMM的时间保持相似。这一结果验证了我们的预测，二次切片可以减少内存访问的一些基于python的预处理的价格，这只需要1个核心和ignor- able时间。另一个结论是，在二次切片之后，计算内核在某些情况下从存储密集型内核转变为计算密集型根据Roofline模型[18]和基于寿命优化的新一代神威超级计算机量子电路仿真PPoPP/（++）Sunway架构的运算强度，浮点运算的数量应该超过42.3倍的字节数的内存访问，以达到峰值性能。该策略的平均融合步长约为10步，有一个小 的平均融合步长为4步，那么在某些情况下，TNC的算术强度可以突破42.3。图图13显示了线程级别上特定情况的Roofline模型。 由于置换，其中包括LDM访问，我们的性能和峰值性能之间仍然有差距。不过，与原来算术强度2. 6（混合精密度）和1 .一、22（单精度），优化极限大大提高。图13.我们工作的屋顶模型在不同情况下，算术强度从10μ m到40μ m不等.在某些情况下，这些问题变成了计算限制。7意蕴本文提出了一种新的基于生命周期的方法，以减少切片开销，提高计算效率，在进程级和线程级并行优化。由于生命周期定义的引入，一系列基于生命周期的引理和定理加深了我们对张量网络和收缩树的认识，从而提出了一种可解释的切片开销处理方法，以及一种就地切片策略来寻找最小切片集，从而减少了切片开销。 我们的就地策略可以独立工作，也可以优化动态方法找到的切片集。因此，它成为一个通用的后处理时，搜索切片集。此外，基于生命周期，我们采用堆叠来避免冗余计算带来的巨大开销，并将其推广到任意多级存储系统。切片优化和堆叠构成了跨国公司的两大战略然后，设计了一种基于运算强度的判别器，对不同层次的记忆进行策略选择。对于Sun-way体系结构，我们将其应用于线程级. 在必要的价格更负担得起的内存访问DMA和更快的通信之间的CG通过RMA。最鼓舞人心的结果是，在某些情况下，计算内核从内存密集型变为计算密集型，这重塑了我们对问题的理解。作为一种广泛应用的方法，张量网络可以在许多研究领域找到，如统计物理[21]，数据科学[22]，社会学[23]等。物理学中的一系列问题都可以归结为TNC。对于大型跨国公司来说，极端的时间和空间复杂性成为了主要的困难。切片将巨大的内存需求转化为可以作为流水线解决的数据流，在这些TNC过程中起着重要的作用。 除了TNC，如果我们需要处理一系列具有数据依赖性的大型矩阵乘法，切片仍然可以用于任务分配。这项工作证明了量子电路的张量网络的寿命本质上是有希望的此外，由于定义简单，寿命可以很容易地推广到具有不同特征的张量作品，并有助于分析收缩的时间和空间复杂性。可以预见，一辈子都可以玩im-在更多领域发挥重要作用确认我们要感谢王震、孙兆奇李泽刚和李宇轩的建议和讨论。本工作得到国家重点研发计划（2020YFB0204804，2020YFB0204800）的部分支持国家自然科学基金（批准号：T2125006，U1839206，项目编号：62102114），江苏创新能力建设项目（项目编号：BM 2022028）和浙江省实验室重点研究项目（项目编号：2021PB0AC01）。通讯作者为刘勇、刘欣、甘林、陈德勋和杨广文。引用[1] F. 阿鲁特湾阿里亚河，巴西-地Babbush，D.Bacon，J.C. 巴尔丹河巴伦兹，R. 比斯瓦斯，S。Boixo，F.G. Brandao，D.A. Buell等人，“Quantum supremacy using a programmable superconductingprocessor，”Nature，vol. 574号不行7779，pp.505[2] J. 韦尔斯湾Bland，J.尼科尔斯，J。哈克，F。Foertter，G.哈根，T. 迈尔，M。阿什法克湾Messer和S.Parete-Koon，“Announcingsupercomputersummit，”62016.[3] H.- S. Zhong，H.王玉-H. 邓，M.-C. 陈湖，澳-地C. 彭，Y.-H.Luo ， J.Qin ， L.Wu ， X. 丁 氏 Y.hu等 ， “Quantum computationaladvantageusingphotons，”Science，vol. 370，不。第6523页 1460-1463，2020年。[4] A. Zlokapa，S.Boixo和D.激光雷达，PPoPPChen等人[5] F. Pan和P. Zhang，[6] Y. Liu，X.Liu，F.Li，H.傅，Y。杨，J.Song，P.Zhao，Z.小王，D.Peng ， H.Chen 等 人 ， “Closingthe”quantumsupremacy”gap ： achieving real-time simulation of a randomquantum circuit using a new sunway supercomputer” ， inProceedingsoftheInternationalConferenceforHighPerformanceComputing ， Networking ，