コグノスケ

未来から過去へ表示(*) link

過去から未来へ表示

もっと前

2017年11月30日 >>> 2017年11月30日

もっと後

2017年11月30日

permalink

編集する

モナコインとCubeHash

先日（2017年11月24日の日記参照）CPUによるモナコインのマイニングcpuminer-multiについて調べました。先日の成果としては、

CubeHashというハッシュ関数がとびきり時間が掛かっている
cpuminer-multiは既に手動で最適化されている
CubeHashを素朴に実装したら遅い
素朴な実装でもコンパイラの最適化でcpuminer-multiの実装と同等の速度が出る

CubeHashを適当にSSE化して遊んでいたところ、基本的には非常に遅く（改変前80kH/s、改変後30〜60kH/s）なりますが、突然100kH/sに速くなるポイントがありました。なお、我が家のマシンはAMD A10-7800/3.5GHzです。

コンパイラの本気

急激に速くなった理由はおそらくコンパイラです。

途中までしかSSE化していないはずなのに、逆アセンブラで見ると1ラウンドが全てベクタ演算命令で記述されていること、また、コンパイラの最適化レベルを変えずに（Ofast）、ベクタ最適化だけ無効にすると、速度が67kH/sに落ちることから、

私が中途半端にSSEを使った
変数間の依存性か何かが途切れた
コンパイラが残りの部分を全部ベクタ化できると判断
1ラウンド全てSSE or AVX化された

このようなメカニズムだろうと思っています。

平たく言えばコンパイラが本気出していなかっただけですね。1ラウンドを全てベクタ演算化すると、なんと120kH/s も速度が出ました。

元のコードの1.5倍の速度を拝めるとは思ってもいませんでした。何でもやってみるものですね！

Intel Intrinsics

SSE化にはIntel Intrinsics（マニュアル）を使いました、というより、Intrinsicが無かったらSSE化をしようと思わないです。

Intrinsicはかなり強引ですけど、一応Cの関数として定義されており、人間が考えると面倒なこと（SSEレジスタ割り当て、退避など）は全てコンパイラがやってくれるため、大変便利です。

インラインアセンブラの一種とも言えますが、gccのインラインアセンブラほど苦痛はありません。SSE/AVXを使いたいだけならIntrinsicがおススメです。

手で頑張ってみよう

最初CubeHashのSTEP5（キューブの上面と下面の入れ替え操作）をシフトとORで計算していたのですが、コンパイラが出す命令を見ていたらshuffleという素敵な命令を使っていたので、そっちで書き直してみました。

コンパイラ任せでも良いのですが、せっかく途中まで書いたので、全部SSE化しました。BeforeとAfterはこんな感じです。

SSE2を使ったCubeHashの素朴な実装


#define SSE_ROTL(x, n) do { \
		__m128i mw0, mw1; \
		mw0 = _mm_slli_epi32((x), (n)); \
		mw1 = _mm_srli_epi32((x), 32 - (n)); \
		x = _mm_or_si128(mw0, mw1); \
	} while (0);

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

#define ROUND_ONE    do { \
		__m128i mx0, mx4, mx8, mxc; \
		__m128i mxg, mxk, mxo, mxs; \
		mx0 = _mm_load_si128((void *)&x0); \
		mx4 = _mm_load_si128((void *)&x4); \
		mx8 = _mm_load_si128((void *)&x8); \
		mxc = _mm_load_si128((void *)&xc); \
		mxg = _mm_load_si128((void *)&xg); \
		mxk = _mm_load_si128((void *)&xk); \
		mxo = _mm_load_si128((void *)&xo); \
		mxs = _mm_load_si128((void *)&xs); \
		/* STEP1 */ \
		mxg = _mm_add_epi32(mx0, mxg); \
		mxk = _mm_add_epi32(mx4, mxk); \
		mxo = _mm_add_epi32(mx8, mxo); \
		mxs = _mm_add_epi32(mxc, mxs); \
		/* STEP2 */ \
		SSE_ROTL(mx0, 7); \
		SSE_ROTL(mx4, 7); \
		SSE_ROTL(mx8, 7); \
		SSE_ROTL(mxc, 7); \
		/* STEP3 */ \
		SSE_SWP(mx0, mx8); \
		SSE_SWP(mx4, mxc); \
		/* STEP4 */ \
		mx0 = _mm_xor_si128(mx0, mxg); \
		mx4 = _mm_xor_si128(mx4, mxk); \
		mx8 = _mm_xor_si128(mx8, mxo); \
		mxc = _mm_xor_si128(mxc, mxs); \
		/* STEP5 */ \
		mxg = _mm_shuffle_epi32(mxg, 0x4e); \
		mxk = _mm_shuffle_epi32(mxk, 0x4e); \
		mxo = _mm_shuffle_epi32(mxo, 0x4e); \
		mxs = _mm_shuffle_epi32(mxs, 0x4e); \
		/* STEP6 */ \
		mxg = _mm_add_epi32(mx0, mxg); \
		mxk = _mm_add_epi32(mx4, mxk); \
		mxo = _mm_add_epi32(mx8, mxo); \
		mxs = _mm_add_epi32(mxc, mxs); \
		/* STEP7 */ \
		SSE_ROTL(mx0, 11); \
		SSE_ROTL(mx4, 11); \
		SSE_ROTL(mx8, 11); \
		SSE_ROTL(mxc, 11); \
		/* STEP8 */ \
		SSE_SWP(mx0, mx4); \
		SSE_SWP(mx8, mxc); \
		/* STEP9 */ \
		mx0 = _mm_xor_si128(mx0, mxg); \
		mx4 = _mm_xor_si128(mx4, mxk); \
		mx8 = _mm_xor_si128(mx8, mxo); \
		mxc = _mm_xor_si128(mxc, mxs); \
		/* STEP10 */ \
		mxg = _mm_shuffle_epi32(mxg, 0xb1); \
		mxk = _mm_shuffle_epi32(mxk, 0xb1); \
		mxo = _mm_shuffle_epi32(mxo, 0xb1); \
		mxs = _mm_shuffle_epi32(mxs, 0xb1); \
		_mm_store_si128((void *)&x0, mx0); \
		_mm_store_si128((void *)&x4, mx4); \
		_mm_store_si128((void *)&x8, mx8); \
		_mm_store_si128((void *)&xc, mxc); \
		_mm_store_si128((void *)&xg, mxg); \
		_mm_store_si128((void *)&xk, mxk); \
		_mm_store_si128((void *)&xo, mxo); \
		_mm_store_si128((void *)&xs, mxs); \
	} while (0)

前回と同様にcpuminer-multiのマクロにはめ込めるように実装しています。

実行例

$ ./cpuminer -a lyra2rev2 -t 1 --benchmark
** cpuminer-multi 1.3.3 by tpruvot@github **
BTC donation address: 1FhDPLPpw18X4srecguG3MxJYe4a1JsZnd (tpruvot)

[2017-12-01 02:21:05] 1 miner threads started, using 'lyra2rev2' algorithm.
[2017-12-01 02:21:06] CPU #0: 140.04 kH/s
[2017-12-01 02:21:06] Total: 140.04 kH/s
[2017-12-01 02:21:10] Total: 145.47 kH/s
[2017-12-01 02:21:15] CPU #0: 145.32 kH/s
[2017-12-01 02:21:15] Total: 145.32 kH/s

CubeHashの最終160ラウンドは一番のボトルネックだった個所だけあって、改善効果はかなり大きいですね。

編集者:すずき(2017/12/01 02:24)

コメント一覧

AVXならこんな感じ？さん(2018/01/23 09:38)
/* STEP1 */ \
mxg = _mm256_add_epi32(mx0, mxg); \
mxo = _mm256_add_epi32(mx8, mxo); \
/* STEP2 */ \
AVX_ROTL(mx0, 7); \
AVX_ROTL(mx8, 7); \
/* STEP3 */ \
AVX_SWP(mx0, mx8); \
/* STEP4 */ \
mx0 = _mm256_xor_si256(mx0, mxg); \
mx8 = _mm256_xor_si256(mx8, mxo); \
/* STEP5 */ \
mxg = _mm256_permute4x64_epi64(mxg, 0xb1); \
mxo = _mm256_permute4x64_epi64(mxo, 0xb1); \
/* STEP6 */ \
mxg = _mm256_add_epi32(mx0, mxg); \
mxo = _mm256_add_epi32(mx8, mxo); \
/* STEP7 */ \
AVX_ROTL(mx0, 11); \
AVX_ROTL(mx8, 11); \
/* STEP8 */ \
mx0 = _mm256_permute4x64_epi64(mx0, 0x4e); \
mx8 = _mm256_permute4x64_epi64(mx8, 0x4e); \
/* STEP9 */ \
mx0 = _mm256_xor_si256(mx0, mxg); \
mx8 = _mm256_xor_si256(mx8, mxo); \
/* STEP10 */ \
mxg = _mm256_shuffle_epi32(mxg, 0xb1); \
mxo = _mm256_shuffle_epi32(mxo, 0xb1); \
すずきさん(2018/01/24 14:40)
コメントありがとうございます。そのようになると思います。
私の実装は下記のような感じです。STEP5, 8 が多少違うくらいですね。

mxg = _mm256_add_epi32(mx0, mxg); \
mxo = _mm256_add_epi32(mx8, mxo); \
AVX_ROTL(mx0, 7); \
AVX_ROTL(mx8, 7); \
AVX_SWP(mx0, mx8); \
mx0 = _mm256_xor_si256(mx0, mxg); \
mx8 = _mm256_xor_si256(mx8, mxo); \
mxg = _mm256_shuffle_epi32(mxg, 0x4e); \
mxo = _mm256_shuffle_epi32(mxo, 0x4e); \
mxg = _mm256_add_epi32(mx0, mxg); \
mxo = _mm256_add_epi32(mx8, mxo); \
AVX_ROTL(mx0, 11); \
AVX_ROTL(mx8, 11); \
mx0 = _mm256_permute2x128_si256(mx0, mx0, 0x01); \
mx8 = _mm256_permute2x128_si256(mx8, mx8, 0x01); \
mx0 = _mm256_xor_si256(mx0, mxg); \
mx8 = _mm256_xor_si256(mx8, mxo); \
mxg = _mm256_shuffle_epi32(mxg, 0xb1); \
mxo = _mm256_shuffle_epi32(mxo, 0xb1);

残念ながら AMD A10 は AVX2 に対応していないので、SSE2 との速度が比較できませんが…。