2015/01/27(火)INTLAB version 9の重要性
(なぜかページが2つあって微妙に中身が違うので両方載せておこう。)
まったく予想してなかったのですが、このINTLABがversion 9にアップデートして、新たにOctaveに対応したそうです。Octaveは、フリーの有名なmatlabクローンです。と言っても、完璧な互換性を目指してるわけでは無さそう。
INTLABはRump先生の大変な努力で作成された素晴らしいソフトウェアで、この分野のデファクトスタンダードと言えるものです。ところが、最近はきちんと動かないことが多く、周囲の研究者に聞くと、matlabのversionを2012aで留めておかないと、いろいろまずいことがおきるのだそうです。
これは、matlabのせいと言うよりは、matlabの中で使っているBLASの問題です。
BLAS(=Basic Linear Algebra Subprograms)は、LAPACKから呼び出される行列積などの基本的なプログラムの集合体です。近年の計算機では計算速度に比較して相対的にメインメモリが遅くなっており、キャッシュメモリを使ってその遅さをカバーしています。そのため、行列積などのプログラムはキャッシュのヒット率を極限まで高めるきわめて技巧的なプログラミングが要求され、高速なプログラムは誰でも書けるものではなくなってしまいました。実際、素人が書いた単なる三重ループとBLASの持つ行列積とでは速度が10倍以上違うのが普通です。また、CPUの性能を極限まで引き出すにはそのCPUに合わせたプログラムが必要になります。そのため、行列積などの基本的なプログラムはインターフェースだけ揃えておいて中身は自由に差し替えられるように分離するようになり、それがBLASです。
最近のmatlabで使っているBLASはIntel Math Kernel Libraryに含まれているもので、これの挙動が精度保証に使っている手法と合わなくなってしまったため、きちんと精度保証が出来なくなってしまったというわけです。
より詳しく説明します。浮動小数点数(double)を係数に持つ行列A,Bがあったとき、行列積ABを精度保証付きで計算する問題を考えます。三重ループで行列積を計算するプログラムを元に、計算過程を全て区間演算に置き換えれば精度保証付きの結果を得ることが出来ます。ところが、このようなことをすると高速なBLASの恩恵にあずかることが出来ません。そこで、
- 丸めの向きを下向きに変える
- C1=ABをBLASで計算する。
- 丸めの向きを上向きに変える。
- C2=ABをBLASで計算する。
- (丸めの向きを元に戻す)
BLASの中でマルチスレッドあるいはマルチコア計算を行っており、他のスレッドまたはコアに丸めの向きの情報が伝わらないことがあって、この場合は精度保証されていない結果が得られてしまうことになります。また、
BLASの中でStrassenアルゴリズムなどの「減算を含む」計算が使われている場合は、「計算式の中の全ての計算が下向き丸めならば最終的な計算結果が下向き丸めになる」という仮定を満たさなくなってしまい、このケースも精度保証が破れてしまいます。Strassenアルゴリズムはある程度大きい行列でないと効果がないことが知られていますが、計算機の発展に伴い大きな問題が解けるようになってきてそろそろStrassenアルゴリズムが有効に機能する段階に入りつつあると考えられています。
上記のような精度保証の破綻は、自分でBLASを書いたならば当然そういうことがありえるのかどうか判断できますが、closed sourceな他人の書いたBLASの場合はそうはいきません。Intel Math Kernel Libraryはまさにclosed sourceであり、2012年に(何があったか窺い知ることは出来ないが)何らかの変更が行われ精度保証を破綻させてしまったというわけです。
さらに考えてみれば、2012aまでのmatlabでも「観察の結果問題が無いように見える」だけであり、実は精度保証が破綻しているケースがあるかも知れません。使っているアルゴリズムも分からずソースコードも見られないプロダクトを使って精度保証が出来ると考えるほうがどうかしてるとさえ思えます。
さて、ここまでお読みいただければ、INTLABがOctaveに移植されたことの重要性がよく分かると思います。Octaveはopen sourceであり、(インストールの仕方にも拠るでしょうが)使われるBLASもatlasやopenblasなどのopen sourceなものです。中身を見れば精度保証に問題があるかどうか判断できるし、問題があるならば修正することも出来ます。
INTLABはversion 7から有償になってしまったので簡単に試せないのが残念ですが、Octaveでどのくらいちゃんと動くものか、近いうちに試してみたいと思います。
※上に書いたような問題点は、ずっと前から感じていたことですが、代替手段が無かったこともあり、あまり明確に否定してしまうと線形計算の精度保証の分野の研究者が困ると思い、あまり口にしないで来ました。INTLABがOctaveで動くようになったことで、書くなら今しかないと思い、この文章を書きました。