Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis - todo314 @ ウィキ

Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis

• IPDPS 2016
• Junya Arai, Hiroaki Shiokawa, Takeshi Yamamuro, Makoto Onizuka, Sotetsu Iwamura

概要

• 主に$$x^{(t+1)} = Ax^{(t)} $$系の反復法=疎行列ベクトル乗算のキャッシュミスを減らしたい
• 頂点順序を工夫しよう
• Q値を基準に併合していってデンドログラムを作る
• PageRankとかが全体で2倍速くなった！

Rabbit Order

• 高い局所性を達成したい
• 問題定義: キャッシュミスを最小化する頂点順序を見つけたい
• 実グラフの階層的コミュニティ構造を意識するよ

第1段階

• 次数の昇順に頂点uを見る
• ΔQ(u,v)を最大化する近傍頂点vを探す
• もし、ΔQ(u,v)>0なら、uとvを併合

第2段階

• デンドログラムのDFS順に頂点IDを割り振る
• ミソ
  • 「密な所は近いID」が階層的になっている
  • L1・L2みたいな多レベルのキャッシュの存在を加味すると効果的そう
• 他
  • 並列処理とかを頑張っている(IPDPSだし)
  • かなり実装に立ち入る書き方をしている

実験

• データセット
  • SNAP・LAW・DIMACSから、ウェブ・ソーシャル・道路、数M辺～数B辺
• 比較手法
  • 実は既存手法は色々ある
• (頂点順序)+(PageRank)の計算時間
  • 大体2倍速くなっている、既存手法はむしろ（全体としては）遅くなっている
  • 前者の効率: 提案手法がかなり速い、既存手法はかなり遅い
  • 後者の効率: 3--5倍の高速化、LLPというのと同じくらい
• その他: DFS, BFS, SCC, 直径, k-core
  • 全体: DFS・BFSは大して速くならない（そもそも軽いので）が、他は2倍以上速くなっている

まとめ

• 某アレで聞いた発表の会議論文なので、話は知っている
• 会議が分散並列なせいか、最適化問題としてというよりは、良そうなことや、実際に良いことを凄くおしている
• とはいえ、最適化問題として更に良く頑張って解くとかしても、ペイできる速度比を達成できるとは思えない…
• スペクトラルなのをそのままぶち込んでもダメかなあ？
• キャッシュとかメッチャ考えて特化した方が良い？

IPDPS グラフ処理 グラフ順序付け

2016/11/28