0.3.6 向け SSE2 CPU での 4 ハッシュ並列処理
このパッチは、ベクトル命令を使用して 1 つのコアで 4 つのハッシュを同時に計算するものである。新しいハッシュ関数を旧来のものと照合するテストプログラムが含まれているため、正確性は担保されているはずである。
このパッチは 0.3.6 に対するものである。khash/s が約 115%向上する。
http://pastebin.com/XN1JDb53
標準コードのパフォーマンス（テスト/ベンチマークプログラムで計測）は約 1500khash/s だ。 私のコードは 3500khash/s を出す。どちらも 1 コアの数値だ。128 ハッシュを一度に処理し、データ構造を CPU キャッシュに収まるほど小さく保つのでスケーラビリティが良い。
2 つのローカル衝突攻撃があり、さらに 300khash/s を絞り出せるが、まだ安定していない。
すごい……
つまり、128 ビットレジスターを使って 4 つの 32 ビットデータを一度に SIMD 処理しているということか？ 長い間それを考えていたが、加算の桁上がりが隣の値に影響するため、不可能だと思っていた。
くそ、これって次のリリースでは、ペースに合わせるために難易度を 1000 くらいまで上げないといけないってことだ、笑える 😁
すごい……
つまり、128ビットレジスターを使って4つの32ビットデータを一度にSIMD処理しているということか？ 長い間それを考えていたが、加算の桁上がりが隣の値に影響するため、不可能だと思っていた。
その通りだ。128 ビットベクトルに 4 つの 32 ビット値を入れる。それぞれ独立に計算されるが、同時に処理される。
ところで、attribute ((aligned (16)))でコンパイル時にアラインメントを指示できるのに、なぜ alignup<16>関数を使っているのか？
うーん…パッチを適用できなかった（初心者なんだ）。自分が bitcoin-0.3.6/src から実行したコマンドはこれだ # patch < XN1JDb53.txt
出力：
1 out of 1 hunk ignored (Stripping trailing CRs from patch.) patching file main.cpp Hunk #1 FAILED at 2555. Hunk #2 FAILED at 2701. 2 out of 2 hunks FAILED (Stripping trailing CRs from patch.) patching file makefile.unix Hunk #1 FAILED at 45. Hunk #2 FAILED at 58.
linux では正しくはどういうコマンドを打てばいいんだ？ それとも、linux 用のバイナリはあるか？
上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？
投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の 0.3.6 クライアントと比較してパフォーマンスが 2倍になった。そのわずかな変更を 0.3.7 にも移植でき、同じ結果が得られた。
変数が正しくアラインメントされていることを確認する方法はあるだろうか？Intel 系のプロセッサーは AMD よりもミスアラインメントに対する許容度が低いのではないかと思っている。
上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？
x86 ではオブジェクトファイルのリストに cryptopp/obj/cpu.o を含める必要があった。そうしないと”make test”が失敗する。x86_64 ではその問題はなかった。
petreeの投稿（2010年8月2日 00:22 UTC）投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の 0.3.6 クライアントと比較してパフォーマンスが 2倍になった。そのわずかな変更を 0.3.7 にも移植でき、同じ結果が得られた。
上で述べたように、パフォーマンスの向上は確認したが、パッチ版が正しく動作するか確信がない。パッチ版でブロックを生成できたか？
knightmbの投稿（2010年8月1日 23:47 UTC）AMD専用の最適化なのか？
あるいは64bit専用の最適化かもしれない。
Q6600 で 64bit Linux（Ubuntu Server）を試したが、そこでは遅くなるので 64 ビット専用ではない。そして Intel i5 搭載の Mac ノート PC（同じく 64 ビット OSX 10.6）でも実行しているが、そこでは大幅な速度向上があるので、AMD 専用でもない。
Ground Loopの投稿（2010年8月2日 00:17 UTC）上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？
x86ではオブジェクトファイルのリストにcryptopp/obj/cpu.oを含める必要があった。そうしないと”make test”が失敗する。x86_64ではその問題はなかった。
petreeの投稿（2010年8月2日 00:22 UTC）投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
上で述べたように、パフォーマンスの向上は確認したが、パッチ版が正しく動作するか確信がない。パッチ版でブロックを生成できたか？
はい、このパッチ適用後に 2 ブロック生成した。
AMD では 2倍速で、Intel では半分の速度ということか？
tcatmの投稿（2010年7月31日 01:12 UTC）ところで、attribute ((aligned (16)))でコンパイル時にアラインメントを指示できるのに、なぜ alignup<16>関数を使っているのか？
試したが、スタック上のものには機能しない。いくつかテストを行った。
エラーすら出ず、単にアラインされないだけだ。
52時間試してブロックがひとつも生成されなかった。諦めて、素の bitcoin に戻すことにする。
51,000 khash/s で 52時間ブロックが得られない確率は 0.011%だ。したがってこのパッチは動いていないと結論づける。そのことに対する自信は 99.989%だ。tcatm が同梱のテストプログラムの使い方について何らかの説明をしてくれることを願う。
テストプログラムを使うには、このファイルをダウンロードしてくれ（または blockchain から自分で生成してくれ）：http://ul.to/hz5wlg
プログラムは各ブロックの正しいナンスを見つけようとし、ハッシュ関数が正しく動作するかを検出する。アルゴリズムのベンチマークも行う。
聞いた話では、このパッチは 32 ビットシステムでは動作しないらしい。理由は分からない。自分は AMD64 マシンで開発していて、そちらでは問題なく動いている。Intel で遅くなる場合は、Hyperthreading を無効にしてみてくれ。SSE2 コードの大きいループには、末尾のジャンプ 1 つを除いて「普通の」x86 命令は一切含まれていない。
ところで、git repo はここにある http://github.com/tcatm/bitcoin-cruncher/
ああ、それは私のパッチが触っていない部分のコードだ。2741 行目（CRITICAL_BLOCK(cs_main)）を削除してみたらどうだろう。
CRITICAL_BLOCK は for ループを含むマクロだ。アサーション失敗は、ループ本体内で break が呼ばれたことを示している。このブロック内で唯一の break 文は 2762 行目にある。オリジナルのソースファイルでは、このクリティカルブロック内に break 文はない。2759-2762 行を削除すべきだと思う。オリジナルの main.cpp にはそのようなものはない。
ありがとう！古い diff でファイルにパッチを当てた時に混同されたようだ。git を修正した：http://github.com/tcatm/bitcoin-cruncher
CRITICAL_BLOCK は for ループを含むマクロだ。アサーション失敗は、ループ本体内で break が呼ばれたことを示している。このブロック内で唯一の break 文は 2762 行目にある。オリジナルのソースファイルでは、このクリティカルブロック内に break 文はない。2759-2762 行を削除すべきだと思う。オリジナルの main.cpp にはそのようなものはない。
申し訳ない。CRITICAL_BLOCK は完璧ではない。その中から break や continue しないよう注意が必要だ。break を検出して警告する assert がある。使用していることを批判されるかもしれないが、これなしでは構文がはるかに冗長でエラーが起きやすくなる。
SSE2 コードが Intel で遅いのは、回避策がある何かの癖のせいだろうか？ 例えば、アラインされていないと動作するが遅い、キャッシュスラッシングが起きている、または特定の種類の命令が本当に遅いなど。利用可能かどうかわからないが、Intel には命令単位でプロファイリングするプロファイラがあったと思う。tcatm が遅いプロセッサーを搭載したテスト用システムを持っていなければ、あまり見込みはないだろう。でも、ほとんどの CPU で動作するようになると本当にいいのだが。
パッチが今は問題なく動作することを確認できる。これで最初の 50 BTC を生成できた。このパッチが速度を 2倍にするものなので、その半分を tcatm に寄付するのが公平というものだろう。
パッチが今は問題なく動作することを確認できる。これで最初の 50 BTC を生成できた。このパッチが速度を 2倍にするものなので、その半分を tcatm に寄付するのが公平というものだろう。
それは嬉しい知らせだ。寄付ありがとう、それに寄付してくれた他の皆にもありがとう！
君の github にある最新版でもう一度試してみた。素のソースに比べてパフォーマンスが落ちているのが依然として見える。
自分のシステムは約 7100 から約 4200 に下がった。
このシステムは具体的には Intel Xeon Quad-Core CPU (E5335) @ 2.00GHz を 2 基積んでいる。
どうやらこういうことのようだ：Core2 より前のものはすべて遅くなり、Core2 以降のものはすべて速くなる。古い AMD64 でコードをテストできる人はいないか？最近のアーキテクチャで SSE2 命令の実行方法に変更があったことは知っている。
どうやらこういうことのようだ：Core2 より前のものはすべて遅くなり、Core2 以降のものはすべて速くなる。古い AMD64 でコードをテストできる人はいないか？最近のアーキテクチャで SSE2 命令の実行方法に変更があったことは知っている。
私の Core2Quad（Q6600）は 50%遅くなり、i5 は約 200%改善した。したがって、あなたの指摘は正確ではないと思う。特定の Core2 以降ということかもしれない。
4倍や 6倍のこれほど大きな速度差は、古いチップが苦手とする何か癖のある弱点や命令があるように感じる。SSE2 を 6倍速くしたという i5 の売りの機能でない限りは。
要約：
Xeon Quad 41%低下
Core 2 Duo 55%低下
Core 2 Duo 変化なし（vess）
Core 2 Quad 50%低下
Core i5 200%向上（nelisky）
Core i5 100%向上（vess）
AMD Opteron 105%向上
aceat64: 私のシステムは約 7100 から約 4200 に低下しました。 このシステムはデュアル Intel Xeon Quad-Core CPU（E5335）@ 2.00GHz です。
impossible7: Intel Core 2 Duo T7300 で x86_64 Linux を実行したところ、ストック版（r121）と比べて 55%低下しました
nelisky: 私の Core2Quad（Q6600）は 50%低下しました、 i5 は約 200%向上しました、
impossible7: AMD Opteron 2374 HE で x86_64 Linux を実行したところ、105%向上しました（！）
これを古い AMD64 で試すのは興味深いだろう。あちらにはこの現象を説明できそうな変更があった：
http://developer.amd.com/documentation/articles/pages/682007171.aspx
もしかすると Intel も公にせず似たようなことをやったのかもしれない？
Phenom と Phenom II プロセッサーは（おおむね）2倍になった、ということだけ報告しておく。 両者のあいだに自分が分かる程度の差はない。
すまないが、今手元に Phenom より古いものはない。 1 週間後には古い X2 にアクセスできるかもしれない。
- 32 ビットでは動作しない（ただしこれはアルゴリズムの問題ではない）。
- パッチは古い SVN 向けだ。git リポジトリは
http://github.com/tcatm/bitcoin-cruncherにある。 - すべての 64 ビット Linux でコンパイルできる。
標準クライアントの代替ではなく、専用の bitcoinminer ボックス向けだ。いつかプラグイン式の bitcoinminer を計画している。ただ現在の難易度では、マイニングの高速化を見つけるより Bitcoin のために働いた方が簡単だ。
この機能が公式ビルドに近いうちに含まれることを強く望んでいる。どのアルゴリズムを使うべきか判断するための内蔵スピードテスト付きで。スピードテストを実行せずに速くなるか遅くなるかを判断する方法がわかったら、後でスピードテストを削除すればいい。
- 32ビットでは動作しない（ただしこれはアルゴリズムの問題ではない）。
- パッチは古いSVN向けだ。gitリポジトリはhttp://github.com/tcatm/bitcoin-cruncherにある。 (
http://github.com/tcatm/bitcoin-cruncher%E3%81%AB%E3%81%82%E3%82%8B%E3%80%82)- すべての64ビットLinuxでコンパイルできる。
標準クライアントの代替ではなく、専用のbitcoinminerボックス向けだ。いつかプラグイン式のbitcoinminerを計画している。ただ現在の難易度では、マイニングの高速化を見つけるよりBitcoinのために働いた方が簡単だ。
-
なぜ 32 ビットで動作しないか分かっているのか？128 ビットを使用しているからか？もしそうなら 64 ビットに下げれば解決するか？
-
ありがとう、自分の 64 ビットシステムへの実装を調べてみる。
-
素晴らしい知らせだ。使うのが楽しみだ。
PE2650 デュアルプロセッサー Xeon @3.2GHz（HT 搭載）で使う予定だ。そのシステムを活用するためにぜひこれを解決したい。私も同様の計画を立てている。現在の難易度ではその通りだと思うが、システムをどのみち動かす必要があり、レイテンシが問題にならない場合は別だ。
Windows 上の MinGW でコンパイルに問題があります：
g++ -c -mthreads -O2 -w -Wno-invalid-offsetof -Wformat -g -D__WXDEBUG__ -DWIN32 -D__WXMSW__ -D_WINDOWS -DNOPCH -I”/boost” -I”/db/build_unix” -I”/openssl/include” -I”/wxwidgets/lib/gcc_lib/mswud” -I”/wxwidgets/include” -msse2 -O3 -o obj/sha256.o sha256.cpp
sha256.cpp: In function `long long int vector Ch(long long int vector, long long int vector, long long int vector)’: sha256.cpp:31: internal compiler error: in perform_integral_promotions, at cp/typeck.c:1454 Please submit a full bug report, with preprocessed source if appropriate. See URL:http://www.mingw.org/bugs.shtml for instructions. make: *** [obj/sha256.o] Error 1
- なぜ 32 ビットで動作しないか分かっているのか？128 ビットを使用しているからか？もしそうなら 64 ビットに下げれば解決するか？
分からない。アラインメントの問題かもしれない。IRC で誰かが原因を突き止めようとしていた。SSE2 対応の 32 ビットシステムを持っていない。64 ビットモードの追加レジスターも有用だ。PE2650 の CPU が十分新しいかどうかわからない。CPU が古すぎると 50%のパフォーマンス低下を経験するかもしれない。
ところで、Intel CPU でハイパースレッディングの有効/無効でパフォーマンスを比較した人はいるか？SSE2 ループは演算ユニットとパイプラインをかなり忙しくさせるので、ハイパースレッディングがパフォーマンスを低下させる可能性がある。
Windows上のMinGWでコンパイルに問題がある：
g++ -c -mthreads -O2 -w -Wno-invalid-offsetof -Wformat -g -D__WXDEBUG__ -DWIN32 -D__WXMSW__ -D_WINDOWS -DNOPCH -I”/boost” -I”/db/build_unix” -I”/openssl/include” -I”/wxwidgets/lib/gcc_lib/mswud” -I”/wxwidgets/include” -msse2 -O3 -o obj/sha256.o sha256.cpp
sha256.cpp: In function `long long int vector Ch(long long int vector, long long int vector, long long int vector)’: sha256.cpp:31: internal compiler error: in perform_integral_promotions, at cp/typeck.c:1454 Please submit a full bug report, with preprocessed source if appropriate. See <URL:http://www.mingw.org/bugs.shtml\> (
http://www.mingw.org/bugs.shtml%5C%3E) for instructions. make: *** [obj/sha256.o] Error 1
ツリーオプティマイザーでコンパイラーのバグを引き起こしているようだ。-O0 でコンパイルしてみてくれないか？
まだであれば、thash のアラインを試してみてほしい。効果があるかもしれない。損にはならない。
tcatmの投稿（2010年8月13日 15:53 UTC）ツリーオプティマイザーでコンパイラーのバグを引き起こしているようだ。-O0 でコンパイルしてみてくれないか？
-O0 でも効果なし、同じエラーだ。
MinGW は GCC 3.4.5 だ。おそらくそれが問題だ。
新しいバージョンの MinGW を入手できるか試してみる。
MinGW GCC 4.5.0： Crypto++が動作しない。X86_SHA256_HashBlocks()が返ってこない 4-way は test.cpp でのみ動作するが、BitcoinMiner から呼び出された時は動作しない
MinGW GCC 4.4.1： Crypto++は動作する 4-way は SIGSEGV
GCC は間違いなく__m128i をアラインしていない。
自分の__m128i 変数をアラインしても、コンパイラーが一時変数として裏で__m128i を使うことを決定する場合がある。
__m128i 変数をアラインし、これらのインライン関数を define に変更することで、4.4.1 の-O0 のみで動作させることができた： #define Ch(b, c, d) ((b & c) ^ (~b & d)) #define Maj(b, c, d) ((b & c) ^ (b & d) ^ (c & d)) #define ROTR(x, n) (_mm_srli_epi32(x, n) | _mm_slli_epi32(x, 32 - n)) #define SHR(x, n) _mm_srli_epi32(x, n)
ただし、それは-O0 での話だ。
さて、報告する。
コンパイル時に gcc に-msse と-msse2 を指定してコンパイルできた。最初は約 692kh/s（SVN r130 の 50%[1400kh/s]）だったが、再コンパイルして現在約 1120kh/s になっている。これは現在ハイパースレッディングなしで両方の CPU を使用する場合と同等だが、ハイパースレッディングが使用されていることは確認できる。ハイパースレッディングをオフにすると約 1350kh/s になる。標準ビルドにかなり近い。
また、git にはパッチ済みで更新されたコードが含まれているのか？
// SVN r130 Using HT.
08/14/10 19:02 hashmeter 4 CPUs 1392 khash/s
08/14/10 19:32 hashmeter 4 CPUs 1387 khash/s
08/14/10 20:02 hashmeter 4 CPUs 1386 khash/s
08/14/10 20:32 hashmeter 4 CPUs 1380 khash/s
08/14/10 21:02 hashmeter 4 CPUs 1363 khash/s
// With -msse -msse2, first run. Using HT.
08/14/10 21:32 hashmeter 4 CPUs 692 khash/s
08/14/10 22:06 hashmeter 4 CPUs 1011 khash/s
08/14/10 22:11 hashmeter 4 CPUs 1104 khash/s
08/14/10 22:16 hashmeter 4 CPUs 1120 khash/s
// NOT using HT.
08/14/10 22:21 hashmeter 2 CPUs 1359 khash/s
08/14/10 22:26 hashmeter 2 CPUs 1340 khash/s自分の経験を伝え、できる限りの情報で貢献したかった。
MinGW GCC 4.4.1 と 4.5.0 の両方で、test.cpp では動作するが、BitcoinMiner から呼び出されると SIGSEGV になる。つまり GCC のバージョンの問題ではなく、別の何か、おそらくスタックのアラインメントの運によるものだろう。
Ubuntu 32 ビットの GCC 4.3.3 では問題なく動作している。
MinGW 4.5.0 での Crypto++の問題を見つけた。以下がそのパッチだ：
--- \old\sha.cpp Mon Jul 26 13:31:11 2010
+++ \new\sha.cpp Sat Aug 14 20:21:08 2010
@@ -336,7 +336,7 @@
ROUND(14, 0, eax, ecx, edi, edx)
ROUND(15, 0, ecx, eax, edx, edi)
- ASL(1)
+ ASL(label1) // Bitcoin: MinGW GCC 4.5用修正
AS2(add WORD_REG(si), 4*16)
ROUND(0, 1, eax, ecx, edi, edx)
ROUND(1, 1, ecx, eax, edx, edi)
@@ -355,7 +355,7 @@
ROUND(14, 1, eax, ecx, edi, edx)
ROUND(15, 1, ecx, eax, edx, edi)
AS2( cmp WORD_REG(si), K_END)
- ASJ( jne, 1, b)
+ ASJ( jne, label1, ) // Bitcoin: MinGW GCC 4.5用修正
AS2( mov WORD_REG(dx), DATA_SAVE)
AS2( add WORD_REG(dx), 64)