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処理しているということ？ ずっと気になっていたが、加算の桁上がりが隣の値に影響するため、不可能だと思っていた。
すごい……
つまり、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日09:22 UTC）投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
上で述べたように、パフォーマンスの向上は確認したが、パッチ版が正しく動作するか確信がない。パッチ版でブロックを生成できた？
knightmbの投稿（2010年8月2日08:47 UTC）AMD専用の最適化なのかな？
あるいは64bit専用の最適化かもしれない。
Q6600で64bit Linux（Ubuntu Server）を試したが、そこでは遅くなるので64ビット専用ではない。そしてIntel i5搭載のMacノートPC（同じく64ビットOSX 10.6）でも実行しているが、そこでは大幅な速度向上があるので、AMD専用でもない。
Ground Loopの投稿（2010年8月2日09:17 UTC）上のパッチでは、テストプログラムをビルドできなかった。そっちはどう？
x86ではオブジェクトファイルのリストにcryptopp/obj/cpu.oを含める必要があった。そうしないと”make test”が失敗する。x86_64ではその問題はなかった。
petreeの投稿（2010年8月2日09:22 UTC）投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
上で述べたように、パフォーマンスの向上は確認したが、パッチ版が正しく動作するか確信がない。パッチ版でブロックを生成できた？
はい、このパッチ適用後に2ブロック生成した。
AMDでは2倍速で、Intelでは半分の速度ということか？
tcatmの投稿（2010年7月31日10: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/
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を計画している。ただ現在の難易度では、マイニングの高速化を見つけるより、働いてビットコインを稼ぐ方が簡単だ。
この機能を、近いうちに公式ビルドにぜひ入れてほしい。どのアルゴリズムを使うべきか判断するための内蔵スピードテスト付きで。スピードテストを実行せずに速くなるか遅くなるかを判断する方法がわかったら、後でスピードテストを削除すればいい。
- 32ビットでは動作しない（ただしこれはアルゴリズムの問題ではない）。
- パッチは古いSVN向けだ。gitリポジトリは
http://github.com/tcatm/bitcoin-cruncherにある。- すべての64ビットLinuxでコンパイルできる。
標準クライアントの代替ではなく、専用のbitcoinminerボックス向けだ。いつかプラグイン式のbitcoinminerを計画している。ただ現在の難易度では、マイニングの高速化を見つけるより、働いてビットコインを稼ぐ方が簡単だ。
-
なぜ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> for instructions. make: *** [obj/sha256.o] Error 1
ツリーオプティマイザーでコンパイラーのバグを引き起こしているようだ。-O0でコンパイルしてみてくれないか？
まだであれば、thashのアラインを試してみてほしい。効果があるかもしれない。損にはならない。
tcatmの投稿（2010年8月14日00: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)