メニーコアプロセッサを用いた構造的類似度に基づくグラフクラスタリングの高速化

• 高橋, 知克

• 塩川, 浩昭

• 北川, 博之

Bibliographic Information

Other Title

• Efficient and Exact Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Processor

Abstract

構造的類似度に基づくグラフクラスタリング手法SCANは，グラフ中からクラスタやハブ，外れ値を高精度で検出できるため幅広く利用されている．しかしながら，SCANはすべてのエッジの構造的類似度を計算するため，大規模グラフの分析には膨大な計算時間を必要とする．そこで本稿では，メニーコアプロセッサIntel Xeon Phiを用いたSCANの高速化手法SCAN-XPを提案する．提案手法は，並列グラフ処理のボトルネックを解消するとともに，アルゴリズムをIntel Xeon Phiの持つ512ビットSIMD演算に最適化する．本稿では実データを用いた評価実験を行い提案手法の有効性を示す．

The structural graph clustering method SCAN is successfully used in many applications because it can extract clusters, hubs and outliers from a graph at the same time. However, it is difficult for SCAN to compute large-scale graphs since SCAN needs to evaluate the density for all edges in graphs. To address the above problem, we present SCAN-XP that performs over Intel Xeon Phi. SCAN-XP avoids the bottlenecks that arise from parallel graph computations and it effectively exploits 512bit SIMD instructions. Our evaluations on real-world graphs demonstrate that SCAN-XP outperforms existing approaches.

Journal

• 情報処理学会論文誌データベース（TOD）

  情報処理学会論文誌データベース（TOD） 10 (4), 1-5, 2017-12-13

Keywords

• [テクニカルノート] グラフクラスタリング，SIMD演算，Intel Xeon Phi

Details

• CRID: 1050282812885224704
• NII Article ID: 170000149096
• NII Book ID: AA11464847
• ISSN: 18827799
• Web Site: http://id.nii.ac.jp/1001/00184834/
• Text Lang: ja
• Article Type: article
• Data Source:
  • IRDB
  • CiNii Articles
  • KAKEN