FastZ：GPU加速的全基因组比对

FastZ：在GPU上加速有缺口的全基因组比对Sree Charan Gundabolu普渡大学美国印第安纳州西拉斐特sgundabo@purdue.eduT. N. 维杰库马尔普渡大学美国印第安纳州西拉斐特vijay@ecn.purdue.edu米图纳·托特托迪普渡大学美国印第安纳州西拉斐特mithuna@purdue.edu摘要认识到全基因组比对（WGA）的重要性，美国国立卫生研究院维护LASTZ，一个连续的WGA应用程序。随着基因组数据的增长，迫切需要可扩展的高性能WGA。不幸的是，使用动态编程（DP）的高灵敏度"我们开发了FastZ，一个GPU加速的，有间隙的WGA软件，在灵敏度上与有间隙的LASTZ相FastZ采用了一种新颖的检查器-执行器方案，其中（a）轻量级检查器省略了DP追溯，除非在常见的极短对齐中，检查器执行有限的，急切的追溯以消除执行器，以及（b）执行器修剪避免了不必要的工作。此外，FastZ采用基于寄存器的循环缓冲来大幅减少内存流量，并按大小对DP问题进行分组以实现负载平衡。在RTX 3080 GPU上运行的FastZ和我们的LASTZ多核实现分别比顺序LASTZ实现了111倍和20倍的加速比CCS概念• 应用计算→生物信息学。ACM参考格式：Sree Charan Gundabolu，T.N. Vijaykumar和Mithuna Thottethodi。2021年FastZ：在GPU上加速有缺口的全基因组比对。在高性能计算，网络，存储和分析国际会议（SC '21），2021年11月14日至19日，圣。关闭 KY ， USA.ACM ， 美 国 纽 约 州 纽 约 市 ， 12 页 。https://doi.org/10.1145/3458817的网站上下载。34762021介绍基因序列比对[2，9，11，22，34]是基因组学的基本计算核心之一。这种比对在许多情况下使用，包括基因组组装（来自片段化读段）和比较基因组学（比较生物体的整个基因组）。具体来说，比较基因组学检查两个或两个以上生物体的整个基因组之间的比对，以回答许多关键的进化和遗传问题 。 美 国 国 立 卫 生 研 究 院 （ NIH ） 维 护 全 基 因 组 比 对（WGA）服务器，特别是LASTZ [11]，作为基因组学的计算服务，反映了对此类比对的广泛兴趣本作品采用知识共享署名国际4.0许可协议进行许可SC© 2021版权归所有者/作者所有。ACMISBN 978-1-4503-8442-1/21/11。https://doi.org/10.1145/3458817.3476202社区[24]我们的重点是WGA，而不是基因组组装（例如，[1、14、33、36]）。基因组数据持续增长，（1）全测序基因组的数量不断增加，（2）更复杂的生命形式的基因组组装（例如，，D.simulans的碱基对比肠道沙门氏菌（一种更简单的生命形式）多几个数量级，以及（3）更快，更便宜的方法来捕获基因组数据[13，20，26]。因此，迫切需要可扩展的高性能WGA.此外，存在对于性能的灵敏度的充分理解的权衡。例如，SegAlign [8]提出了对无间隙过滤版本的GPU优化，这比包括插入和删除的有间隙版本更快，但找到更因为我们的目标是高性能WGA而不牺牲敏感性，所以我们只考虑LASTZ的缺口LASTZ采用“种子和延伸”方法，其中精确匹配的短序列（即，‘seeds’) are extended with gaps, LASTZ中用于种子扩展的局部比 对算法[9] 是Smith-Waterman 算法[ 34 ] 的变体，Smith-Waterman算法[34]是用于为匹配分配分数的动态规划（DP）算法。最近的工作[37]集中在使用定制ASIC（或较低性能点的FPGA）加速有间隙的WGA，这对大多数基因组学用户来说仍然不可用，直到研究产品成为产品。在本文中，我们表明，现成的GPU可以实现高性能，有间隙的WGA。为此，(1) 我们确定了关键的工作负载特征和性能瓶颈，以及（2）基于这些见解，我们开发了FastZ，一个GPU加速的，直接替代有间隙的LASTZ的产品。还有更老的GPU加速的Smith-Waterman实现用于间隙扩展（例如，[38]我们比较一下。WGA的工作负载可以用两种方式来描述首先，必须计算大量的种子扩展。独立的种子扩展是彼此独立的，并且可以并行计算（尽管如果以顺序顺序计算，则可以进行一些工作减少优化）。这些种子扩展之间的工作分布是高度倾斜的。绝大多数种子扩展几乎没有工作，因为它们导致低评分，短比对。例如，超过97%的种子位点导致不长于128个碱基对的比对。相比之下，高得分比对可以是更长的数量级（例如，数以万计的碱基对）。其 次 ， Smith-Waterman 计 算 占 了 大 部 分 执 行 时 间 （ 例如，>99%）的缺口LASTZ。DP评分矩阵是一个关键的数据结构，它逐渐填充了较小问题的最佳解决方案，然后用于识别较大问题的最佳解决方案。图1显示了沿行和列显示的两个序列的Smith-Waterman DP矩阵。右边的递归完全定义了2.Σ图1：Smith-Waterman中的重复性和并行性计算每个矩阵单元。每个矩阵位置i， j分别保存关于两个序列的部分比对的最佳得分的信息，直到并包括第i个和第j个碱基对对于每个细胞，该算法跟踪总得分（S），该得分假设空位插入（I）和缺失（D），以及回溯指针（T），其使得能够重建精确比对。这样的DP算法有几个关键特征，其中一些与GPU相关。(1) DP算法计算超出最佳比对点的更大比对空间的分数和回溯指针，以确保没有遗漏更高分数例如，即使超过97%的比对短于128个碱基对，超过90%的搜索探索长达5700个碱基对（包括空位）的比对。(2) DP计算仅对所访问的每个字节执行适度的工作量四次比较和五次加法，需要五次单元读取和六次单元写入，如图1中的递归中所示）。当并行化时，不平衡的计算带宽比导致内存带宽限制算法。Darwin-WGA的[ 37 ]前辈Darwin [36(3) 与回溯数据不同，回溯数据必须保留到DP算法结束以重建比对，分数在写入后不久被读取不到五次，然后就死了。由于不连续的访问不能被合并，因此未被寻址的沿着DP矩阵对角的存储器访问将降低存储器带宽然而，存在公知的缓解（例如，Feng等人 [38]），其变换布局以确保对角元素是连续的并且可以合并。然而，低存储器-计算比仍然是一个挑战。FastZ采用了两种高级内存策略来应对这一挑战。首先，最佳对齐长度以及因此DP和回溯矩阵的大小是先验未知的，并且同时GPU内核中的动态存储器分配是未知的。慢[12，18，23，35，40]。因此，FastZ采用了众所周知的检查器-执行器方法[30]，其中（较大）对齐搜索空间的轻量级扩展快速确定最佳对齐长度，而无需为DP矩阵分配任何动态内存;执行器通过内核启动时的内存分配完全计算（小得多）实际对齐，以使用检查器的对齐长度进行回溯。其次，FastZ采用额外的内存优化（1），以识别和消除大部分的DP矩阵访问的检查员和执行器，（2）省略全局内存访问的回溯矩阵在常见的情况下，短的比对。FastZ我们观察到，回溯状态只需要最佳的对齐，而不是更大的对齐搜索空间。因此，检查器省略回溯状态跟踪以使其轻量化，但有一个例外（接下来是省略DP矩阵分配）。因此，检查器不仅消除了不必要的存储器访问，而且还减少了存储器占用，从而实现更多的并行性（即，更多线程）。例外是极短对齐的常见情况（例如，16个碱基对或更少的长度），其中执行者执行有限的、急切的回溯以完全消除执行者。早期回溯消除了执行器大约80%的DP计算。此外，回溯状态足够小（例如，限制为16x16），以适应GPU使用来自检查器的最佳对齐信息，FastZ使用执行器修剪来计算DP矩阵，并仅对小得多的最佳对齐进行回溯。如上所述，DP矩阵分数仅暂时需要用于计算其他矩阵元素。因此，FastZ通过使用循环使用和丢弃缓冲方案，通过使用循环模式中的两个先前对角线中的值来产生一个对角线的值，从而显著减少了DP矩阵存储器流量此外，三对角状态足够小，可以保存在寄存器中，从而消除了绝大多数（97%）的内存访问，····3DP评分矩阵的任何动态内存分配这种优化在检查器和执行器中都有使用。最后，由于对齐长度的变化，在同一GPU内核中混合短对齐与长对齐导致负载不平衡和利用不足。FastZ根据对齐长度（从检查器中已知）将种子扩展任务分组到大小箱中，以减轻这种负载不平衡。我们在Nvidia的RTX 3080（Ampere），QV100（Volta），Titan X（Pascal）GPU上实现和评估FastZ我们的实现产生了与NIH的缺口LASTZ相同（或偶尔更长）的比对FastZ和我们的LASTZ多核实现不需要定制硬件，分别比（顺序）LASTZ实现了111倍和20倍的加速2背景和影响FASTZ全基因组比对通常作为三阶段计算进行在第一阶段，轻量级精确匹配搜索识别短序列（19个碱基对长）作为种子位点。由于种子搜索导致大量种子，第二阶段过滤种子站点以获得较短的有希望的种子站点列表最后，第三阶段使用Smith-Waterman动态规划（DP）算法扩展过滤的种子位点，以进行具有仿射空位罚分的序列比对[9]。2.1基线LASTZ优化LASTZ支持在最后阶段，两个版本都使用带间隙的扩展。然而，在无空位过滤中，许多导致高分比对的种子可能会被丢弃，导致灵敏度降低，这也是在其他工作中认识到的[37]。为了简洁起见，我们将具有无空位过滤的LASTZ称为更敏感的、有空位的版本因其更高质量的结果（更多、更长、更高评分的比对）而优选，图2通过比较LASTZ的无缺口和有缺口变体在比较C的序列时发现的比对来说明这种权衡。 elegans和C. brig-gsae基因组，每个基因组包含一百万个种子。基于比对长度（以碱基对数计，X轴）和比对分数（Y轴），每个比对在散点图中显示为点缺口版本找到更多、更长、更高评分的比对，如图中可见。例如，空位版本发现得分超过10，000的比对是无空位版本的两倍多（41对17）。最近提出的SegAlign [8]作为过滤的一部分加速了无间隙的延伸，而FastZ加速了高质量比对的有间隙的版本在LASTZ的间隙版本中，这是一个顺序实现，超过99%的时间花在DP组件上，其中1%用于回溯分析。例如，我们分析了第一条染色体的排列，C. elegans和C. Briggsae使用LASTZ（没有无间隙过滤的高灵敏度变体），使用AMD µ Prof v3.4分析器。我们图2：空位与非空位比对发现执行DP计算的一个函数（ydrop_one_sided_align）占执行时间的99.75%以上因此，DP组件是我们的重点。LASTZ的间隙Smith-Waterman的默认操作在可能的情况下，LASTZ减少了计算工作，而不影响对齐的质量或长度图3（a）示出了DP评分矩阵作为评分热图的操作（较暗的阴影意味着较高的评分），其中仅探索了完整矩阵的一部分在水平维度（沿着行）评估矩阵时，如果单元格的分数低于阈值（相对于最高观察分数），则修剪该行上的其余单元格在垂直维度中，如果一行的所有分数都低于阈值，则后续行探索也被修剪。虽然在y-丢弃算法中捕获的对后面的单元的这种修剪基本上依赖于LASTZ此外，在过滤阶段，Darwin-WGA采用了基于Banded Smith-Waterman [7]的启发式算法，该算法将搜索空间限制在固定宽度的对角线周围的有界带内，在该区域可能找到最佳比对。许多插入和删除意味着偏离对角线，这可能是次优的。然而，最优解可能并不总是在带内找到 在本文中，我们追求的是最优解，而不是潜在的次优带状方法（在第3.4节中解释）。此外，LASTZ在达到先前发现的比对时终止正在进行的种子延伸，因为组合先前和当前比对是无利可图的因为这种工作减少也依赖于LASTZ在比对搜索结束后，回溯阶段计算来自最高得分单元的比对（包括空位），如图3（b）所示。因此，回溯空间比全搜索空间小得多。FastZ在其检查器-执行器方法中利用了这一差异。·4×(a)比对搜索：得分热图（b）最高得分比对ment图3：Smith-Waterman操作2.2记忆的有界性、重复性和重复性从图1所示的带间隙的史密斯-沃特曼递归式中，我们得到了四个关键的观察结果。(1) 在单个种子扩展中，考虑DP矩阵的任意单元（比如i，j）的 如图1所示。该操作需要对先前计算的单元进行五次存储器读取、五次加法和四次比较（对于图1中的max运算符）以及三次存储器写入（访问Si， j、Ii， j、Di， j评分矩阵）。此外，为了最终通过回溯重建对齐，每个矩阵中的回溯指针有三个额外的写入。计算操作的存储器访问（9）与存储器访问（11）的总体比率小于1。因此，工作负载变得内存受限，具有更多的并行性;除非内存带宽瓶颈得到改善，否则计算加速不会提供任何进一步的加速。(2) 在扩展单个种子时，（种子内并行性）沿着对角线分布（图1）。 如第1节中所讨论的，沿着对角线的不规则访问是已知的问题，对于该问题，存在DP矩阵的公知数据布局变换以使访问连续（例如，[38]）。布局变换提供矩阵单元的原始i， j坐标到新i′， j′坐标的一对一映射，使得原始沿反方向的元素被重新映射到对角线位于变换坐标系中的行上例如，图4显示了使用i′=i的这种转换+j和j′=j作为变换函数。沿着逻辑DP矩阵中的反对角线的位置（参见图4中的阴影单元）的并行访问在变换后的布局中在物理上连续的行中（并且因此可以在现代GPU上合并）。这种转换后的布局需要在角落中进行一些填充，这会导致内存占用增加。然而，内存的小幅增加这种转换对于性能来说是必要的，但远远不够。(3) 虽然足迹乍一看似乎很大（分别用于长度为M和N的序列的M N矩阵），但DP矩阵中的浅依赖性确保仅需要保留DP矩阵的一小部分。例如，在图1中，当计算深色阴影单元时，只需要两个相邻的对角线（浅色阴影）。FastZ通过寄存器内的循环使用和丢弃缓冲来利用这一观察结果，以消除大多数内存访问。图4：改进内存行为的转换布局(4) 必须保留回溯指针以重建对齐。然而，FastZFastZ2.3以前的工作Darwin-WGA [37]是一种ASIC加速器设计，采用特殊的脉动阵列来利用沿DP矩阵对角线的并行性。另一方面，FastZ采用先前提出的数据布局转换来实现对现成GPU的合并访问。Darwin-WGA使用硬件加速进行种子过滤、带状对齐和回溯。特别是对于条带比对，Darwin-WGA使用基于条带Smith-Waterman的启发式方法[7]。相比之下，FastZ使用精确过滤，我们将在3.4节中讨论。最后，Darwin-WGA使用硬件分块（从Darwin [36]继承），其中除了分块间重叠区域之外，评分矩阵不溢出到存储器，这降低了存储器带宽需求。通过使用固定的硬件瓦片，Darwin-WGA避免了加速器中的存储器分配，而主机可以处理重叠区域的分配。相反，FastZ采用循环使用和丢弃来省略对DP得分矩阵的大多数存储器访问并且省略检查器中的回溯。Darwin-WGA先前计算的种子扩展的最终输出）在LASTZ中顺序确定，但在Darwin-WGA和FastZ中同时确定。相反，Darwin-WGA通过一些基于分数的算法来实现工作减少相比之下，FastZ放弃了一些工作减少，以避免更改对齐边界，同时仍然实现显着的加速。已经提出了用于单个Smith-Waterman DP计算的GPU加速[38]。然而，WGA问题由数百万个DP计算实例组成（每个种子扩展一个）。以前的工作利用有限的单问题并行性5×而FastZ专注于重要的多问题并行性。3FASTZWGA算法中使用的传统一遍执行与GPU的交互很差，因为对齐长度分布很广一方面，为最坏情况的对齐长度分配内存会降低并行性，因为可用内存中可以容纳更少的种子扩展。另一方面，GPU上的动态内存分配很慢[12，18，23，35，40]。为了解决这个问题，FastZ用两遍检查器-执行器方法取代了一遍方法[30]。FastZ自己的并发症。第一个目标是将功能拆分到一个轻量级检查器中，该检查器收集运行时信息，以显著减少后续执行器阶段的工作量和内存占用。第二个目标是提高GPU内存性能并最大限度地提高并行性，同时在GPU的内存占用和带宽限制内运行本节的其余部分将介绍FastZ3.1FastZ的检查执行器设计回想2.1节，比对在短比对周围搜索大的搜索空间，以确保附近的高分比对不被错过。回想一下，图3（a）将分数显示检查器探索更大的搜索空间，以找到得分最高的单元（图3（a）中的黑色单元）。然后执行器执行一个完整的计算，直到（并包括）最高得分的单元，但完全避免了在搜索空间的其余部分的计算，如图3（b）所示。FastZ3.1.1探长 为了使Inspector更加轻量化，FastZ降低了Inspector的内存带宽需求和占用空间，从而通过支持更多并发DP问题间接提高了并行性。具体地说，检查器将捕获回溯状态的繁重工作留给了执行器，只有一个例外（下面解释）。这个轻量级检查器是我们的第一个贡献。检查员精确地识别产生最佳对准的DP矩阵单元。这些信息对执行者来说至关重要在检查器中，FastZ将单个种子扩展DP任务分配给扭曲。扭曲内的通道有效地计算沿着DP矩阵对角线的独立单元然而，由于对角线布局变换，对角线的元素是连续的（见2.2节）。虽然这种DP内并行性的程度（特别是对于短对齐的常见情况）低于GPU可以利用的程度，但是高得多的DP间并行性的程度足以使GPU保持忙碌（例如，一百万种子扩展）。因此，多个种子扩展（DP问题）同时运行（作为线程块以及多个线程块内的线程束）以利用GPU多线程。这个简单的策略捕获DP内和DP间的问题并行性。通过从检查员获得的对齐长度对DP问题进行分箱的负载平衡优化仅适用于执行者而非检查员。幸运的是，因为检查员是轻量级的，负载不平衡在检查器中远没有那么严重，并且通过众所周知的技术（如CUDA流）进一步缓解[25]。3.1.2在常见情况下，通过急切回溯避免执行器冗余尽管检查器-执行器方法在减少不必要的内存流量和增加并行性方面很有吸引力，但该方法确实会为每个种子扩展带来冗余计算为了在不恶化内存流量的情况下最小化冗余，FastZ完全消除了执行器，在常见的情况下，通过在执行器中进行有限的、急切的回溯来进行非常短的对齐这个检查员回溯异常是我们的第二个贡献。为了实现这种追溯，FastZ增强了检查器，以跟踪一个小的（16 16）追溯矩阵。任何极短的对齐的有限情况，完全落在这个范围内，可以立即执行回溯;从而完全避免执行器。超出此范围的对齐将在执行器阶段重新评估人们可能会认为，这种技术捕获的短比对是无趣的，因为它们无论如何都是低评分比对。然而，LASTZ和FastZ在将两者结合用于最终扩展之前分别执行任何种子站点的因此，不能先验地消除短的左（右）比对，因为它可能在组合之后产生高得分的最终比对。早期回溯由于其高收益和低成本而特别有吸引力。好处很高，因为绝大多数种子扩展（>80%）都很短，避免了执行器中的冗余成本很低，因为16x16回溯状态足够小，可以放入GPU的L1缓存（或共享内存）中因此，检查器3.1.3执行人FastZ采用执行器修剪，其中，使用最佳比对的精确信息，执行器计算DP矩阵并仅针对短得多的最佳比对而不是在检查器中探索的较大搜索空间跟踪回溯信息（我们的第三个贡献）。回溯状态本身与评分矩阵相比相形见绌。因此，人们可能会认为这种改善是微不足道的。然而，FastZ也减少了对检查器和执行器中的得分矩阵的内存访问，正如我们在下一小节中讨论的那样。检查员信息的另一个好处达到所需的精确尺寸。因为大多数种子扩展都很小，所以执行器实现了内存占用的巨大减少。更重要的是，考虑到GPU上的内存有限，精确的分配使FastZ能够将更多的种子扩展打包到一个内核中，从而最大限度地提高并行性。执行器阶段继承了检查器每个经线一个种子延伸然而，主要由于回溯状态不是由检查器而是由执行器捕获，所以存在关键的差异我们现在关注回溯状态。追溯状态记录了每个单元格的选择在DP计算期间，写回溯状态，但从不读回溯状态。为了最小化写入回溯数据的写入存储器带宽需求（在回溯数据不能像评分数据那样被丢弃的约束内），FastZ采用了两个进一步的优化。6××首先，我们观察到任何给定DP矩阵的回溯数据追溯数据记录了各种评分选择中最大值的标识（参见图1）。矩阵I、D和S的递归分别在2、2和3个选择中选择最大值，这可以分别使用1、1和2位来由于现代系统不允许子字节访问，我们将所有三个评分矩阵的跟踪状态压缩到一个字节中。其次，为了实现跟踪写回的缓存块级聚合，我们合并多个单元的跟踪以填充共享存储器中的缓存块，该缓存块在一次写入中写入存储器。虽然简单地写入L1缓存也可以实现这种合并，但GPUFastZ回溯性记忆。 尽管很小（小于1%），但回溯可以将FastZ的净加速比限制为50（Amdahl定律限制，假设除了回溯之外，主DP计算的加速比约为100倍）。事实上，由于FastZ将DP计算速度提高了100倍，Amdahl与DP计算不同，给定种子扩展的回溯没有内部并行性。因此，唯一可用的并行性是种子间并行性考虑到FastZ通过这种结构，FastZ有效地利用了种子间回溯并行性，这是通过多线程和在不同SM上执行来捕获的由于每个SM存在多个线程束，因此多线程的程度（以及由此产生的延迟隐藏）与DP计算的程度保持相同。有人可能会认为，曲速内并行性的丧失是回溯的一个然而，回溯并行化的目的仅仅是将Amdahl定律限制推对于这个有限的目的，完全多线程SM间并行性（可以从Titan X（Pascal）上的28路，RTX 3080（Ampere）上的68路到Volta（QV100）上的80路变化）已经足够了。当并行化28路时，1%的组件3.2最大限度地减少内存带宽需求，循环丢弃理想情况下，我们希望尽量减少将DP分数写回内存。回想一下2.2节，实时状态仅限于数据的三个连续对角线，因为每当矩阵中的一个对角线单元被完全计算时，就不会再使用位于前三个对角线及以上的单元由于大矩阵的类似扫描的访问模式，活动状态限于DP矩阵数据的三个对角线不足以避免严重的高速缓存污染在并行执行多个问题时，扫描的数量会被放大;大量的大型扫描会导致不必要的内存溢出（和重新加载）为了解决这个问题，FastZ使用了循环使用和丢弃缓冲区，可以保存DP矩阵的三个对角线，如图5所示（我们的第四个贡献）。在图5：FastZ如图5所示，原始DP矩阵对角线已被转换为如图4所示的行，但被转置为列以匹配熟悉的DP行优先遍历。FastZ通过在计算新对角线时丢弃（并因此丢弃）最旧的对角线来循环因为即使对于最终解决方案也不需要分数（只记住最大分数的位置），FastZ对检查器和执行器阶段都使用循环使用和丢弃优化。对于执行器，消除评分矩阵写入将内存带宽需求降低了92%。（剩余的- ING 8%占追溯状态，其必须被写回到存储器以便重建对齐。FastZ因为FastZ只并行化给定DP矩阵计算的一个经线宽度的条带（第3.1.1节），所以循环缓冲区一次保存三个原始对角线的经线宽度的条带（图5）。因此，必须解决条带边界问题。具体而言，不能丢弃条带的边界单元，因为它们保持着当计算进行到对角线中的下一个条带时将需要的活动状态因此，必须保留状态并将其写出到存储器中，以便稍后重新加载其他非边界小区可以被丢弃。因为这样的边界条件仅影响在扭曲中处理的32个单元中的一个单元，所以带宽减少实际上大于96%（=31/32）。我们将GPU共享内存和GPU寄存器视为循环使用和丢弃缓冲区的物理位置。可以在单个流式多处理器（SM）上调度的所有线程的三个对角线的聚合状态超过当前GPU的共享存储器容量。例如，2个线程块，每个线程块具有32个线程的64个线程束，每个线程束需要36个字节（3个分数，每个分数为4个字节），对应于144 KB的共享存储器存储。相比之下，每个线程36字节的存储可以很容易地容纳在每个CUDA线程的寄存器空间中。最后，我们的并行化要求线程束中的每个线程访问其他线程（相邻DP矩阵）产生的活动状态7单元），这在使用线程私有寄存器时可能是一个挑战幸运的是，CUDA包括细粒度的寄存器交换指令，允许必要的跨线程通信。因此，FastZ在寄存器中包含循环使用和丢弃缓冲区3.3通过检查员确定的对齐长度分组实现负载平衡除了优化内存流量外，FastZ还利用来自检查器的信息来实现GPU上的负载平衡（我们的第五个配置）。GPU的批量同步方法（其中内核仅在所有SM上的线程块完成时才因此，FastZ使用比对长度的精确知识（来自检查器）来按长度对种子延伸进行FastZ将每个bin中的我们使用四个箱，箱边界分别为512x512、2048x2048、8192x8192和32，768x32，768在DP矩阵单元i， j处找到的最佳对准被放置在其中包含对准的最小仓我们的基准测试不需要更大的bin，但是如果需要的话，可以使用类似的4x缩放因子添加bin。3.4执行如果不仔细调整，GPU性能可能会很脆弱为此，FastZ采用了其他众所周知的优化。溪流。 如第3.1节所述，即使在检查器中，每个种子扩展也需要可变的时间。（由于对齐长度未知，因此无法在检查器阶段使用长度分箱优化。）为了实现线程块到SM的良好调度，我们使用CUDA流[25]。每个流并行实现中的工作减少。回想一下第2.1节，LASTZ执行两个工作减少优化：（1）当沿着行或列的分数低于阈值时进行修剪，以及（2）在达到先前比对时终止对于第一个优化，因为FastZ不能使用在没有显著通信开销的情况下同时产生的分数信息，所以FastZ以一些额外的工作为代价沿着行或列使用先前完成的分数（如果完成的分数已经低于阈值，则停止探索是安全的）。虽然保守，这种近似实现良好的修剪。LASTZ因此，FastZ中的每个种子扩展（如Darwin-WGA中的那些）仅使用不依赖于其他比对的基于分数的工作减少。种子间并行的好处超过了工作减少的适度损失因此，FastZ探索与LASTZ相同或严格的碱基对超集，导致相同或偶尔更长的比对（所有基准中最多0.005%的比对，中值长度增加5.5倍）。控制发散。递归计算使用max运算符，该运算符使用数据相关分支指令实现，可能导致控制流发散。然而，控制表1：基因组通用名称物种碱基对线虫C.秀丽隐杆线虫（chr1）C. Briggsae（chr1）15,072,43415,455,979C.秀丽隐杆线虫（chr2）15,279,421C.布里格塞（chr2）16,627,154C.秀丽隐杆线虫（chr3）13,783,801C. Briggsae（chr3）14,578,851C.秀丽隐杆线虫（chr4）17,493,829C. Briggsae（chr4）17,485,439C.秀丽隐杆线虫（chr5）20,924,180C. Briggsae（chr5）19,495,157果蝇D.黑腹肌（chr2R）25,286,936D.拟暗细胞（chr2）30,794,189A. 白蛉12,318,379蚊子A.小萎缩A.冈比亚（chrX）17,503,69724,393,108图6：用于全基因组比对的发散仅限于几条路径，每条路径仅具有几个指令。例如，计算两个操作数的最大值（对于I和D矩阵）需要至多两个控制路径，每个控制路径仅具有几个指令（例如，2-4）。即使SIMT执行必须执行所有可能的控制路径，开销也是有限的。我们在CUDA中实现了FastZ作为LASTZ推出的内核在我们的原型中，LASTZ识别由FastZ扩展的种子。我们通过比较未修改的LASTZ的比对与我们的比对来确保正确性多核实施。作为比较，我们还开发了一个LASTZ的变体，它利用了多核上的多进程并行性.我们的实现对种子集进行分区，每个分区在一个顺序进程中运行。FastZFastZFastZ最后，FastZ使用大小分仓来缓解GPU中的内核内负载不平衡，这在多核中是不存在的即使是众所周知的布局变换（图4）也与多核无关，多核不具有SIMT不需要反对角并行）。4方法基因组和成对比对：在我们的评估中，我们使用了表1中所示的七个物种的基因组，包括两种线虫、两种果蝇和三种蚊子。表1包括了每个物种基因组中特定染色体的碱基对数量。如图6所示，当我们在C. elegans和C. briggsae，我们从果蝇和蚊子的基因组中选择单个染色体对进行比对。8图7：FastZ性能我们使用图6中所示的配对标签来指代被比对的特定染色体对。例如，将C. elegans和C. Briggsae基因组标记为C11，1。类似地，我们进行总共九次成对比对-线虫之间的五次（C1，j，其中j = 1. 5），果蝇（D12R， 2）和蚊子（A1X， X，A2X， X和A3X， X）中的一个为了实现可管理的运行时间的顺序版本，我们报告的性能种子扩展为一百万种子网站。我们从整个染色体中随机选择一个种子位点，并使用所选种子位点附近的一百万个种子位点这种选择保留了种子点密度，使LASTZ最大限度地受益于其减少工作的优化（2.1节）。基线测试：当我们将FastZ与公开的LASTZ顺序版本进行比较时，我们还将基于多进程的多核实现和GPU实现纳入比较中。我们的多核版本使用粗粒度，种子间并行跨核心;每个进程执行LASTZ 我们还开发了一个GPU实现的冯等人。 方案[38]用于利用种子内并行性的单个Smith Waterman计算（第2.3节）。 GPU实现（1）利用数据布局转换来改进内存合并行为，以及（2）使用跨线程束的同步来保持对角到对角依赖性。所有基于GPU的实现都使用CUDA 11.0版本。FastZ性能：FastZ 执行器使用四个bin进行负载平衡，如3.3节所述。评估平台：我们在三种GPU上评估FastZ：（1）具有28个流多处理器（SM）和12 GB内存的Nvidia Titan X（Pascal）GPU，（2）具有80个SM和32 GB内存的V100 GPU，以及（3）具有 68个 SM和10 GB内存的 RTX 3080（ Ampere）GPU。我们还在AMD Ryzen 3950x上评估LASTZ（原始顺序版本和我们的多进程版本），该AMD Ryzen 3950x具有16个高性能内核和32 GB内存。5结果5.1性能图7显示了每个基准测试（X轴上的条形组）在顺序LASTZ基线（Y轴）上的加速。此外，最右边的一组条形图显示了所有基准测试的平均加速比。基准测试从左到右按负载平衡bin4计数递减的顺序排列（表2，稍后讨论在每组中，各个条形图（从左到右）显示了GPU基线（第2.3节中描述的并行化单个Smith Waterman DP [38]）在三种GPU配置（Pascal，Volta和Ampere），32进程多核配置以及最后FastZ在三种GPU上实现的加速比。前三条（Pascal、Volta和Ampere GPU上的GPU基线）几乎不可见，因为基线在所有基准测试中相对于顺序LASTZ实现了减速（慢18%至43%GPU基线具有32个进程并行性的多核配置在所有基准测试中实现了20倍的平均加速（单个基准测试的加速相似）。虽然种子扩展可以在32个进程中三重并行化，但由于存储器带宽限制，加速不会线性地扩展到32倍。回想一下第3. 4节，多核无法从FastZ的创新中受益FastZ在所有基准测试中都实现了显著更高的加速比，在Pascal、Volta和Ampere一代GPU上的总体平均加速比分别为43倍、93倍和111倍。趋势表明，加速比更高的新一代GPU。特别是Pas- cal一代TitanX GPU也受到其较少SM（28）的阻碍，而Volta V100（80）和Ampere RTX 3080（68）GPU的SM明显更多。此外，为了正确看待FastZ而gpu9表2：100万个种子的比对长度分布基准渴望回溯箱1234C15， 577645322266365120825C12， 277177622721181018716C11， 1757731240979110117712C13， 3764269234331122516510C14， 47592402400406031143A1X， X816817182879240622A2X， X814634185014300502A3X， X819519179978426761D12R， 28125781874081310具有更多的内存带宽，FastZ削减了带宽需求，不使用GPU最后，对于一个给定的GPU，FastZ此外，更短的对齐会导致更高的加速比，因为更短的对齐自然会在检查器中引起更少的负载不平衡，这会支配FastZ5.2执行时间分解图8显示了FastZ在Ampere GPU上的基准测试（X轴）的标准化执行时间（Y轴，堆叠条）的分解对于每个基准，执行时间被分解为三个部分：检查者、执行者和其他。正如预期的那样，in-spector是最大的组件，占大多数基准测试的执行时间的三分之二（高达79%）。遗嘱执行人所占比例较小（约10%）。虽然执行者比检查器更重要，但它只对一小部分种子扩展问题有效，这些问题在快速回溯中幸存下来。最后，剩余部分（图8中的其他部分）负责其他工作，例如读取锚点、序列文件、分配内存、将所有这些复制到GPU、读取最终比对、基于比对长度将锚点分类到bin中请注意，对于顺序LASTZ，另一个分量的分数要小得多。只有在FastZ各个基准测试之间执行时间分解的差异完全可以由图7表2显示了每个基准中我们的100万个种子的比对长度分布。根据我们在3.3节中的负载平衡箱对长度进行分组：在急切回溯中最多16个碱基对，在箱1中16-512个碱基对，在箱2中512- 2K个碱基对，在箱3中2K-8 K个碱基对，在箱4中该表显示75-80%的比对是16个碱基对或更少。绝大多数剩余的比对都落在bin 1内。其余的箱子都很小。然而，bin4 D 1 2 R，2），图8中的检查器和执行器运行时组件越小，检查器负载不平衡越低，图7中的基准加速就越高。图8：执行时间分解（Ampere GPU）5.3隔离FastZ优化的影响图9隔离了FastZ的各个优化的影响。为此，我们从FastZ的一个变体开始，它使用检查器-执行者的方法与长度分箱负载平衡和轻量级检查器。我们不包括排除负载平衡的配置，这不仅会导致负载不平衡，而且会导致在没有每个bin分配的情况下每个问题的内存分配然后，我们逐步添加一个接一个的循环使用和丢弃缓冲区管理，短对齐的渴望追溯和执行器修剪。最后，我们还隔离了CUDA流的影响。图9显示了我们的三个GPU（X轴，条组）的这些渐进组合方案（X轴，单个条）的加速（Y轴）。优化的逐步添加意味着图9中的任何条都包括其左侧条的所有优化（在同一组内）。所有优化的倒数第二个栏是FastZ。为了隔离流的影响，最后一个条形图显示FastZ使用单个CUDA流（FastZ-单流），而前面所有的条形图都使用32个流。对于每个GPU，我们显示了所有基准测试的平均加速比，因为每个单独的基准测试的结果在质量上是相似的在每一种情况下，以下共同意见都成立。首先，FastZ其次，每一次优化都是有价值的。循环使用和丢弃缓冲区（绿色条）的添加分别将Pascal，Volta和Ampere架构的加速提高到4.7倍，6.1倍和17倍种子扩展的最佳对齐位于16x16 DP矩阵内，其快速回溯进一步将Pascal、Volta和Ampere GPU的性能分别提升至15倍、21倍和46倍倒数第二条添加了执行器修剪，其中执行器根据检查员对最佳对齐的了解修剪自己的执行足迹最后，在Pascal、Volta和Ampere GPU上，使用单个流分别将平均性能降低了1.7倍、1.7倍和2.4倍因为我们逐步添加了FastZ10××图9：隔离FastZ优化的影响图10：用于全基因组比对的跨属对在更大基础上的改进会产生一种光学错觉，即后期优化提供了更高的加速比（例如，50倍到100倍的跳跃在视觉上看起来比2倍到4倍的跳跃大，即使在两种情况下的分析相对加速比，我们发现没有一个单一的