FenixWalk：面向异构架构的大规模动态图自适应采样

摘要：随机游走是图分析的基础，但在大型动态图上高效执行仍具挑战。现有方法需在采样效率、更新开销和内存消耗之间取得平衡。针对吞吐量优化的采样结构往往带来较大的内存开销和高昂的维护成本，而轻量级方案在高度数顶点或权重分布偏斜时又可能面临较高的采样延迟。这些挑战在异构CPU-GPU平台上尤为突出，其中主机内存容量充足，但GPU内存限制了可从并行加速中获益的图数据量。 我们提出了FenixWalk，一个面向大规模动态图的内存高效随机游走系统，它将统一的原地采样与选择性GPU加速相结合。FenixWalk的核心采用原地Fenwick表示，无需复制边级权重存储即可支持拒绝采样和逆变换采样。该表示使拒绝采样具备期望O(1)的时间复杂度，同时支持O(log d)的前缀采样和更新操作。为高效利用异构硬件，FenixWalk将完整图及其采样结构保留在主机内存中，同时将频繁重用的顶点本地采样器选择性放置于GPU上。通过传输紧凑的游走器状态而非反复迁移图分区，该系统减少了跨设备通信，并有效利用了有限的GPU内存。在大型真实世界图和代表性随机游走工作负载上的实验表明，FenixWalk相较于现有随机游走系统实现了平均2.06倍至400.57倍的加速。 提交历史 访问论文： 查看PDF HTML （实验性） TeX 源代码 附加功能 音频摘要 当前浏览上下文： 参考文献与引用 Google 学术搜索 Semantic Scholar 书签 机构 arXivLabs 是一个框架，允许合作者直接在我们的网站上开发和共享新的 arXiv 功能。 无论是个人还是使用 arXivLabs 的组织，都认同并接受了我们关于开放、社区、卓越以及用户数据隐私的价值观。arXiv 致力于践行这些价值观，并且只与遵守这些价值观的合作伙伴开展合作。 您是否有一个能为 arXiv 社区创造价值的项目构想？请了解更多关于 arXivLabs 的信息。