SCAN-XP: Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Coprocessors
SCAN-XP: Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Coprocessors
复制标题
DOI：
10.1145/3068943.3068949
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Tomokatsu Takahashi;Hiroaki Shiokawa;H. Kitagawa
中科院分区：
文献类型：
--
作者：
Tomokatsu Takahashi;Hiroaki Shiokawa;H. Kitagawa
由Xu等人提出的结构图聚类方法SCAN被成功地应用于许多应用中，因为它不仅将密集连接的节点检测为簇，而且将稀疏连接的节点提取为中心或离群点。然而，由于扫描需要评估给定图中所有相邻节点的密度，因此将扫描应用于大规模图是困难的。为了解决上述问题，我们提出了一种在Intel Xeon Phi上运行的新算法Scan-XP。为了更好地利用Intel Xeon Phi的硬件潜力，我们设计了Scan-XP，采用了以下方法：首先，Scan-XP通过在Intel Xeon Phi上的内核之间提供良好的负载平衡来避免并行图形计算产生的瓶颈。其次，Scan-XP有效地利用Intel Xeon Phi中实现的512位SIMD指令来加速密度计算。因此，Scan-XP可以从大规模图表中检测集群、中枢和离群值，计算时间比Scan短得多。具体地说，Scan-XP的运行速度大约是Scan的100倍；对于有1亿条边的图，Scan-XP能够在几秒钟内执行。在本文中，对真实世界的图形进行了广泛的评估，证明了Scan-XP相对于现有方法的性能优势。
The structural graph clustering method SCAN, proposed by Xu et al., is successfully used in many applications because it not only detects densely connected nodes as clusters but also extracts sparsely connected nodes as hubs or outliers. However, it is difficult to applying SCAN to large-scale graphs since SCAN needs to evaluate the density for all adjacent nodes included in the given graphs. In this paper, so as to address the above problem, we present a novel algorithm SCAN-XP that performs over Intel Xeon Phi. We designed SCAN-XP in order to make best use of the hardware potential of Intel Xeon Phi by employing the following approaches: First, SCAN-XP avoids the bottlenecks that arise from parallel graph computations by providing good load balances among cores on the Intel Xeon Phi. Second, SCAN-XP effectively exploits 512 bit SIMD instructions implemented in the Intel Xeon Phi to speed up the density evaluations. As a result, SCAN-XP detects clusters, hubs, and outliers from large-scale graphs with much shorter computation time than SCAN. Specifically, SCAN-XP runs approximately 100 times faster than SCAN; for the graphs with 100 million edges, SCAN-XP is able to perform in a few seconds. In this paper, extensive evaluations on real-world graphs demonstrate the performance superiority of SCAN-XP over existing approaches.