« intel SSE2命令(SIMD)によるAES暗号処理 | トップページ | AES暗号・複合ツール作ってみた »

2011/01/08

AES暗号・復号 さらなる高速化の研究?

AES暗号・復号の、さらなる高速化を試行錯誤してみた。
SSE2命令によるSIMD並列化もおそらく、効果はあるのだろうけど、もっと早くできるのではないか?と。

Intel(R) Celeron(R) M CPU 430 @ 1.73GHz における、8 MByte(500,000ブロック)の暗号・復号の計測結果では、

 ・C言語で記述      … 暗号:約 1,848 Mclk  / 復号:約 2,943 Mclk
 ・アセンブリ言語で記述 … 暗号:約 1,282 Mclk /  復号:約 1,774 Mclk
 ※ただし、Core2 Quadでは、暗号化は逆に若干であるが遅くなった。考察は以下に述べる。

と高速化に寄与できた。その産物は、以下のページに公開した。
intel SSE2命令(SIMD)によるAES暗号処理

さて、具体的にやったことは・・・

●アセンブリ言語で書き直しました。
──────────────────
上の公開ページでも書いた通り、Visual C++.net 2008 Express Editionでは、C言語のSSE2命令の最適化は頭良くなかったです。
CPUの命令デコードの効率化を考えた命令の並べ替え位はしてくれますが、それよりもメモリアクセスが多くて足を引っ張っています。
関数を終わる毎に、演算結果をxmmレジスタからメモリに格納して呼び出し元に渡して、呼び出し元でそのメモリから読み込んでxmmレジスタに代入するとか、そんな無駄な事を結構やっています。
とにかく、メモリアクセスが多い最適化になっていました。
アセンブリ言語で書いたものは、そのような無駄を排除し、書いています。

又、メモリアクセス以外にも減らしたリスクがあり、『条件分岐』です。
パイプライン化されているCPUにおいては、条件分岐の予測ミスは結構ペナルティーが大きいため、
暗号・復号共に、while() ループ以外の条件分岐を排除しました。
これで、分岐予測ミスによるペナルティーは、ほぼ無くなります。

特にガロア体GF(28)の掛け算は、while()相当の命令も、if()相当の命令もなくしました。
テーブル参照の他は、掛け算がクロック数を食うだろうので、自分が論理回路で組むとしたらどう組むかを考え*0x0E、 *0x09, *0x0D, *0x0Bの掛け算マクロを作っています。


●アルゴリズムの最適化
──────────────────
暗号化は、掛け算とSubByte()を同時に行うテーブルに置き換えました。
#掛け算ルーチンの呼び出しは無くなりましたが、テーブル参照(つまりメモリ読み込み)は増えています。
#Celeron等の旧世代CPUでは効果が出ましたが、高速のCPU(Core2 Quad)では逆効果になりました。

復号を最適化する方法は思い浮かびませんでした。InvSubByte()とInvAddRound()の順番は入れ替えれないので。
SSE命令で、更に高速化する手法があるかもしれません。もし何か気付いた事がありましたら、教えて頂けると嬉しいです。

|

« intel SSE2命令(SIMD)によるAES暗号処理 | トップページ | AES暗号・複合ツール作ってみた »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/36969/50526315

この記事へのトラックバック一覧です: AES暗号・復号 さらなる高速化の研究?:

« intel SSE2命令(SIMD)によるAES暗号処理 | トップページ | AES暗号・複合ツール作ってみた »