研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

hugetlbfs と最短路ソルバー。

2008-03-25 15:46:13 | Weblog
前回の方法では、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 を用いて測定してみようと思う。

最新の画像もっと見る

4 コメント

コメント日が  古い順  |   新しい順
Unknown (後藤)
2008-03-24 21:52:46
1/5 ではなくて、1/512 では?それから、2MB は 64bit の場合で、32bit の場合には 4MB になります(なぜでしょう?)
問題が大きくなると結局性能は落ちることになるので、メモリのアクセスを工夫する必要があります。まぁ、難しいかもしれませんが、チューニングの目標としては HugeTLB fs を使った場合と使わない場合とで性能がほとんど変わらない程度とするのがいいかも。
返信する
Unknown (u1low_cheap)
2008-03-25 03:42:33
> 1/5 ではなくて、1/512 では?それから、2MB は 64bit の場合で、32bit の場合には 4MB になります(なぜでしょう?)

おっしゃる通り、1/512 の間違いです。ご指摘ありがとうございます。ページサイズについては PAE モードで動作しているためではないでしょうか?


> 問題が大きくなると結局性能は落ちることになるので、メモリのアクセスを工夫する必要があります。まぁ、難しいかもしれませんが、チューニングの目標としては HugeTLB fs を使った場合と使わない場合とで性能がほとんど変わらない程度とするのがいいかも。

メモリアクセスに関しては改善したいとは思っているのですが、いまだよい方法が見つからずです。。HugeTLB fs なしでも同じとくらいにチューニングですか。最終的にはそのようにしたいです。
返信する
Unknown (後藤)
2008-03-25 05:03:52
> PAE モードで動作しているためではないでしょうか?

1 ページは 4kB。32bit 時のポインタの大きさは 4 bytes = 1024 エントリ、64bit 時のポインタの大きさは 8 bytes = 512 エントリ。1 エントリは 4kB であるので…という具合。

> いまだよい方法が見つからずです。。

HugeTLB で TLB ミスを抑えることができたので、今度はキャッシュミスが頻発する部分を見つけることが容易になります。見つけた後は、アクセスパターンの徹底解析でしょう。

ちなみにキャッシュミスをすること自体には大きな問題はないです。事の本質はこのアクセス先がコンピュータにとって予測不可能であるということです。予測しやすい形式に変更するといいことがあるかも。
返信する
Unknown (u1low_cheap)
2008-03-25 10:51:56
> 1 ページは 4kB。32bit 時のポインタの大きさは 4 bytes = 1024 エントリ、64bit 時のポインタの大きさは 8 bytes = 512 エントリ。1 エントリは 4kB であるので…という具合。

なにか難しく考えていたようです。とてもよく分かりました。ありがとうございます。


> HugeTLB で TLB ミスを抑えることができたので、今度はキャッシュミスが頻発する部分を見つけることが容易になります。見つけた後は、アクセスパターンの徹底解析でしょう。

次はキャッシュミスですね。以前は、一番内側の if 文で大量に起きておりました。ここをどう改善するかがポイントかもしれません。


> ちなみにキャッシュミスをすること自体には大きな問題はないです。事の本質はこのアクセス先がコンピュータにとって予測不可能であるということです。予測しやすい形式に変更するといいことがあるかも。

次アクセスするところをどのように予測するかがポイントなのは分かるのですが。いろいろいじってみたいと思います。
返信する

コメントを投稿