Scalable Graph Exploration on Multicore Processors

Virat Agarwal, Fabrizio Petrini, Davide Pasetto, and David A. Bader. 2010. Scalable Graph Exploration on Multicore Processors. In Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC '10). IEEE Computer Society, Washington, DC, USA, 1-11. DOI=10.1109/SC.2010.46 http://dx.doi.org/10.1109/SC.2010.46

  • 問題・環境
    • BFS
    • SMP 1 台
    • Nehhalem-EX 8 コア × 4 ソケット (= 32 コア)
  • アプローチ
    • 並列 BFS を最適化する．
  • 結果
    • 1.3B edges / sec
    • すごい速そう (主観． でも，その辺の分散より速いし．)
      • てか 1 スレッドですら元よりかなり高速
      • 既存のライブラリと比較してほしかった
  • 最適化
    • 1
      • 到達したかのフラグをビットセットに
      • ロックする前に値みてからロック
    • 2
      • ソケットごとにキューを別に
      • ソケット内での push とソケット外への push を別に
      • ソケット外から push されたのは後でまとめて処理
      • 良い感じの lock-free queue
      • Inter-socket キューの処理の batching (何個か頂点まとめて push/pop)

スッゲーはやくなっててかっこいい