FastCC：一种用于大型幂律图上连通分量计算的系统-算法协同设计方法

《ACM Transactions on Architecture and Code Optimization》：FastCC: A System-Algorithm Co-Design for Connected Components Computation on Large Power-Law Graphs

Connected Components (CC)算法在处理具有幂律度分布的实时图时面临线程利用率低和同步开销大的问题。本文提出FastCC系统算法协同设计方案，通过混合粒度任务划分（初始边粒度分配，后续顶点粒度分配）将初始线程利用率提升至60%以上，结合松散同步机制消除层间刚性屏障，实现多跳并行处理，显著降低同步开销。实验表明FastCC在42亿边规模图上的处理速度达传统算法21.8倍，并获GreenGraph500最新冠军。

　　

摘要人工智能摘要

要查看此由人工智能生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

连通分量（Connected Components, CC）是分析复杂系统中拓扑结构的基础，其应用领域涵盖社交网络、通信基础设施和图机器学习等关键领域。由于度分布不均匀，高效计算现实世界中常见的幂律图（power-law graphs）的连通分量仍然具有挑战性，这种不均匀性会导致冗余的内存操作和严重的性能瓶颈。我们对23种最先进的算法进行了系统评估，发现采样阶段占据了运行时间的大部分（平均超过85%），并且对于幂律图来说，使用广度优先搜索（BFS）进行采样是最优的选择。然而，现有的BFS采样实现存在两个关键的硬件利用率问题：（i）由于在第一次迭代中任务分配是在顶点级别进行的，导致线程利用率较低（<2%）；（ii）由于传统BFS中固有的刚性层次结构，产生了过多的同步开销。

为了解决这些限制，我们提出了FastCC，这是一种针对幂律图优化的系统-算法协同设计方法。FastCC通过两项核心创新来最大化硬件资源利用率：（i）混合粒度任务划分（Hybrid-granularity Task Partitioning, HTP）采用初始的边级分配策略，使所有线程都能有效参与计算，在第一次迭代中实现超过60%的线程利用率；随后迭代中切换到顶点级划分，以提高任务分配效率。（ii）放宽同步限制（Relaxed Synchronization, RS）消除了严格的层次结构限制，允许在迭代过程中进行乱序、多跳处理，从而大幅降低同步开销和冗余计算。实验结果表明，FastCC具有出色的效率和可扩展性。在各种数据集上，其速度比最先进算法快4.8倍到35.9倍（平均快21.8倍）。更重要的是，FastCC能够在单个节点上使用不到384GB的DRAM内存，在不到2秒的时间内处理拥有超过420亿条边的图，使其成为大规模幂律图分析的领先解决方案。此外，当FastCC作为预处理阶段部署在天河超级计算机原型上时，该系统在最新的GreenGraph500榜单中排名第一，效率比第二高效的系统高出1.44倍。

人工智能摘要

人工智能生成的摘要（实验结果）

此摘要是由自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助读者发现相关内容、评估文章的相关性，并帮助来自相关研究领域的读者理解本文的研究成果。它是对作者提供的摘要的补充，作者提供的摘要仍然是文章的官方总结。完整文章才是权威版本。点击此处了解更多。

点击此处对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的版本。

要查看此由人工智能生成的通俗语言摘要，您必须具有高级访问权限。