Fast Community Detection in Graphs with Infomap Method using Accelerated Sparse Accumulation
Fast Community Detection in Graphs with Infomap Method using Accelerated Sparse Accumulation
复制标题
DOI：
10.1109/ipdpsw59300.2023.00103
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;S. Arifuzzaman;Doru-Thom Popovici;J. Shalf;Cy Chan
中科院分区：
文献类型：
--
作者：
M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;S. Arifuzzaman;Doru-Thom Popovici;J. Shalf;Cy Chan
与基于模块化的算法相比，信息论社区发现方法（通常称为Infomap）以在Lancichinetti-Fortunat-Radicchi （LFR）基准测试中提供更高质量的结果而闻名。由于生物科学、社会科学、商业和其他领域中信息的巨大增长导致了分析大量图形的计算挑战，因此为Infomap开发了并行算法。信息论社区发现的最新技术使用哈希表来存储顶点邻域流信息，由于冲突处理操作和CPU分支错误预测，这可能会导致计算成本很高。用于散列积累的加速稀疏积累（ASA）硬件加速器是近年来开发的用于稀疏矩阵-矩阵乘法（SpGEMM）的硬件加速器。我们推广了ASA加速器的接口，并证明了对于最先进的并行Infomap，具有快速片上存储器的哈希积累加速器可以克服软件哈希表的性能瓶颈，并且可以实现5.56倍的加速，同时将分支错误预测次数减少59%，CPI率减少21%，指令总数减少24%。
Information-theoretic community discovery method (popularly known as Infomap) is known for delivering better quality results in the Lancichinetti–Fortunat–Radicchi (LFR) benchmark compared to modularity-based algorithms. Parallel algorithms have been developed for Infomap due to the computational challenge of analyzing massive graphs resulting from the tremendous growth of information in bio-sciences, social sciences, business, and other domains. The state-of-the-art techniques on information-theoretic community discovery use hash tables for storing vertex neighborhood flow information, which can be computationally expensive due to collision handling operations and CPU branch mispredictions. The Accelerated Sparse Accumulation (ASA) hardware accelerator for hash accumulation has been developed recently for sparse matrix-matrix multiplication (SpGEMM). We generalize the interface of the ASA accelerator and demonstrate that for state-of-the-art parallel Infomap, the accelerator for hash accumulation with fast on-chip memory can overcome the performance bottlenecks of software hash tables and can achieve a speedup of $5.56\times$ while reducing the number of branch mispredictions by 59%, the CPI rate by 21%, and the total number of instructions by 24%.