link もっと前
   2017年 11月 30日 -
      2017年 11月 30日  
link もっと後

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

日々

link 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月 1日 02:24]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
   2017年 11月 30日 -
      2017年 11月 30日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 12/7 11:16

カレンダー

<2017>
<<<11>>>
---1234
567891011
12131415161718
19202122232425
2627282930--

最近のコメント 5件

  • link 17年11月24日
    すずき 「SHA-3 はもう決定していて、kecc...」
    (更新:11/26 17:09)
  • link 17年10月21日
    すずき 「家だとブリッジで良いんですが、会社だとそ...」
    (更新:10/28 12:43)
  • link 17年10月21日
    hdk 「VirtualBox 用に ICS 使う...」
    (更新:10/26 01:13)
  • link 17年09月23日
    すずき 「そうですね、体験していたはずなんですが、...」
    (更新:10/17 22:53)
  • link 17年09月23日
    hdk 「我々も小学校低学年の頃はまだ学校週5日制...」
    (更新:10/16 23:53)

最近の記事 3件

link もっとみる
  • link 17年11月24日
    すずき 「[モナコイン] 仮想通貨の勉強がてら、モナコイン(以外の仮想通貨に...」
    (更新:12/07 11:16)
  • link 17年12月01日
    すずき 「[ARM で CubeHash] 先日(2017年 11月 30日...」
    (更新:12/03 01:35)
  • link 17年11月30日
    すずき 「[モナコインと CubeHash] 先日(2017年 11月 24...」
    (更新:12/01 02:24)

こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報