0.3.6向けSSE2 CPUでの4ハッシュ並列処理
このパッチは、ベクトル命令を使用して1つのコアで4つのハッシュを同時に計算するものである。新しいハッシュ関数を旧来のものと照合するテストプログラムが含まれているため、正確性は担保されているはずである。
このパッチは0.3.6に対するものである。khash/sが約115%向上する。
標準コードのパフォーマンス（テスト/ベンチマークプログラムで計測）は約1500khash/sだ。 私のコードは3500khash/sを出す。どちらも1コアの数値だ。128ハッシュを一度に処理し、データ構造をCPUキャッシュに収まるほど小さく保つのでスケーラビリティが良い。
2つのローカル衝突攻撃があり、さらに300khash/sを絞り出せるが、まだ安定していない。
すごい……
つまり、128ビットレジスタを使って4つの32ビットデータを一度にSIMD処理しているということか？ 長い間それを考えていたが、加算の桁上がりが隣の値に影響するため、不可能だと思っていた。
Quote from: satoshi on July 31, 2010, 12:29:20 AM
すごい……
つまり、128ビットレジスタを使って4つの32ビットデータを一度にSIMD処理しているということか？ 長い間それを考えていたが、加算の桁上がりが隣の値に影響するため、不可能だと思っていた。
その通りだ。128ビットベクトルに4つの32ビット値を入れる。それぞれ独立に計算されるが、同時に処理される。
ところで、attribute ((aligned (16)))でコンパイル時にアラインメントを指示できるのに、なぜalignup<16>関数を使っているのか？
上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？
投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
変数が正しくアラインメントされていることを確認する方法はあるだろうか？Intel系のプロセッサはAMDよりもミスアラインメントに対する許容度が低いのではないかと思っている。
Quote from: Ground Loop on August 02, 2010, 09:17:07 AM
上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？
x86ではオブジェクトファイルのリストにcryptopp/obj/cpu.oを含める必要があった。そうしないと”make test”が失敗する。x86_64ではその問題はなかった。
Quote from: petree on August 02, 2010, 09:22:29 AM
投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
変数が正しくアラインメントされていることを確認する方法はあるだろうか？Intel系のプロセッサはAMDよりもミスアラインメントに対する許容度が低いのではないかと思っている。
上で述べたように、パフォーマンスの向上は確認したが、パッチ版が正しく動作するか確信がない。パッチ版でブロックを生成できたか？
Quote from: impossible7 on August 02, 2010, 09:00:55 AM
Quote from: knightmb on August 02, 2010, 08:47:04 AM
AMD専用の最適化なのか？
あるいは64bit専用の最適化かもしれない。 Quote from: knightmb on August 02, 2010, 08:47:04 AM AMD専用の最適化なのか？
Q6600で64bit Linux（Ubuntu Server）を試したが、そこでは遅くなるので64ビット専用ではない。そしてIntel i5搭載のMacノートPC（同じく64ビットOSX 10.6）でも実行しているが、そこでは大幅な速度向上があるので、AMD専用でもない。
Quote from: impossible7 on August 02, 2010, 09:31:44 AM
Quote from: Ground Loop on August 02, 2010, 09:17:07 AM
上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？
x86ではオブジェクトファイルのリストにcryptopp/obj/cpu.oを含める必要があった。そうしないと”make test”が失敗する。x86_64ではその問題はなかった。
Quote from: petree on August 02, 2010, 09:22:29 AM
投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
変数が正しくアラインメントされていることを確認する方法はあるだろうか？Intel系のプロセッサはAMDよりもミスアラインメントに対する許容度が低いのではないかと思っている。
上で述べたように、パフォーマンスの向上は確認したが、パッチ版が正しく動作するか確信がない。パッチ版でブロックを生成できたか？ Quote from: Ground Loop on August 02, 2010, 09:17:07 AM 上記のパッチでは、テストプログラムをビルドできなかった。そちらはどうだ？ Quote from: petree on August 02, 2010, 09:22:29 AM 投稿されたオリジナルのパッチは自分の環境（Opteron 2376）で問題なく動作しており、標準の0.3.6クライアントと比較してパフォーマンスが2倍になった。そのわずかな変更を0.3.7にも移植でき、同じ結果が得られた。
変数が正しくアラインメントされていることを確認する方法はあるだろうか？Intel系のプロセッサはAMDよりもミスアラインメントに対する許容度が低いのではないかと思っている。
はい、このパッチ適用後に2ブロック生成した。
AMDでは2倍速で、Intelでは半分の速度ということか？
Quote from: tcatm on July 31, 2010, 10:12:38 AM
Quote from: satoshi on July 31, 2010, 12:29:20 AM
それは驚異的だ……
つまり128ビットレジスタを使って4つの32ビットデータをSIMDで同時に処理するということか？長い間考えていたが、加算が隣の値にキャリーオーバーするため不可能だと思っていた。
その通りだ。128ビットベクトルに4つの32ビット値を入れる。それぞれ独立に計算されるが、同時に処理される。
ところで、attribute ((aligned (16)))でコンパイル時にアラインメントを指示できるのに、なぜalignup<16>関数を使っているのか？
試したが、スタック上のものには機能しない。いくつかテストを行った。
エラーすら出ず、単にアラインされないだけだ。
CRITICAL_BLOCKはforループを含むマクロだ。アサーション失敗は、ループ本体内でbreakが呼ばれたことを示している。このブロック内で唯一のbreak文は2762行目にある。オリジナルのソースファイルでは、このクリティカルブロック内にbreak文はない。2759-2762行を削除すべきだと思う。オリジナルのmain.cppにはそのようなものはない。
ありがとう！古いdiffでファイルにパッチを当てた時に混同されたようだ。gitを修正した：http://github.com/tcatm/bitcoin-cruncher
Quote from: impossible7 on August 06, 2010, 11:37:20 AM
CRITICAL_BLOCKはforループを含むマクロだ。アサーション失敗は、ループ本体内でbreakが呼ばれたことを示している。このブロック内で唯一のbreak文は2762行目にある。オリジナルのソースファイルでは、このクリティカルブロック内にbreak文はない。2759-2762行を削除すべきだと思う。オリジナルのmain.cppにはそのようなものはない。
申し訳ない。CRITICAL_BLOCKは完璧ではない。その中からbreakやcontinueしないよう注意が必要だ。breakを検出して警告するassertがある。使用していることを批判されるかもしれないが、これなしでは構文がはるかに冗長でエラーが起きやすくなる。
SSE2コードがIntelで遅いのは、回避策がある何かの癖のせいだろうか？ 例えば、アラインされていないと動作するが遅い、キャッシュスラッシングが起きている、または特定の種類の命令が本当に遅いなど。利用可能かどうかわからないが、Intelには命令単位でプロファイリングするプロファイラがあったと思う。tcatmが遅いプロセッサを搭載したテスト用システムを持っていなければ、あまり見込みはないだろう。でも、ほとんどのCPUで動作するようになると本当にいいのだが。
どうやらこういうことのようだ：Core2より前のものはすべて遅くなり、Core2以降のものはすべて速くなる。古いAMD64でコードをテストできる人はいないか？最近のアーキテクチャでSSE2命令の実行方法に変更があったことは知っている。
Quote from: tcatm on August 08, 2010, 11:52:53 AM
どうやらこういうことのようだ：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%向上しました（！）
- 32ビットでは動作しない（ただしこれはアルゴリズムの問題ではない）。
- パッチは古いSVN向けだ。gitリポジトリはhttp://github.com/tcatm/bitcoin-cruncherにある。
- すべての64ビットLinuxでコンパイルできる。
標準クライアントの代替ではなく、専用のbitcoinminerボックス向けだ。いつかプラグイン式のbitcoinminerを計画している。ただ現在の難易度では、マイニングの高速化を見つけるよりBitcoinのために働いた方が簡単だ。
この機能が公式ビルドに近いうちに含まれることを強く望んでいる。どのアルゴリズムを使うべきか判断するための内蔵スピードテスト付きで。スピードテストを実行せずに速くなるか遅くなるかを判断する方法がわかったら、後でスピードテストを削除すればいい。
Quote from: tcatm on August 13, 2010, 09:27:14 PM
- 32ビットでは動作しない（ただしこれはアルゴリズムの問題ではない）。
- パッチは古いSVN向けだ。gitリポジトリはhttp://github.com/tcatm/bitcoin-cruncherにある。
- すべての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
Quote from: sgtstein on August 13, 2010, 11:17:51 PM
Quote from: tcatm on August 13, 2010, 09:27:14 PM
- 32ビットでは動作しない（ただしこれはアルゴリズムの問題ではない）。
- パッチは古いSVN向けだ。gitリポジトリはhttp://github.com/tcatm/bitcoin-cruncherにある。
- すべての64ビットLinuxでコンパイルできる。
標準クライアントの代替ではなく、専用のbitcoinminerボックス向けだ。いつかプラグイン式のbitcoinminerを計画している。ただ現在の難易度では、マイニングの高速化を見つけるよりBitcoinのために働いた方が簡単だ。
なぜ32ビットで動作しないか分かっているのか？128ビットを使用しているからか？もしそうなら64ビットに下げれば解決するか？
ありがとう、自分の64ビットシステムへの実装を調べてみる。
素晴らしい知らせだ。使うのが楽しみだ。
PE2650デュアルプロセッサXeon @3.2GHz（HT搭載）で使う予定だ。そのシステムを活用するためにぜひこれを解決したい。私も同様の計画を立てている。現在の難易度ではその通りだと思うが、システムをどのみち動かす必要があり、レイテンシが問題にならない場合は別だ。
分からない。アラインメントの問題かもしれない。IRCで誰かが原因を突き止めようとしていた。SSE2対応の32ビットシステムを持っていない。64ビットモードの追加レジスタも有用だ。PE2650のCPUが十分新しいかどうかわからない。CPUが古すぎると50%のパフォーマンス低下を経験するかもしれない。
ところで、Intel CPUでハイパースレッディングの有効/無効でパフォーマンスを比較した人はいるか？SSE2ループは演算ユニットとパイプラインをかなり忙しくさせるので、ハイパースレッディングがパフォーマンスを低下させる可能性がある。
Quote from: satoshi on August 14, 2010, 12:49:18 AM
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のアラインを試してみてほしい。効果があるかもしれない。損にはならない。
Quote from: tcatm on August 14, 2010, 12:53:07 AM
Quote from: satoshi on August 14, 2010, 12:49:18 AM
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でコンパイルしてみてくれないか？
-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にはパッチ済みで更新されたコードが含まれているのか？
Code:// 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)