| Item type |
Trans(1) |
| 公開日 |
2017-12-13 |
| タイトル |
|
|
タイトル |
メニーコアプロセッサを用いた構造的類似度に基づくグラフクラスタリングの高速化 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Efficient and Exact Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Processor |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[テクニカルノート] グラフクラスタリング，SIMD演算，Intel Xeon Phi |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
筑波大学大学院システム情報工学研究科 |
| 著者所属 |
|
|
|
筑波大学計算科学研究センター |
| 著者所属 |
|
|
|
筑波大学計算科学研究センター |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Systems and Information Engineering, University of Tsukuba |
| 著者所属(英) |
|
|
|
en |
|
|
Center for Computational Sciences, University of Tsukuba |
| 著者所属(英) |
|
|
|
en |
|
|
Center for Computational Sciences, University of Tsukuba |
| 著者名 |
高橋, 知克
塩川, 浩昭
北川, 博之
|
| 著者名(英) |
Tomokatsu, Takahashi
Hiroaki, Shiokawa
Hiroyuki, Kitagawa
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
構造的類似度に基づくグラフクラスタリング手法SCANは，グラフ中からクラスタやハブ，外れ値を高精度で検出できるため幅広く利用されている．しかしながら，SCANはすべてのエッジの構造的類似度を計算するため，大規模グラフの分析には膨大な計算時間を必要とする．そこで本稿では，メニーコアプロセッサIntel Xeon Phiを用いたSCANの高速化手法SCAN-XPを提案する．提案手法は，並列グラフ処理のボトルネックを解消するとともに，アルゴリズムをIntel Xeon Phiの持つ512ビットSIMD演算に最適化する．本稿では実データを用いた評価実験を行い提案手法の有効性を示す． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464847 |
| 書誌情報 |
情報処理学会論文誌データベース（TOD）
巻 10,
号 4,
p. 1-5,
発行日 2017-12-13
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7799 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TOD1004002.pdf (1.8 MB)
