Parallelizing Louvain Algorithm: Distributed Memory Challenges
Parallelizing Louvain Algorithm: Distributed Memory Challenges
复制标题
并行化 Louvain 算法：分布式内存挑战
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Arifuzzaman
中科院分区：
文献类型：
--
作者：
Naw Safrin Sattar;S. Arifuzzaman
Louvain算法是一种众所周知的有效方法，用于检测社会和信息网络中的社区或集群（图）。大型网络数据的出现需要该算法的高性能计算平台并行化。有几种基于共享内存的平行算法用于Louvain方法。但是，这些算法并未扩展到大量核心和大型网络。如今，分布式内存系统已广泛可用，可提供大量处理节点。但是，现有的仅基于MPI（消息传递接口）的分布式内存并行实现了Louvain算法仅显示对16个处理器的可扩展性。在本文中，我们同时实施了共享和分布式内存的并行算法，并确定了阻碍可伸缩性的问题。在使用OpenMP的基于共享记忆的算法中，我们为多个现实世界网络获得了4倍的速度。但是，此加速仅受我们系统可用的物理内核的限制。然后，我们使用消息传递接口设计基于分布式内存的并行算法。我们的结果证明了对中等数量的处理器的可伸缩性。我们还提供了经验分析，该分析表明，沟通开销如何在分布式内存设置中对可扩展的可扩展Louvain算法构成最关键的威胁。
Louvain algorithm is a well-known and efficient method for detecting communities or clusters in social and information networks (graphs). The emergence of large network data necessitates parallelization of this algorithms for high performance computing platforms. There exist several shared-memory based parallel algorithms for Louvain method. However, those algorithms do not scale to a large number of cores and large networks. Distributed memory systems are widely available nowadays, which offer a large number of processing nodes. However, the existing only MPI (message passing interface) based distributed-memory parallel implementation of Louvain algorithm has shown scalability to only 16 processors. In this paper, we implement both shared- and distributed-memory based parallel algorithms and identify issues that hinder scalability. In our shared-memory based algorithm using OpenMP, we get 4-fold speedup for several real-world networks. However, this speedup is limited only by the physical cores available to our system. We then design a distributed-memory based parallel algorithms using message passing interface. Our results demonstrate an scalability to a moderate number of processors. We also provide an empirical analysis that shows how communication overhead poses the most crucial threat for deisgning scalable parallel Louvain algorithm in a distributed-memory setting.