hugetlbfs と最短路ソルバー。

前回の方法では、malloc で確保した領域が全て HugeTLB の上に乗ってしまうので、mmap を用いて自作のルーチンを作った方が良いかもしれない。正直、最短路ソルバーで malloc するものは、かなり大きな配列（構造体の配列も）であるのでこのままでもよいが、小さなグラフの場合ではかなり遅くなってしまうかもしれない。

やはり自作で作った方がいいとは思うのだが、ソースに手を加える前に実験を行ってみた。


実験環境は
CPU : Core2Duo E8200 3.2 GHz (2.66 GHz からクロックアップ)
OS : CentOS 5.1 64bit
gcc : gcc 4.3
HugeTLB : 1GB (2048 KB x 512)

クエリファイルはこれを用いている。

0. multi-bucket(by goldberg)
20.13[s]

1. bucket
14.55[s]

2. bucket with libhugetlbfs
12.07[s] (x 1.21)

3. heap
21.39[s]

4. heap with libhugetlbfs
18.20[s] (x 1.18)

と、1.2 倍ほどに高速化されている。ページサイズが 4KB → 2MB と大きくなり、TLB ミスが 1/512 となったためであろうか。こちらも OProfile を用いて測定してみようと思う。

libhugetlbfs。

TLB (Translation Look-aside Buffer) は、仮想メモリ空間のアドレスを物理メモリのアドレスに変換するための情報を格納/管理するキャッシュである。このサイズはデフォルトで 4096 Byte であるので、それ以上大きなサイズのデータにアクセスする際には、TLB ミスが発生してしまう可能性がある。HugeTLB を用いることで、より大きなサイズに変更することができる。

用いている CPU は Core2(SMP) なので HugePages のページサイズは、2048 kB となってる。この値は CPU、OS によって異なり、可変なものもあるようだ。

具体的な作業としては、su になってから、以下のようにすればよい。
まずは作業用ディレクトリを用意する
# mkdir /huge

type device directory、読み書き可能なモード、パーミッションマスクを以下のように指定し、mount する。
# mount -t hugetlbfs hugetlbfs /huge -o rw,mode=0777

エントリ数を設定するには以下のようにすればよい。
# echo 512 > /proc/sys/vm/nr_hugepages

以下のように、そのページサイズを確認することができる。
$ grep Huge /proc/meminfo
HugePages_Total: 512
HugePages_Free: 512
HugePages_Rsvd: 0
Hugepagesize: 2048 kB


実行する際に、環境変数を設定することで malloc を HugeTLB にのせることができる。
$ HUGETLB_MORECORE=yes LD_PRELOAD=libhugetlbfs.so ./a.out


当然ながら Hugepagesize x HugePages_Total (今回は 2048 kB x 512 = 1GB)分だけメモリが確保されてしまうので、必要な分のみ確保する方がよいだろう。

データ構造へのアクセスを改善 その２。

始点 ID 順にソートした後に、枝長順にソートして、データ構造にアクセスを少しでも減らそうと考えていたが、良い結果にはなっていない。特にファイルからグラフデータを形成するまでにかかる時間が、環境にもよるが５０秒から６０秒とかなり増えてしまっている。また、ダイクストラ法の部分も分岐が増えたためか、返って遅くなってしてしまっている。


また、
export MALLOC_TRIM_THRESHOLD_=-1
export MALLOC_MMAP_MAX_=0
といった環境変数を export すると、グラフによっては Segmentation fault が発生するといったバグも見つかった。こちらもみていくしかない。

データ構造へのアクセスを改善。

bucket 法がとても改善しずらい実装（とてもシンプルであるため）であるのに対して、heap は何かと改善できる部分が多いような印象を受ける。

いま考えていることは、どちらにも適用できそうであり、実験するのが楽しみである。グラフは Forward star representation で持っているが、同一点 ID では枝長順で更にソートする。そうすれば、枝の走査時に次の候補点が見つかれば、データ構造にいれずにすぐに次の走査ができる。グラフ格納の時間が増えてしまうが。

どちらのデータ構造にも適応できると文頭で書いたが、正直 heap にしか効果がないようにも思える。bucket 法では最長枝の長さ分の配列を距離分だけインクリメントすることになってしまうからだ。また、データ構造の走査にあまり処理を要さないからだ。

アライメントは関係ない？その２。

こちらでは、

export MALLOC_TRIM_THRESHOLD_=-1
export MALLOC_MMAP_MAX_=0

として、それ以外は前回と同じ条件で行っている。



・heap1 に関して
環境変数を設定する前と比べ、アライメントの効果を受けやすくなった。8byte, 128 byte 以外では大きいところで１秒ほども改善された。


・heap2 に関して
heap1 とちょうど反比例するかのように、全体的に性能が悪くなってしまったが、一番良いところではあまり変化がないので、気にすることではないのかもしれない。ただ、こちらをメインに改善していこうと思っていたところなので、なんとなくショックである。


・bucket に関して
こちらは全体的に改善されている。特に 16 byte で良い結果を残している。

アライメントは関係ない？その１。

まずは、
　export MALLOC_TRIM_THRESHOLD_=-1
　export MALLOC_MMAP_MAX_=0
を設定しない状態で。


画像についての説明だが、
・heap1 というのは、通常の heap を用いた実装。
・heap2 は、ポテンシャルの更新と、heap の操作を分離した仕様。
・bucket は、Dial の実装になっている。

・前回と同じクエリファイルを用いている。

・実験環境は
CPU : Intel(R) Xeon(R) CPU E5345 @ 2.33GHz
OS : CentOS 5.1 64bit
compiler : gcc 4.1.2

8 byte ～ 8192 byte まで、アラインメントを変えて実験しているが、大雑把に見るとほとんど変化が見られない。


・heap1 に関して
アライメントはあまり関係ないようで、デフォルト(8 byte)が一番良い結果になった。むしろ関係あるのかともいえるかもしれない。


・heap2 に関して
heap1 に比べこちらの方が若干ではあるが、高速化されている。1024 と 8192 以外はおおむね改善されていると思ってよいだろう。


・bucket に関して
こちらは連続的なアクセスが多いので、アライメントの効果が得られやすいと思っていたが、64byte、128byte、256byte 以外では効果が小さいながら良くなっていた。

ページフォルト？

後藤さんにアドバイスを頂いたので、紹介します。

「確保するサイズが大きい場合は、ページフォルトが問題になるので、

export MALLOC_TRIM_THRESHOLD_=-1
export MALLOC_MMAP_MAX_=0

と環境変数を設定すると良い。」


・MALLOC_TRIM_THRESHOLD_
は OS に未使用になったメモリを返却する契機をあらわしていて、-1 では決して返却しないことを表している。

・MALLOC_MMAP_MAX_
は最大 mmap 数をあらわし、０は決して mmap しない。1MB 以上のメモリ確保では、malloc は内部で mmap を呼び出しているようだが、どんなに大きなメモリでも brk を使ってメモリを取る。


こちらのブログを参考させていただきもらいました。

アライメント。

今さらなのだが、アライメントの揃っているデータを用いるように改良してみた。malloc では、８バイトにアライメントされたメモリアドレスを返すが、他のサイズアライメントは次のように posix_memalign() を用いることで、簡単にアライメントの揃った領域を動的に確保する事が出来る。


#define _XOPEN_SOURCE 600
#include <stdlib.h>

static inline void *aligned_malloc (int size, int align) {
　void *p;
　if (posix_memalign((void**)&p, align, size)) exit(1);
　return p;
}


align の部分をいろいろ変えて実験してみたがあまり変化が現れない。posix_memalign() を用いたのがまずかったのか。まずは初期化部分くらいは SIMD 化したい。

オーバークロックと最短路。

研究室の Penryn コアのマシンをオーバークロックしたので、実験行った。いつも通り p2p タイプの１０個のクエリの最短路問題を解いてみた。１０クエリであるので、始点終点のペアが１０対に対してダイクストラ法を実行したものである。用いているクエリファイルものせておく。つまり１つ１つは１～２秒で実行できる。それに比べ、グラフ読み込みが４０～５０秒とかなりかかってしまうので、どうにかならないものかと思ってしまう。

[p2p タイプの１０個のクエリ]
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



[環境]
CPU : Core2Duo E8200 2.66GHz
Mem : 4GB
CentOS 5.1 / gcc 4.1.2

[データの見方]
「使用したデータ構造」、「実行時間」、「オーバークロックによる高速化」、「オーバークロックした比率との割合」


[Penryn 2.66 GHz]
１レベルバケット　　　16.34 [sec]
マルチレベルバケット　 ---
ヒープ　　　　　　　　26.66 [sec]

[Penryn 3.56 GHz] (x1.34)
１レベルバケット　　　12.88 [sec] (x1.27 : 94%)
マルチバケット　　　　18.58
ヒープ　　　　　　　　20.68 [sec] (x1.29 : 96%)

[Penryn 3.92 GHz] (x1.47)
１レベルバケット　　　11.74 [sec] (x1.29 : 87%)
マルチバケット　　　　16.85
ヒープ　　　　　　　　18.80 [sec] (x1.42 : 96%)



ヒープはどちらもクロックを上げた分だけ、高速化されていることがわかる。それに比べ、バケット法はまだまだ速くなるだろう。ちなみに「マルチバケット」は Goldberg 氏のもので、9th DIMACS Implementation Challenge から持ってきたものだが、いろいろ実行してみると２レベルだけというわけではないようなので、このようにした。

TLB ミスの測定。

oprofile を用いるとキャッシュミスの測定や、TLB ミスの測定を行える。

イベント一覧の表示
$ sudo opcontrol --list-events

イベントの設定
$ sudo opcontrol --event=DTLB_MISSES:500:0x01

初期化する
$ sudo opcontrol --shutdown
$ sudo opcontrol --start

実行
$ sudo opcontrol --reset
$ ./a.out
$ sudo opcontrol --dump

テーブルの表示
$ opreport -c ./a.out

ソースコードレベルでのプロファイル情報の表示
（-a でアセンブリコード、-s でソースコードの表示）
$ opannotate -a -s ./a.out

一時停止
$ opcontrol --stop

終了する
$ opcontrol --shutdown




p2p タイプの１０クエリを１スレッドで解いた際のサンプリング結果を一部のせておく。
・バケット法
2181704 99.6357 dijkstra_with_heap
4150 0.1895 quicksort_by_tail
1017 0.0464 read_dimacs_graph

・２分ヒープ
1540940 99.4507 dijkstra_with_bucket
4108 0.2651 quicksort_by_tail
1022 0.0660 read_dimacs_graph

やはりダイクストラ法のループ内で大量の TLB ミスが起こってしまっている。
特にポテンシャルを比較するところである。これを減らしていくことが今後の目標だ。