コグノスケ

ARMでCubeHash

先日（2017年11月30日の日記参照）CPUによるモナコインというかLyra2REv2の計算で、ボトルネックとなっていたCubeHashをSSE化してみました。今回はARMでチャレンジしてみます。

Raspberry Pi 3（ARM Cortex A53/1.2GHz x 4）でCPUマイナーを実行してみるとたったの8kH/sしか出ません。4コア並列で動作させると32kH/sとなり、きっちり4倍になるのは素晴らしい（※）ですが、x86_64 CPUの1コアにも敵わないです。

NEONにもIntrinsicsがあることを知ったので、不親切なNEON命令のマニュアルと戦いながら、CubeHashをNEON化してみたところ、10kH/sほどになりました。

#if defined(__ARM_NEON__)
#  include <arm_neon.h>
#endif

//...

#define NEON_ROTL(x, n) do { \
		uint32x4_t mw0, mw1; \
		mw0 = vshlq_n_u32((x), (n)); \
		mw1 = vshrq_n_u32((x), 32 - (n)); \
		x = vorrq_u32(mw0, mw1); \
	} while (0);

#define NEON_SWP(a, b) do { \
		uint32x4_t mw; \
		mw = b; \
		b = a; \
		a = mw; \
	} while (0);

#define NEON_STEP5(x) do { \
		uint64x2_t mw; \
		mw = vreinterpretq_u64_u32((x)); \
		mw = vextq_u64(mw, mw, 1); \
		x = vreinterpretq_u32_u64(mw); \
	} while (0);

#define ROUND_ONE_NEON    do { \
		mxg = vaddq_u32(mx0, mxg); \
		mxk = vaddq_u32(mx4, mxk); \
		mxo = vaddq_u32(mx8, mxo); \
		mxs = vaddq_u32(mxc, mxs); \
		NEON_ROTL(mx0, 7); \
		NEON_ROTL(mx4, 7); \
		NEON_ROTL(mx8, 7); \
		NEON_ROTL(mxc, 7); \
		NEON_SWP(mx0, mx8); \
		NEON_SWP(mx4, mxc); \
		mx0 = veorq_u32(mx0, mxg); \
		mx4 = veorq_u32(mx4, mxk); \
		mx8 = veorq_u32(mx8, mxo); \
		mxc = veorq_u32(mxc, mxs); \
		NEON_STEP5(mxg); \
		NEON_STEP5(mxk); \
		NEON_STEP5(mxo); \
		NEON_STEP5(mxs); \
		mxg = vaddq_u32(mx0, mxg); \
		mxk = vaddq_u32(mx4, mxk); \
		mxo = vaddq_u32(mx8, mxo); \
		mxs = vaddq_u32(mxc, mxs); \
		NEON_ROTL(mx0, 11); \
		NEON_ROTL(mx4, 11); \
		NEON_ROTL(mx8, 11); \
		NEON_ROTL(mxc, 11); \
		NEON_SWP(mx0, mx4); \
		NEON_SWP(mx8, mxc); \
		mx0 = veorq_u32(mx0, mxg); \
		mx4 = veorq_u32(mx4, mxk); \
		mx8 = veorq_u32(mx8, mxo); \
		mxc = veorq_u32(mxc, mxs); \
		mxg = vrev64q_u32(mxg); \
		mxk = vrev64q_u32(mxk); \
		mxo = vrev64q_u32(mxo); \
		mxs = vrev64q_u32(mxs); \
	} while (0)

#define SIXTEEN_ROUNDS_NEON   do { \
		int j; \
		uint32x4_t mx0, mx4, mx8, mxc; \
		uint32x4_t mxg, mxk, mxo, mxs; \
		mx0 = vld1q_u32((void *)&x0); \
		mx4 = vld1q_u32((void *)&x4); \
		mx8 = vld1q_u32((void *)&x8); \
		mxc = vld1q_u32((void *)&xc); \
		mxg = vld1q_u32((void *)&xg); \
		mxk = vld1q_u32((void *)&xk); \
		mxo = vld1q_u32((void *)&xo); \
		mxs = vld1q_u32((void *)&xs); \
		for (j = 0; j < 16; j ++) { \
			ROUND_ONE_NEON; \
		} \
		vst1q_u32(&x0, mx0); \
		vst1q_u32(&x4, mx4); \
		vst1q_u32(&x8, mx8); \
		vst1q_u32(&xc, mxc); \
		vst1q_u32(&xg, mxg); \
		vst1q_u32(&xk, mxk); \
		vst1q_u32(&xo, mxo); \
		vst1q_u32(&xs, mxs); \
	} while (0)

//...

#if defined(__ARM_NEON__)
#  define ROUND_ONE    ROUND_ONE_NEON
#  define SIXTEEN_ROUNDS    SIXTEEN_ROUNDS_NEON
#else
#  define ROUND_ONE    ROUND_ONE_SLOW
#  define SIXTEEN_ROUNDS    SIXTEEN_ROUNDS_SLOW
#endif

前回と同様にcpuminer-multiのマクロに無理矢理はめ込んで実装しています。NEONを触るのは初めてで、非効率的な書き方になっているかもしれません。お気づきの点があれば教えてくださいませ。

（※）AMD A10-7600は昨日書いた通り1コア145kH/sですが、4コア並列だと145 x 4 = 580kH/sとはならず、少し効率が落ち490〜500kH/sほどになります。

コンパイラの本気はどこ行った

前回SSE化したときは1ラウンドの処理だけ書き換えれば事足りましたが、今回NEON化したときは16ラウンドのループも書き換える必要がありました。

何故かというとx64と違ってarmhfの場合、コンパイラがあまり良い結果を出力してくれないからです。gcc-7.2 x64の場合、

• load
• add
• xor
• store

このような処理をループさせても、生成されたバイナリの逆アセンブルを見ると、

• load
• ※
• add
• xor
• ※に戻る
• store

以上のようにload/storeの無駄を検知してループ「外」に追い出してくれました。しかしgcc-4.9 armhfの場合、ループ「内」にload/storeが残ってしまい、かなり遅くなります。

原因としてgccのバージョンが古い、アーキテクチャの最適化がこなれてない、NEONのIntrinsicsを使うと最適化が制限される、などいくつか考えられますが、今のところ分かりません。gcc-7にしたらコンパイラが賢くやってくれるようになれば一番楽ですけどね……。

ハッシュ関数と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から転記しておくことにした。

SHA-3

SHA-3に応募されたハッシュ関数の一覧です。SHA-3 2nd roundは下記のハッシュ関数が評価されました。(NIST IR 7764)

• BLAKE
• Blue Midnight Wish
• CubeHash
• ECHO
• Fugue
• Grøstl
• Hamsi
• JH
• Keccak
• Luffa
• Shabal
• SHAvite-3
• SIMD
• Skein

候補が絞られて、最終のSHA-3 3rd roundでは下記5つのハッシュ関数が評価されています。(NIST IR 7896)

• BLAKE
• Grøstl
• JH
• Keccak
• Skein

最終的にSHA-3に選ばれたのはKeccakです。

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

Raspberry Pi 3とUART

今までRaspberry Pi 3にsshが繋がらなくなった時に、HDMIケーブルを繋いで画面を映していました。しかしディスプレイのHDMI端子は大抵、背面にあって接続が面倒です。

代わりにUSBシリアル変換ケーブルを買いました。PC側はUSB端子、Raspberry Pi側はGPIOピンヘッダに挿すだけで済みます。

うまく動いたのは良かったのですが、RasPiのピンヘッダがポッキリ折れそうで怖いです。この状態で常用するのは危ない気がしますね。世の中の人はどうしてるのかしら…？？

マウスの調子が良くない

半年くらい前（2017年5月27日の日記参照）に買ったエレコムのマウスですが、マウスを動かしてもポインタが動かない時があり、動きが悪くなってしまいました。

症状としては透明なテーブルの上でマウスを動かしたときのように、マウスを動かしてもポインタは左右に小刻みに震えるだけ、という症状です。

常にではなく、たまにこの症状が出ます。買った当時は全く出ていませんでした。

電池を替えても、レーザー出力口を掃除しても、マウスパッド代わりのコピー用紙を新しいものに交換しても、症状が改善しません。

これ以上、原因が思いつかないので諦めて一時引退させました。壊れたわけじゃ無いので、捨ててはいません。

代打

エレコムの代わりに買ったのはLogicool M705です。ジョーシンで3,000円くらいでした。

特に不満は無いのですが、エレコムのマウスに比べたら小さいせいなのか、コピー用紙の上だと滑りが良すぎるせいなのか、右手と肩に変な力が入ってしまい、使っていると疲れて肩が痛くなってきます。

会社で使っている安物オプティカルマウスもM705と同じくらいのサイズのはずなのに、会社では肩が痛くならず、家だと肩が痛くなるのはなぜでしょう……？

もしかしてマウスじゃなくて、マウスパッドを買った方が良いのかなあ？？

アイス履歴

アイス履歴を10個ほど増やしました（リンク）。これで64種類かな。

棒付き袋入りアイスだけでなく、箱入りアイス（高いアイスが多い）、特殊な形のパピコなどにも手を出し始めました。