How To Write Fast Numerical Code: A Small Introduction

by syoyo

How To Write Fast Numerical Code: A Small Introduction
Srinivas Chellappa, Franz Franchetti and Markus Püschel
to appear in Proc. Summer School on Generative and Transformational Techniques in Software Engineering, Lecture Notes in Computer Science, Springer, 2008

http://spiral.ece.cmu.edu:8080/pub-spiral/abstract.jsp?id=100

とりあえず MUDA という SIMD 言語を作ったりしているものの、
この article でも示されているように、最適化で一番重要なものを上から並べると、

– 効率的なアルゴリズム
– メモリアクセス(キャッシュまわり)
– 最後に、SIMD 化

になるわけです。結局のところ、小手先の SIMD 化というのは、実はあまり効果がないのです。

アルゴリズムの改善

まずアルゴリズムを改善することが一番重要。
悪いアルゴリズムをどんなに最適化しても、効率の悪いパフォーマンスしか実現できない。
効率の良いアルゴリズムは、どんな小手先の最適化にも勝ります。
そして効率の良いアルゴリズムをさらに SIMD 化などで最適化すれば、
大きな処理効率の飛躍が望めます。
ただ、アルゴリズムを考えだすのには頭をとっーーーても使う。
(でもインド人に勝つためには、こういう知的生産を行うべきなのです)

考えて考えて考えて、でも効率の良いアルゴリズムが見つからないか、
もうこれでいくと決めたら、次のメモリアクセスの最適化へ進みます。

メモリアクセスの最適化

最近の CPU は、キャッシュミスするとレジスタアクセスのサイクルにくらべて容易に
10~100 倍以上のサイクルストールしてしまうわけで、
SIMD 化で演算効率 4 倍に比べたら、メモリアクセス周りを最適化して
キャッシュミス率を減らしたりメモリアクセスの局所性を高めたほうが
よっぽど効果があります。

# ちなみにこれは x86 などの一般的な汎用 CPU でのお話です。

SIMD 化

で、アルゴリズムもメモリアクセスもどーしても改善できなかったら、
最後に SIMD 化です。

そう、本来なら最後に SIMD 化するべきなのです。

でも多くの場合、まずは SIMD 化から、というひとが多いのではないでしょうか?
(私もそうでした)

アルゴリズムやメモリアクセスに比べて、SIMD 最適化は直感的に分かりやすい(気がする)のと、
実現(コーディング)の障壁も低いからなのでしょうか。

しかし、CPU 依存性が大きいので、ポータブルでない。
コンパイラの自動ベクトル化も、十分ではない。
SIMD 化では、データ構造から根本的に変えないと、効果が出にくいから。
(私は将来の CPU では SIMD unit は無くなると思っています.
理由はスカラコード + マルチコア化のほうがやりやすいからです.
なので SIMD 化には拘らないほうが長期的にはよいと思います。
そんなことよりアルゴリズムを考えようということです)

それに、SIMD 化なんて、ちょっと覚えればあとはサルでもできるわけです。

こんな非生産的で知的生産性がないところでうろうろしていたら、
インド人に容易に追い越されちゃう。

なので MUDA ではそんな非生産的なコーディング時間を減らしたい、
という意味合いもあります。

かなり抽象的なお話になってしまいました。
個人的な経験則に基づく割合が多いので、あまり説得力はないかも。

いずれにせよ、そんなわけで、MUDA では、 SIMD 化をするだけではなく、
メモリアクセスの最適化もそれなりに自動に出来る仕組みに拡張したいなーと考えています。

さすがに汎用的に効率的なアルゴリズムを発見して最適化を行うみたいなことは無理だと思うので、
アルゴリズムの自動最適化というのは考えていませんが。

そしていまは手作業でトライアンドエラーでやっているような最適化のサイクルを、
automate できるフレームワークを作る、という方向性を目指したい。
いずれにせよ、インド人に勝つためには、我々日本人は生産性を上げるしかないわけで、
このような道を進むしかないのですから。

まずは SPRAL や ATLAS あたりの仕組みを調べてみるのが役に立ちそうでしょうか。

Advertisements