インライン・アセンブラ。

前回の Penryn コアでの実験結果より、最短路ソルバーではキャッシュサイズが大きさが実行時間に大きく関与しているようである。キャッシュ利用がうまくできれば、より高速化できる見込みがありそうだ。ソフトウェア・プリフェッチを行いたいので、最近はインライン・アセンブラについて調べてみている。アセンブラは今回初めて触ったのだが、いまだによく分からないことが多い。



まとめると、アセンブリ言語には AT&T(gcc)、Intel(icc) と２種類の形式があり、つぎのように命令の方向が異なるので注意が必要である。
[AT&T]
　asm ("命令 source, dest");

[Intel]
　asm {命令 dest source};



拡張機能を用いれば、次のように変数名をそのまま用いる事が出来る。単純な足し算を行う関数の例では次のようになる。

　asm (アセンブリコード : 出力オペランド : 入力オペランド : 破壊レジスタ);

int add_test (int a, int b) {
　int tmp;
　tmp = a + b;
　return tmp;
}

int add_test_asm (int a, int b) {
　int tmp;
　asm ("add %1, %2" : "=r"(tmp) : "r" (a) ,"r" (b));
　return tmp;
}



実装する際にはダイクストラ法のループに、次の探索点になりそうなデータをプリフェッチするコードを埋め込むことになるだろう。

ary[i] をプリフェッチするためには、次のようなコードを埋め込めばよいようだ。

asm("prefetcht0 %0" : : "m" (ary[i]) : "memory");

また、プリフェッチ命令には次の４種類があるが、これもいろいろ試してみる必要がありそうである。
・prefetcht0
・prefetcht1
・prefetcht2
・prefetchnta



[参考]
IA-32 インテルR アーキテクチャソフトウェア・デベロッパーズ・マニュアル
http://www.yuasa.kuis.kyoto-u.ac.jp/~yasugi/4/k2.html
http://yashiromann.sakura.ne.jp/memo/GCC-Inline-Assembly-HOWTO.html
http://www.mars.sannet.ne.jp/sci10/on_gcc_asm.html
http://7ujm.net/linux/asm.html

Penryn。

研究室で新たに Penryn コアのマシンを導入した。秋葉原のショップの方は、Mac の方に流れており、かなり品薄なのだとアピールされていた。さっそく既存のマシンとの比較を行ったが、最短路問題ではかなり良い結果となっている。クロック数に多少差があったとしても、L2 キャッシュサイズのおかげか、逆転できている。

ちなみにクエリは p2pタイプ で １０個で実験しており、かっこの中の数字はスレッド数を表している。

gcc と icc その２。

指摘をいただいたので。実験をしたマシンはデフォルトで 64-bit であったのに、-m64 をつけた場合とそうでない場合という実験を行っていました。複数回計測しても -m64 なしの方がより早い結果になってしまったのですが、-m32 と比べると明らかでした。

　　　　bucket　　heap
-m64　　24.75　　36.89
-m32　　26.06　　44.98


また、最短距離のみを計算するヴァージョンも作成した。

bucket　　heap
22.91　　35.80

演算数が減ったからといって、ヒープが思ったより早くならず、より差が開く結果になった。

gcc と icc。

コンパイラとそのオプションを見直した。そろそろこのクエリ（p2p を１０クエリ）では実験がしずらくなってきた。クエリをスレッド並列しているため、１０クエリでは８並列するメリットが半減してしまう。次からはもう少し大きいもので実験してみようと思う。

前回まで基本的には「gcc -O2 -march=nocona」で行っていたのだが、そろそろ見直すころかなと思い、いくつかのパターンについて実行時間を測定してみた。なお、gcc は 4.1.2 を、 icc は 10.1 を用いている。

結果として、最適化オプションは 「-O2」 で十分であることがわかる。また、思ったより gcc も icc も大差はないことがわかり、頻繁に扱っているバケット法では gcc の方が良い結果となった。64bit にすると若干速度が低下してしまう事がわかった。さまざまな要因によって、起きていると思われるので、１つ１つ対応を付けられるように調べていきたい。

１レベルバケット or ヒープ。

今まで、dimacs graph data をそのまま用いて実験を行っていたが、枝長についてはあまり考慮しなかった。しかし、バケット法での枝長はかなりクリティカルなものであるため、枝長に影響を受けないヒープも見直していこうと思う。

まずは、pthread で書き直したヒープの実行時間である。やはり通常の道路ネットワークではバケット法に勝ち目はないようだ。ただ goldberg 氏の２レベルバケットと比べてもあまり大差はなく、最適化次第では逆転も十分考えられそうである。

[ヒープ]
１スレッド　38.54 [sec]
２スレッド　21.05 [sec]
４スレッド　12.53 [sec]
８スレッド　 9.58 [sec]

[１レベルバケット]
１スレッド　24.19 [sec]
２スレッド　13.80 [sec]
４スレッド　 8.36 [sec]
８スレッド　 6.92 [sec]

[２レベルバケット]
１スレッド　36.08 [sec]



次にグラフの枝長を10倍、100倍にしたものに対して、上記の「１レベルバケット法」、「ヒープ」について、実験を行った。

[ヒープ]
　　１倍　38.54 [sec]
　１０倍　40.23 [sec]
１００倍　42.37 [sec]


[１レベルバケット]
　　１倍　24.19 [sec]
　１０倍　50.85 [sec]
１００倍 222.84 [sec]

予想よりもヒープは枝長に影響を受ける結果となったが、それでもほとんど実行時間は変わらず、安定していた。バケット法は距離分だけ、バケット配列をインクリメントするため、グラフの枝長の範囲が大きいとき、無駄な処理が大きくなってしまう。できれば、グラフの特性を選んでデータ構造を自動的に、データ構造を選ぶのが望ましいだろう。

signed or unsigned。

いろいろプログラムを作成しながら、実験している。

今まで、未探索点に対するラベルとして -1 で初期化していたが、unsigned 同士の演算のときは unsigned の方が良いと思い、#include <limits.h> で定義されている UINT_MAX にすることにした。以前はあまり効果がなかったと思うのだが、データの流れをしっかりした後では少しであるが効果があるようだ。それにともない、探索ループを少しだけだが、変更した。

[1] 変数は int、-1 で初期化
24.89[s]

[2] 変数は int、UINT_MAX で初期化
25.00

[3] 変数は unsigned int、UINT_MAX で初期化
24.98

[4] 変数は unsigned int、UINT_MAX で初期化、ループ内の処理をまとめる
24.19

非負の数で初期化したことにより、ループを１つにまとめることができるので、多少効果が合ったのではないか。

[4] については、スレッド数が１でないときも実験してみた。

1 thread　：24.1934 [sec]
2 threads ：13.8004 [sec]
4 threads ： 8.3606 [sec]
8 threads ： 6.9205 [sec]


よく見てみると以前のものと、実はほとんど変化はないようである。いろいろいじっているうちに、変更点が分からなくなってしまっているようにも思える。。参考までに前回の実験結果をのせておく。

[前回]
1 thread　：24.3334 [sec]
2 threads ：13.7868 [sec]
4 threads ： 8.2452 [sec]
8 threads ： 6.9109 [sec]

先読みスレッド。

とりあえずクエリごとにマルチスレッドで動かすプログラムでいろいろ実験をしてはいるが、どのような方向性にするのかうまく決まらず、あまり作業が進まない。まず考えていることをまとめることから初めていこうと思う。


＜先読みスレッドについて＞
・I/O 周りはオーバーヘッドも大きいため、とりあえず別スレッドへ。
・I/O スレッドにて、先読みを行う。


＜先読みの方法＞
・複数のスレッドで、バケット内にあるデータを見張る（バケット内の点から出ている枝なども）
　→無駄な処理が大きい

・ダイクストラ法を動かしているスレッドと同期をし、最小ポテンシャルノードを渡す
　→同期のためのオーバーヘッドが大きく、かえって遅くなるかもしれない

・ダイクストラ法を動かしているスレッドと同期をせずに、計算量を見積もり次使いそうな点を見張る
　→正確な見積もりができないと、効果を得られない。


やりたいのは３つ目であるが、どのように実現するか迷っている。いろいろ調べてみよう。