Hydra-MCS：一种加速最大公共子图计算的 CPU-GPU 混合方法

《IEEE Transactions on Parallel and Distributed Systems》：Hydra-MCS: A Hybrid CPU-GPU Approach to Accelerate the Maximum Common Subgraph Computation

　　

摘要：

最大公共子图（MCS）问题是图论中的一个基本挑战。它是子图同构问题的一般化，且已知是NP完全的并难以近似求解。这种固有的复杂性凸显了对高效解决方案的需求。本文提出了Hydra-MCS，一种新型的CPU-GPU混合方法，可显著加速MCS计算。我们的方法使用一种轻量级度量来准确估计给定解决方案的剩余计算量（RC）。然后利用该度量将计算卸载到GPU，维持负载均衡，并最大限度地减少线程之间的不必要任务共享。通过仔细分析我们的混合实现，我们确定了CPU和GPU必须共享的基本信息以优化性能。此外，我们还讨论了将计算卸载到GPU的显著优势。我们的方法在性能上建立了新的最先进水平。在匹配的CPU资源下，与Hydra-MCS CPU相比，GPU集成提供了约3×倍的额外加速；在可扩展工作负载上，与并行McSplit相比提供了约4×倍的加速；在长时间运行的基准实例中，相对于McSplit的加速通常达到4-5×倍，峰值超过12×倍。我们还讨论了可扩展性和鲁棒性，因为随着线程数量的增加和问题的难度加大，我们的算法表现显著优于原始算法。对随时间解决的实例进行的全面分析表明，混合实现始终比原始框架多解决30-40%的实例，对于最复杂的图对，在接近超时阈值时峰值达到70%。

一、引言

图是一种通用的数据结构，能够有效地将信息和关系抽象为机器可读的表示。在这个框架中，节点表示数据点，边表示它们之间的关系。这种强大的抽象使图适用于广泛的领域，包括化学[1]、[2]、[3]、[4]、社交网络[5]、网络搜索[6]、恶意软件检测[7]、硬件设计仿真[8]以及软件组件依赖检测[9]、[10]。