コグノスケ

ハッシュ関数とSIMD演算

CubeHashはSIMD演算が非常に有効なアルゴリズムでしたが、他のハッシュ関数をざっと見た感じSIMD演算にできる箇所があまりなく、速くならなさそうです。

今回のようにSIMDでハッシュ計算の速度を4倍にする方向に頑張るのはアルゴリズムに大きく依存するので、応用が効きません。

ハッシュ検索がお互いに独立していることを利用し、SIMDのレジスタにA, B, C, Dの4つのハッシュを入れて、4つのハッシュを同時に演算する方が応用範囲が広いです。

しかしこの方法も万能では無いです。

問題その1は、ワーク領域が16で済むアルゴリズムは無いので、明らかにx64の16レジスタではレジスタ数が足りません。L1キャッシュ頑張れ。

問題その2は、ワーク領域の内容を条件とする、条件分岐処理がほぼ不可能になることです。例えばSIMDレジスタにA, B, C, Dの4つのハッシュを入れて、4つ同時に計算しているとしましょう。こんな処理がアルゴリズムに入っていたとき、

if (w == 0)
    w++;
else
    w--;

SIMD命令をどう書くのが正解でしょうか？デクリメント？インクリメント？

わかりやすくするため、A, B, Dのワーク領域は0以外、Cのワーク領域だけが0だったとします。

もしデクリメント命令を書けばA, B, Dは正しいですが、Cの結果はおかしくなります。逆にインクリメント命令を書けばCは正しいですが、A, B, Dの結果はおかしくなります。従って「記述は不可能」が答えです。

もしSIMD演算命令に一部フィールドだけ（例えばCだけ、とか）演算するような特殊な命令があれば話は変わりますが、通常、分岐の実装は不可能です。

ちなみに、検索していたら、SIMDによる並列演算に成功されている方がいました。CubeHashはもちろんkeccak, BLAKE2, skeinはAVX2で大層速くなるそうです。しかも半年ほど前に実装までされていました。すっごいなこの人…！

モナコイン界隈で有名な人らしくてASK Monaという掲示板でccminer（CUDAを使ったマイナー）を速くしたり、sgminer（OpenCLを使ったマイナー）を速くしている方のようです。

メモ: 技術系の話はFacebookから転記しておくことにした。