2017年9月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

tweet

  • tweets

« クラスタ環境探してます | トップページ | もはやこれまでか… »

ボナンザ hash/ehashの問題点

前々回の記事はちょっと記述はしょりすぎでしたね。オープン戦の片手間に書いてたのがまずかったか…もうちょいちゃんと説明します。

>Pentium 以降の ia32 は 64bit アラインされた quadword が atomic のようです。

それはたしかにそうなんですけれども、C言語でたとえば

uint64_t a,b;
  :
a = b;

のような代入文があったとして、これを普通に32bitでコンパイルするとマシン語レベルでは32bit load 命令2つになります。ia32の一般命令には64bit loadの命令が存在しないですから。Intel マニュアルの記述はマシン語レベルの話なので、2マシン命令になれば当然ながらatomicityは保証されません(間に別のストアが入り得る)。

ia32でatomicにするには、SSEなりMMXなりの64 bit loadを指定する必要がありますが、これにはソースをいじる必要があります。64bit modeならば普通のコンパイルで64 bit loadになりますので問題ありません。

この原因によりハッシュが壊れるのは、確率的には非常に小さいでしょう。本家ボナンザでは影響は微々たるものなんだと思います。実際、以前に並列ボナのRを測ったときも32bitでやりましたが、劣化には気づきませんでした。ただ、影響が確率的に小さいというだけで、バグとしては確実に存在するはずです。

hashの方はword1,word2どちらかでも壊れるとSignKeyのためhitしないかもしれませんね。だからアサートにひっかからないのかもしれません。その意味では、hashの方はバグではないとも言えるかも。ですがehashの方は時々壊れた値を使ってると思います。ただαβ探索では1ノードで評価値間違っても全体の結果に影響与えることはまずないので、なかなか顕在化しないのでしょう。

bonasseではevaluateを差分計算しています。1コアではこの効果はかなりあったのですが、これを32bitで並列にするとぼろぼろに弱くなりました。1コアよりも弱いくらいに。この原因はと考えるにおそらく、ehashである局面で破壊が起きると、差分のためそれより下の局面全部で間違うので、本家ボナよりはるかに大きく影響が出たのではないかと推測しています。実際、まったく同じソースで64bitにするとちゃんと強くなったので、この仮説は正しいのだろうと思っています。

« クラスタ環境探してます | トップページ | もはやこれまでか… »

将棋プロセサ」カテゴリの記事

コメント

確かに、私の方が間違えていたようです。

ehash_tbl[(unsigned int)key&EHASH_MASK ]
= hash_word;

の箇所をコンパイルすると

mov DWORD PTR [_ehash_tbl+ebp*8], ecx
or esi, edx
mov ecx, edi
mov DWORD PTR [_ehash_tbl+4+ebp*8], esi

となっておりました。ehash はバグですね...
発見して頂きありがとうございました。

32-bit excutable にする場合は Xor しあうよう修正しようと思います。

保木

hashの方がOKなら、ehashでxorだけ、とするのがたしかにいちばん簡単そうですね。これならうちでもすぐできそうです。

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/507007/34250489

この記事へのトラックバック一覧です: ボナンザ hash/ehashの問題点:

« クラスタ環境探してます | トップページ | もはやこれまでか… »