サイボウズ・ラボの光成です。
今回は3月15日に開催された「x86/x64最適化勉強会7」の模様についてお伝えします。前回から約1年半振りと久しぶりの開催です。
今回の発表内容は浮動小数点数周りの話が2件、CSSパーサ周りの話が1件、暗号関係の話が3件でした。
以下、それぞれの発表内容について簡単に解説します。
浮動小数点数関係
@ksmakotoさんの発表は「非正規化数のFZ(FTZ)とDAZの違い」(動画1)でした。 浮動小数点数には正しい精度で扱える最小の正の数DBL_MIN(約2.225074e-308)があります。 0とDBL_MINの間の数は精度は落ちるけれども扱うことはでき、非正規化数と呼ばれます。
非正規化数を扱うのはなかなか難しく、ハードウェアやソフトウェアによってはサポートしていなかったり、していてもとても遅かったりすることがあります。そのため非正規化数を0と見なすことで処理の負担を減らすことがあります。 Intel CPUには0と見なす方法にFZ(Flash-To-Zero)とDAZ(Denormals-Are-Zero)の2種類がありその違いについて解説と簡単なコードによるデモをされました。
@tanakmuraさんの発表は「いまどきのmatmul」(動画2)という発表でした。 科学技術系の計算では大きな行列の積を求めることが非常に多いです。行列の積自体はCで書くとわずか数行のコードなのですが、これを高速化するのはとてもやっかいです。
HaswellにはFMA(Fused Multiply Add)という浮動小数点数の乗算と加算を一度に行う命令が追加されていてこれを使ってうまく最適化する話をされました。ちょっと書き換えるだけでも数十倍程度の高速化ができるのですが、@tanakmuraさんの話はそこからが本番でした。
Haswellの資料から行列演算の速度の理論限界値を求め、いかにその速度に近づけるかの試行錯誤を繰り返します。キャッシュミスをどう克服するかの話は非常に興味深かったです。 最終的にはDTLB(Data Translation Lookaside Buffer)のペナルティを減らし、インラインアセンブラの細かいテクニックによって理論限界値の80%を超えるという当初の目標を達成したそうです。 ちなみにトップレベルの人たちによるコードはNinja codeと呼ばれ、Ninjaへの道はまだまだ遠いそうです。
ブラウザ関係
@Constellationさんの発表は「CSS JIT: Just-in-Time Compiled CSS Selectors in WebKit」(動画3)でした。 ブラウザで使われるCSSでは非常に多くのパターンマッチが必要です。 @ConstellationさんはWebKitにそのパターンマッチ関数をJITコンパイルする手法を取り入れることで3倍程度高速化させました。 WebKitはOS XやiOSなどで使われているブラウザのレンダリングエンジンです。 ブラウザの実行中に、指定されたCSSのセレクタに対応するステートマシンを作り、それに対応するJITコードを生成します。 そのとき各ステート上で保持しないといけない情報をできるだけ少なくします。 WebKitのJavaScriptCoreには、x86/x64/armなどのアーキテクチャを薄くラップしたJIT用アセンブラがあり、それを使っているとのことです。
デバッグが大変ではという質問に対しては、やはりがんばって生成コードを読むしかないというお話でした。 なお@Constellationさんはサイボウズ・ラボユースでも独自のブラウザを開発されていました(サイボウズ・ラボユースの最終成果報告会にて発表しました)。
暗号関係
青木和麻呂さんの発表は「改ざん検知暗号Minalpherの設計とIvy Bridge/Haswellでの最適化」(動画4)でした。 改竄(かいざん)検知暗号とは暗号化の機能に、暗号文が壊れたり書き換えられたりしていないかをチェックする機能を一体化させた暗号のことです。認証付き暗号(AEAD)とも呼ばれます。
通常は、(狭義の)暗号とメッセージ認証符号(MAC)と呼ばれるチェック機構を組み合わせてAEADをつくります。しかしその組み合わせ方はなかなか難しいです。近年CBCモードのパディング処理にかかわる部分で脆弱性が立て続けに報告されています。 現在はAEADとしてAES-GCMが一般的に使われていますが、より良いものの研究がされています。提案されたMinalpherは認証付き暗号のコンペに応募しているものです。
IntelのCPUにはpshufbというレジスタのシャッフル命令があります。今回の暗号はそれを前提にして設計したとのことです。 最適化といえば大抵は既にある何かを速くするものですが、今回はどのような暗号にすれば速いコードにできるかという視点で設計したのが面白かったそうです。
Haswellには同時に処理できる実行ユニットがポート0からポート7まであります。それぞれのユニットでFMA, div, mul, lea, load, storeなどのどんな命令を実行できるかが決まっています。一度に互いに依存関係の無い命令を実行できるようにうまく命令を詰め込めば高速化できます。カードに書いてそれらを組み合わながら考えたそうです。
富士通研究所 下山武司さんの発表は「準同型暗号の実装とMontgomery, Karatsuba, FFTの性能」(動画5)でした。 準同型暗号というのは数値を暗号化したまま足したり、掛けたりできる暗号で近年活発に研究されている分野です。 たとえばたくさんの人の身長を暗号化したままクラウドにアップロードし、クラウドは暗号化したまま平均値や分散を求めてユーザに返し、ユーザは復号して結果を取得することができます。 医療データの統計計算や指紋や静脈情報の認証などの応用を考えているそうです。
その暗号の実装には大きな多項式や巨大な整数の計算が必要になり、それらをどうやって高速に実装したのかについて説明されました。 FFTとkaratsubaという二つの方式を実装し、大きさによってどちらが有利になるかといった実験やMontgomery演算の細かい話が興味深かったです。
最後は私が「LLVM最適化のこつ」(動画6)について発表しました。 スマートフォンやタブレット端末が普及し、ARMプロセッサで高速なコードを実行する必要があるケースも増えています。 ARM向けのアセンブラを一から書くのではなく、LLVMアセンブラで書いて開発が楽できないかという動機で調べてみました。
LLVMで書いたコードからx86/x64向けのコードを生成し、それが最適になるように修正すればそのLLVMでARMのコードを出せばよいだろうという方針です。 楕円曲線暗号などに使われる小さいサイズの多倍超演算をLLVMで書こうとするとなかなかやっかいな問題が出てきました。 発表ではそのあたりの話について触れています。 ただ今回試した限りでもそのような方針で(固定長サイズにすれば)標準的な多倍長演算ライブラリGMPの数倍の性能は簡単に出せることがわかりました。
まとめ
今回も活発に鋭い質疑応答が行われ、とても勉強になりました。 発表者は随時募集していますのでご興味のある方は、ぜひ私のtwitterアカウント@herumiまでご連絡ください。
最後になりましたが、いつも会場と無線LANの提供、およびustreamの中継をしてくださっている(株)AXELL社のご好意に感謝いたします。