基于稀疏四叉树的块和任务并行稀疏矩阵库

软件X 19（2022）101159原始软件出版物Chunks and Tasks Matrix库伊曼纽尔·H放大图片创作者：John W. 阿尔捷莫夫科学计算司，信息技术系，乌普萨拉大学，Box 337，SE-751 05乌普萨拉，瑞典ar t i cl e i nf o文章历史记录：2021年10月24日收到收到修订版，2022年4月23日接受，2022年保留字：块和任务编程模型四叉树稀疏矩阵的分解基于任务的编程a b st ra ct我们提出了一个C++的头只并行稀疏矩阵库，基于稀疏四叉树表示的矩阵使用的块和任务编程模型。该库实现了许多用于分布式内存并行化的稀疏矩阵算法，这些算法能够动态地利用数据局部性来避免数据移动。这是证明的块稀疏矩阵矩阵乘法应用于三个序列的矩阵具有不同的非零结构的例子，使用CHT-MPI 2.0运行时库实现的块和任务模型。运行时库成功地动态负载平衡计算，而不管稀疏结构。版权所有©2022作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本2.1用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-21-00207Code Ocean compute capsule不适用合法代码许可证修改BSD使用git的代码版本控制系统使用C++的软件代码语言、工具和服务、Chunks和Tasks（http://chunks-and-tasks.org）、BLAS编译要求、操作环境依赖性Linux/MacOS/其他类Unix系统如果可用，链接到开发人员文档/手册chunks-and-tasks.org问题支持电子邮件info@chunks-and-tasks.org1. 动机和意义计算两个矩阵的乘积是科学计算中最基本的运算之一[1]。Matrix–matrix multiplication is a core operation in for examplecombinatorics [其他常用的线性代数运算，如线性求解，矩阵求逆和因子分解，在高效的分块实现中被简化为在稠密矩阵的情况下，有效的软件通常使用基本线性代数子程序（BLAS）。这使得代码可移植，并在链接到优化的BLAS库时提供高性能。稠密线性代数问题的并行化方案通常基于数据的静态分布，例如矩阵到二维过程网格上的二维块和块循环映射，例如用于并行矩阵-矩阵的SUMMA算法中*通讯作者。电子邮件地址：emanuel. it.uu.se（Emanuel H. Rubensson）。https://doi.org/10.1016/j.softx.2022.101159乘法[7]和HPLinpack基准的HPL实现[8]。由于矩阵是密集的，所有的计算和通信成本都是事先已知的，并且通常可以使用相同的方案，而不管应用如何，因为唯一可能变化的参数是矩阵维度。另一方面，利用并行稀疏矩阵-矩阵乘法的软件这种实现可以在许多电子结构代码中找到[9，10]。虽然通常可以实现很好的性能，但缺少通用算法和库的好处并行稀疏矩阵-矩阵乘法的一类通用算法在随机置换后，应用了一些稠密矩阵的方法，但用稀疏乘积代替了局部块乘积。这给出了一种普遍适用2352-7110/©2022作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx伊曼纽尔·H放大图片创作者：John W.阿尔捷莫夫软件X 19（2022）1011592×≥而不需要关于稀疏模式的先验信息，但你必须付出的代价是非零结构和任何数据局部性被破坏。这种无法利用输入矩阵结构的情况对通信成本产生了严重的后果[14]。在没有关于稀疏模式的先验信息并且不影响性能的情况下，必须在计算期间动态地完成工作和数据到物理资源的映射直接在标准消息传递接口（MPI）之上开发此类方案是一项艰巨的任务。这就是为什么人们无法将算法和软件的性能和可移植性结合起来的原因。使用某种任务并行框架似乎是一种可行的方法。然而，大多数任务并行框架主要是为共享内存开发的，并且当扩展到具有分布式内存的计算机集群时，通常采用静态分布或集中式数据管理。我们在这里提出的块和任务矩阵库，可用于实现算法，不作出假设的输入矩阵的结构，但有效地利用数据的局部性时可用。开发这个库的关键是它使用了Chunks and Tasks编程模型[15]，该模型提供了工作和数据的抽象，因此使得局部感知并行稀疏矩阵算法的实现变得可行。该库是用C++编写的，可以用于并行化C++程序的性能关键矩阵操作，也可以作为成熟的Chunks and Tasks应用程序的一部分。Chunks and Tasks Matrix Library在开发、实现和分析用于分布式存储系统的许多新型并行稀疏矩阵算法中不可或缺，包括有效利用非零矩阵项局部性的通用并行稀疏矩阵-矩阵乘法[ 14 ]、具有衰减的矩阵的稀疏近似矩阵-矩阵乘法[ 16，17 ]、局部逆因子分解[ 18，19 ]、用于对称正定矩阵逆因子分解的新的2. 软件描述Chunks and Tasks Matrix Library是一个C++ Header Only库，使用Chunks and Tasks编程模型实现。要在C++程序中使用该库，您需要一个Chunks and Tasks运行时库和基本线性代数子程序（BLAS）的实现[21]。开源Chunks和Tasks库实现可在www.example.com上公开获得chunks-and-tasks.org。在这个网站上，你还可以找到示例程序，展示如何使用Chunks andTasks Matrix Library，以及如何使用Chunks and Tasks MatrixLibrary以及不同的Chunks and Tasks运行时库实现来编译和运行程序的分步描述在Chunks and Tasks Matrix Library中，矩阵使用稀疏四叉树（quadtree）表示[22]。在这种表示中，矩阵是1）相同为零，2）使用小矩阵的数据结构存储，或3）分裂成四个象限，每个象限由稀疏四叉树递归表示的子矩阵。矩阵运算被表述为遍历矩阵四叉树的非零分支的递归算法四叉树提供了一种有效的方法，可以从表示中挤出零条目，并暴露数据和工作中的并行性。四叉树稀疏矩阵表示可以看作是矩阵分裂为x的层次稀疏矩阵表示的特殊情况x， x在层次结构中的每个级别上有2个子矩阵，例如在[23，24]中使用。在我们继续描述块和任务矩阵之前，库中，我们将简要地描述块和任务编程模型.关于更完整的解释，我们参考[15]。2.1. 块和任务编程模型在Chunks and Tasks编程模型中，程序由任务的注册驱动。Chunks and Tasks运行时库在物理资源上调度任务。在这个意义上，Chunks and Tasks模型与其他基于任务的并行编程模型类似。这个模型的突出之处在于，它还包括数据的抽象。数据的基本抽象是块的概念。块类型指定要存储的数据的类型以及运行时库可以用来打包/解包该类型的块对象的序列化函数。用户可以通过使其他组块成为组块子组块来将它们附加到组块。通过这种方式，可以构造块层次结构，这是可伸缩并行化的重要构造。与任务注册类似，用户注册块以进行存储。运行时库负责将数据（块）映射到物理资源。[15]中讨论了与其他提供数据一个任务接受多个块作为输入，并生成一个输出块。任务注册返回一个标识符，该标识符可以用作其他任务的输入，以这种方式指定任务之间的依赖性。因此，在任务注册时，to tasks被指定为块或任务的标识符两个工作输入和输出可以是特殊的CHUNK_ID_NULL标识符。如果任务输入标识符是CHUNK_ID_NULL，则库将调用应用程序员提供的回退任务执行函数，指定在这种情况下要做什么。例如在 在矩阵库的情况下，CHUNK_ID_NULL可用于指代全零矩阵，以避免存储和操作零数据。然后，零和非零矩阵之间的加法任务应该简单地返回非零矩阵，如应用程序员在回退任务执行函数中指定的那样这样的技术可以用于构造稀疏分层数据结构并对其进行操作，如将在以下部分中进一步描述的。在本文的数值实验中，我们将使用CHT-MPI 2.0实现的Chunks 和 Tasks C++ 编 程 接 口 。 CHT-MPI 2.0 Chunks andTasks 列 表 使 用 MPI 和 POSIX 线 程 实 现 ， 可 在 chunks-and-tasks.org上公开获取。CHT-MPI 2.0运行时库的一些重要特性将在第3节中描述。该库也在[15]中与模型一起详细描述。2.2. 软件构架Chunks and Tasks Matrix Library的主要组成部分如下：矩阵块模板使用块和任务模型实现矩阵的稀疏四叉树表示，使用块和任务模型实现在稀疏四叉树上操作的各种递归算法的多个任务模板用于叶矩阵表示的三个独立矩阵库。用于四叉树矩阵表示的块模板用叶矩阵类型参数化，用于叶节点处的矩阵表示。此叶矩阵类型可能是也可能不是与块和任务矩阵库一起分发的类型之一，并且可能使用稀疏或密集表示。四叉树中的非叶每个子块由其块标识符引用，并且表示与该非叶节点相对应的矩阵A块，···伊曼纽尔·H放大图片创作者：John W.阿尔捷莫夫软件X 19（2022）1011593× × × × ××+•×+•×•×+表1用于设置弱标度实验的参数，如文中所述。Tflop值是指每个稀疏矩阵-矩阵乘法所需的浮点运算的万亿次弱标度实验装置矩阵尺寸10521054105810 51 610 6 3 21066410 6工作进程数CHUNK_ID_NULL标识符用于引用完全为零的子矩阵。矩阵操作的任务模板也使用叶矩阵类型进行参数化。每个任务实现中的关键组件是由运行时库调用的执行函数，以执行任务执行。此函数在四叉树的单个级别上执行操作。对于非叶输入，执行函数通常注册在输入块的子块上操作的任务。在叶级，调用对应于给定任务类型的叶矩阵功能。矩阵稀疏性，即四叉树中的零分支，在回退执行函数中处理，每当输入矩阵块标识符之一为CHUNK_ID_NULL时，由块和任务运行时列表调用。三种独立的叶基质类型分布在库，每个库都位于一个具有以下名称的数据库中：basic_matrix_lib：使用矩阵元素的标准列式布局的密集矩阵表示[15]。block_sparse_matrix_lib：块稀疏矩阵表示，其中均匀大小的子矩阵（块）以二维数组布局[14]。 零子矩阵既不存储也不引用。hierarchical_block_sparse_lib：稀疏四叉树矩阵表示，类似于块和任务级别的实现[16]。四叉树块模板描述了一种适合于矩阵并行分布的数据结构，但没有指定数据应该存储在矩阵操作的任务模板描述了适合并行执行的递归算法与库一起分发的叶矩阵列表是串行的，除非链接到BLAS的线程实现。当库与块和任务模型的并行实现一起使用时，可以实现并行性2.3. 软件功能块和任务矩阵库中的任务模板提供的主要功能与叶矩阵类型相结合，可以分类如下：矩阵元素的分配和提取：任务类型从具有行和列索引的向量和值构造矩阵，以及提取由具有行和列索引的向量指定的矩阵的元素的任务类型。矩阵加法：加法任务类型，包括常规矩阵加法和矩阵与缩放单位矩阵的加法。Matrix–matrix multiplication逆因子分解：对称正定矩阵的逆因子分解的任务类型，包括逆Cholesky和局部逆因子分解。截断：用于删除具有不同错误控制变体的小矩阵元素的任务类型。所有任务类型都能够处理和利用矩阵稀疏性。这个功能列表反映了这样一个事实，即开发库的主要动机是将其应用于大规模电子结构计算。该库还包括许多此处未列出的辅助任务模板3. 说明性实例在本节中，我们将使用一般稀疏矩阵-矩阵乘法作为示例，说明本文前面概述的库的功能。我们构造了一系列不断增长的矩阵，对于每个序列中的每个矩阵，计算矩阵与自身的乘积对于每个序列，设置为使得乘积所需的浮点运算的数量与矩阵维度成比例。用矩阵维数扩大计算资源给出了每个序列的弱缩放实验。三个矩阵序列构造如下：带状：带宽为2 3000 1的带状矩阵。增长块：带状矩阵，同样具有带宽2 3000 1，但在左上角添加了一个大的密集块。块的大小被选择为使得与带状矩阵相比，用于矩阵乘法的浮点乘法的总数这给出了随着矩阵大小而增长的块大小。随机块：带状矩阵，同样具有带宽2 30001，但是具有沿着主对角线放置在随机位置处的多个密度相等大小的块，没有重叠。块的数目与矩阵维数成比例。选择块的大小，使得与带状矩阵相比，矩阵乘法的浮点乘法随着矩阵大小的增加，块大小基本上保持不变在所有三个实验中使用相同的矩阵维度集。表1中给出了具有矩阵大小、块大小等的实验设置。所有实验都是在斯德哥尔摩KTH皇家理工学院PDC高性能计算中心的Beskow集群上进行的，使用了Chunks和········带状特弗洛7.02214.2228.6357.44115.1230.3460.8生长块大小的块15716196522462130899388254882861446特弗洛14.0428.4557.26114.9230.1460.6921.6随机区组区块大小15716157051570015697156961569515695区块数1248163264特弗洛14.0428.4557.26114.9230.1460.6921.6伊曼纽尔·H放大图片创作者：John W.阿尔捷莫夫软件X 19（2022）1011594××Fig. 1. 使用Chunks and Tasks Matrix Library执行稀疏小组（a）：墙时间。 图（b）：效率被测量为每秒实现的浮点操作与所采用的计算节点的理论峰值性能之间的比率。面板（c）：每个工人流程收到的数据。在图（d）和（e）中，实线显示平均值在四次测试运行中，虚线示出了最小值和最大值。在图（f）中，不仅取平均值、最小值和最大值，在四个测试运行上，而且在所有工作进程上。虚线显示了随机置换和稀疏SUMMA算法对每个测试用例所带来任务库CHT-MPI 2.0，可在chunks-and- www.example.com上公开获取tasks.org。Beskow是一个Cray XC40系统，具有2060个基于Intel Haswell和Broadwell处理器的计算节点，以及一个Cray Aries与Dragonfly拓扑的互连。本研究使用Haswell节点，每个节点配备两个16核Intel Xeon E5-2698 v3 2.3 GHz CPU和64 GB内存。每个计算节点的理论峰值性能约为1280 Gflop/s [16]。CHT-MPI 2.0库使用消息传递接口（MPI）进行节点之间的通信代码使用GCC 9.3.0和Cray MPICH7.7.14. 在CHT-MPI 2.0中，MPI父进程运行主程序，并产生许多执行任务的MPI工作进程该程序被配置为每个节点使用1个工作进程，每个工作进程使用31个工作线程来执行任务。因此，每个节点一个核心留给线程处理与其他节点的通信。每个CHT-MPI 2.0工作进程的块缓存大小设置为4GB。叶矩阵维度设置为2048 2048。 叶矩阵表示使用块稀疏矩阵库与 叶内 部块 大 小64 - 64 和 矩阵 元素 存 储在 双 精度 。 单线 程OpenBLAS 0.3.10 [25]用于对块稀疏叶矩阵库中的子矩阵进行BLAS操作。输入矩阵被构造成分布在工作进程上。图图1（a）示出了三个测试用例的作为工作进程数量的函数的壁时间。该图显示了4次重复测试运行的平均、最小和最大壁时间。该实验证实了带状矩阵的先前理论和实验结果，显示壁时间随节点数的增加而增加[14]。我们可以得出结论，在非零结构不均匀的其他两种情况下，库也成功地动态平衡了负载。虽然标量操作的数量是带状矩阵测试用例的两倍，但壁时间明显小于带状矩阵测试用例的壁时间的两倍。一个可能的解释是，大的添加块给出了具有更大算术强度的计算，即，每个非零元素有在同一块上操作的任务很可能由同一个工作进程执行。请注意，CHT-MPI 2.0利用了工作进程之间的工作窃取，这些工作进程具有基于广度优先策略从任务树中选择的窃取任务。“增长块”和“随机块”测试用例的更高效率也可以在图中看到。1（b）显示效率测量为每秒浮点运算次数与所用计算节点的理论峰值性能之间的比率。注意，矩阵库动态地平衡工作负载，同时利用非零结构中的局部性来减少通信。该库不使用关于矩阵的非零结构的先验信息。图1（c）显示了以下列数额衡量的通信：在乘法期间每个过程接收的数据。该图显示了所有过程和四次重复测试运行的平均值。最大（最小）值取为所有过程和四次重复测试运行的最大（最小）值。作为参考，我们提到带状测试用例中的最大矩阵具有约38亿个非零元素，对应于双精度浮点表示的307 GB内存。伊曼纽尔·H放大图片创作者：John W.阿尔捷莫夫软件X 19（2022）1011595⌈⌉理论表明，O（（二）通信成本占主导地位√√√√在图1（c）中，我们还包括了三个测试用例中的每一个的随机置换和稀疏SUMMA算法的替代方法的理论通信成本的比较。这种方法已被用于例如组合BLAS [26]和CP2K [27]。每个进程接收的矩阵元素的数量使用公式2n/ p计算，其中n是非零矩阵元素的总数，p是工作进程的数量[13]。使用该公式，假设随机置换成功地对数据进行了完美的负载平衡。请注意，该图展示了已知的结果，显示了在这种弱缩放场景中带宽成本随O（p）增加。特别是，数值模拟实验已经证实了具有或多或少稀疏性的矩阵的壁时间[14，27]。 这与Chunks andTasks Matrix Library中使用的四叉树方法形成对比，在Chunksand Tasks Matrix Library中，壁时间由沿着关键路径的任务执行控制，其规模为O（（logp）2）[14]。后来的发展利用三维（3D）过程网格，而不是稀疏SUMMA算法[11，28原则上如果使用3D网格，O（p）缩放最终应该被打破。不幸的是，这不会发生，直到非常大量的进程，其中初始的O（p）缩放已经导致非常高的通信成本。为了最小化带宽成本，沿第三维的进程数应选择为：p/m2 其中m是非零条目的平均数每一行[28]。对于这里考虑的三个测试用例中的每一个，这样的选择使得3D算法在超过3600万个工作进程的情况下有效地与2D稀疏SUMMA算法4. 影响Chunks and Tasks Matrix Library已经为分布式内存并行化开发了许多稀疏矩阵算法，如第1节所述，并在第2节中进一步描述。这些算法的共同点是能够动态地利用数据局部性来避免数据移动，如第3节中稀疏它们也有一个共同点，即它们是大规模电子结构计算中性能最关键的稀疏矩阵运算。特别地，矩阵-矩阵乘法的不同变体已经在用于电子结构计算的方法和软件的开发者中受到充分关注。Chunks and Tasks Matrix Library实现了并行稀疏矩阵-矩阵乘法的任务类型然而，块和任务矩阵库最重要的贡献可能是它展示了使上述成就成为可能的新技术块和任务矩阵库代表了稀疏矩阵操作并行化这种转变意味着应用程序的部署者和运行时库之间的职责分工发生了变化对于任何并行编程模型，这种职责划分基本上由与模型相关联的库或语言的编程接口定义。使用Chunks and Tasks编程模型的应用程序程序员担心将数据和工作中的并行性暴露给运行时库，但不担心将这种并行性映射到物理资源。这意味着应用程序员不必明确考虑数据应该存储在哪里，哪个进程应该执行特定的任务，同步或通信。与此同时，我们已经看到，该模型具有足够的表现力，来描述复杂的并行数据结构和算法。的模型对访问用户代码中的数据施加了某些限制特别是，CHT-MPI2.0实现使用完全分散的工作和数据管理，这对于由运行时处理数据分发的模型来说是不典型的。Chunks and Tasks编程模型的这些属性都被Chunks and Tasks Matrix Library继承，并使该库成为并行稀疏矩阵运算开发和实现的潜在游戏规则改变者。Chunks and Tasks Matrix Library是在修改后的BSD许可证下发布的，可在chunks-and-tasks.org上公开下载。5. 结论我们提出了Chunks and Tasks Matrix Library，它是一个基于Chunks and Tasks编程模型和矩阵稀疏四叉树表示的稀疏矩阵库。四叉树表示的优点是稀疏矩阵的大零块可以在高级别上跳过，从而在具有数据局部性的情况下提高可扩展性。该库提供了一组方便的例程，用于在分布式环境中处理大型稀疏矩阵，主要关注乘法繁重的算法，这在电子结构计算中很常见该库的未来工作和扩展包括稀疏矩阵-矩阵乘法算法的继续开发竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢这项工作得到了瑞典国家战略电子科学研究计划（ESSENCE）的支持。计算资源由斯德哥尔摩KTH皇家理工学院PDC高性能计算中心的瑞典国家计算基础设施（SNIC）引用[1]高军，季伟，谭志，赵勇.一般稀疏矩阵-矩阵乘法的系统综述。2020，ArXiv电子打印，arXiv：2002.11273。[2]戴维斯TA。算法1000：SuiteSparse：GraphBLAS：稀疏线性代数语言中的图 形 算 法 。 ACMTransMathSoftware2019;45 （ 4 ） .http://dx.doi.org/10.1145/3322125网站。[3]Chetlur S，Woolley C，Vandermersch P，Cohen J，Tran J，Catanzaro B，etcuDNN ： 深 度 学 习 的 高 效 原 语 。 2014 年 ， ArXiv 电 子 打 印 arXiv ：1410.0759。[4]作者：Bowler DR，Miyazaki T.电子结构计算中的O（N）方法。Rep ProgrPhys 2012;75：036503.[5][10]李文，李文.使用图形处理单元和混合精度矩阵乘法库加速相关量子化学计算。J Chem Theory Comput 2010;6（1）：135-44. http://dx.doi.org/10的网站。1021/ct900543q，PMID：26614326。[6] Elmroth E，Gustavson F，Jonsson I，Kågström B.稠密矩阵库软件的递归分 块 算 法 和 混 合 数 据 结 构 SIAM Rev 2004;46 （ 1 ） ： 3-45 。http://dx.doi.org/10.1137/S0036144503428693网站。[7]Van De Geijn RA，Watts J. SUMMA：可扩展通用矩阵乘法算法。ConcurrPract Ex1997;9（4）：255-74.[8]HPL算法2020，[在线]，http://www.netlib.org/benchmark/hpl/algorithm.html[2020 年 11 月 20 日 访问]]。伊曼纽尔·H放大图片创作者：John W.阿尔捷莫夫软件X 19（2022）1011596[9] Hine NDM，Haynes PD，Mostofi AA，Payne MC。Al2O3中带电点缺陷的线性标度密度泛函模拟。J Chem Phys2010;133（11）：114111.[10]Weber V， Laino T， Pozdneev A， va IF ，Curioni A.半 经验 分 子动 力学（ SEMD） I：基 于中点 的并行稀 疏矩阵-矩阵乘法 算法。 J Chem TheoryComput2015;11（7）：3145-52.[11]Azad A，Ballard G，Bulupla A，Demmel J，Grigori L，Schwartz O，et al.Exploitingmultiplelevelsofparallelisminsparsematrix-matrixmultiplication.SIAMJSciComput2016;38 （ 6 ） ： C624-51 。http://dx.doi.org/10.1137/15M104253X.[12]Borštnik U，VandeVondele J，Weber V，Hutter J.稀疏矩阵乘法：分布式块压缩稀疏行库。并行计算2014;40（5-6）：47-58.[13]布卢什一、吉尔伯特Jr.平行稀疏矩阵-矩阵乘法和索引：实现和实验。SIAM J Sci Comput2012;34（4）：C170-91。[14]放大图片作者：John E.使用块和任务编程模型的局部感知并行块-稀疏矩阵-矩阵乘法。并行计算2016;57：87-106.[15]放大图片作者：John E.块与任务：动态算法并行化的编程模型。并行计算2014;40：328-43. http://dx.doi.org/10.1016/j.parco.2013.09.006网站。[16]Artemov AG.基于任务的全递归分布式并行框架中近似稀疏矩阵的乘法运算。2019年，ArXiv电子打印arXiv：1906.08148。[17]Artemov AG，Rubensson EH.稀疏近似矩阵-矩阵乘法用于误差控制的密度矩阵纯化。JComputPhys2021;438：110354.http://dx.doi.org/10.1016/j.jcp.2021.110354网站。[18]吴 晓 松 ， 李 晓 松 . 局 部 逆 分 解 。 IMA J Numer Anal 2020;41 ： 729-63.http://dx.doi.org/10的网站。1093/imanum/drz075.[19]放大图片Artemov AG，Rudberg E，Rubensson EH.使用块和任务编程模型对逆因式分解进行分解和可伸缩性分析。并行计算2019;89：102548。[20]杨志华，王志华，王志华.在分布式计算机系统上具有误差控制的密度矩阵的有效计算。2019年，ArXiv电子打印arXiv：1909.12533。[21]Dongarra JJ，Du Croz J，Hammarling S，Duff IS.一组3级基本线性代数子程序。ACMTransMathSoftware1990;16（1）：1-17.http://dx.doi.org/10.1145/77626.79170网站。[22]聪 明 的 DS 。 将 矩 阵 表 示 为 并 行 处 理 器 的 四 叉 树 ： 扩 展 抽 象 。 SIGSAMBull1984;18（3）：24-5.[23]Rubensson EH ， Rudberg E ， Sainteek P. A hierarchic sparse matrixdatastructureforlarge-scaleHartree-Fock/Kohn-Shamcalculations.JComputChem2007;28（16）：2531-7.[24]张文辉，王文辉，王文辉. GPU上高效分层稀疏矩阵运算的动态调度。上一篇：国际超级计算机会议论文集ICS'1 7 ， 纽 约 ， 美 国 ： 计 算 机 协 会 ;2 0 1 7 年 。[25]先义Z优化的BLAS库。2020年，[在线] http://www.openblas。net/[2020年10月27日查阅]。[26]Bulupla，Gilbert Jr.组合BLAS：设计，实现和应用。Int J High Perform C2011;25（4）：496[27] VandeVondele J，Borštnik U，Hutter J.凝聚相中数百万原子的J ChemTheory Comput 2012;8（10）：3565http://dx.doi.org/10.1021/ct200897x网站。[28]Ballard G，Buluyana A，Demmel J，Grigori L，Lipshitz B，Schwartz O，et al. 稀疏随机矩阵的通信最优并行乘法。在：第二十五届年度ACM研讨会上的并行算法和架构的会议记录。SPAA '13，New York，NY，USA：ACM;2013，p. 222比31[29]Azad A ， Selvitopi O ， Hussain MT ， Gilbert JR ， Buluyama A.Combinatorial BLAS 2.0 ： Scaling combinatorial algorithms on distributed-memory systems. IEEE Trans Parallel Distrib Syst 2022;33（4）：989-1001.http://dx.doi.org/10.1109/TPDS.2021.3094091。[30]Dawson W，Nakajima T.使用NTPoly进行大规模并行稀疏矩阵函数计算。Comput Phys Comm 2018;225：154