SSCA#2 - 乱数

今まで乱数の質にはあまりこだわらないような実装が多かったので、drand48()は今回初めてみた。グラフジェネレータでは乱数質が問題の難易度に大きく関わってくるので、非常に重要である。

rand()、drand48()いずれも線形合同法を使っている。

rand()は32bit演算を行いそのうち31bitsを、drand48()は64bit演算を行いそのうち48bitsを使用しており、周期はrand()が2^31、drand48()が２^48となる。

drand48() のデメリットは、mrand48()の最下位ビットの周期は131072しかないことと、64bit演算のためにコストが大きいことである。

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 関係かと予想してみる。

SSCA #2

David A. Bader @ Georgia Tech. らの Betweenness Centrality を求めるプログラムは SSCA #2 として公開されている。正確にはその実行時間により、計算機性能を測る benchmark software となっている。

SSCA(Scalable Synthetic Compact Application) link

SSCA #2 - Graph Analysis; stresses memory access; uses integer and character operations (no floating point required); compute-intensive and hard to parallelize.

C/OpenMP ver. では次のように実行することで、その環境での計算機性能を測ることができる。

./SSCA2 <No. of threads> <SCALE>

具体的には
1. n=2^<SCALE>, m=2^(<SCALE>+3) の random グラフを生成
2. bfs based の Betweenness Centrality を計算
3. その際の TEPS 値を算出

centrality の種類

簡単に調べてみるだけでも、

1. degree centrality
ある点の次数
※ 次数はある点に対して入ってくる(もしくは出ていく)枝の数

2. betweenness centrality
ある点の最短路の寄与率

3. closeness centrality
ある点から各点の最短路長の平均(もしくはその逆数)

4. eigenvector centrality
点の重要度。
Google の PageRank はこの手法の変形版。

5. graph centrality
ある点から各点の最短路の最大長(もしくはその逆数)

6. stress centrality
ある点を通る最短路の総数

と思ったよりも多い。

Centrality. http://en.wikipedia.org/wiki/Centrality
Ulrik Brandes. "A faster algorithm for betweenness centrality"

betweenness centrality

グラフの特性を解析する指標の一つとして、centrality(中心性)がある。centrality にはいくつか種類があり、今回扱うのは betweenness centrality となっている。

betweenness centrality は点が全ての最短路にどれだけ寄与しているかを示している。betweenness centrality が高い点は何度も最短路に登場するので、重要な点であるといえる。

基本的に最短路を求める bfs か Dijkstra's Algorithm を用いて計算している。bfs だが cray の XMT を用いて並列で処理するという先行研究もある。

CPUID: inline assembler

gcc の拡張機能である inline assembler の使い方。基本的には次のように記述し使用する。

asm ( assembler_template 
       : output operands                 /* optional */
       : input operands                   /* optional */
       : list of clobbered registers    /* optional */
     );

次のように cpuid() 関数を用意すれば良い。

void cpuid(int op, int *eax, int *ebx, int *ecx, int *edx) {
  __asm__ __volatile__ ("cpuid" :
                         "=a" (*eax), "=b" (*ebx), "=c" (*ecx), "=d" (*edx) :
                         "a" (op) :
                         "cc");
}

今回 assembler template はもちろん "cpuid"。

output operands の "=a" (*eax) は、 EAX レジスタの値を *eax に格納することを意味している。ここで a は EAX に対応し、= で書込みを指定している。b, c, d も同様である。

input operands の "a" (op) は、EAX レジスタに op の値を格納することを意味している。

list of clobbered registers の "cc" は condition codes が変更されることをコンパイラに伝えている。

Intel Processor Identification With the CPUID Instruction

とても興味深い資料。CPUID に関する仕様書となっている。CPUID を調べる事でそのプロセッサがどのような構成になっているか把握することができる。使用法としては EAX レジスタに値を代入して CPUID 命令を実行すると、EAX, EBX, ECX, EDX にそれぞれ値が格納されるというしくみである。

#241618 "Intel® Processor Identification and the CPUID Instruction" pp.14

/proc/cpuinfo

/proc/cpuinfo には色々と面白い情報があり気に入っている。

この情報をどうやって取得しているか気になったので、調べてみるとそのほとんどは CPUID によって取得できるようだ。CPUID を用いれば識別情報を見ることができるので、プログラムの実行時に CPU の名前などを表示したり、SSE 等が使えるか判断するといった気の利いたこともできる。

超大規模ネットワーク n=2^30, m=2^31-1 その2

前回紹介した超大規模グラフへの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

超大規模ネットワーク n=2^30, m=2^31-1 その1

n=2^30, m=2^31-1 という超大規模グラフを作成し、SSSP(1対全最短路問題) を計算してみた。

まず作成方法から。generator は 9th DIMACS で公開されている Goldberg のもの。使用方法は次の通りである。

./sprand.exe #nodes #arcs minLen maxLen seed > output.gr

「2^30 点, 2^31-1 枝数, 枝長 全て1」と指定しグラフを生成する。
Nehalem-EP 系の Xeon X5550 でも次のように 23 分もかかる。

time ./sprand.exe 1073741824 2147483647 1 1 971 > rand_1G_2G-1_1.gr

1133.70s user 87.21s system 89% cpu 22:46.73 total

さてお待ちかねの SSSP 実行時間。

(1) グラフファイル読み込み時間
server1: 1045.282 seconds
server2: 1088.592 seconds

(2) グラフ表現構築時間(Bucket-Sort)
server1: 789.239 seconds
server2: 1363.551 seconds

(3) SSSP (始点1の1対全最短路問題)
server1: 868.166 seconds
server2: 1890.330 seconds

○ server1 (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

○ server2 (6cores x 4sockets = 24cores)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64
GCC : 4.4.4

超大規模グラフ作成 n=2^30, m=2^32

Goldberg による benchmark graph generator を使用して n=2^30, m=2^32 という超大規模グラフを作成してみた。作成には 1 時間ほどかかる。

./sprand.exe 1073741824 4294967296 1 1 971 > rand_1G_4G_1_931.gr  3048.89s user 201.03s system 98% cpu 54:57.39 total

大きさのイメージが掴みにくいので、全米道路ネットワークグラフの USA-road-d.USA.gr を基準に考えてみよう。このグラフは 23947347 点 58333344 枝である。

● ファイルサイズ
102769815175(96G) / 1387075114(1.3G) = 74.091 倍となる。

● 点数・枝数
点数は 2^30 / 23947347 = 44.849 倍、
枝数は 2^32 / 58333344 = 73.619 倍となる。

● SSSP, P2PSP 実行のための領域
USA : (4 * 24M + 8 * 58M) + (16 * 24M) * #threads = 560MB + 384MB * #threads + Priority Queue
(8 * 2^30 + 16 * 2^32) + (24 * 2^30) * #threads = 72GB + 24GB * #threads + Priority Queue

思ったよりも Priority Queue サイズが大きく、一時的にも 160 GB 程になってしまったため、実行不可能。もう少し小さいものでリトライしよう。

新しい MacBook Air

非常に薄い MacBook Air が発売された。現行のモデル(13inch)の最新版とiPad を一回り大きくした程度の 11inch の2種類である。SSD をケースなしで搭載する事でこの薄さを実現したそうだ。ディスクが少ないのと光学ドライブがないことから、メインとしては心もとないが、2nd としては申し分のない出来である。値段も iPad + alpha 位なので手に入れやすい。これまで windows ユーザで新たに mac に手を出すユーザも増えそうである。

結婚式

学部生の頃、活動していたサークルでよく行動を共にすることが多かった友人の結婚式にお呼ばれされた。幸せそうな２人を見てこちらもほくほくさせてもらった。久しぶりにその頃の友人にも再会する事ができ、ちょっとした同窓会でした。

マンデルブロ

卒論で Cell を扱ったとき、サンプルプログラムとして、マンデルブロ集合の描画があった。特に並列計算との相性が良く、目に見える面白さ・分かりやすさから、よく扱う題材としても有名。GPGPU でも CUDA のデモとして含まれている。

10/24 にその Benoît B. Mandelbrot さんがなくなったそうです。お悔やみ申し上げます。

GEMM on GPGPU

GPGPU での行列積の話を聞いた。研究室にある NVIDIA の Geforce ではなく、AMD(ATI) 系の Radeon での話となる。Fermi(NVIDIA) と Cypress(AMD(ATI)) がほぼ同様の peak 性能を示すそうで、Cypress ではキャッシュメモリをうまく使う事で非常に高性能を出す事が出来るようだ。