海报：高吞吐量GPU随机游走与微调并发查询处理-上海交通大学、香港科技大学、新加坡国立大学、阿里巴巴

432（）下一页（）下一页海报：高吞吐量GPU随机游走与微调并发查询处理徐成1、李超1、王鹏宇1、侯晓峰2、王静1、孙世轩3、郭敏义1、吴汉青4、陈东柏4、刘祥文41上海交通大学2香港科技大学3新加坡国立大学4阿里巴巴摘要随机游走是处理大规模图的有力工具，它在保持结构信息的同时减少了数据量。不幸的是，现有的系统框架都专注于串行执行单个walker任务。我们提出了CoWalker，一个高吞吐量的GPU随机游走框架，专为并发随机游走任务。提出了一种多级并行执行模型，使并行随机游走任务能够以较低的开销有效地共享GPU资源 我们的系统原型证实，所提出的系统可以优于（高达54%）的最先进的在广泛的光谱的情况下。关键词：随机游走，GPU，协同定位1引言由于图神经网络（GNN）的广泛部署，随机游走最近已经成为当今数据中心中非常常见的云工作负载。 它负责从大型原始图中提取低维特征向量，这些特征向量将依次用于各种任务，如节点/图分类，链接预测和推荐系统。由于随机游走可以在不牺牲性能的情况下减小目标图的大小，因此它已被广泛采用为GNN应用程序的一部分[7]。我们已经见证了对用于优化CPU和GPU上的随机游走工作负载的专用框架的日益增长的兴趣[2，5，6]。GPU随机工作系统具有超越基于CPU的系统的巨大潜力原因是在一个任务中对不同顶点进行采样的操作彼此独立，不需要通信[1]。最近的工作已经模拟了在各种架构上部署并发图应用程序[3，4]。 在这方面，GPU的大规模并行性允许基于GPU的框架跨越数千个并发walkers。允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。本作品的第三方组件的版权必须得到尊重。对于所有其他用途，请联系所有者/作者。PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577482然而，利用GPU来执行随机游走是不平凡的，因为其密集的、复杂的存储器访问模式。当前基于GPU的框架都将基于CPU的系统的执行模式直接应用于GPU，其中单个随机游走任务是高度可执行的[5]。虽然这种模型在CPU上表现良好，但它可能会导致严重的GPU存储并降低整体吞吐量。随机游走是一种内存密集型的工作负载，并且存在内存到计算带宽的不平衡。特别是对于超过GPU内存容量的图形，CPU和GPU之间的低PCIe带宽导致大多数GPU核心保持空闲以等待数据，从而导致严重的GPU利用率不足。如果应用设计良好的空间共享技术，则一个GPU可能能够服务于来自多个GNN工作负载的并发随机游走任务。在本文中，我们表明，它需要细粒度的控制，货币优化和重大的工程努力，以开发一个框架，利用大规模的随机行走任务。 我们采用并发模型来减少停滞的GPU核心。 通过大量的实验，我们表明，我们的框架表现出很大的性能和可扩展性。我们的贡献可以概括为：我们介绍了一个多层次的并发执行模型的随机行走任务。我们在GPU上实现并验证了一个高吞吐量的并发随机游走框架2背景我们选择别名方法作为我们的邻居选择方法。它在预处理阶段构建两个表：概率表和别名表 来绘制样本。 方法可以在脱机或联机模式下执行。离线模式首先为整个图构造一个别名表，这样执行阶段就可以在1001中执行，代价是对每个顶点进行并行预处理另一方面联机模式只在需要时构造部分别名表3并发随机游动系统我们设计了一个新的并发执行模型，使细粒度的GPU空间共享。该算法综合考虑了算法的执行模式和图的性质，有效地缓解了计算停滞问题如图1所示，我们的框架将模式级并发和··433（）下一页（）下一页∗ || + | |∗ || +∗ ||∼∼×∼×PPoPP(a) 图级图1.多级并发。图形级并发，实现最高的整体系统吞吐量。 该功能使我们的系统能够适应各种场景。模式级并发。离线和在线使用别名方法的随机行走任务是相辅相成的。通过分析它们的时间复杂度和空间复杂度可以看出 在时间复杂度方面，离线任务以直接查找表模式工作，每个顶点只需要 1个。因此，在线任务需要首先使用为 运行中的顶点构造别名表的特定分区，其中 是该顶点的度。一小部分CUDA核心可以满足离线任务的计算资源需求和在线任务的其余工作在空间复杂度方面，离线任务依赖于别名表构造，需要42 的空间。对于一些大型图形，这意味着存储空间的差异超过15 GB。 同时运行离线和在线任务可以缓解GPU内存和带宽的压力，因为在线任务不需要额外的别名表，只需要2来存储图形数据。图级并发。在图级并发中，我们巧妙地将不同图大小的任务与相同的模式结合起来。 对于离线任务，存在由于缺乏存储器带宽而停滞的大量计算资源，特别是对于存储在主机存储器中的大型图。 我们的想法是重叠的数据访问，以增加等效内存带宽和更好地利用GPU核心。在完成一定的计算过程后，GPU核心需要根据结果为后续处理提取图形数据要访问的图形数据当前可以存储在GPU存储器或主机存储器中，其被不同地访问 存储在主机内存中的数据必须首先通过PCIe链路传输到GPU存储器，并且此传输过程可能非常漫长。因此，我们同时启动另一个内核，在GPU内存中存储的小图上执行随机游走任务，以在传输这些数据的同时利用板载GPU内存资源，这显著增加了等效内存带宽。(b) 模态电平图2.与串行和MPS相比，CoWalker的标准化执行时间与均衡的查询执行时间。LJ、SK、UK和GG是常用的图数据集。4评价图2显示了CoWalker使用的两级并发优化的贡献如果没有CoWalker，这些任务是串行执行的。 对于图级并发，我们执行DeepWalk;对于模式级并发，我们使用node2vec执行DeepWalk和PPR。由于粗粒度的资源管理策略导致不同任务之间的干扰，MPS实现在大多数情况下都无法超越串行基线。这在模式级并发中尤其明显，MPS实现慢1.87 2.11。当涉及到图级并发的情况下，MPS实现在离线模式下的执行时间范围从1.02 1.08。但是，在联机模式下，它的执行时间在所有情况下都小于串行基线在LJ+LJ的情况下，它甚至超过了CoWalker 13%，显示出在同时在线的小图上行走的优势。在 所 有 情 况 下 ， CoWalker 的 执 行 时 间 都 少 于SkyWalker。使用图级并发，CoWalker的最低执行时间仅为SkyWalker的67%对于模式级并发，CoWalker花费了SkyWalker的75%-89%的执行时间 这是因为留出部分计算资源将不可避免地降低node2vec工作负载的性能。5结论我们提出了CoWalker，一个高吞吐量的GPU随机游走框架，使微调并发查询处理-ING。 我们希望我们的研究能够促进异构系统上并发图处理的进一步研究。434海报：High-ThroughputGPURandomWalkwithFine-tuneedConcurentQueryProinPgPoPP引用[1] 潘 培 天 和 李 超 。 2017 年 。 Congra： Towards Efficient ProcessingofConcurrent Graph ， Shared-Memory Machines. ICCD 2017 。 217-224. https://doi.org/10.1109/ICCD.2017.40[2] Shixuan Sun et al.2021年ThunderRW：一个内存图形随机游走引擎。 Proc. VLDB赋予14，11（2021），1992-2005。http ：//www.vldb.org/pvldb/vol14/p1992-sun.pdf[3] Jing Wang et al.2022年。 在基于RDMA的远存储体系结构上挖掘图存储的潜力。在IPDPS2022中。IEEE，1029https://doi.org/10.1109/IPDPS53621.2022.00104[4] Pengyu Wang et al. 2021. Grus ： Toward Unified-Memory-EfficientHigh-Performance Graph Processing on GPU 。 ACM Trans.Archit.代码优化18，2（2021）.[5] Pengyu Wang et al. 2021. Skywalker ： Efficient Alias-Method-BasedGraph Sampling and Random Walk on GPU. 在PACT 2021中。IEEE，304- 317. https://doi.org/10.1109/PACT52795.2021.00029[6] Ke Yang et al.2019年。KnightKing：一个快速的分布式图随机游走引擎。在SOSP 2019中。ACM，524-537. https://doi.org/10.1145/3341301的网站上下载。3359634[7] Rex Ying等.2018年 用于网络规模推荐系统的图卷积神经网络。 第24届ACM SIGKDD知识发现&数据挖掘国际会议论文集（2018）。