link もっと前
   2017年 12月 7日 -
      2017年 11月 28日  
link もっと後

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

日々

link permalink

Raspberry Pi 3 と UART

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

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

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

[編集者: すずき]
[更新: 2017年 12月 15日 00:15]
link 編集する

コメント一覧

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



link permalink

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 から転記しておくことにした。

[編集者: すずき]
[更新: 2017年 12月 15日 00:06]
link 編集する

コメント一覧

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



link permalink

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

[編集者: すずき]
[更新: 2017年 12月 15日 00:00]
link 編集する

コメント一覧

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



link permalink

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倍になるのは素晴らしい(※)ですが、x64 CPU の 1コアにも敵わないです。

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

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

#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 にしたらコンパイラが賢くやってくれるようになれば一番楽ですけどね……。

[編集者: すずき]
[更新: 2017年 12月 3日 01:35]
link 編集する

コメント一覧

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



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 編集する

コメント一覧

  • AVXならこんな感じ? 
    /* 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月23日 09:38:41)
  • すずき 
    コメントありがとうございます。そのようになると思います。
    私の実装は下記のような感じです。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 との速度が比較できませんが…。 
    (2018年01月24日 14:40:47)
open/close この記事にコメントする



link もっと前
   2017年 12月 7日 -
      2017年 11月 28日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

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

最終更新: 12/10 12:33

カレンダー

<2017>
<<<12>>>
-----12
3456789
10111213141516
17181920212223
24252627282930
31------

最近のコメント 5件

  • link 18年11月28日
    すずき 「Linux に contribute す...」
    (更新:12/10 12:33)
  • link 18年11月28日
    T4 「やっぱり貴方でしたか、ご苦労さまでした。...」
    (更新:12/05 09:20)
  • link 18年11月28日
    すずき 「RK3228 じゃなくて RK3288 ...」
    (更新:12/05 02:19)
  • link 18年11月28日
    すずき 「ありがとうございます。Linux のコミ...」
    (更新:12/05 02:04)
  • link 18年12月01日
    すずき 「私も最初、HDD, SSD は使いまわそ...」
    (更新:12/04 12:49)

最近の記事 3件

link もっとみる
  • link 18年11月29日
    すずき 「[ROCK64 のアナログオーディオが動いた] 先日(2018年 ...」
    (更新:12/03 10:21)
  • link 18年12月01日
    すずき 「[PC パワーアップ計画] 普段、家の PC のパワー不足を感じる...」
    (更新:12/02 18:32)
  • link 18年11月28日
    すずき 「[ROCK64 の I2S1 が動いた] 先日(2018年 11月...」
    (更新:12/02 16:34)

こんてんつ

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 2018年
open/close 過去日記について

その他の情報

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