前回の方法では、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 を用いて測定してみようと思う。
やはり自作で作った方がいいとは思うのだが、ソースに手を加える前に実験を行ってみた。
実験環境は
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 を用いて測定してみようと思う。
なにか難しく考えていたようです。とてもよく分かりました。ありがとうございます。
> HugeTLB で TLB ミスを抑えることができたので、今度はキャッシュミスが頻発する部分を見つけることが容易になります。見つけた後は、アクセスパターンの徹底解析でしょう。
次はキャッシュミスですね。以前は、一番内側の if 文で大量に起きておりました。ここをどう改善するかがポイントかもしれません。
> ちなみにキャッシュミスをすること自体には大きな問題はないです。事の本質はこのアクセス先がコンピュータにとって予測不可能であるということです。予測しやすい形式に変更するといいことがあるかも。
次アクセスするところをどのように予測するかがポイントなのは分かるのですが。いろいろいじってみたいと思います。
1 ページは 4kB。32bit 時のポインタの大きさは 4 bytes = 1024 エントリ、64bit 時のポインタの大きさは 8 bytes = 512 エントリ。1 エントリは 4kB であるので…という具合。
> いまだよい方法が見つからずです。。
HugeTLB で TLB ミスを抑えることができたので、今度はキャッシュミスが頻発する部分を見つけることが容易になります。見つけた後は、アクセスパターンの徹底解析でしょう。
ちなみにキャッシュミスをすること自体には大きな問題はないです。事の本質はこのアクセス先がコンピュータにとって予測不可能であるということです。予測しやすい形式に変更するといいことがあるかも。
おっしゃる通り、1/512 の間違いです。ご指摘ありがとうございます。ページサイズについては PAE モードで動作しているためではないでしょうか？
> 問題が大きくなると結局性能は落ちることになるので、メモリのアクセスを工夫する必要があります。まぁ、難しいかもしれませんが、チューニングの目標としては HugeTLB fs を使った場合と使わない場合とで性能がほとんど変わらない程度とするのがいいかも。
メモリアクセスに関しては改善したいとは思っているのですが、いまだよい方法が見つからずです。。HugeTLB fs なしでも同じとくらいにチューニングですか。最終的にはそのようにしたいです。
問題が大きくなると結局性能は落ちることになるので、メモリのアクセスを工夫する必要があります。まぁ、難しいかもしれませんが、チューニングの目標としては HugeTLB fs を使った場合と使わない場合とで性能がほとんど変わらない程度とするのがいいかも。