GPU并行高性能过滤器设计

160→→××−∈−GPU的高性能过滤器Hunter McCoy犹他大学美国hunter@cs.utah.edu史蒂文·霍夫迈尔劳伦斯伯克利国家实验室美国shofmeyr@lbl.gov凯瑟琳·耶利克大学美国加州伯克利yelick@berkeley.edu犹他大学Prashant Pandey美国pandey@cs.utah.edu摘要过滤器近似存储一组项目，同时权衡空间效率的准确性，并可以解决加速器（如GPU）上然而，由于过滤器研究的大多数进展都集中在CPU上，因此缺乏高性能和功能丰富的GPU过滤器。在本文中，我们将探索滤波器的设计空间，目标是为GPU开发大规模并行、高性能和功能丰富的滤波器。 我们从性能、可用性和支持的功能方面评估了各种滤波器设计，并确定了两种滤波器设计，它们在性能、功能和可用性方面提供了正确的权衡。我们提出了两个新的基于GPU的过滤器，TCF和GQF，可以在各种高性能的数据分析应用。TCF是一个集合成员过滤器，支持更快的插入和查询，而GQF支持计数，这需要额外的性能成本。GQF和TCF都提供点和批量插入API，旨在利用GPU中的大量并行性，而不会牺牲可用性和必要的功能。 TCF和GQF最高可达4。4和1。4比我们基准测试中以前的GPU过滤器更快，同时克服了当前GPU过滤器在性能和可用性方面的基本限制CCS概念：·计算理论数据结构设计和分析;·软件及其工程并行编程语言;并行程序设计语法结构1介绍随着科学和商业数据集在数量和数据速率上的爆炸式增长，一些高性能数据分析管道利用GPU的大规模并行性和高级计算架构。GPU已被证明是机器学习的有效加速器，本作品采用知识共享署名国际4.0许可协议进行许可PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577507模拟问题[1，39]，数据库引擎[10，11，33，51，55，56]和大规模基因组学管道[6，25，27，30，54]。在本文中，我们考虑在过滤中使用GPU，这是许多数据处理和分析管道中的关键操作之一GPU既为性能改进提供了机会，也为数据分析带来了挑战，因为有限的GPU内存可用。过滤器，如Bloom [7]，商[4，19，20，38，44，46]和布谷鸟过滤器[9，21]，保持一个集合或多集合1的近似表示。近似表示通过允许查询偶尔返回误报来节省空间。 对于一个给定的假阳性率 ：一个成员资格查询的过滤器为集���返回存在的任何��� ，并返回缺席的概率至少为���1的任何���一个。大小集的筛选器���使用的空间取决于���和���，但比显式存储的所有项小得多 。鉴于滤波器的普及和广泛影响，在过去十年中有许多论文推进了滤波器的理论和实践[2，4，8，9，12，1744、46、52、53]。这些论文中的大多数都集中在提高空间使用和性能方面的最新技术水平。 一些论文还探索了在过滤器中添加新功能，例如删除，将小值与哈希值相关联，以及计数，这些在许多应用程序中至关重要[4，21，44，46]。然而，在为GPU构建快速、节省空间和功能丰富的过滤器方面的工作很少Costa等[17]和Iacob et al.[28]展示了如何在GPU上构建和查询Bloom过滤器Geil等人[24]首先展示了如何使用批量构建API在GPU上构建和查询商过滤器这些过滤器实现提供次优性能，不提供空间使用和误报率权衡方面的选择，并且没有足够的API集成到许多数据分析应用程序中。此外，这些实现不支持关键功能，如删除、计数或将值与项相关联，这些功能是现代应用程序所需要的[40，43，45]。 由于缺乏可用选项，现代GPU加速应用程序通常会绕过过滤器的限制，1计数筛选器维护多集中项的计数估计值。 计数滤波器可以具有错误率 。返回true的概率至少为1 。每当查询返回错误计数时，它必须始终大于真实计数。计数过滤器不像计数草图那样提供对高估的保证。我们建议读者参考Goswami等人[26]的论文进行详细比较。161×××PPoPP导致资源的次优使用，并进一步阻碍它们对更大数据集的可扩展性例如，MetaHipMer [25，27]是一种极端规模的从头宏基因组组装器，它利用GPU来加速原始数据处理，并设计用于扩展到数千个节点来处理TB规模的数据。MetaHipMer需要一个过滤器，它可以将指纹映射到小值，以在原始数据处理过程中清除单例，并在管道的后期阶段使用输出 它不能使用布隆过滤器，因为布隆过滤器不支持将小值与项关联。类似于布隆过滤器，Geiletal。s [24]商过滤器（SQF）无法关联值。此外，SQF只能扩展到几百万个，并且在空间使用和误报率方面不能进行权衡类似地，许多利用GPU来加速合并和连接操作的数据库引擎[31，32，55]不能使用现有的过滤器，因为它们不支持合并和连接操作所需的项的计数和枚举。为GPU设计过滤器需要一系列独特的挑战GPU的体系结构最初设计用于加速渲染操作，以有限的内存、更简单的指令和同步工具为代价提供了大量并行性。CPU和GPU之间架构的差异导致为CPU设计的过滤器在直接移植到GPU时通常具有次优性能。线程争用和颠簸通常是GPU数据结构的问题，即使是那些具有大尺寸的数据结构。此外，将线程分组为线程束是设计上的另一个约束，分组访问模式比简单的实现提供了巨大的速度提升许多现有过滤器的随机访问模式放大了这个问题，因为线程束中的线程可能会在整个过滤器中随机访问内存位置时发散。我们的贡献。在本文中，我们探索了过滤器的设计空间，并确定了可以利用GPU上的大规模并行性而不会引入基本功能限制并放弃性能和可用性的设计。我们确定了两个滤波器的设计，提供适当的权衡性能和必要的功能。在此基础上，我们开发并评估了两种新的GPU过滤器：二选过滤器（TCF）和基于GPU的计数条件过滤器（GQF）。TCF不支持计数，这可以实现更快的插入和查询，而GQF支持计数，但会增加性能成本。这两个过滤器都支持删除和关联小值与指纹。TCF旨在将指纹组织成大小为以适应GPU缓存行。它使用Cuda协作组在这些块内执行插入，查询和删除操作，以实现无争用的大规模并行性TCF还使用了二次选择幂（POTC）散列[3]来最大限度地减少固定大小块之间的负载不平衡，并实现高负载因子。然而，TCF中的块大小小于CPU过滤器中使用的块大小[46]。这导致导致块之间的负载变化增加，从而导致最大可实现负载因子较低。为了克服这个问题，TCF使用后备存储器来实现高负载因子。 据我们所知，TCF是第一个使用后备存储器的滤波器设计。TCF以正确的方式结合了POTC哈希、后备存储和协作组，并展示了一种新的算法范例，以实现稳定的过滤器设计。TCF剥离了计数的能力，以支持更快的插入和查询操作。 TCF提供并发插入和查询以及批量插入API。TCF可以近似地表示一组项，并支持删除、枚举和将小值与项关联。GQF是计数商滤波器的GPU优化实现[43]。 GQF旨在克服早期在GPU上实现商过滤器[24]的基本限制，例如仅支持固定的假阳性率和仅扩展到数百万项。GQF提供了现代数据分析应用所需的所有功能，例如，更好的空间精度折衷、计数、删除、将值与项相关联以及可重新调整大小。此外，它还提供并发插入和查询以及批量插入API，这与早期基于GPU的过滤器实现不同。GQF展示了一种新的协调无锁实现批量插入。无锁实现将过滤器划分为独占访问的奇偶区域，并将线程内部的线程分配给固定的内存区域，以实现低线程发散并避免颠簸。我们相信，我们用于批量插入的奇偶方案也可以应用于其他基于线性探测的哈希表，以加速插入[41]，也可以用于在GPU上存储动态图[47，49]。我们的成果。 TCF和GQF提供了更好的（在某些情况下高达三个或多个量级）性能，并且比GPU上的其他过滤器使用更少或相似的空间，提供更小的功能集。1. 点TCF最高为4。插入和查询比所有支持删除的过滤器快452. GQF最高为1。93和2。4比基于GPU的Bloom过滤器分别快插入和查询。3. 批量TCF实现了3. 在NVIDIA A100 GPU上每秒处理40亿个项目。4. 批量TCF实现了Blocked Bloom过滤器的70%的插入吞吐量，而误报率只有Blocked Bloom过滤器的一半5. 对于删除，TCF比所有其他过滤器快一个数量级6. GQF支持模拟和真实世界数据集的高吞吐量计数（800+百万/秒）162. Σ×不超过（+/）（） （）（/）| |（）（/）+（）下一页（）（/）≈GPU的高性能滤波器PPoPP2过滤器简史在本文中，我们考虑动态过滤器，因为它们在数据分析中有广泛的应用。 动态过滤器近似表示一组在构造之前不需要知道的项。 动态过滤器在过去的几十年里取得了更大的进步，因为应用程序通常不知道预先的项目集。 动态过滤器的示例是布隆过滤器[7]、商过滤器[5，19，20，38，45]、和布谷鸟过滤器[9，21]。布隆过滤器消耗loglog1 空间，大约是log1。44倍以上的下限���[13]第十三章. 相比之下，对于从全 ������域取的一个集合，其中，无错误字典需要ΩlogΩ log bits。Bloom过滤器在插入和肯定查询也会导致log 1的缓存行丢失，从而使它们的插入和查询性能很差Blocked Bloom filter [52] 通 过 构 建 一 系 列 较小的Bloom filter来克服Bloomfilter的缓存局部性差，每个Bloomfilter都足够小，可以容纳少量的缓存行。 第一散列函数用于选择块，其余散列函数用于设置/测试块内的位。然而，缓存效率是以较高的误报率为代价的。与Bloom过滤器相比，Blocked Bloom过滤器在理论上和经验上具有更高的误报率（高达5）。FP率的经验计算见表2。商过滤器[4，15，19，38，44，46]表示通过罗宾汉散列[14]压缩存储集合中项目商过滤器使用1。053 2. 每个元素125 log 2 1 位，这小于布隆过滤器每当 1 64时的情况，这在几乎所有应用中都是这种情况。它支持插入、删除、查找、删除和合并。计数商过滤器（CQF）[44]改进了quotient过滤器的性能，并添加了可变大小的计数器，以使用渐进最优空间对项目进行计数，即使在大型和偏斜的数据集中也是如此。 在计数商过滤器中，我们还可以通过重新利用可变大小的计数器[40]来存储值或通过在表[48]中显式地存储小值来将小值与项相关联。布谷鸟过滤器[9，21]也将小指纹完整地存储在表中。然而，与使用罗宾汉散列的商过滤器不同，布谷鸟过滤器使用布谷鸟散列来解决指纹之间的冲突。布谷鸟散列法使用踢（或布谷鸟），当桶中的所有插槽都被占用时，为新项目找到一个空插槽。这导致级联的反冲序列，直到滤波器收敛到新的稳定状态。 当结构变满时，插入会变慢，事实上，如果在单个插入期间踢的次数超过指定的阈值（在作者的参考实现中为500），插入可能会失败。双选择过滤器[46]将指纹复杂地在类似于布谷鸟过滤器的块但不同于布谷鸟过 滤器， 没 有踢。 双选择过滤 器中的块的大 小（log ，其中 是项目的数量，通常是大多数机器上的缓存行的大小）比布谷鸟过滤器更大，并且使用双选择幂散列来减少块之间的差异并实现高负载因子。 在插入过程中，如果对应于指纹的两个块都已满，则数据结构被声明为已满。 二次幂选择散列使过滤器能够在插入和查询期间探测两个高速缓存行，并在插入期间写入单个高速缓存行。给定较大的块大小，矢量商滤波器[46]使用重排序（类似于商滤波器）来组织块内的指纹。它将指纹分为商和余数部分，只将余数存储在商给出的槽中。 它使用两个额外的元数据位来解决元数据之间的冲突。3设计GPU过滤器在这里，我们将讨论在GPU上构建快速且节省空间的滤波器所需的设计原则，并使用它们来分析各种滤波器设计。3.1GPU设计原则在GPU上实现数据结构时，需要考虑四个主要设计原则1. 低线程发散：线程束内的线程应该执行相同的指令。这使得编写简单的内核可以利用GPU中的大规模并行性2. 高内存一致性：线程束内的线程应该从本地区域访问相同的内存。 随机的内存访问开销很大，会导致线程停止。3. 高并行度：大量线程使内存带宽饱和，隐藏内存延迟。4. Atomicoperations：atomicoperationshelpeficientthreadscheduling insidea warp。非原子写入和数据移动会导致速度降低，并需要锁定大的内存区域。 锁定导致高开销并影响总吞吐量。3.2滤波器设计分析现在我们来看看第2节中讨论的动态过滤器，并根据GPU设计原则对其进行评估布隆过滤器很容易在GPU上实现，因为它们只需要测试和设置操作。这些操作可以使用原子操作实现，并实现低线程发散。然而，每个操作导致多个高速缓存未命中，因此布隆过滤器具有低存储器一致性。他们也有次优的空间使用。此外，Bloom过滤器不支持删除、计数2和将小值与项关联.2计数布隆过滤器[22]，布隆过滤器的一个变体，支持计数，但它具有很高的空间开销，这使得它在实践中非常低效。163（）下一页PPoPPBlocked Bloom filter更适合GPU。每个操作都需要在单个块内进行探测它们实现了低线程发散、高内存一致性、高度并行性和原子操作。因此，分块Bloom过滤器可以满足所有GPU设计原则。 然而，阻塞的Bloom过滤器与Bloom过滤器相比有很高的误报率，并且不支持必要的功能，如删除和计数。商过滤器中的操作具有高缓存局部性，这使得它成为实现高存储器一致性的适当选择。然而，商过滤器中的插入操作需要移动指纹，这使得更难以使用原子操作，并且还导致高线程发散。然而，商过滤器可以支持所有必要的功能，如删除，计数，并将小值与项相关联，这使得商过滤器成为多个应用程序可以受益的高度可用的数据结构。实现高速操作同时保持商滤波器的GPU实现中的所有特征Geil等人[24]实现了GPU商过滤器的初步版本然而，该实现是根据Bender等人的的商过滤器[4]，它没有所有的功能，如计数和值关联，也有更高的空间开销。此外，Geil等人 它支持固定的假阳性率，并且只能被调整大小以存储少于26个项目），从而导致较差的性能和有限的可伸缩性。布谷鸟过滤器将指纹存储在固定大小的块中。这种设计适合于高存储器一致性和低线程发散。 原子操作也可用于读取和写入指纹。然而，对随机存储器位置的读取和写入的级联序列使得布谷鸟过滤器难以在GPU上有效地实现。特别是，在高负荷因素，当踢项目的数量变得很高，每次插入将导致非常低的内存一致性。此外，每个踢操作导致多个高速缓存行写入。 这使得在GPU布谷鸟滤波器中实现高速操作具有挑战性。此外，布谷鸟过滤器不支持计数和将小值与项相关联.二选一过滤器具有布谷鸟过滤器的优点设计它有固定大小的块。 每个操作都需要探测到两个块，插入和删除只写入一个块。 这导致低线程发散、高内存一致性和高度并行性。然而，由于大的块大小，需要更复杂的结构来保持每个块内的指纹因此，使用原子操作来读取或写入块内的指纹并不简单。在GPU上使用原子操作实现二选择过滤器以实现高吞吐量是一项具有挑战性的任务图1. 使用合作组在TCF中插入块。3.3最高效的GPU过滤器设计我们现在确定提供必要功能并可以在GPU上实现高速操作的过滤器首先，我们选择两个选择过滤器（TCF）。TCF实现了四个设计原则中的三个。它实现了低线程发散、高内存一致性和高并行度 它还支持不同于Bloom过滤器变体的删除。我们重新设计了TCF，使用原子操作和协作组来利用大规模的GPU并行性。其次，我们选择了计数商滤波器（CQF）。CQF提供了现代应用所需的所有必要功能。特别是，它支持计数和值关联，这是许多应用程序的关键功能。然而，在CQF中很难实现低线程发散度和高并行度。 我们将重新设计CQF，以使用协调的无锁方法并实现大规模并行性和可扩展性。4TCF实施在本节中，我们将详细介绍两个选择过滤器（TCF）在GPU上的实现细节我们首先解释通过使用原子来支持并发插入和查询的版本然后，我们解释了批量无锁版本，它利用排序来预处理项目，以实现更快的操作。在TCF中，我们将表组织成块。 每个块可以存储位指纹。块的大小被调整为适合GPU缓存行内部。TCF使用二选幂（POTC）哈希方案来执行操作。 在POTC方案中，每个项目都通过一对唯一的哈希分配两个块。对于插入，将查询每个块的填充，并将项目插入到填充较少的块中。如果在任一块中找到查询项，则返回truePOTC散列有助于减少块 之 间 的 负 载 差 异 ， 将 最 大 块 的 大 小 减 少 到10logloglogn，其中n是项目的数量，如Azar等人所示 [3]的文件。164≤2×GPU的高性能滤波器PPoPP算法1块_插入（键、值、CG）1：fori = CG.thread_rank（）; i bucket_len; i+=CG.size（）do2：bool ballot = 0;3：如果bucket[i]==空或bucket[i]==墓碑，则4：ballot = 1;5：ballot_result = CG.ballot（ballot）;6：while doballot！= 07：ifCG.thread_rank（）==FFS（投票）-1，然后曲速增加线程束中协作组的数量会增加可同时调度用于加载的缓存行的数量，但会减少每个块可用的工作线程的数量。对这种现象的更详细的分析，以及改变合作组规模的实验结果，见6.3节。后台。 为了避免插入失败（没有空插槽8：如果atomicCAS（bucket+i，EMPTY，Key-Val），则9：CG.选票（真）10：返回true11：其他12：CG.ballot（false）13：其他14：如果CG.ballot（false）则返回如果当前leader插入，则返回15：返回true在两个块中）在达到90%的加载因子之前，我们使用支持表。 我们使用一个基于双哈希的小型备份表，其大小为主表大小的1/100，用于存储任何未能插入的项。由于有1%的条目插入失败，因此从该表插入和查询所需的额外成本可以忽略不计，并且它对插入或肯定查询的速度没有可测量的影响<<然而，它确实有影响16：ballot = ballot= 1 ffs（ballot）-1<<关于假阳性查询的性能，至少有一个17：returnfalse没有可用的插槽。块内的查询和查询使用协作组来执行。一个组协作地将块加载到共享内存中，然后跨越该块以检查空槽或项目的存在。一旦找到一个空的插槽，合作组投票选出一个领导者，他将尝试一个atomicCAS操作将项目写入全局内存。成功后，合作小组返回，而失败后，小组将在区块内寻找一个新的空位置，并重新投票以确定新的领导者。有关块操作的更多详细信息，请参阅算法1和图14.1TCF设计优化三个因素主导TCF性能：块的大小，每项的比特数，和合作组的大小块的大小决定了操作期间高速缓存行访问的次数因此，我们强制块的大小为 128字节（GPU上的缓存行），这限制了对于大多数操作，访问次数为2TCF的假阳性率由2π给出，其中π是将不得不搜索额外的块 TCF可以使用支持表实现90%的负载因子。最优化。 如Pandey et al. [46]，在主块具有非常低的填充率的情况下，我们可以安全地插入到主块中，而无需查询辅助块。这将插入所需的缓存加载次数减少了一次，从而提高了速度。 经过实证检验，我们发现0。75的填充率是这种快捷优化的理想截止值，因为它提供了最佳性能，而不会影响块之间的差异。4.2散装TCFTCF的批量版本利用排序来提高GPU中读/写操作的效率。 与读操作一样，GPU上的写操作也可以合并，一次操作最多可写入128字节的连续内存。例如，如果所有要插入到同一缓存行的16位键都可以在插入之前聚合，那么我们可以看到内存操作的性能提高高达32。如果在插入上节省的时间小于聚集的成本块的大小，指纹的大小。更大的手指-通过对项目进行门控，我们可以通过聚合来提高吞吐量打印尺寸降低了假阳性率，但增加了空间。atomicCAS事务的最小大小为2字节。如果密钥设置为最小CAS大小，块大小为16，则错误率为。04%。然而，大多数实际应用要求错误率在0左右。百分之一 为了达到这个错误率，我们可以增加块大小或减小指纹大小。 增加块大小对性能有负面影响，因为每个线程需要查看更多数据。 存储12位指纹降低了空间使用率，但50%的插入现在需要两个原子操作，指纹不再完全占用原子事务，这意味着atomicCAS可能会由于操作插槽之外的位发生变化而失败。协作组的大小对于滤波器设计的性能是特别重要阶段。 项被排序并作为要插入到块中的项的排序列表传递到批量TCF。TCF的块在插入项之前被加载到共享内存中，并且所有的读写都使用共享内存原子来执行。 最后，内核写入作为合并写入全局。这将最大限度地减少写入全局的数据，因为所有写入全局的操作都是协作的缓存范围合并写入。与点TCF不同，批量版本中的块在块内维护一个排序的项列表 这允许通过二进制搜索在对数时间内查询块，或者在线性时间内进行批量查询。 为了有效地插入，同时保持排序顺序，每个协作组在插入期间维护三个列表：当前存储在块中的项目列表，可以快捷到块中的项目的排序列表，以及通过POTC散列分配给块的项目列表。这三个列表使用165U（）U →{−}简体中文（）下一页（）下一页（）（）（）下一页（）下一页/（���−）−���PPoPP并行压缩策略，并将结果块协作写入全局内存。批量过滤器的错误率为0。3%，块大小为128，每项16位虽然这适用于大多数应用程序，但它需要每个项目多33%的空间才能实现与点过滤器相同的错误率。5GQF实施在本节中，我们概述了Pandey等人的研究。s[43]计数商滤波器（CQF）。我们还描述了线程安全操作的计数商过滤器中的锁定机制，因为它是基于GPU的商过滤器（GQF）中的构建块最后，我们将解释如何设计GPU的计数商过滤器5.1CQF概览计数商滤波器（CQF） 通过存储多集的紧凑无损表示来存储多集���的近似，其中，k：0，.，2���1是一个哈希函数，它将来自宇宙的项映射到一 个位指纹。为了处理多达���不同项目的多集，同时保持最多的假阳性率 ，CQF集���= log 2���（参见原始的商滤纸分析[4]）。图2. 在GQF中分两个阶段进行批量插入。8192个插槽[43]。为了保证每个插件至少有这么多插槽，我们将过滤器分成8192个插槽的部分插入线程获取两个锁，分别对应于项的规范槽和紧随其后的在计数商过滤器中锁定两个连续的区域可以确保避免内存损坏错误，即使我们在插入操作期间溢出到下一个区域插入螺纹保持这些锁，计数商滤波器将k（k）分成其第一个k比特，所有改变都被刷新到存储器。Ln2商0，其馀位，余数1。它维护一���个2������位插槽数组，每个插槽可以保存一个余数。当插入一个元素���时，计数商过滤器尝试将余数1���存储在索引0���处���（我们称���之为的规范槽）。如果该槽已经在使用中，则计数商过滤器使用罗宾汉散列[42]来找到下一个可用的空槽来存储1���。所有共享同一个规范槽的项一起存储在一个运行中，连续存储且没有空闲空间的运行序列称为簇。在插入操作期间，在群集的末尾找到下一个可用的空插槽如果一个项目在集群的开始，然后集群中的所有项目必须移动，以创建一个空的空间。5.2点插入API在点实现中，每个线程获得对内存的一部分的独占访问以进行写入。内部余数移位使用自定义memmove函数处理，因为驱动程序API仅支持memcpy，当源区域和目标区域重叠时，memcpy不能保证写入安全。要执行插入操作，线程需要锁定一个足够大的区域，以便移位项不会破坏另一个线程可能正在操作的后续区域。因此，槽被分成锁定区域，这些锁定区域足够大以在插入期间处理移位器的移位，而不会导致溢出到下一个锁定区域。考虑到过滤器只填充到95%的负载因子，我们可以有把握地说，最大集群大小将是最长簇的长度以ln为界1具有高概率[4，44]，其中 是商位数，2���是QF中的时隙数，是负载因子。例如，如果n=40（即，240个时隙）和k=3 4时，滤波器中的最大簇具有736个时隙。平均而言，集群的大小为1001为了执行操作，CUDA原子需要独占访问缓存行特斯拉V100上有128字节在每个锁一位的情况下，在高速缓存行中将存在1024个锁。这将导致严重的线程争用，并导致绝大多数线程出现抖动。 为了改善这一点，我们使用了缓存对齐锁，因为锁的数量相对于数据结构的总大小足够小，它们只占整体空间使用的一小部分。5.3批量插入API在批量API中，我们将散列到同一区域的项目分组，并为每个区域分配一个线程以插入所有分组的项目。这保证了线程将独占访问区域。为了避免锁定的开销，我们分两个阶段执行插入操作在第一阶段，插入属于偶数区域的项，每个线程分配一个特定区域。由于在奇数区域中没有线程操作，我们可以安全地执行插入操作，而不会出现任何内存损坏问题。 在第二阶段中，插入属于奇数区域的项。这种“奇偶区域”方案最大化了可以安全地同时发生的插入的数量。 虽然它只允许在给定阶段插入一半的区域，166≈⟨⟩GPU的高性能滤波器PPoPP对于大的滤波器尺寸，区域的数量远远超过线程的数量，从而允许GPU的完全饱和。每个区域的大小为8192个插槽，分阶段插入保证线程间隔16K插槽，并在溢出到下一个区域之前找到空插槽请参见图2。我们实现的这个插入方案使用临时缓冲区来保存对应于每个区域的项为了-最近将项目分布到区域中，我们使用原子操作来设置缓冲区大小并为每个项目分配缓冲区中的索引。实际上，我们不分配临时缓冲区。 相反，我们使用指向输入数组的指针来标记缓冲区的绑定。 这节省了内存和在运行时分配内存所需的时间。排序哈希。在内部，GQF存储类似于线性哈希表的项目，其中运行中的排序器按排序顺序排列。因此，插入到运行中的新项必须移动任何大于它们的移位器，以保持排序结构。这些移位是插入时间的主导我们可以通过按排序顺序插入哈希（或散列）来避免这些内存移位 如果整个数据集在插入之前被排序，则不需要移位，因为每个新的余数将存储在最后一个空槽中。 当对输入数据集进行批处理时，这种情况的一个变体也适用：虽然不可能避免移动内存中已经存在的项，但对输入批处理进行排序会删除当前批处理中任何无关的内存移动项。我们的实现使用推力库[37]来执行对输入数据进行就地排序排序后，使用后继搜索来设置缓冲区的开始，该后继搜索找到大于或等于当前缓冲区的最小散列的最小项的索引。 这消除了使用原子来设置缓冲区的需要，从而节省了多个插入阶段的时间。5.4偏态分布具有偏态分布的数据集（其中项的计数来自幂律或Zipfian分布[16]）导致点插入API中的线程之间的高度争用和批量插入API中的负载不平衡这导致插入吞吐量慢得多，并且随着滤波器大小的增加而扩展受限。对于批量插入API，我们采用映射缩减方法来避免高争用。 我们首先对这批输入项进行排序，然后执行约简，将重复项压缩为项、计数对。 这种减少允许我们对批次中的每个项目执行具有聚合计数的单个插入，而不是对应于重复项目的每个实例的多个插入。 这分摊了获取锁和执行插入的成本。它还使我们能够减少跨区域的负载不平衡，从而提高插入吞吐量。在我们的实现中，映射和归约由Thrust库处理[37]。表1. 各种过滤器支持的API。GQF是唯一支持一系列操作的过滤器RSQF可以支持删除，但作者没有实现。6评价在本节中，我们将评估各种GPU过滤器实现的性能。我们比较了我们的实现的两个选择过滤器（TCF）和基于GPU的计数 商过滤器（GQF）对盖尔等人。s[24]标准商滤波器（SQF）和秩选择商滤波器（RSQF）。SQF是商过滤器的GPU实现，支持插入、查询和删除。RSQF不支持删除。SQF和RSQF都不支持计数。 我们根据作者的建议配置SQF和RSQF以实现最佳性能。作为不支持删除的过滤器性能的基准，我们还在评估中包括Bloom filter（BF）和Blocked Bloom filter（BBF）。BF和BBF与评估中使用的其他过滤器不具有直接可比性，因为它们不支持类似功能。BBF取自Junger et al. [29]并根据作者的建议进行配置，我们使用CUDA原子逐位操作将C++ BF实现[50]修改为1位编码的GPU实现。我们评估每个过滤器的两个基本操作：插入和查找。 对于筛选器中存在的项和不存在的项，都将对查找进行评估。我们对过滤器的评估是根据过滤器的状态分为批量或点API。点过滤器具有设备端API，可以被调用来插入或查询单个项，而批量过滤器必须从主机函数调用。TCF和GQF支持批量和点API。我们将TCF和GQF的批量实现与SQF和RSQF进行比较，因为它们都是为批量API设计我们比较了我们的点实现的TCF和GQF的布隆过滤器和阻塞布隆过滤器。Bloom和Blocked Bloom实现仅支持点API。请参阅表1，以获得各种过滤器支持的API的完整列表 只有GQF和TCF支持插入、查询、删除和计数操作的批量和点模式。 我们仅针对删除操作将GQF和TCF与SQF进行比较。GQF不与其他过滤器进行比较以进行计数，因为没有其他过滤器支持计数。我们还评估了使用TCF过滤单体 时MetaHipMer中的内存减少。过滤器插入件查询删除计数点散装点散装点散装点散装GQFTCFBFSQFRSQF✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓167TCF GQF SQF RSQFPPoPPTCF GQF Bloom Blocked Bloom642022 24 26 28 30滤波器大小8642022 24 26 2830滤波器大小108642022 24 26 28 30滤波器大小(a) 科里角105(b) 科里点阳性2015105(c) Cori Point Random2015105022 24 26 2830滤波器大小022 24 26 28 30滤波器大小022 24 26 28 30滤波器大小(d) 珀尔马特角(e) Perlmutter Point Positive(f) Perlmutter Point Random图3.不同过滤器之间的点API聚合吞吐量比较。21022 24 26 28 30滤波器大小(a) Cori Bulk321022 24 26 28 30滤波器大小321022 24 26 28 30滤波器大小(b) Cori Bulk Positive（Cori原液阳性）642022 24 26 28 30滤波器大小42022 24 26 28 30滤波器大小(c) Cori Bulk Random8642022 24 26 28 30滤波器大小(d) 珀尔马特散装(e) Perlmutter Bulk Positive(f) Perlmutter Bulk Random图4.批量API聚合不同过滤器之间的吞吐量比较。微基准测试设置。我们的评估设置包括过去过滤器数据结构论文[4，9，20，21，23，24，44，46]使用的所有微基准。我们测量原始插入和查找的性能如下。我们从cuRandXORWOW生成器的散列输出生成64位输入项 项目被插入到空过滤器中，直到它达到其最大推荐负载因子（例如，90%）。为了成功查找，我们查询已经插入的项 对于随机查找，我们生成一组不同的64位哈希，而不是用于插入的哈希。这是通过使用XORWOW生成器的散列输出来完成的用不同的种子播种我们报告插入或查询一组项的操作的总吞吐量。我们在设计实验时面临的一个挑战是，过滤器并不都支持相同的假阳性率。例如，GQF支持8位、16位、32位和64位的移位器，以保持表中的槽与机器字对齐。当多个线程修改不同的插槽时，这有助于避免内存冲突，从而简化GPU实现。然而，SQF和RSQF过滤器仅支持5和13的剩余大小，因为它们将3个元数据位与8和16位机器字中的剩余部分一起打包。它们还要求商位和余数位之和为吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）吞吐量（B/s）168≈ ×≈×GPU的高性能滤波器PPoPPGQF BF SQF RSQF Bulk TCQF TCQF Blocked BloomFPBPIFPBPIFPBPIFPBPIFPBPIFPBPIFPBPI0.19%10.680.15%10.10百分之一点一七9.7百分之一点五五7.87百分之零点三六160.024%160.71%9.73表2.图4和图3中实验的各种过滤器的假阳性率（FP）和每项位数（BPI）。少于32。因此，它们最多只能支持2个26项的5位解码器和2个18项的13位解码器。我们选择0.1%的目标误报率，并配置每个过滤器以尽可能接近该误报率。我们在GQF中使用8位解码器我们在Bloom和Blocked Bloom过滤器中使用7个散列和每个项目10.1位 我们使用5位的SQF和RSQF的解码器，虽然这导致几乎一个数量级的较高的误报率，它支持这些实现的最大数量的项目（2 - 26）。在此错误率下的最小TCF字对齐是16位，因此我们报告了滤波器这种变化的结果。 表2示出了这些实验中不同过滤器的经验空间使用、假阳性率和每项比特数（BPI）。我们测量空间使用率，假阳性率我们评估这些过滤器在GPU内存中的性能，因此我们在实验中调整过滤器的大小，以便它们始终驻留在GPU内存中计数基准设置。 计数基准包括具有不同计数分布的三个数据集。均匀随机（UR）数据集包含从均匀随机分布中提取的项目，几乎没有重复。均匀随机计数（UR count）数据集包含项目，其中项目的计数从1到100之间的均匀随机分布中提取。 Zipfian count（Zipfian count）数据集包含的项目的计数是从Zipfian分布中提取的（系数为1.5，项目是从与数据集大小相同的宇宙中选择的）。数据集中的所有项目都被插入到GQF中的一个大批量中 我们还包括一个真实世界的基因组数据集的计数基准。我们拿到了原始的序列文件，M. balbisiana，来自Squeakr [45]基准数据集，并提取 -mer用于计数。机器规格。 我们的微基准测试和计数基准测试在Cori [ 35 ]和 Perlmutter [ 36 ] 的 GPU 节 点 上 运行。 Cori 节 点 由NVIDIA Tesla V100和5120@1445MHz 微 处 理 器 组 成， 16GB 4096位HBM2存储器，以及82，000个并发线程的活动线程限制。Perlmutter节点由NVIDIA A100 Tensor Core GPU和6912@1410MHz 40 GB 5120位HBM2内存组成，活动线程限制为110，000个线程。6.1点API性能点API基准测试的结果可以在图3中找到。在支持插入、查询和删除的过滤器中，TCF具有最高的插入和查询性能。对于大多数查询，它需要两个缓存行探测，对于插入，它需要一个写操作，这比所有其他过滤器都要小得多。后备表的开销可以忽略不计，因为只有不到0.07%的项进入后备表。然而，对于否定查询（即，过滤器中不存在的项），则后备表增加了最坏情况下的性能：查询必须检查后备表中的至少一个桶，并且在最坏情况下可以探测多达20个桶。支持表有助于实现90%的负载系数。如果没有支持表，TCF只能达到79.6%的加载因子，然后无法插入项目。此外，由于快捷优化，插入和查询操作的平均性能要好得多在第4节中提到。在本评价中，TCF的假阳性率高于GQF和BF。然而，TCF在空间使用和误报率方面支持多种配置。我们在第6.3节中评估了各种TCF配置的性能。由于执行点插入的锁定开销，GQF的性能比TCF慢 锁定实现要求我们为GQF中的每个块维护单独的锁，这会导致锁抖动。基于正查询性能，GQF可以比BF可以对所有7个位操作更快地到达用于插入的槽，因为每个