非同期デリゲートを用いた並列計算の結果に関する考察(3)

最初に

非同期デリゲートを用いた並列計算の結果に関する考察(1)

http://d.hatena.ne.jp/kaminarioyaji/20081227/1230404072

で書いた計算プログラムが、コア/CPU間で非共有型のL2キャッシュをもつPentiumD・Athlon64X2に限って並列化の効果が薄かったので、この原因を推測するとともに、コードの見直しを行った。結果、CPUのキャッシュ構造によらず、デュアルコアではほぼ理論どおり2倍の性能が出るようになった。

非共有型L2をもつCPUで速度が伸び悩んだ原因

原因については、

非同期デリゲートを用いた並列計算の結果に関する考察(2)

http://d.hatena.ne.jp/kaminarioyaji/20081228/1230412212

で述べたように、非同期デリゲートを用いて生成した複数スレッドが、計算時に用いるデータの一部を共有しているためであると推測した（デリゲートに引数としてデータの一部を渡す際、データの型が自前のクラスになっていたために、参照渡しされてしまっていた*1）。

コア/CPU間で共有されてないキャッシュ上に同一データがキャッシングされると、各コア(≒スレッド)がデータを読み書きする際、キャッシュコヒーレンシを維持するためにキャッシュ間で通信が発生する。

各スレッドがデータを共有した場合の、CPU(ex. Athlon64X2)動作概念図。

このとき発生するコストは演算コストよりもだいぶ高い*2ので、コヒーレンシ維持のための通信待ち時間＝CPUの空き時間が発生すると、大幅に見かけの性能が低下することになると考えられる。実際、Athlon64X2で2スレッド計算時、タスクマネージャでCPU使用率を確認すると80%*3程度しか使用されなかった。このときの、2threadで計算時の性能の伸びは1threadで計算したときに比べ1.6倍だったので、L2のコヒーレンシ維持のためにCPUが20%分遊んでいたと考えるとよく一致する。

コードの改良と結果

非同期デリゲートに渡していた引数に使っていた自前のクラスを、構造体に書き直すことで値渡しされるようにした。これにより、各スレッドは完全に独立したデータのみを用いて計算を行えるようになっているはず･･･。

というわけで、改良前と後の計算結果。上段(暖色系の色)が改良前、下段（寒色系の色）が改良後。バーが短いほど高速。

計算に用いてた複素数を、クラスから構造体に変えたところ全体的に処理時間が向上した。詳しい原因は調べてないのでよく分からないけど･･･。インスタンス生成時にかかってたコスト分下がったのかなぁ？？まぁいいや。
このおかげなのか、Athlon64X2はCore2に迫るまでに高速化された。FPUの性能は元々高いので、余計な処理が減ったことで計算におけるFPU演算の比率が高まって、Core2との差が狭まったのかなぁとか。

で、改善前と後で、2thread時の速度向上率(時間の短縮具合を算出)をまとめた。

改善後、シングルコアのPentiumMでも2thread時に微妙に速くなってるような･･･。これに関してはイミフなので無視。非同期デリゲート（スレッドプール）の仕組みが何かいい方向に働いてるのかなぁ･･･。

肝心のAthlon64X2・PentiumDに関しては、想像通り2thread時の性能が理論値(2倍)に近いところまで改善された。このことから、キャッシュコヒーレンシ維持にコストがかかっていたっていう仮定が合っているのではないかなぁと思われます。

Core2に関しても、今回のコード変更による影響はほとんどないようで。上手いことコードを書けたなぁと自己満足。

感想とかその他雑多な話

Phenom徹底分析（前）：ネイティブクアッドコアに意味はないのか？

http://www.4gamer.net/games/039/G003983/20071223001/

の中ほどで紹介されている、Intel 64 and IA-32 Architectures Optimization Reference Manual(リンク先はPDF)の8.6.2.1に『共有バスをまたいでのデータの共有は最小限にせよ』とある*4ので、今回結果的にはこれに準じたコードを書いていたってことになるのかなぁ。intelの資料は非常に薀蓄に富んでいるんだなぁと改めて思った。てか、intel向けの最適化リファレンスと銘打ってはいるけど、内容自体はCPU全般に当てはまる話じゃんとか。

ま、それはさておき、.NET Framework 4.0でParallel FX Libraryなる並列化ライブラリが導入される予定みたいで。ForをParallel.Doに置き換えたらうまいこと並列計算してくれる超クールなライブラリ！っていうか、こんなん出るなら、今回の俺の努力とか超絶的時代錯誤な感がMAXなわけなのですが、実際に走らされた方の日記を見てみると

Parallel Extensions to the .NET FX CTP(2)

http://d.hatena.ne.jp/NyaRuRu/20071203/p2

確かに速度向上は Dual Core で 1.6 倍ぐらいですな．あくまでお気楽 qsort で，ですが．

『quick sortで』と書かれているので、単純な数値計算の話から類推していいものか大いに怪しいのですが、おおむね1.6倍程度しかでない、となるとキャッシュコヒーレンシ(Core2を使われているっぽいのでL1$のコヒーレンシ、かなぁ？)維持のための通信コストがかかってる＝自動で生成されるスレッド間でデータを共有してしまってるじゃないかなぁとか。

べっ、別に自動生成されるコードなんかより自分が書いたコードの方が優秀だって言いたいわけじゃないんだからねッ！

閑話休題。

キャッシュコヒーレンシ維持による速度の低下は、現行の主流メニイコア（共有L2のみを持つCore2や、共有L3をもつCore i7）ではそう問題にならない気はするものの、今回問題になった共有L2を持たないK8はまぁ当然として、共有L3があるもののVictim Cache形式のK10、今後出てくるLarrabbe（16〜コア間で物理的には共有しているL2があるものの、各コアごとに固定的に分割される、予定*5）では、性能向上を妨げる - 16コアあるのに速度が10倍くらいにしかならないとかの - 要因になりうるんじゃないかなぁとか。

Parallel FX Libraryってそのへん上手くやってくれるのかなぁと、CTP版のパフォーマンスを見てちょっと不安になったのでした。ま、正式リリースされたらどうなっていようが使うだろうけどｗ

*1:C#では、メソッドの引数は通常値渡し。ただし、ユーザー定義クラスは参照渡し。

*2:参考：http://www.4gamer.net/games/039/G003983/20071223001/ グラフ4,5

*3:2コアでフルに使ったときが100%

*4:逆に言うと単一プロセッサ内での共有は禁止していない。

*5:参考： http://pc.watch.impress.co.jp/docs/2008/1125/kaigai477.htm