在新型Sunway超级计算机上模拟量子电路的基于生命周期的优化

0基于Sunway超级计算机的量子电路模拟的lifetime优化0陈耀建 清华大学北京，中国0刘勇 无锡国家超级计算中心浙江实验室，杭州，中国0史新民 信息工程大学郑州，中国0宋佳伟中国无锡国家超级计算中心0刘昕 中国无锡国家超级计算中心浙江实验室，杭州，中国0甘琳 清华大学中国无锡国家超级计算中心0郭楚 信息工程大学郑州，中国0傅浩欢 清华大学中国无锡国家超级计算中心0高杰北京并行工程技术研究中心北京，中国0陈德训中国无锡国家超级计算中心0杨广文 清华大学中国无锡国家超级计算中心浙江实验室，杭州，中国0摘要高性能的经典模拟器对于量子电路，特别是张量网络收缩算法，已经成为验证嘈杂量子计算的重要工具。为了解决内存限制，使用切片技术来减少张量维度，但这也可能导致额外的计算开销，从而大大降低整体性能。本文提出了基于lifetime的新方法来减少切片开销并提高计算效率，包括一种处理切片开销的解释方法，一种用于找到最小切片集的原地切片策略，以及一种专为申威架构定制的自适应张量网络收缩路径细化方法。实验结果显示，在大多数情况下，我们的原地切片策略的切片开销将小于cotengra。0获得本作品或其中部分内容的数字或印刷副本，供个人或教室使用，不收取费用，但不能为了盈利或商业利益而制作或分发副本，并且副本上必须带有本通知和第一页的完整引用。必须尊重本作品中的第三方组件的版权。对于其他所有用途，请联系所有者/作者。PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC ©2023版权由所有者/作者持有。ACM ISBN 979-8-4007-0015-6 / 23 /02. https://doi.org/10.1145/3572848.35775290，这是目前最常用的图路径优化软件。最终，对于Sycamore量子处理器RQC，模拟时间缩短到了96.1秒，使用超过41M个核心生成1M个相关样本的可持续单精度性能达到了308.6Pflops，与2021年Gordon BellPrize作品相比，性能提升了5倍以上的60.4Pflops。0关键词：量子计算，电路模拟器，张量网络收缩，申威架构，切片，直接内存访问，融合设计01 引言量子计算机在特定任务上具有指数级的优势，有潜力比经典计算机提供指数级的加速。声明“量子优势”是指那些只能通过使用量子计算机在合理时间内解决的任务[1][2][3]。然而，尽管在计算能力上具有这种优势，低保真度仍然是量子计算机的主要挑战[4]。因此，经典模拟器对于验证量子计算机设计[5]仍然非常重要。此外，依赖可靠计算资源的领域（如量子算法、量子编程语言和量子）0PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加拿大陈等人0编译器可以在经典模拟器上工作，并获得接近性能[6]。考虑到指数级复杂性和紧急需求，提高最先进的经典模拟器的效率非常重要。在经典计算机上直接存储任意量子状态对于量子位的数量来说需要指数级的内存。因此，使用传统的状态向量方法来模拟量子电路目前限制在不超过50个量子位[7]。近年来，张量网络收缩（TNC）[8]算法展示了很大的潜力，特别是在模拟随机量子电路（RQC）方面。当与切片技术结合使用时，TNC算法可以仅使用有限的内存有效地模拟更大的量子电路。在TNC算法中，量子位和量子门被表示为张量，并且整个量子电路被视为张量网络[9]。计算输出量子态的振幅的问题被转化为收缩相应的张量网络。TNC的性能主要由TNC路径决定。在一个具有数百个张量的网络中，一个好的收缩路径可以将复杂性减少几个数量级。同时，在收缩过程中，可能会出现巨大的中间张量。切片技术可以减少内存需求[10][11]，但代价是一些计算开销。本文旨在减少切片引起的计算开销。与主要使用启发式算法的以前工作不同，本文引入了一个新概念，即lifetime，以便为张量网络收缩中的切片优化提供更好的可解释性。通过使用lifetime，可以将计算转化为具有更少内存需求的等价形式。切片作用于多级存储系统上的每两个相邻的可手动控制的级别。对于申威架构（中国最先进的超级计算系统），从硬盘到主存储器的数据交换，以及从主存储器到本地数据存储器（LDM）（即进程级别和线程级别）的数据交换都可以通过切片进行优化。对于进程级别，我们对张量进行切片以进行分布式存储和并行化，并应用基于lifetime的切片查找器来减少进程划分的开销。对于线程级别，切片有助于设计融合算法以减少内存访问，并在某些情况下将内存密集型的核转换为计算密集型的核，从而提高优化能力。本工作的主要贡献包括：0•提出了一种图边（张量维度）的lifetime概念，用于解释每个维度的影响，切片如何消除这种影响，切片开销的来源以及如何避免这种开销。0•在lifetime的引导下，提出了一种新的目标函数的动态切片方法，以帮助找到更小的切片集，并减少切片开销。0•根据lifetime指示，提出了一种适用于申威架构的TNC高性能算法。02 背景02.1 张量网络收缩和切片 2.1.1 符号。张量网络可以被视为一个无向图，其中张量和维度分别由顶点和边表示。我们定义了与cotengra[12]的工作类似的符号：我们用 �  =  ( �, � ) 表示一个图。� 是顶点集，�是边集。边 � 的关联集 � � 包含连接的两个顶点。映射  �  : �→  �表示边的权重，以及每个维度的大小。特别在经典模拟中，对于所有  �  ∈  � ，� ( � ) 为2的幂。顶点 �的关联集定义为 � �  =  { �  :  �  ∈  �, �  ∈  � � }。顶点收缩通过删除共享的边并保留其他边将两个顶点合并为一个。在生成的图� ′ 中，合并的顶点 � 0 ，� 1被新的顶点 � 2 取代，并且在新的边集中移除了 � 0 与 � 1之间的边。在 � � 0 和 � � 1 中未合并的边将由 � � 2继承。如果我们按顺序依次执行成对的合并，直到只剩下一个顶点，那么顺序将形成一个收缩路径。事实上，可以通过重新排序一些独立的步骤来组成等价类，并且所有等价路径可以通过树结构唯一描述。收缩树 � 定义为�  =  ( � � , � � )，其中每条边由原始图的顶点或通过收缩生成的中间顶点表示。特别地，与叶节点连接的边由 �中的顶点表示。以三元组 ����  =  ( � 1 ,� 2 ,� 3 )表示的节点表示收缩。特别是，诸如 (1,� 1 ,� 1 )之类的叶节点可以视为与标量1的乘法。然后，叶节点可以表示读取过程。给定一个收缩树，可以定量评估相应收缩过程的时间和空间复杂性。空间成本是最大的中间张量，即 max � ∈ � � � �  ∈ � � � ( � ) 。0基于寿命的优化方法用于在新的神威超级计算机上模拟量子电路 PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔0图1.张量网络及其收缩树。当形成一条特定的收缩路径时，应添加额外的收缩来得到最终的标量。时间复杂度为：0� ( � )  = ∑�0( � 1 ,� 2 ,� 3 ) ∈ � 0�0�  ∈( � � 1 ∪ � � 2 ∪ � � 3 ) (1)0为了最小化内存和时间成本，通常将上述两个表达式视为目标函数。对于大型张量网络，内存限制始终是一个严重的问题。因此，在找到一条路径之后，有必要决定是否需要切片来减少张量的维度。在张量网络中，沿着一个维度（张量网络中的一条边）切片可以将一个 �-维度张量转化为 � 个不同的（ � − 1）-维度子张量。切片临时取消了这些子张量之间的相关性，并提供了并行性。图2展示了一个简单的切片示例。在本工作中，切片是在原始的 �上进行的，其中对于所有的 � ∈ � ，有 � ( � ) = 2。因此，2个切片边界构成了2 �个独立的任务，其结果将在各自的计算之后累积。在某些情况下，切片后总的时间复杂度可能会增加，然后切片开销定义为：0� ( �,� )  = � �0� ��������  ( � ) (2)0其中 �表示切片边界的集合。切片开销来自于由于任务分割而产生的冗余计算。从更高的角度来看，切片提供了一种分布式存储策略和自然的流式设计，因为大型张量被切片存储和在多个进程中计算。与基于大量通信的传统方法相比，切片通过独立的子任务显示出其优势。然而，作为代价，切片开销决定了效果，因此本工作的主要目标之一是解释和减少这种开销。0图2.切片的直观示例。后半部分以图形的形式表示为并行。2.1.2相关工作。切片的需求源于高秩张量的显著内存成本。在一些量子优势电路中，存在维度超过60的张量[12]。它们可能占用高达1000PB的内存，超过了大多数存储系统的容量。切片有助于将内存需求减少到TB甚至GB的级别，以便进行模拟。Cotengra[12]整合了几种任意时间方法，并声称与Google[1]的估计相比，速度提高了10000倍以上。它引入了一系列有效的启发式算法来搜索收缩路径，例如社区[13]和图分区[14]。在[15]中实现的预处理之后，吸收了秩1和秩2张量，并且张量网络得到了大幅简化。Cotengra中内置了一种基于贪心策略的切片策略。它重复选择导致切片开销最小的维度，直到满足内存需求。与大多数贪婪方法一样，这种切片策略存在局部最小值。在我们的工作中，Cotengra用于找到合适的收缩路径。阿里巴巴提出了一种基于观察到的结构“干扰”的模拟器[16]。干扰是收缩树中的一个计算密集区域，包括大部分高秩张量。廉价的部分称为分支。在单个干扰中，较大的张量依次吸收较小的张量，并且约99%的计算成本发生在这些收缩中。对于切片，他们使用类似的贪心策略，在两个切片选择步骤之间进行收缩树的局部调整。这种动态设计极大地减少了收缩树的固有切片开销。然而，如果局部调整的条件不满足，这种策略可能无法找到最优的切片集。这项工作可以提供18.8倍的复杂度、4倍的切片开销和14.7%的FLOPS效率。由于效率很高，(3)0PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔 Chen等人。0动态设计是由其他软件应用或更新的，例如cotengra[12]。至于新的神威系统，一些研究集中在TNC的高性能算法上。Sw_Qsim[17]提供了一系列矩阵乘法和张量置换的方法，特别适用于窄张量。赢得2021年ACM GordonBell奖的工作[6]在神威架构上实现了TransposeTranspose GEMMTranspose（TTGT）算法，这是一种融合了张量置换和矩阵乘法的设计，以减少内存访问。这些工作显著提高了FLOPS效率，但都集中在整个路径的一个步骤上，而没有从整体上进行综合考虑。根据Roofline模型[18]，优化很快将达到带宽受限的问题的极限。对于极深的电路，还在神威架构上实现了其他基于张量的方法，如矩阵积态[19]。在本工作中，我们专注于受硬件驱动和高度纠缠的电路，其具有清晰的二维几何结构且相对较浅。02.2 神威26010Pro处理器0作为一个耗时和占用内存较大的部分，执行实际的收缩通常需要先进的超级计算机的支持。本工作选择了一台新的神威超级计算机。新一代神威超级计算机与神威太湖之光[20]具有类似的架构，其主要计算能力由核心组（CGs）提供。为这台超级计算机设计了一种异构多核处理器SW26010pro。图3显示了芯片的结构。每个处理器芯片有6个CGs。每个CG的计算处理单元（CPEs）排列成8×8的网格。每个CG包含16GB的主存储器，每个CPE包含256KB的本地数据存储器（LDM）。LDM和主存储器之间提供带宽为51.2GB/s的直接内存访问（DMA）。由于算术强度巨大，内存访问瓶颈经常成为优化的关键问题。神威架构内部的CPE之间的数据交换使用了峰值带宽超过800GB/s的远程内存访问（RMA）。03 寿命03.1 定义0这里是一个简单的示例，展示了切片开销的来源。图4显示了在一个4×2的张量网络上进行的收缩过程，目标秩限制为3。理想情况下，在一个子任务中的所有收缩的时间复杂度在进行切片之后变为2−�。0图3.SW26010pro处理器。在本工作中，6个CG的主存储器合并成了一个16×6GB的交叉转储，以容纳大型张量。切割 �边界，保持了原始的复杂度。然而，从右侧来看，切片边界 �之后的第一个收缩和最后两个收缩没有改变，它们将被计算两次。这些冗余计算构成了开销。0图4.一个示例，展示了切片开销的来源。左侧是用图形表示的张量网络，箭头给出了收缩顺序。右侧显示了切片前后的复杂度。切片后，总的复杂度是所有子任务的总和。0实际上，切片边界 �决定了将要进行的冗余收缩。考虑切片前的收缩，边界 �包含四个收缩：[ �,�, � ] × [ �,�, � ] → [ �,�,�, � ]0[ �,�,�, � ] × [ �,� ] → [ �,�,�, � ]0[�,�,�,�] × [�,�] → [�,�,�,�]0[�,�,�,�] × [�,�,�] → [�,�,�]0这些收缩仅限于图4中的虚线框内，不会进行冗余计算。基于上述分析，本工作提出了一个新概念，生命周期，用于描述切片过程中切片维度的影响范围。符号来自第2.1.1节。0基于生命周期的优化：在新一代申威超级计算机上模拟量子电路PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0定义1. 给定张量网络� = （�，�）和收缩树� =（��，��），边索引� ∈�的概念生命周期是指一组张量{��1，��2，...，���} � ��，如果� ∈����，对于所有1 ≤ � ≤ �。0通过定义生命周期，清楚地表示了切片边的影响范围。我们可以得出结论，切片来自张量网络的边�切片后，生命周期上的张量的大小将减半，而其他张量的大小不会改变。对应这些张量的收缩的时间复杂度不会改变，而其他收缩的时间复杂度会加倍。生命周期不仅仅限于整个收缩树，还可以通过简单地替换定义中的收缩树，递归地定义在每个子树或在收缩过程中生成的中间树上。这里的优势在于我们可以更多地关注计算密集区域。03.2 生命周期和切片开销0大型张量网络从Sycamore等大电路中需要切片数十个边，这使得多边切片成为复杂性分析的关键问题。考虑到不同边的生命周期是独立的，我们可以逐个分析每个切片边的生命周期。图5给出了具有索引�和索引�的两条边的切片示例。从左到右，收缩树分为5部分，索引�的生命周期经过第2和第3部分，而�经过第3和第4部分。索引�和�将第1、第4、第5部分的时间复杂度加倍，将第1、第2、第5部分的时间复杂度加倍，并将整个冗余计算的倍数以分段生产的形式显示在图5中。扩展到更一般的情况，如果一个张量包含�个切片索引，总共�个，它将被分成2�个较小的张量。对于所有2�个子任务，将有2�-�次冗余数据。然后，时间复杂度将乘以2�-�次。因此，生命周期的密度在一个区域的内存和计算复杂性中起着决定性作用。更多的切片边往往会导致更高的开销。作为一个简单的条件，当给定一个切片集时，如果我们额外选择更多的边进行切片，那么除非添加的边的生命周期穿越整个收缩树，否则开销将增加，这种情况很少发生。然而，对于具有�个边和�+1个边的任意切片集，我们能否找到它们之间的开销的部分排序关系？我们可以通过给定目标大小证明以下定理。它更深入地解释了冗余切片，并为我们的切片策略奠定了理论基础。它表明，较小的有效切片集在大多数情况下表示较低的切片开销。0图5.开销的叠加规则。收缩顺序在切片前（上半部分）和切片后（下半部分）显示。每个分支表示一个张量，收缩发生在交点处。张量中不同颜色的线表示边，具有相同颜色的所有线的集合自然成为这些边的生命周期。定理1.对于张量网络�（�，�），收缩树�（��，��）和一个�-边切片集�1，如果找到了一个（�-1）-边切片集�2，并且�1和�2的交集非空，则必定存在一个（�-1）-边切片集�3，其开销小于�1。0图6.在一个常见的Sycamore电路的干扰上通过切片前后的时间复杂度。0图6比较了Sycamore电路的常规收缩树在切片前后的整体时间复杂度[1]。从图中可以得出一个结论，低开销的关键是保持主要计算密集部分的时间复杂度，这意味着大的张量包含在尽可能多的切片边的生命周期中。理想情况下，时间复杂度和由多个切片引起的切片是负相关的。0PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加拿大陈等03.3切片优化的路径由于受到内存限制，我们必须进行切片并承担一些开销。然而，在多级存储系统中，在某些情况下，计算开销可以转化为数据移动。对于TNC，我们将在以下几个部分中介绍两种处理开销的主要方法，即通过寻找更好的切片集合来减少开销，或者通过堆叠来替代开销。堆叠是切片的逆操作，在低存储或分布式存储的容量足够满足整个内存需求的情况下是可行的。例如，我们可以将第53秩张量存储在硬盘中，在收缩步骤中通过IO获取第30秩切片，然后在计算后将其放回。这个过程通过获取进行切片和通过放置进行堆叠。如果在切片边的生命周期结束后立即进行堆叠，那么该边的开销就被自然地消除了，并且内存需求得到了解决。然而，数据访问（使用低级存储）或通信（用于分布式存储）期间会有大量的数据交换成本。寻找更好的切片集合可以避免内存访问和通信，但它会引入来自冗余计算的开销。选择要依赖于特定的带宽和开销值。在带宽较低且开销较低的情况下，切片优化具有更好的性能，而在带宽较高且开销较高的情况下，堆叠更合适。图7显示了不同目标大小的典型开销分布。数据访问成本通过不同级别的算术强度（AI）转化为相等的开销。相等开销线和存储容量将图分为几个部分。最常见的可手动控制的存储级别包括硬盘、主存储器和LDM（适用于申威架构）。对于内存访问，������������������������������得更有潜力，而相反，应该应用切片优化。这些方法不针对特定的架构。事实上，我们只需要一个多级存储系统。04 切片开销减少04.1 切片优化概述0IO的低带宽限制了堆叠，切片开销直接影响并行可扩展性。如定理1所示，切片的优化可以分为两个步骤：寻找较小的切片集和调整选定的切片集以实现较低的开销。下面的两个小节分别讨论了这两个步骤。0图7.在cotengra中不同存储级别的开销分布。（以Sycamore（�=20）为例，原始内存成本为数十PB。对于申威架构，每个CPE有96GB主存储器和256KB的LDM）0在符合内存绑定的情况下最小化开销描述了一个带约束的优化问题。对于一个收缩树  �  =  ( � � , � � )，目标函数可以通过切片后的总时间复杂度来描述。0� ( �,� )  = ∑�0�  ∈ � � 2 | � �  |+| �  |−| � ∩ � �  | (4)0其中  �  是被切片的边缘的集合，� �  是涉及到在TN中对  �进行收缩的边缘的集合。不超过内存容量的目标大小表示为  � 。对于每个  �  ∈  � � ，  | �  ∩  � � | ≥ | � � | −  �。目标函数和公式结合起来可以确定优化问题。04.2 切片策略0在这里，我们在起点上定义了生命周期[16]，虽然起点的定义有些不同。在这项工作中，起点被定义为收缩树上最计算密集的路径。根据图论，路径上的每个收缩步骤都与其下一步有数据依赖关系。由于大多数分支与内存约束无关，它们被预先收缩，只有起点保留下来进行优化。预处理之后，起点变成一个新的收缩树，我们可以检测到其上每条边的生命周期。假设切片集的最佳大小为  �，则起点被分为两个连续的部分：  �  = � 1  +  � 2 ，并且令 � 1  的最佳大小为  � 1 。对于  � 1，有多个候选集具有相同的大小  � 1 。根据上述讨论，  � 1 的生命周期通过  � 2  的生命周期的张量越多，更新后的  �2中被切片的边缘就越少。严格来说，较长的生命周期不一定会导致更低的切片开销。然而，生命周期的包含关系确实会产生这样的效果。同样，减少内存的效果也是如此。特别是对于收缩树的叶节点，0基于生命周期的模拟量子电路在新的神威超级计算机上的优化 PPoPP ’23, 2023年2月25日-3月1日，加拿大蒙特利尔0收缩树上，只有一个扩展方向，然后它的长度决定了包含关系。因此，我们从起点的两端开始搜索，并每次选择一个张量作为  � 1 ，将剩余部分作为  � 2。因此，具有更长生命周期的边缘更好。如果我们迭代执行这个过程，可以期望得到一个更小的切片集。我们提出了详细的算法1。0算法1  切片查找程序0输入：收缩树的起始点  � , 目标维度  �0�  =  ��� ( � ) ,�  ← � ,��  =  ���� () 对于  �中0计算  ��  [ ����� ]0结束循环0��  =  ( � [ 0 ] .���  <  � [ �  −  1 ] .��� ) ? � [ 0 ]  : 将具有最长生命周期的  �� .���  − �  的索引添加到  � 对于  �  ∈  �  执行0如果  � .���  ≤  �  则0���� ( � )0结束循环0结束循环 �0直到  �  ==  00输出：切片集  �0尽管上述策略并不总是提供最低开销的切片集，有时甚至比contengra找到的切片集更差，但我们已经成功满足了上述定理的所有先决条件。上述方法可以找到一个尽可能小的切片集，针对给定的收缩树。结合路径搜索的动态过程，开销可能会降低。然后，细化器将找到一个更好的切片集来减少开销。04.3 基于模拟退火的切片细化我们的切片查找程序不能保证找到最优的切片集，它会寻找一个尽可能小的切片集。因此，本节的主要任务是在给定一定数量的切片边缘的情况下找到最佳的切片集。考虑到切片集的大小是固定的，从前者到后者的排列可以描述为边缘替换。在切片后，有一些张量的维度恰好等于目标维度，它们被称为“关键张量”。如果一个切片边缘的生命周期不包含任何关键张量，那么这个边缘对于内存减少没有贡献，可以从切片集中移除。此外，从另一个角度来看，要用索引  �替换一个切片边缘，一种直接的方法是找到另一个未切片的索引  � ，其生命周期包含了  �的生命周期中的所有关键张量。0贪心地简单替换索引有时会导致局部最小值。例如，最优集包含索引  �  和索引  � ，而我们找到的集合却包含  � 和 � ，但是从  �  中替换  �可能会增加开销，或者无法满足内存约束。穷举搜索或动态规划将导致最优解，但会遇到搜索空间组合爆炸的问题。然后，随机算法成为在时间和搜索质量之间平衡的选择。模拟退火在避免局部最小值的同时忍受临时的复杂度增加，并提供了实际的速度，如算法2所示。0算法2  切片细化程序0输入：目标维度  � ，切片集  � ，收缩树  � ，最终温度  ��，参数  � 初始化温度  � 对于  �  中的每个边缘索引执行0计算  ��  [ ����� ]0结束循环0从  � �  中随机选择  �����0将  �����  替换为  ��� 计算时间复杂度  � ��� ,� ���如果  � ���  <  � ���  则0更新  �0否则0用概率更新  �  为  � = ��� (( � ���  − � ��� )/ � ��� / � )0结束循环0结束循环0直到  �  <  ��0输出：切片集  �05 通过二级切片设计融合05.1 线程级优化的困难对于线程级别，如果将整个路径组织在CPE上，考虑到256KB的LDM，将会有很大的开销。因此，之前的工作采用逐步优化线程级别的方法[17][6]来避免这种情况，转而将重点放在内存访问上，而不是冗余计算。然而，频繁的内存访问也大大限制了FLOPs的效率。张量之间的收缩是通过矩阵乘法实现的[17]。基于这个策略，对于类似方阵的矩阵，可以获得超过70%的峰值性能。然而，对于窄矩阵乘法，特别是当 �,�,�中有两个小于16时，这在许多仿真任务中占主导地位[1]，我们可以0PPoPP ’23, 2023年2月25日-3月1日，加拿大蒙特利尔 Chen等人0通过易于推断出  Θ ( ��� ) ≈  Θ ( ��  +  ��  +  �� )，使得GEMM从一个计算强度问题变成了带宽受限问题。另一个约束来自于每个CPE上的256KBLDM，它只能容纳一个秩为13的张量进行乘法运算。然后，用一个秩为31的张量进行收缩至少需要212次低效率的GEMM计算。为了充分利用512位单指令多数据（SIMD），应用了一个4×4复数GEMM内核。当�,�都小于4时，数据长度的需求会导致高性能内核和2D数据分布之间的冲突。相比之下，1D分布避免了大部分填充，并将GEMM过程切分为简单的并行子任务。最重要的是，数据分布中的隐式切片作为克服LDM内存限制的方法，与在进程级别上切片的问题类似。我们提出了一种更高效的基于生命周期的切片堆叠策略，可以大大减少数据移动的成本。对于线程级别，它被命名为二级切片（第一次切片发生在进程级别）。在LDM和主内存之间进行二级切片将提供一个融合的运算符，用于组织CPE上的部分收缩路径，并大大节省内存访问成本。05.2 切片堆栈设计0如果我们在整个收缩路径上进行切割，一个子任务可以在一个进程上执行，无需中间通信和IO，同时具有计算开销。相反，如果我们接受通信或内存访问，则可以避免计算开销。这种策略在进程级别上不起作用，因为IO的带宽很低，计算开销也很低，但在LDM和主存储器之间可用。由于新的神威超级计算机上的LDM仅适用于13阶张量，如果按步骤执行收缩，我们应该经常在每两个步骤之间进行DMA-get和DMA-put。考虑到上述的算术强度，内存访问将是主导因素。为了减少LDM和主存储器之间频繁的数据交换，我们在一个计算核心中连续执行�个收缩路径的计算步骤有助于降低。在这些步骤的开始，我们只需要进行一次DMA-get来获取更大的张量，在经过n个计算步骤后，结果将通过DMA-put写回。然后，减少了�−1次DMA-get和DMA-put。如图8的顶部所示，CPE可以从主存储器中的一个张量中获取一个较低的秩张量，丢弃一些维度。在特定的收缩中，通常有一些维度05.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。对于�，显然，前3个维度将不参与置换，因此只需要一个1/8的映射即可。对于�，置换期间的最后4个维度是相同的，因此由4,5,6,7形成的4个元素的邻接性将被保持，并且映射的大小减小到1/16。通过偏移量，可以通过���[�+�]=���[�]+�*����当�<������时计算对应的映射。0基于生命周期的优化：在新的神威超级计算机上模拟量子电路PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏陈等。0图8.线程级优化的融合设计。顶部显示了以前工作中的逐步策略，底部是融合设计。我们的策略在LDM上组织了一个子路径，并为长度为�的子路径减少了�−1次DMA-get和DMA-put。上标�表示置换，张量的下标表示切割的维度。0图9.二级切片的示例。有5条边的生命周期贯穿整个路径。在切割这些边之后，最大的内存需求从28减少到23，并生成25个用于线程级并行的子任务。每个核心中只执行虚线框内的计算，并且内存访问发生在计算的开始和结束时。�(1)与预计算映射相同。空间复杂度将减少到�(�/2�)，其m是在末尾或开头的连续索引的数量。05.3.2通过通信消除离散内存访问。尽管融合策略大大减少了DMA，但DMA的效率成为一个障碍。由于我们从原始张量中切割了一些边，我们需要的子张量通常是离散分布在中的。0主存储器。如果我们想要获取一个没有最后一个索引的子张量（假设它已经被切割），那么我们所需要的元素之间将会有一个空间间隔。结果，DMA的粒度将非常小，这会损害带宽。在实践中，切割边在不同位置上是分散的。在这种情况下，DMA的带宽只能达到峰值性能的不到0.1%，导致负优化。为了提高带宽，64个CPE的合作变得至关重要。在我们的并行框架下，最后的6个切割索引在64个CPE之间组织。通过远程内存访问（RMA），CPE之间的数据交换更快，其峰值性能可以达到每秒800GB。然后，我们将64个CPE的子张量视为一个整体，让每个CPE连续访问内存。这种策略保证了DMA的基本粒度为512B，提供了超过峰值性能的50%以上。在内存访问之后，我们使用RMA重新排列CPE之间的数据。我们还应用了额外的置换来提高RMA的粒度并确保效率。对于其他体系结构，我们可以通过简单地划分通信组来实现这种策略。0PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏陈等。06 结果0相关工作（例如Cotengra[12]、Alibaba[16]和[6]）都对SycamoreRQC[1]进行了模拟。为了进行适当的比较，除非另有说明，本文中使用的缩减树也来自Sycamore的张量网络。06.1 切片开销和扩展结果0图10.与cotengra相比的分割大小和开销。红点表示cotengra与我们相比的额外分割边的数量；绿点表示开销的比率。当差异为0且比率为100%时，两种方法的性能相同。0根据第4节中的切片策略，给定一个收缩路径，我们可以找到一个期望开销较低的切片集。图10显示了我们的工作与cotengra的比较。我们通过cotengra找到了400个收缩路径，并分别使用我们的方法和cotengra来寻找切片集。与cotengra相比，我们找到的切片集可能更小，从而导致更低的开销。对于每个路径，我们的策略在98%以上的情况下表现更好。至于几个异常情况，我们观察到的现象是路径的计算密集区域是分散的。而且，由于SA是一种随机方法，无法保证找到最优解。我们找到的最佳开销结果小于1.05，并且我们全面选择了一个复杂度较低的路径进行线程级优化。由于切片，进程之间高度独立，只在程序结束时进行一次全局归约。强扩展结果和弱扩展结果如图11所示。0图11.（总共65536个子任务的强扩展结果和每个节点上的16个子任务的弱扩展结果。0图12.线程级别的二次切片优化。在一个拥有390个核心的单个节点上进行优化，并针对收缩路径上的不同大小测试性能。使用逐步策略进行比较。 6.2 计算效率图12显示了我们的工作能够显著提高计算效率。使用1024个节点，可以在10098.5秒内生成完美样本或1M个相关样本。考虑到扩展结果，我们预计使用107520个节点（41932800个核心）可以将整个时间成本降低到96.1秒。可持续单精度性能预计为308.6Pflops。根据图12，通过二次切片大大减少了内存访问的时间，置换和GEMM的时间保持相似。这个结果验证了我们的预测，即通过二次切片，可以减少内存访问的时间，但需要一些基于Python的预处理，只需要1个核心和可忽略的时间。另一个结论是，在某些情况下，经过二次切片后，计算核心从内存密集型变为计算密集型。根据Roofline模型[ 18]和神威体系结构的算术强度，浮点运算数量应超过内存访问字节数的42.3倍才能达到峰值性能。我们的策略的平均融合步骤约为10，对于平均为4的小 � ， ��� /( �� + �� + �� ) ≈  �，因此在某些情况下，TNC的算术强度可以突破42.3。图13显示了线程级别上特定情况的屋顶线模型。由于置换中包含LDM访问，我们的性能与峰值性能之间仍存在差距。然而，与原始的算术强度2 . 6（混合精度）和1 .22（单精度）相比，优化限制大大提高了。0基于生命周期的优化在新的神威超级计算机上模拟量子电路 PPoPP ‘23，2023年2月25日至3月1日，加拿大蒙特利尔，魏琛等。07. 含义在本文中，我们提出了基于生命周期的新方法，以减少切片开销并提高在进程层和线程层进行并行优化的计算效率。由于引入了“生命周期”定义，一系列基于“生命周期”的引理和定理加强了我们对张量网络和收缩树的认识，然后提出了一种可解释的方法来处理切片开销，并提出了一种原地切片策略来找到最小的切片集合，从而减少切片开销。我们的原地策略可以独立工作，也可以优化动态方法找到的切片集合。因此，在寻找切片集合时，它成为一种通用的后处理方法。此外，基于“生命周期”，我们采用了堆叠方法来避免冗余计算带来的重负载，并将其推广到任意多级存储系统。切片优化和堆叠填补了空白。0图13.我们工作的屋顶线模型。对于不同的情况，算术强度与10 � 到 40 �不同。在某些情况下，问题变成了计算密集型。0致谢0TNC的两种主要策略。然后，我们设计了一种基于算术强度的判别式，以选择不同存储层次上的策略。对于神威架构，我们在线程级别上应用它。通过DMA实现更经济的内存访问和通过RMA实现CG之间更快的通信的必要代价。最令人鼓舞的结果是，在某些情况下，计算核心从内存密集型变为计算密集型，这改变了我们对问题的理解。作为一种广泛应用的方法，张量网络可以在统计物理学[21 ]、数据科学[ 22 ]、社会学[ 23]等许多研究领域中找到。物理学中的一系列问题可以简化为TNC。对于大规模的TNC，极端的时间和空间复杂性成为主要困难。将巨大的内存需求转化为可解决的数据流，切片在这些TNC过程中起到了重要的作用。除了TNC之外，如果我们需要处理一系列具有数据依赖性的大规模矩阵乘法，切片仍然可以用于任务分配。本工作证明了生命周期对于量子电路的张量网络来说是具有潜力的。此外，凭借简单的定义，生命周期可以轻松推广到具有不同特征的张量工作，并帮助分析收缩的时间复杂性和空间复杂性。可以预见，生命周期在更多领域中将发挥重要作用。0参考文献0我们要感谢王振、孙照奇、李泽刚和李玉轩的建议和讨论。本工作部分得到了中国国家重点研发计划（2020YFB0204804，2020YFB0204800），中国国家自然科学基金（批准号T2125006、U1839206，项目号62102114），江苏省创新能力建设计划（项目号BM2022028）和浙江实验室重点研究项目（项目号2021PB0AC01）的支持。通讯作者是刘勇、刘欣、甘林、陈德勋和杨光文。0[1]  F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R.Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell,等，“利用可编程超导处理器实现量子霸权，”《自然》，第574卷，第7779期，第505-510页，2019年。0[2]  J. Wells, B. Bland, J. Nichols, J. Hack, F. Foertter, G. Hagen, T.Maier, M. Ashfaq, B. Messer, and S.Parete-Koon，“宣布超级计算峰会，” 6 2016。0[3]  H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng,Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu,等，“利用光子进行量子计算优势，”《科学》，第370卷，第6523期，第1460-1463页，2020年。0[4]  A. Zlokapa, S.