実験 - 08/04/27 現在。

ソースコードをいろいろいじっているうちに、ヒープ版の実行時間が短くなってきたので、ここら辺で全米グラフに対しての１対１最短路の実行時間を測定してみた。

実行環境は以下の通りになっている。すべて１スレッドで実行しており、ファイル読み込みを含めての実行時間となっている。

CPU : Xeon(R) E5345 2.33GHz (4core x 2)
Mem : 16 GB
OS : CentOS 5.1 (64bit)


バケット　　　　　　　2548 秒
ヒープ　　　　　　　　3920 秒
マルチレベルバケット　4088 秒


[binary heap] で [malti-level bucket] を抜くというのが１つの目標だったので、とりあえず達成する事が出来た。[binary heap] は特にメモリ要求量が少ないため、低スペックな組み込み系ハードで実行する際に必要になってくるといえる。

改善点３。

ダイクストラ法では、配列もしくは構造体の配列を一定の値で初期化しなければならない。ダイクストラ法自体の実行時間に比べ、初期化は５％ほどであるため、簡単には無視できない。

用いる型が unsigned int であれば、最大値である 4294967295 の値を INFINITY として扱っているが、通常は以下のような for ループで行うことが多いだろう。


for (i = 0; i ＜ size; i++) {
　node[i] = INFINITY;
}


ただ、構造体のコピー（代入）はコストも高いために、最大値のような値をセットするためには、memset() を用いた方が効率的である。しかしながら、memset() は１バイトずつ書き込むことになるので、決まった値のときに有効である。

たとえば、unsigned int の最大値であれば、全ビットの値が１であるので、以下のようにすれば、セットできる。

memset(node, 255, sizeof(node_t)*size);

改善点２。

バケット法において、バケットへノードを代入する際に用いる余算について。

前回記事の [2] に相当するものである。


[1]
node_potential が bucket_size に対して大きくないときでも、毎回余算を行う。

bucket_insert (node_id, node_potential % bucket_size);


[2]
大きい場合のみで、余算を行う

bucket_insert (node_id,
　　　　　　　node_potential <bucket_size ? node_potential : bucket_size);

実験してみると [2] の方が高速化されているような気もする。ただ、グラフにも影響を受けるようになるので、ここは注意しておこうと思う。

改善点１。

バケット法において、循環リスト内で要素の入っているバケットを探すためにインクリメントする方法について。

[1]
循環リストなので、容易に考えられる実装。
一番端までインクリメントされたら、余算により先頭要素へ。

i = (i + 1) % bucket_size;



[2]
１度しか必要でない余算を毎回するのはもったいない。
余算コストに比べ、比較コストは小さいので、効果あり。
ダイクストラ法では１割ほど高速化。

i++;
if (i >= bucket_size) i = 0;



[3]
先頭ノードに向かうのは１度だけであるので、ループをわけてしまう。

for (i = crt_bucket; i <bucket_size; i++){　}

実行時間は [1] >> [2] > [3] と、なっている。

クエリの割り振り。

前回の記事で少し見積もりに触れたので。

現在は１０００クエリを４スレッドでスレッド並列した場合、
１スレッド目　：　　　１～２５０
２スレッド目　：　２５１～５００
３スレッド目　：　５０１～７５０
４スレッド目　：　７５１～１０００

という風に、あらかじめ割り振ってしまっている。

１対１最短路では実行時間の見積もりが立てづらく、１つ１つのクエリが全米でも数百ミリ秒～５秒と実行時間は短めであるために、クエリを割り振る部分でのオーバーヘッドが効いてきてしまうのではないかという懸念からである。

だからと言っても、やはりスレッドごとがうまく平均化されるというのは考えにくいので、いくつかの塊に分け、ブロック毎に動的に割り振るという方法がいいのではないかと思う。

多クエリ対策。

ここのところ 1000 クエリを扱ってみて気づいたこととしては、クエリ数が増えていくにつれて同じ始点からの最短路を扱うこと必然的に増えてくる。

そういった際に複数回演算してしまうのは勿体ないので、別ルーチンにしようかと検討している。

「１対全最短路を解いてしまい、あとから必要なデータを抜き出す」か、
「すべての終点までの最短路を求めるまでで終了する」
という２パターンが考えられるが、前者を採用しようと思う。

理由としては、「１対全最短路は思ったより時間がかからなく」、「すべての終点まで最短路が求まった段階で終了するのでは、分岐の多くなってしまってかなりの低速化が起きてしてしまう」からである。また１対１最短路よりも実行時間の見積もりも立てやすい。もちろん単にコーディングが容易であるというメリットもある。

NY 1000 queries [2]。

CPU : Dual Core AMD Opteron(tm) Processor 270 (2GHz, L2 1MB) (2core x 2)
OS : CentOS 5.1 64bit
GCC : 4.1.2

Graph : USA-road-d.NY.gr
Query : NY1000.p2p （ランダムな 1000 クエリ）


実行時間は Xeon には及ばないにしても、スレッドごとの割合はほぼ等しいといえる。

NY 1000 queries [1]。

CPU : Xeon E5345 2.33 GHz (L2 4MB) (4core x 2)
OS : CentOS 5.1 64bit
GCC : 4.1.2

Graph : USA-road-d.NY.gr
Query : NY1000.p2p （ランダムな 1000 クエリ）

USA に比べ１クエリに要する実行時間が極端に小さいため、すぐに終了する。USA のときのグラフを重ねて見ても、割合にはあまり変化がないようにみれる。ひとつ異なる点としては、８スレッド時にそこまで性能が落ちないことだが、NY では扱うデータの大きさが USA に比べ極端に小さいためであると推測できる。

USA 256 queries。

CPU : Dual Core AMD Opteron(tm) Processor 270 (2GHz, L2 1MB) (2core x 2)
OS : CentOS 5.1 64bit
GCC : 4.1.2

Graph : USA-road-d.USA.gr
Query : USA256.p2p （ランダムな 256 クエリ）

Opteron では 1000 クエリで実行するには荷が重いので、ランダムな 256 クエリで実行した。こちらは個人的に作成したものである。こちらは 4 core であるので、４スレッドまでしか測定できなかったが、４スレッドまでは Intel でも、HT の AMD でも、リニアに伸びる。２つのグラフを重ねてみても、ほとんどその伸び率は変わらないようにも見えた。全米データは基本的にグラフ特性が似ており、他のグラフで計測してみると何か分かるかもしれない。

USA 1000 queries。

現段階での最短路ソルバーの実行時間を計測してみた。

CPU : Xeon E5345 2.33 GHz (L2 4MB) (4core x 2)
OS : CentOS 5.1 64bit
GCC : 4.1.2

Graph : USA-road-d.USA.gr
Query : USA-road-d.USA.p2p （ランダムな 1000 クエリ、こちらからいただきました）

結果としては 1, 2, 4 ではリニアに性能が伸びているが、8 スレッドにすると性能が伸びずバケット法では悪化してしまう。FSB のバンド幅がボトルネックになってしまっているのであろう。他の CPU （AMD 系など）でも試してみよう。

HugeTLB と TLBミスの測定。

penryn マシンでは oprofile が動作しないので、少し古めのマシンになってしまうが、Xeon 2.80GHz (L2 cache 1MB) を用いて測定してみた。

HugeTLB ファイルシステムへ全米で用いる 1GB のメモリに割り当てる際には、素早く終了する場合と、そうでない場合がある。特に、メモリ割り当てによりシステムが不安定になってしまうこともあるため、注意が必要であるといえる。

結果として、HugeTLB を用いると「ダイクストラ法を走らせるルーチン dijkstra_with_bucket()」でのTLB ミスが無くなった。その分、「クイックソートルーチン quicksort_by_tail() 」で TLB ミスが増えている。ページサイズが 2MB になったために、細かい単位で操作するクイックソートでは TLB ミスが多発してしまうのであろうか。


CPU : Xeon 2.80GHz (L2 cache 1MB)
OS : Fedora 8 64bit
gcc : 4.3.0


[HugeTLB 未使用]
61.7530[sec]

-------------------------------------------------------------------------------
236899 99.1305 dijkstra_with_bucket
236899 100.000 dijkstra_with_bucket [self]
-------------------------------------------------------------------------------
1981 0.8290 read_dimacs_graph
1981 100.000 read_dimacs_graph [self]
-------------------------------------------------------------------------------
97 0.0406 .plt
97 100.000 .plt [self]
-------------------------------------------------------------------------------


[HugeTLB 使用]
46.3576[sec]

-------------------------------------------------------------------------------
136896 98.7050 quicksort_by_tail
136896 100.000 quicksort_by_tail [self]
-------------------------------------------------------------------------------
1717 1.2380 read_dimacs_graph
1717 100.000 read_dimacs_graph [self]
-------------------------------------------------------------------------------
79 0.0570 .plt
79 100.000 .plt [self]
-------------------------------------------------------------------------------

循環リスト(circularly-linked list) その２。

前回の記事で扱った循環リスト高速化の工夫 (bucket+ のほう) について実験をした。いつもどおりクエリは以下のもの。

p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879





[Intel(R) Xeon(R) E5345 @ 2.33GHz]
OS : CentOS 5.1 64bit
gcc : 4.1.2
option : -O2
bucket+ 23.0508[sec]
bucket 24.3352[sec] (x 1.05)



[Intel(R) Core(TM)2 Duo CPU E8200 @ 3.2 GHz]
OS : CentOS 5.1 64bit

gcc : 4.3.0
option : -O2
bucket+ 13.5265[sec]
bucket 14.4001[sec] (x 1.06)


gcc : 4.1.2
option : -O2
bucket+ 13.1757[sec]
bucket 14.0092[sec] (x 1.06)



わずかながら、penryn の方が高速化の割合が大きい。それから、gcc のヴァージョンは 4.1.2 の方が良い結果になった。

循環リスト(circularly-linked list)。

バケット法 (Dial's implementation) では、探索候補ノードの順番を最大枝長分の配列 bucket[max_length] と、両方向リストによって保持している。bucket[] は、循環リスト（circularly-linked list）であるので、次の要素を参照するときに、次のような演算を多用する。(bucket_size == max_length である)

i = (i + 1) % bucket_size;

バケット法では距離分だけ上記の演算をする（全米データ１対全では 4000万～5000万回ほど）ため、除算のコストがばかにならない。以下のように if 文に書き直すことで改善できる。

i++;
if (i >= bucket_size) i = 0;


また、bucket_size が２のべき乗であるならば、さらに改善できるようなので、bucket[] を切り上げて使用するというのも手のなのかもしれない。

アクセスパターン解析と並行して演算の再確認をしておこうと思う。

oprofile 9.3。

penryn マシン（Core2Duo E8200 2.66GHz -> 3.2 GHz）には、CentOS 5.1 64bit が入れている。デフォルトで入っている OProfile は 9.2 であるため、Penryn に対応していないようだった。

こちらから 9.3 を Download してきた。

基本的に
./configure;make;make install
でいけるのだが、

gcc 4.3 ではうまくいかなったため、gcc 4.1.2 で行ったら難なくできた。


$ opcontrol -v
opcontrol: oprofile 0.9.2 compiled on Mar 14 2007 17:43:08
$ sudo opcontrol --list-events
Using timer interrupt.


$ opcontrol -v
opcontrol: oprofile 0.9.3 compiled on Apr 3 2008 10:55:12
$ sudo opcontrol --list-events
Using timer interrupt.


penryn には 9.3 でも対応していないようである。