Hatena::ブログ(Diary)

Bonanzaソース完全解析ブログ

2010-01-14

クラスター化でどれぐらいRがあがるのか

クラスター化でどれぐらいRがあがるのかを含むブックマーク クラスター化でどれぐらいRがあがるのかのブックマークコメント

floodgateで1スレッドと8スレッド走らせてみました。対局数少ないので若干不正確かと思いますが、1t R2376, 8t R2593。R200+差ですね。

(中略)

2.7倍くらいですか。8tといっても4コアのHTなので、ルートN以上出てるといっていいでしょうね。ときどき1を越えたりしてるのは、時間が短いためスレッドオーバーヘッドが見えたのではないかと思います。


ボナ1thr vs 8thr 比較(A級リーグ指し手1号)

http://aleag.cocolog-nifty.com/blog/2010/01/1thr-vs-8thr-21.html

4コアで2.7倍出るというのは大変興味深いデータですね。

(8tは4コア4t以下の性能しか出ていない気はしますが。)


ところで、floodgateでの対局数は少なすぎる気はします。floodgateは最初、Rが確定するまで弱い相手としか当たらないのです。1tのほう、18局のうち8局はmattari_yuchan_SHUQIが相手です。これではかなり不正確なデータになっています。


8tのほうも6局はmattari_yuchan_SHUQIであり、また、Gekisashi_Xeon-X5482_1cには、3-2で負け越しています。勝ち越している側のGekisashi_Xeon-X5482_1cのRは2587ですので、長期的にはこれより下がる可能性が高いですね。


あと、floodgateの上位陣にBonanzaが多いので、Bonanza同士だと自己対戦みたいな形になって、わずかでも探索量が上回るほうが大きく勝ち越してしまいます。ちょうどR2400〜R2500ぐらいのところにBonanza家族が生息しているので、ここより勝ち越すか勝ち越さないかでRが二分されてしまうという特徴があるようです。


話を戻しますと、今年はCore i9×3台 = 18コアでの大会出場するチームもあるかも知れませんし、そろそろ、N台(N CPU)で、√Nという仮説から解き放たれるべきときが来ているのかも知れませんね。aki.さんの実験によると、次のようになっています。

スレッド数    2   3   4

時間の比の平均 1.746 2.284 2.463

(参考)√N    1.414 1.732 2.000

(参考)平均/√N 1.23 1.32 1.23


並列探索の効率はsqrt(N)なのかもっとなのか

http://d.hatena.ne.jp/ak11/20090906

どう見ても、√Nよりはずいぶんマシなようです。昨今、コンピュータの速度向上は鈍化していますが、コア数が増えたのはコンピュータ将棋にとって福音だったようです。

usapyonusapyon 2010/01/14 11:02 √N仮説はおそらく2chでの私の発言が起源なんですが、√Nに「しかならない」には厳しい制限があります。
仮に指し手のオーダリングが完全だったら√Nにしかならないというものです。
αβ法がオーダリングが完全だったら√で早くなる、というのと一緒で、前提条件が成り立っていることの方が少ないはずです。

それから、最初に仮説を唱えた時には、思考実験で、splitの仕方がこうであれば…というのを仮定して√Nと発言したのですが、その後、splitの仕方に工夫の余地があるんじゃないかということで…今は正確な値はどのあたりになるのか分からないというのが私の感覚です。

64コア使っても8倍しか早くならないのか?と言われると、実際に実験すれば16倍位になるんじゃないかなぁと最近は思っています。

LS3600LS3600 2010/01/14 11:14 それは大変参考になりました。フォロー、ありがとうございます。

ここ近年、CPUの速度は4年で倍にすらなっていないと思いますが、コア数だけは順調に増えているので、コンピュータ将棋もそろそろクラスター化に向かうべきときなのかも知れませんね。

highcalchighcalc 2010/01/14 12:30 アムダールの法則では、並列度が4倍になったとき並列化部分率が0.8なら速度比は2.5倍になりますね。
0.9なら速度比は3倍です。
並列度64倍の場合は以下
並列度64倍 並列化部分率0.8 速度比 4.7倍
並列度64倍 並列化部分率0.9 速度比 8.7倍
並列度64倍 並列化部分率0.95 速度比15.4倍

highcalchighcalc 2010/01/14 16:32 アムダールの法則に基づくと
並列化部分率が0.7以下だと速度比は√並列度より低くなります。
並列化部分率が0.7だと並列度8くらいまでなら速度比は√並列度より少し良くなります。
並列化部分率が0.8だと並列度16くらいまでなら速度比は√並列度より少し良くなります。
並列化部分率が0.9だと並列度16までなら速度比は√並列度x2くらいになります。
並列化部分率が0.8-0.9だと並列度64あたりで速度比は√並列度より低くなります。

現在のIntelアーキテクチャでは並列化部分率を出すのは難しいですけどね。

LS3600LS3600 2010/01/14 18:10 アムダールの法則は私はよくわかってないのですが、コンピュータ将棋の並列化部分率はほぼ1.00とみなせると思いますよ。

探索したときにあるスレッドで枝刈りが発生したときに、別のスレッドでの探索している内容が無駄になったり、splitのときに局面コピーのオーバーヘッドなどがあるために探索効率(並列度)が低下するだけの話で・・。

2台で k倍 の効率が出ているなら、64倍で k^6 近くは出ると考えていいと思います。しかし実際はマシンがネットワーククラスターですと16台ぐらいから局面コピーのオーバーヘッドが無視できなくなってくるので、もう少し低下すると思いますが。

highcalchighcalc 2010/01/14 20:18 並列化部分率が1.0に限りなく近いと4スレッドだと速度比は4倍になるわけです。

4スレッドで2.7倍のとき、アムダールの法則に従えば並列化部分率は0.87くらいかなと逆算しただけの話です。
「アムダールの法則に従えば」2スレッドのとき、並列化部分率は0.87であるならば速度比は1.8倍くらいになります。

アムダールの法則は
・非並列化部分が0.1(10%)あった場合、いくら並列化しても絶対に10倍以上速くならない。
・非並列化部分が0.01(1%)あった場合、いくら並列化しても絶対に100倍以上速くならない。
ことから導き出されたものです。

usapyonusapyon 2010/01/14 21:46 理想的には、allノードでのみsplitしたいので…
うさぴょんの並列化のコードでは、cutノードになる可能性が高い、ハッシュの最善手やヒステリームーブその他の手を生成して、1スレッドで探索後、カットが起きなかった場合に残りの全手を並列探索に回してたりします。

確かこの辺りの工夫は試してみた後で、思考実験で「理想的にオーダリングされていたら√N倍にしかならないなぁ…」という結論に至ったはず、なんですが、詳細を失念した上に、もう一回同じ思考をたどることが出来ないという…。


ところで、highcalcさんの

>並列度64倍 並列化部分率0.95 速度比15.4倍

この辺の数字が私の現在の感覚に非常に近い感じです。

コンピュータ将棋の並列化部分率は95%位ということになるのかな?実際には99%位並列化されていて、4%位別の探索によりカットされる無駄なノードを探索していると思えばそんな数字に…?

LS3600LS3600 2010/01/14 22:10 highcalcさん
> 4スレッドで2.7倍のとき、アムダールの法則に従えば並列化部分率は0.87くらいかなと逆算しただけの話です。

ああ、意味はわかりました。

コンピュータ将棋プログラムの場合、並列化部分率自体は1.00に近いのですが、splitのときに局面コピーのオーバーヘッドがあるので、これと、あと別の探索によりカットされたときのロスを評価する計算モデルのほうが正確な予測ができるのになぁと思いました。


usapyonさん
>>並列度64倍 並列化部分率0.95 速度比15.4倍
> この辺の数字が私の現在の感覚に非常に近い感じです。

A級さんの4コアで2.7倍というのから考えると、log(4)64 = 3 , 2.7^3 = 19.7なので、これに10〜20%程度のオーバーヘッドがあるとすれば、確かにそれぐらいになりそうですね。

highcalchighcalc 2010/01/14 22:12 LS3600さんの話分かりました。
評価関数を呼ぶまたは末端の局面数が2.7倍になっただけでFLOPSベースでは違うということですね。

書き散らかしましたが、私の書きたかったことは以下です。

1)Nが小さい場合において√N仮説がいい近似になっていること。
 しかし√N仮説では実測値が√Nより速くなることを説明できません(FLOPSベースで√Nならロスを含む処理結果が√Nを超えることはない)が、アムダールの法則ではNが小さいときに√Nを超えることがあるので説明できること。

2)Nが大きいときにアムダールの法則が物理的限界を示すこと。
√Nやk^6といった表現はNやkが大きくなれば全体が幾らでも大きくなる印象を受けますが、1%でも非並列化部分があれば100倍を超えることはないことを、アムダールの法則が示しています。
それはメモリバスが共有されていることだったりいろいろな原因があるでしょう。
また呼び出し局面数はロスを含んでいるので、FLOPSベースで考えると2.7倍より大きいというのは分かります。ですが最悪2.7倍として考えた場合について提示しました。64並列とっても最悪8倍以下になることもある事をアムダールの法則は示してくれます。

長文失礼しました。

LS3600LS3600 2010/01/15 00:03 > 1%でも非並列化部分があれば

ええと、探索しかさせていないので、プログラムに占める探索の割合は100%とみなせるのではないですかね。コンソールに指し手を出力すると言っても、それはCPU時間の0.01%未満でしょうし。

> 評価関数を呼ぶまたは末端の局面数が2.7倍になっただけでFLOPSベースでは違うということですね。

これ、私の説明がまずかったですね。splitするために局面コピーのオーバーヘッドはCPU時間で言うと1%未満です。また、置換表へのアクセスはそこがボトルネックにならないように設計するのが普通なので、メモリバスが共有されていること(DRAMへのアクセス)は1コア→4コア化のときのボトルネックにはなっていません。

また、splitも空きスレッドがあって、かつ、残りノードが一定以上あればすぐにsplitされますので、空きスレッドの発生率もきわめて低いです。

よって、1コアで100knps(nps = nodes per second)出ているならば、4コアで380knpsぐらいは出ます。

さきほど、Nが増えてくると局面のコピーのオーバーヘッドが無視できなくなると書いてしまいましたが、これは私の勘違いで、あまり正しくありませんでした。本当は別の理由でした。以下に詳しく書いておきます。

それで、なぜ、4コアで2.7倍にしかならないかというと、1コアでαβ探索していれば、枝刈り(β cut)が生じて、本来なら探索しないでいいはずの枝を延々と探索していたスレッドがいたからです。(私は中断するときのlossであるかのように書いたのでこの点、誤解を招いたかも知れません。中断したときの探索していたノードが無駄になるという話ではなく、中断するときまでにそのスレッドが探索していたものがまるまる無駄になるということです)

どれくらいの割合で「本来なら探索しないでいいはずの枝を延々と探索」することになるのかというと、これは探索のオーダリングとか、将棋のゲーム木の性質とか、いろいろ絡んできて結構評価するのが難しいのですが、Nが大きくなるほどハズレくじを掴まされる確率はあがります。

それだけであれば、「2台で k倍 の効率が出ているなら、64倍で k^6」近くになるのですが、置換表は共有していないので、Nが大きくなると(別のパソコンであれば)、異なる二つのパソコンで(手順前後などで同じ局面に合流して)同じところを重複して探索する可能性があります。

どれくらいの確率で同じ局面に合流するのかというのは将棋のゲーム木の性質とか、splitさせる条件とかが絡んでくるのでこのへん一概には言えません。うまくやれば、同じ局面にはこないようなところでsplitできるかも知れませんし、このへんは工夫のしがいがあるとは思います。

そんな理由で、4台で2.7倍なら、64台で2.7^3×80%倍ぐらいの実効にはなるんじゃないかというのが、「usapyonさんの感覚」で、私もそれぐらいの値だと思います。

A級A級 2010/01/15 09:48 なんかすごい盛り上がってますね^^;

対局数はたしかに少ないので、マシン空いてるときにもう少し流してみようかと思ってます。HTオフ4cも試す予定なので乞うご期待。

実際何倍行くのか?は…どうせ考えたってわからんから実際に作って動かしてみるしかねーだろ、というのが、頭がガテン系の私の発想なんですよね、はい。

LS3600LS3600 2010/01/15 16:07 > HTオフ4cも試す予定なので乞うご期待。

おお、期待しております。

HTオフ4cとHTオン4cとで自己対戦とかも結構興味深かったり、ネットワーククラスターで2c×2と1台4cとの自己対戦ではどれくらい差があるのかだとか、そういうのも興味があります。

一番、切実なのは、ネットワーククラスターCorei7 4c×2と1台Xeon*2 8cとの比較なのですが。これ大差ではないなら、(大会では)前者のようにXeonを使わずに構成したほうがはるかにお得ですよね…。

pompom 2010/01/19 18:47 クラスターといえば文殊ってソフトが、合議っていう
お手軽並列処理をしてましたけど、それは導入の検討は
されておられないのですか?

LS3600LS3600 2010/01/19 23:10 合議はお手軽ではあるのですが、普通にネットワーククラスターにするよりはるかに効率が劣ると私は考えています。

「普通にネットワーククラスター」にするのにそれほど手間がかかるわけではないのです。他人が書いたソースですとそのソースを読み解く時間が必要になるので大変ですが、自分が書いたソースならばそういう手間は必要がないので、2,3日あれば十分です。

ですので、合議にする意味は全くないと私は考えています。あくまで、私がそう考えているだけで、本当は違うのかも知れません。