GPU加速宏基因组组装的挑战与突破

→使用GPU加速大规模从头宏基因组组装Muaaz Gul Awan，Steven Hofmeyr，RobEgan，Nan Ding，Aydin Buluc，JackDeslippe，LeonidOliker美国加利福尼亚州伯克利劳伦斯伯克利国家实验室mgawan@lbl.gov摘要宏基因组工作流程涉及直接从环境中研究未培养的微器官。这些环境样品在被现代测序仪处理时产生了超过宏基因组软件能力的大而复杂的数据集。不断增加的数据集的大小和复杂性为具有exascale能力的宏基因组组装器提供了强有力的理由。然而，底层的算法基序并不适合GPU。这带来了挑战，因为大多数下一代超级计算机将主要依赖GPU进行计算。在本文中，我们提出了第一种GPU加速实现的本地组装方法，这是一个广泛使用的大规模宏基因组组装程序，MetaHipMer的一个组成部分。 本地汇编使用的算法会导致随机内存访问和非确定性工作负载，这使得GPU卸载成为一项具有挑战性的任务。 我们的GPU实现优于CPU版本约7倍，并在64个Summit节点上运行时将MetaHipMer的性能提高了42%。CCS概念Katherine Yelick加州大学伯克利分校，美国美国加利福尼亚州伯克利劳伦斯伯克利国家实验室kayelick@lbl.gov1介绍随着基因组测序技术的快速发展，现在可以以前所未有的规模对基因组进行采样和研究[5]。这包括对未培养的微生物的研究，这些微生物必须作为一个群体从其环境中取样[27]。大多数微生物不能在实验室中培养，必须直接从生活在不同环境中的微生物异质群落中取样[15]。对这些微生物群落的研究揭示了这些群落中存在的重要而复杂的关系以及它们与环境形成的关联。除其他好处外，宏基因组研究为更好的抗生素[15]，了解气候变化的影响[18]，法医学[29]以及了解不同的环境及其对生命的影响[30][10]铺平了道路。微生物的集体采样导致非常大且复杂的数据集，这些数据集无法使用为研究单个基因组而开发的常规基因组组装方法进行处理和分析[5][13][21]。典型的宏基因组工作流程涉及对DNA读段（DNA的短链）进行采样• 计算方法学→自组织;自组织;使用测序技术获得）• 计算基因组学;生物信息学;计算基因组学。关键词宏基因组，基因组，GPU，CUDA，序列组装，稀疏数据结构，图算法ACM参考格式：Muaaz Gul Awan ， Steven Hofmeyr ， Rob Egan ， Nan Ding ， AydinBuluc，Jack Deslippe，Leonid Oliker and Katherine Yelick.2021年使用GPU加速大规模从头宏基因组组装。在高性能计算，网络，存储和分析国际会议（SC '21），2021年11月14日至19日，圣。关闭KY，USA.美国纽约州纽约市ACM，10页。https://doi.org/10.1145/3458817.3476212本作品采用知识共享署名国际4.0许可协议进行许可SC关闭MO，USA©2021版权归所有者/作者所有。ACM ISBN978-1-4503-8442-1/21/11。https://doi.org/10.1145/3458817.3476212取样并试图重建基础基因组的相邻区域。 DNA读数是冗余的、重复的、容易出错的，并且当从环境样品获得时，它们可能包含比例偏差，这取决于样品中不同器官的群体。这使得宏基因组组装与单基因组组装显著不同，并且比单基因组组装更复杂，其中样品含有仅来自单个培养生物体的遗传物质。由于大多数单细胞生物从未被测序，因此没有参考基因组存在，并且该过程必须从头开始，这进一步加剧了问题。随着现代测序技术的出现，宏基因组数据生成的速度已经远远超过软件和硬件的计算能力。宏基因组数据集的大小非常大，即使是中等大小的样本也会超过典型共享内存服务器的内存容量[9]。生物信息学软件社区试图通过开发内存高效方法与多组装（单独组装数据集的部分，然后获取共识）等技术相结合来克服这些挑战，但这些导致运行时间长和组装质量差[13][9]。 为了克服这些挑战，MetaHipMer作为一种大规模的宏基因组组装器被引入，它可以利用超级计算机的大内存和计算能力来协同组装TB级规模的宏基因组。SC关闭MO，USAM.G. Awan等人数据集[7]。MetaHipMer与其他最先进的宏基因组组装器相比的性能和准确性已被详细研究[9]。最初，MetaHipMer 是用UPC 和MPI 编写的，但后来它被UPC++完全重写;这个新版本被称为MetaHipMer 2。在本文中，我们在一般情况下（包括所有版本）提到MetaHipMer时使用术语MetaHipMer，在讨论具体实现时使用术语MetaHipMer2，因为我们使用最新版本进行所有实验。MetaHipMer的不断发展使其能够应对不断增加的宏基因组数据规模所带来的日益严峻的挑战。 随着下一代超级计算机的不断发展，其计算能力的很大一部分来自图形处理单元（GPU），因此，发展MetaHipMer以利用GPU处理变得非常重要。许多生物信息学算法（例如宏基因组组装中的大多数算法）由于其稀疏和不规则的性质而不适合GPU。此外，GPU上缺乏对哈希表、字符串和向量等动态容器的支持，使得在GPU上实现生物信息学算法成为一个挑战[31]。图1：MetaHipMer2管道概述局部装配模块（红色显示）占用了许多数据集总运行时间的最大如图1所示，MetaHipMer有一个复杂的工作流程，由执行组装管道不同阶段的独立组件组成。图2a中对单个MetaHipMer运行的分解显示，大约三分之一的总执行时间花费在本地组装模块上，正如其名称所示，它是在每个节点上本地执行的，而其他模块则将大部分时间花在跨进程的通信上。本地组装模块包括并行构建数千个哈希表，然后使用这些哈希表执行重叠群（DNA的连续链）延伸遍历。本地汇编的CPU实现在很大程度上依赖于哈希表、向量和字符串等动态结构，这是在GPU上实现的一个挑战。此外，局部组装的算法基元不确定的工作量，这使得在GPU上实现该模块成为一个非常具有挑战性的问题。在本文中，我们提出了一个优化的GPU实现的本地组装，集成在MetaHipMer管道。 我们在真实数据集上的实验显示，使用GPU时，性能提高了7倍，整体流水线加速率为42%。2背景2.1文献综述根据研究类型和参考基因组的可用性，有时可以将DNA读数与参考基因组进行比对。这个过程的核心涉及到一种动态编程技术，由于可预测和重复的内存访问模式，这种技术在GPU上表现良好[1]。[16][3][26]. 对于宏基因组学研究，参考基因组很少可用，因此重新进行组装。在没有参考基因组的帮助下重新组装培养生物体的基因组是一个研究得很好的问题。通常这是使用汇编图方法来执行的，它可以采取两种形式[25]。第一种是de Bruijn图方法，其使用称为k-mer的DNA读数的短子串构建图[23]，其中每个k-mer由图中的顶点表示，并且当两个对应的k-mer重叠时，边连接两个顶点。基础基因组可以通过在de Bruijn图中找到受某些约束的路径来组装。第二种方法是重叠图，其使用顶点的完整DNA读段而不是k-mer，并且边缘对应于两个读段之间的重叠[14]。通过重叠图的路径对应于底层基因组。DNA读段容易出错、冗余并且可能不覆盖完整的基因组。这使得通过组装图寻找路径的任务非常困难。通常，重叠方法仅用于长读段，因为对所有读段进行全对全比对的计算成本对于具有更多更短读段的数据集是过高的。已经有多种使用GPU加速基因组扩增的方法。一些流行的GPU加速基因组组装器包括LaSAGNA [8]，它使用重叠字符串图方法并利用GPU进行排序和前缀扫描等操作，但在CPU上执行大部分组装图相关计算。它实现了约3倍的性能提高，一个CPU的并行汇编器。另一个基因组集成器GPU-Euler [19]使用de Bruijn图方法，并在GPU上执行大多数与汇编图相关的操作GPU-Euler展示了与串行CPU方法相比约5倍的加速。 GAGM [11]是另一个GPU加速的汇编程序，它也使用de Bruijn图方法，并实现了几乎端到端的GPU卸载工作流，并具有一些CPU操作。 它显示了比使用四核CPU运行的基于CPU的并行汇编方法大约7倍的加速。 一些类似的方法执行使用序列比对算法比对中间重叠群的不同部分的附加步骤;序列比对是昂贵的过程，但比其余的基于图的算法更适合GPU。蚱蜢[28]是这样一个汇编器：它将大部分汇编流水线保持在CPU上，并将序列对齐部分卸载到GPU。另一个GPU加速的基因组组装器使用双向de使用GPU加速大规模从头宏基因组组装SC关闭MO，USABruijn在GPU上绘制并执行汇编图构建[17]，并且仅比较仅CPU方法的图形构建阶段与GPU方法，他们展示了2到7倍的加速比用于比较的仅CPU汇编器利用了多个CPU内核。所有这些GPU加速的基因组组装器都受到所涉及算法的性质以及组装问题的数据和内存密集型性质的挑战。 这是由于组装图的构造、图的遍历和哈希表的构造和探测所导致的不规则的内存访问模式。此外，GPU上的有限内存由于低CPU-GPU通信带宽而构成另一个挑战。 尽管存在这些挑战，但GPU加速的基因组组装器已证明比仅CPU版本的性能有所改进。然而，宏基因组组装的一系列挑战是-MetaHipMer配置文件（CPU本地程序集）百分之十点六27.0%百分之三十四点二5.3%21.3%合并读取k-mer分析重叠群生成比对内核局部汇编脚手架文件IO除了上面讨论的那些之外，还由于涉及更大和更复杂的数据集而进一步复杂化。宏基因组组装需要更专门的方法，现有的基因组组装方法不能在这里使用。一些流行的宏基因组组装器包括MetaHipMer[7]，Megahit [13]和MetaSpades [21]。 Megahit和MetaSpades是共享内存汇编器，不能处理超过单个节点内存要求的数据集。MetaHipMer可以跨多个节点扩展，并且能够处理TB级数据集[9]。由于所涉及的算法在GPU加速方面的挑战，在将宏基因组组装移植到GPU方面所做的工作很少 Megahit通过将k-mer计数阶段卸载到GPU来展示其早期版本中GPU的使用;然而，在最近的工作中，已经表明Megahit的仅CPU优化版本可以优于早期的GPU加速版本[13]。 相比之下，MetaHipMer已经从GPU的使用中看到了明显的性能提升（在对齐操作中）[3]。2.2MetaHipMerMetaHipMer是唯一已知的分布式内存宏基因组组装器，可以扩展到数千个节点，同时匹配最先进的共享内存组装器的质量[9]。MetaHip-Mer使用迭代de Bruijn图方法从输入DNA读段构建DNA的连续链，称为重叠群[24]。它还使用了一种专门的支架方法，将多个重叠群缝合在一起，以增加最终重叠群的长度。MetaHipMer管道由多个组件组成，这些组件执行完整的组装，如图1所示。它首先将输入读段分解为长度较短的子串 ，称为k-mers。在过滤掉错误的k-mer（只出现一次的k-mer）后，这些k-mer被用来构建de Bruijn图。遍历所得到的图中的明确连接的路径以获得基因组的连续区域。 这之后是比对阶段，其中重叠群与读段比对以找到可用于进一步延伸重叠群的读段。然后使用局部组装模块将与重叠群末端比对的读段用于在两个方向上延伸重叠群。 局部组装模块还执行de Bruijn图构建和遍历，但对于与每个重叠群末端比对的读段单独进行。最后，在前几个阶段产生的重叠群(a) 使用CPU本地程序集时MetaHipMer2运行时故障总时间2128秒MetaHipMer配置文件（GPU本地组装）合并读取k-mer分析重叠群生成比对内核局部汇编脚手架文件IO(b) MetaHipMer2在使用GPU本地程序集时的运行时间故障总时间1495秒图2：此处的饼图显示了MetaHipMer2在使用海洋社区数据集的Summit系统的64个节点上运行时不同阶段的运行时间分解（百分比）[12]。在支架阶段连接在一起以进一步增加邻接性。以前，MetaHipMer中只有一部分对齐阶段被卸载到GPU [3]。图2a中MetaHipMer的时间分解显示，对于64个OLCF（橡树岭领导计算设施）Summit节点上的一个特定数据集，34%的总时间花费在本地装配上。 在任何一个阶段中花费的时间的确切比例取决于数据集和并发性，但是本地组装花费的时间总是整个运行时的重要部分。虽然不是流水线中最适合GPU的部分，但大多数本地组装都在每个节点上本地执行，与其他阶段相反，这些阶段本质上是分布式的，并且由网络通信主导 因此，本地汇编是GPU卸载的一个很好的候选。百分之十四点八6.3%百分之三十七点九百分之三十点八7.7%SC关闭MO，USAM.G. Awan等人←←（）下一页（）下一页（）下一页||+（）下一页←←（）←←←（）2.3本地组装模块宏基因组样品是复杂的，包含具有不同丰度的不同生物体的群体，这导致测序机对某些生物体的采样多于其他生物体。测序错误和DNA片段在生物体中的共性可能导致全局de Bruijn图中路径的错误重叠，产生无法解析的分叉。 本地组装通过完全本地执行de Bruijn图遍历来解决这个问题，仅使用映射到重叠群末端的读取来延伸该末端。在当前仅CPU版本中，本地汇编以并行方式执行这是一个两步的过程，迭代执行，直到满足正确的终止条件。每个过程挑选重叠群的局部子集并获得与每个重叠群比对的候选读段重叠群的右侧和左侧的读数保持分开。对每个重叠群的右侧和左侧重复相同的算法算法1kmer哈希表构造1：C重叠群2：对于每个叠连群，3：对于每一个读在_做4：对于每个kmer在马格德堡5：_���.���������������������������������6：结束锻造7：结束8：结束算法2DNA步移1：c重叠群2：一个人的世界3：_4：kmer_5：对于=0__<6：如果是_，则7：end_walk8：如果结束9：ext_.������������������������������������������10：如果=，则11：_12：休息13：如果结束14：=15：=_，16：结束一旦所有数据都在本地可用，第一步是从所有读段构建k-mer哈希表，其中k-mer用作键，值是扩展。 扩展对象包含k聚体之后的碱基（核苷酸字符），还包含关于该碱基的质量和该k聚体的计数（出现次数）的信息。 对于每个重叠群的所有候选读段，重复在哈希表中插入k-mer的过程;在算法1中可以看到用于此的伪代码。第二步是[6]和[7]中所讨论的，执行mer-walksmer-walk从重叠群的末端切割k聚体，并在哈希表中查找，如果k聚体可用，则将相应的延伸碱基附加到重叠群的末端重复此操作，直到遇到死端或分叉（参见算法2）。 如果遇到分叉，则增加或上移k（k-链节的长度），并重复从第一步开始的整个过程;如果出现死端，则下移k。当降档后遇到分叉或升档后遇到死端时，合并行走阶段终止。2.4GPU卸载面临的挑战本地汇编模块对GPU卸载提出了三种类型的挑战：GPU上缺乏对动态容器的支持如上所述，底层算法严重依赖于哈希表和字符串哈希表，这两者都需要动态内存分配，这在GPU上是不支持GPU上的可用内存有限Summit节点上所有六个GPU的总内存为96 GB，而同一节点上CPU可用的总DRAM为512 GB [22]。这限制了可以卸载到GPU的工作量本地汇编的内存访问模式和工作分配并不适合GPU。哈希表引入了一种本质上是随机的内存访问模式，并导致GPU上的非合并内存访问，这会导致很大的性能损失。此外，mer步移需要顺序进行，并且它们的最终长度不能预先确定 这会产生高度随机的工作负载，导致GPU上的翘曲停滞。这些挑战使得局部组装和宏基因组组装通常是GPU的难题，无论是从实现复杂性还是从获得良好性能的难度来看。3gpu加速 当地组装在本节中，我们将讨论我们将本地汇编模块卸载到GPU的方法，并解决上述挑战，并描述我们采用的解决方案 在这项工作中，我们使用NVIDIA的CUDA API进行GPU卸载。 GPU加速的本地组装的概述可以在图4中看到;我们的实现的各个方面在下面详细描述。3.1数据分箱以实现更好的负载平衡来自上游流水线的每个重叠群可以具有不同数量的候选读段，用于在局部组装阶段延伸它这个数字的范围可以从零到3000（经验上限）。候选读段的数量越大，需要的工作就越多卸载所有重叠群而不进行任何类型的排序将导致线程束之间的负载不平衡，这将导致线程束的一些线程停止其余线程，并导致性能低下。作为一种解决方案，我们根据候选读段的数量将CPU侧的重叠群分为三个基于经验分析选择箱限：第一个箱包含具有零读段的那些重叠群;第二个箱包含所有那些重叠群···使用GPU加速大规模从头宏基因组组装SC关闭MO，USA）（− +（− +）其具有少于10个读段;并且所有剩余的重叠群进入第三仓。我们的研究表明，通常大多数重叠群具有零读段，而分配给第二个箱的重叠群的百分比可能在10%和30%之间变化，并且第三个箱得到不到1%的重叠群。图3中可以看到跨箱的重叠群分布示例（对于arcticsynth [9]数据集）。跨箱的重叠群分布Bin-3Bin-2Bin-1100755025021 33 55 77k-链节尺寸图3：arc- ticsynth[9]数据集的三个bin中重叠群的分布可以看出，Bin-3始终得到小于总重叠群的1%，而Bin-2在10%和30%之间变化更大的k聚体尺寸导致具有大于零的候选读段的重叠群的数量更大。第一个bin不卸载到GPU，并且在不执行任何扩展的情况下返回，因为不存在要针对其扩展 对于第二个和第三个bin，启动单独的内核循环。这种排序确保了可以快速处理的重叠群在单独的内核上启动，并且不会面临长时间的翘曲停滞延迟，而需要最长时间的重叠群在单独的内核上被分组在一起请注意，即使第三个bin包含不到总重叠群的1%，它仍然可能占用大部分计算时间。图4：GPU本地汇编模块概述3.2最小化设备内存使用读段中所有k-mer的总大小远大于单个读段占用的内存。假设每个字符都存储在一个字节中，那么长度为1的读取将占用相同读段的k-mer占用的总内存（以字节为单位）为1 .一 、在GPU上执行本地汇编时，重要的是要节省内存，以便最大限度地存储数据，工作可以卸载。这一点特别重要，因为本地汇编是一种内存带宽有限的算法，而获得性能的方法之一就是将尽可能多的工作卸载到GPU上。这也是有帮助的，因为GPU的延迟隐藏性质，即 当一个线程束的数据不可用时，可以调度另一个线程束前进。图5：GPU本地程序集扩展内核概述绿色虚线箭头表示被遮盖的螺纹。每个CUDA扭曲分配一个重叠群。为了最小化内存使用量并最大化卸载的工作量，我们使用了一些措施来重用存储在全局内存中的数据。我们的分析表明，GPU上最大的内存量被哈希表使用 该算法使用两个不同的哈希表来扩展每个重叠群：一个用于存储k-mer和扩展，另一个用于跟踪访问的k-mer（以避免循环）。大多数哈希表的实现都要求它们根据负载因子调整大小加载因子是已填充的哈希表槽的百分比更高的加载因子可能导致哈希冲突增加，从而导致更长的插入和访问时间。在GPU上，由于动态内存分配的限制，我们无法启用哈希表的扩展一种简单的方法是计算所有扩展的最大可能哈希表的大小，并为每个扩展保留那么多内存，但这很快就会占用所有GPU全局内存。 作为一种变通方法，我们计算任何重叠群扩展所需的哈希表的确切大小，并将所有大小存储在一个名为“hash���_”的数组中���������������。然后我们计算所有哈希表使用的总内存，并在GPU上分配。在哈希表_hash_hash数组的帮助下，我们可以跟踪每个哈希表的开始和结束，并最大限度地减少整体内存使用。哈希表的大小取决于存在于一组候选读段中的最大唯一k聚体的数量：假设每个k聚体是唯一的，哈希表的大小将是是���最大读段长度，k是k聚体大小，k是重叠群的总候选读段，k是哈希表中每个条目的大小������������为了防止哈希表达到高负载因子，我们使用哈希表作为哈希表������重叠群百分比SC关闭MO，USAM.G. Awan等人−300尺寸这将哈希表加载因子限制为最大值约0.93. 使用这种方法，我们能够最大限度地减少分配给哈希表的总GPU内存，同时最大限度地提高哈希表性能。上面讨论的策略的负载因子可以计算为：负载系数=−+1���为了计算最坏情况的负载因子，我们用最长可能的读段长度代替nc2，用最短可能的k聚体长度代替nc2。 短读段的最大长度为300，而合理准确度的最短k-mer长度为21，给出：最差情况载荷系数= 300 − 21 +1= 0。93如上所述，读段的组成k-mer比读段本身占用更多的空间然而，如果k-mer的起始位置和长度已知，则也可以直接从读段获得k-mer。 如图6所示，我们不将完整的k-mer存储在GPU上的哈希表中，而是仅存储指向k-mer的起始位置和k-mer的长度的指针。例如，为了存储长度为77的k聚体，将需要相同数量的字节。然而，使用图6中的技术来存储相同的k聚体将仅需要5个字节， 每个k聚体使用约15个更少的存储器。这有助于释放大量的内存。我们在DNA步行阶段使用类似的策略，仅存储读取中不同k-mer的指针，而不是存储完整的k-mer。图6：左边的表存储完整的k-mer，而右边的表仅存储指向所存储的read内的k-mer起始位置的指针以及k-mer的长度。右表中的k-mer与左表中3.3Warp本地哈希表构造局部组装的第一步是使用其候选读段构建每个重叠群的k聚体哈希表这使用算法（伪码1）中概述的方法来执行 对于GPU实现，我们分配了一个CUDA线程束来构造一个哈希表，如图5所示。CUDA线程束是调度到GPU硬件上的最小线程单元。NVIDIA硬件上的每个线程都由32个线程组成。 当在线程束级别上工作时，可以利用几个优点，例如线程束的线程可以通过寄存器到寄存器的直接数据传输彼此通信，并且线程可以在线程束内同步。我们通过将线程束的线程映射到第一个候选读段来开始哈希表的构建，使得线程指向该读段中的连续k-mer，如图7所示。每个线程使用murmurhash 2函数将分配给它的k-mer插入哈希表[2]。在哈希表插入过程中，可能会发生几种情况;这些情况如图7所示，并在下面进行讨论：哈希冲突：如果一个线程遇到一个已经被占用的哈希表条目，我们执行一个键到键的比较，其中键是插入的k-mer和已经存在的k-mer。如果键是匹配的，则增加k聚体计数并更新其扩展的质量度量。如果键不匹配，这是一个哈希冲突，并使用线性探测来解决，其中键被插入到下一个可用的空槽中。线程冲突：当两个线程获得相同的k-mer时，就会发生这种情况，例如图7所示。 这产生了一种独特的情况，其中两个线程竞争在相同位置插入相同的k-mer。为了解决这种情况，需要独占区域，然而，独占区域不能在GPU上创建。 作为一种解决方案，我们使用CUDA的比较和交换（CAS）原子操作来将条目标记为由线程独占占用。 CAS原子确保只有一个冲突线程能够将条目标记为已占用;将此线程称为获胜线程。接下来，我们使用CUDA的match_any_sync操作来获得一个掩码，该掩码表明线程束中的哪些线程正在发生冲突，并同步它们。 在同步之后，我们允许获胜线程在if块中初始化哈希表的条目，然后在if块之后使用上面的掩码再次同步冲突线程。 一旦获胜线程添加了条目，冲突中涉及的其余线程就可以访问条目并原子地更新值。图7：在左边的表中，线程1和线程2各自得到不同的k-mer，但它们都散列到相同的位置。这种类型的碰撞通过线性探测解决，即，找到下一个空位。 在右边的表中，线程1和4得到相同的k-mer，这导致线程冲突，使用独占区域解决。3.4DNA漫步一旦构建了k-mer哈希表，线程束的32个线程（其构建了哈希表）中的一个线程遍历该表以执行DNA行走，如第2.3节所述和算法2所示。对于每一个线程束，除了第一个线程之外的所有线程都被屏蔽掉，因为不能执行遍历··使用GPU加速大规模从头宏基因组组装SC关闭MO，USA（见图5）。 局部组装是一个迭代过程，重复直到找到可接受的行走。如果在步移结束时未找到可接受的步移，则用不同的k值重建k聚体散列表以重做DNA步移。检查遍历是被接受还是被拒绝的计算由执行遍历的同一线程执行。重要的是要将有关遍历状态（接受或拒绝）的信息广播到线程束的其他线程，以便根据哈希表是否需要重建来屏蔽或取消屏蔽它们。 对于每个扩展，遍历的状态作为变量存储在寄存器中，然后使用shuffle指令与线程束的其他线程共享该值，该shuffle指令使线程束内的线程间通信成为可能，如第3.3节所讨论的。在图5中可以看到内核实现的概述以及有关线程参与的详细信息。4性能分析为了分析GPU加速的本地汇编模块的性能，我们首先研究了它的独 立 性 能 ， 然 后 将 该 模 块 集 成 到 MetaHipMer 的 最 新 版 本MetaHip-Mer4.1测试系统和数据集NVIDIA的CUDA API用于GPU本地汇编内核的开发，CUDA10.1.2版用于构建所有CUDA模块。UPC ++版本2021.3.0用于从源代码构建MetaHipMer。对于以下所有研究，我们从git commit80090的master分支获得了MetaHipMer2的源代码。仅CPU运行是使用完全相同的版本执行的，而对于GPU集成，我们从上述版本开始。对于独立性能分析，我们使用Cori系统 Cori GPU分区上的每个节点包含八个V100 NVIDIA GPU，每个GPU具有两个插槽的英特尔Sky-lake处理器，每个插槽具有20个CPU核心。每个节点上的总可用DRAM为384 GB，而每个NVIDIA V100的总全局内存为16 GB。 对于大规模研究，我们使用了Summit超级计算机[22]。Summit的每个节点由两个POWER9处理器和六个NVIDIAV100 GPU组成。CPU可用的总RAM为512GB，而每个GPU包含16GB的全局内存。对于在较少节点上的小规模测试，我们使用arcticsynth数据集[9]，其包含3200万个长度为150 bp的合成读段，对于大规模测试，我们使用WA数据集，其是来自北冰洋西部的海洋微生物群落的集合，由813 GB的2， 465，328， 090 Illumina组成长度为150的HiSeq双端读取[12]。对 于 独 立 运 行 ， 我 们 使 用 arcticsynth [9] 数 据 集 并 通 过MetaHipMer管道处理它，以转储输入到本地组装模块的重叠群及其候选读段。然后使用此数据转储来评估GPU本地汇编内核的性能。4.2屋顶线分析为了了解设备利用率和算法的限制，我们使用了指令Roofline[4]。指令Roofline模型是一种基于边界和瓶颈分析方法来理解给定内核性能的直观方法。它允许我们分析指令吞吐量和量化内存访问的效率通常，指令根线模型将内核在数十亿指令（GIPS，y轴）中的性能表征为其指令强度（II，x轴）的函数。指令强度被定义为内存流量的每个内存事务的翘曲指令 在指令屋顶线中，绘制的指令点显示内核的性能和利用率。这些实心点（指令吞吐量）离图的右上角越远，内核实现的性能/利用率就越对于开放点（内存模式），它们越靠近最右边的内存墙，内核的内存访问效率就越高我们评估了从开发周期中获得的两个不同版本的GPU本地组装模块 第一个版本（称为v1）仅使用单个CUDA线程来构建k-mer哈希表（参见图8），而第二个版本（称为v2）每个k-mer哈希表使用单个线程束（32个线程）（参见图9）。对于这两个版本，DNA遍历的第二步由每个扩展的单个线程执行。v2内核从读取中提取k-mer，以便线程束访问连续的内存位置，如图7所示，这减少了全局内存事务的数量从图8（v1）和图9（v2）可以明显看出，当从v1移动到v2时，L1点在右上方这表明v2通过减少全局存储器事务和全局存储器加载/存储指令的数量来实现更高的指令吞吐量和更好的指令强度。图10显示了两种实现的指令分解，可以观察到全局内存指令的数量显著减少。此外，Roofline图还显示v2比v1更好地利用内存带宽然而，这并没有改善在哈希表中插入时的存储器访问模式，但是并行插入确实改善了每次访问。 可以进一步观察到，由于散列表的随机访问的性质，两个版本都接近Stride-1存储墙。Roofline图中的虚线显示了底层内核可以实现的非断言warp指令的数量。红点和虚线之间的间隙表示线程谓词的存在这表明v1和v2内核都受到线程预测的影响大多数线程预测发生在算法的第二步，其中大多数线程必须被屏蔽（图5）以执行顺序DNA遍历，并且工作量是不确定的，并且在线程之间变化很大。例如，对于某些线程，DNA步行可以长达300步，而对于另一个线程，它可能会在开始时终止。 对于v2，线程预测适度减少，因为多个线程用于构建哈希表。总之，没有一个版本达到接近峰值的性能，但v2达到了更高的峰值性能，14个。4 GIPS。这主要是由于该算法的性质，随机访问的全局内存和大量使用的本地存储器。 大约70%的L1存储器事务和L1存储器指令来自本地存储器，这在这种情况下限制了性能。SC关闭MO，USAM.G. Awan等人v1 v2v1 v2图8：扩展内核（v1）图9：扩展内核（v2）的图10：性能洞察细分4.3MetaHipMer中的集成为了测试本地汇编阶段的GPU卸载对MetaHipMer性能的影响，我们使用了最新版本，本地汇编的GPU模块使用驱动程序函数集成到MetaHipMer2中，该驱动程序函数执行所有CPU端数据打包，设备到等级映射，并启动设备内核。使用驱动程序功能可以完全隔离GPU和CPU代码，这证明非常有帮助，因为UPC++和CUDA代码需要在链接之前单独构建MetaHipMer2中GPU本地组装集成的概述如图11所示。图11：MetaHipMer2中GPU本地组装模块的集成。绿色框显示与GPU相关的调用，而绿色箭头表示在后台运行的线程在收集了来自多个节点的所有所需数据之后，基于第3.1节中所述的候选读段计数进行重叠群的分箱。 一旦bin可用，在新线程内进行驱动程序函数调用，并将包含具有较大数量候选读段的重叠群的第三个bin传递给驱动程序（图11）。 使用单独的线程启动GPU调用允许控制返回到父线程，CPU可以开始在第二个bin上执行本地组装一旦GPU代码返回，第二个bin也被卸载到GPU。在图11中，绿色箭头显示了在后台运行的新分叉线程。首先在GPU上启动第三个bin的原因是基于一项实证研究，该研究表明，当使用具有更大数量读段的重叠群时，GPU会更好，即当工作量更大时。 这是真的，因为GPU是隐藏延迟的设备，更多的工作允许它们迎合底层算法引入的随机内存访问模式。4.4性能改进为了研究MetaHipMer2流水线与新集成的GPU本地组装的性能改进，我们使用了上面提到的两个数据集。我们获得了前面提到的MetaHipMer2版本，并使用它来执行CPU本地汇编的运行，然后按照前面的部分所述更改了本地汇编模块，并使用相同的数据集重做了运行。MetaHipMer2在使用CPU本地组装模块时使用节点上的所有可用内核，在使用GPU加速本地组装模块时使用所有可用GPU。对于小规模运行，我们使用两个顶点节点。 图12显示了GPU本地汇编模块的性能比CPU本地汇编模块高出约4.3倍，并使整体运行时间提高了约12%。请注意，MetaHipMer的每个模块所花费的时间取决于所使用的数据集对于arcticsynth数据集，在本地组装阶段花费的总时间约为14%，这比使用WA数据集时要少得多，如图2a所示。图13显示了本地汇编的CPU和GPU版本的运行时间之间的比较，这是在处理WA数据集时从MetaHipMer2的完整运行中提取的。 可以看出，GPU版本在64个节点上运行时的性能快了7倍以上，但随着节点数量的增加，性能优势会恶化（尽管在1024个节点上仍然快了2.65倍）。这是因为在更大规模运行时，可以卸载到一个GPU的工作量减少，这会导致更大的GPU开销。Global_memory_inst FP_inst2.51010百分之二十三Local_memory_instINT_inst4500400021.53500300025001百分之十八0.52000150037%1000500百分之十五百分之三百分之三百分之四十占7%数目的指令时间（毫秒）使用GPU加速大规模从头宏基因组组装SC关闭MO，USA2个节点运行500400文件IO脚手架本地程序集总体性能比较使用CPU本地汇编使用GPU本地汇编加速2500 50300200ALN内核对齐重叠群生成k-mer分析合并读数2000 401500 301000 20500 10100064128025651201024CPU本地程序集GPU本地程序集节点图12：使用arcticsynth[9]数据集运行两个节点的运行时间比较。当卸载到GPU时，本地组装阶段的速度提高了约4.3倍。CPU vs GPU本地汇编（CPU）本地汇编（GPU）加速800 8图14：MetaHipMer2管道在有GPU本地程序集支持和没有GPU本地程序集支持的情况下的总运行时间。5结论和今后的工作在本文中，我们提出了一个使用GPU加速大规模宏基因组组装流水线的首次尝试。Metage-nomic组装依赖于本质上不规则和稀疏的算法，这使得它们成为GPU的一个具有挑战性的问题。6004002000642064 128 256 512 1024节点随着现代基因组测序技术的发展，大型和复杂的宏基因组数据集的生成速度如此之快，以至于很快这些数据将超过当前最先进的软件工具。这为利用亿次级超级计算机提供了强有力的理由，这些超级计算机将利用GPU来实现其大部分计算能力。为此，我们确定并加速了MetaHipMer的计算最占主导地位的部分之一，这是唯一可用于社区的大规模宏基因组组装程序MetaHipMer管道的本地汇编模块使用图13：本地汇编模块的CPU和GPU版本的运行时间比较。这些运行时间是从Summit超级计算机上MetaHipMer2管道的完整运行中获得的图14显示了完整的MetaHipMer2流水线运行时比较，有和没有GPU本地组装。GPU本地组装在多达128个节点上提供了约42%的峰值性能提升。随着流水线被与越来越多的节点的通信所支配，这种性能提高会降低在更大的规模下，GPU可用的工作量也会下降，并且通过将本地组装阶段卸载到GPU所获得的优势也会减少，这是预期的，因为我们具有很强的可扩展性。 从512到1024个节点时加速的突然下降是由于代码中通信量大的部分所花费的时间的波动。 对多个运行求平均值会使加速比线性下降;然而，由于资源有限，我们只对512和1024个节点执行了单次运行。 通过多次执行较小的运行来推断预期的变化。图2b显示，对于64个节点，本地汇编部分从图2a所示的仅CPU时的总运行时间的34%减少到仅占总运行时间的6%。哈希表、向量和字符串搜索来执行DNA步行，以扩展基因组的连续区域我们使用了CUDA的warp级内部函数和高效的线程间通信方法来实现快速的warp本地哈希表，并最大限度地减少了GPU全局内存的使用，从而将最大量的工作卸载到GPU上。这使我们能够更好地利用GPU的延迟隐 藏 特 性 。 当 在 Summit 超 级 计 算 机 上 大 规 模 运 行 时 ， 与MetaHipMer自己的CPU实现相比，我们实现了本地组件模块高达7倍的加速。我们还演示了在MetaHipMer管道中集成GPU加速的本地汇编模块，以在Summit超级计算机上运行时获得高达42%的性能提升。我们已经证明，通过利用GPU的延迟隐藏性质和低级编程内在函数，我们可以在宏基因组分析软件中获得显著的性能改进。在未来的工作中，我们将把MetaHipM