前回紹介した超大規模グラフへの1対全最短路問題(SSSP)のマルチスレッド計算の結果。
● instance
Graph : n=2^30, m=2^31-1, U=1(全ての枝長が1)
Query : SSSP x 10
※ 枝長をすべて1としていることが影響しているのか、heap size の最大値は 145,783,040 にも及ぶ。
● results
SSSP x 10 を 2 スレッドで実行した際の計算時間は 29903 seconds = 8.3 hours
となり SSSP 単位の計算時間は 49.8 分となる。
1スレッドで動作させたときの SSSP 単位の計算時間は 14.5 分であるので非常に遅くなってしまっている。
使用した合計メモリは 20.5 GB + 18.6 GB x 2 = 57.7 GB である。
ここでスレッド単位で消化したクエリ数をみると、
0-thread : 9
1-thread : 1
となるため、片方のスレッドはほとんど動いていない。
使用したマシンは、NUMA 環境 2sockets で 72 GB メモリなので、36 GB/socket となっている。
thread-parallel ではグラフデータは共有し、作業領域は local に確保するようにしているが、
グラフデータと作業領域で 20.5 GB + 18.6 GB = 39.1 GB となるため、
今回は作業領域も local に配置できない状況になる。
それが原因にしても性能低下が大きすぎると思うので、もう少し調べていこう。
○ server (4cores x 2sockets = 8cores)
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
GCC : 4.4.4