SSCA#2 - その2

より詳しく見ていく。

準備段階 : (始点,終点,重み) を枝数分生成する。

kernel 1 : Graph Construction
(始点,終点,重み)の組から疎な有向グラフを構築する。

kernel 2 : Classify Large Sets
全枝の重みを調べ、最大枝長を持つ枝(点のペア)を探す。

kernel 3 : Graph Extraction
枝リストを指定し、各枝から始まる bfs 結果を返す。

kernel 4 : Graph Analysis Algorithm
Betweenness Centrality を計算する。厳密解を求める実装ではなく近似解を計算しているため、注意点がいくつかある。
1. 下位 3bits が少なくとも0でない枝のみを探索することで、|E| = 7/8m = 7n と約7/8になる。
2. 厳密にはAPSPもしくは全点対BFSが必要だが、探索候補を 2^(K4Approx=10) で済ませている。1024点以下であれば厳密解。

openmp 版では、2種類の実装がある。
1. betweennessCentrality()
探索点の候補毎に openmp で並列化する

2. betweennessCentrality_parBFS()
探索内部も openmp で並列化する


PCレベルで計算できる小さな instance では 2 はもの凄く時間がかかってしまい、使えないが MPI で実行しなくてはならない規模のものであるとうまくいっているのだろう。もしくは XMT 関係かと予想してみる。