別冊MultiCore ('06/03号)

テーマ:

皆さんこんにちは、MultiCoreの時間です。皆様、マシンのご用意はお済でしょうか。もう、後がありません。Opteron285(2.6GHz版)は先週から出ていたようです。同時にOpteron280以下が一気に値崩れを起こした感じがします。

--
                          '06/03時点 ('06/01時点   '05/11時点   '05/09時点   '05/07時点)
FX-60(2.6GHz/L2:1M  x2) : \130k前後  (\130k前後)
4800+(2.4GHz/L2:1M  x2) :  \78k前後  ( \80k前後     \95k前後    \110k前後)
4600+(2.4GHz/L2:512Kx2) :  \67k前後  ( \70k前後     \78k前後     \85k前後    \100kを割る)
4400+(2.2GHz/L2:1M  x2) :  \56k前後  ( \60k前後     \61k前後     \66k前後     \80kを割る)
4200+(2.2GHz/L2:512Kx2) :  \45kを割る( \48k前後     \50kを割る   \58k前後     \66k前後)
3800+(2.0GHz/L2:512Kx2) :  \37kを割る( \39k前後     \40kを割る   \43k前後)
Opteron285(2.6GHz)      : \136k最安
       280(2.4GHz)      : \115k前後  (\166k前後    \165k前後)
       275(2.2GHz)      :  \95k前後  (\135k前後    \130k前後    \135k前後    \160k前後)
       270(2.0GHz)      :  \63k前後  (\110k前後    \110k前後    \120kを割る  \130k前後)
--

やっぱ懐に余裕があればDualCoreのDualOpteronで4CPU構成をやってみたいところですが、計算機将棋は、ほら、ハングリイスポーツだし。我々が失業したら、あんたたちのせいですからね、ね、ね(笑)

AD

やはり最先端計数将棋学として、この将棋を採り上げないわけにもいくまい。左図は、2006/03/08の情報処理学会全国大会のイベントとして行われた▲清水上アマ竜王▽激指戦の終盤、132手目に激指が▽13玉と王手をかわした局面。

実戦は▲21竜以下少し長引くのだが、ここでは▲12竜▽同玉▲23金▽11玉▲32角成までの5手必至がある。これは簡単な必至なので激指はこの手順を読み切っていただろうと思われる。そのような簡単な必至手順がありながら何故図のように▽13玉と指したのかを考えてみると、実際にはその数手前から寄せられていたようで、「(どう受けても必至を掛けられてしまうにせよ)最も逆転の可能性の高い手」を選んだのではないかと謎電の作者は分析している。直前手▲41角に対して▽32香や▽32桂より、早必至になる▽13玉の勝負手は理に適っていて、最も手駒を残す必至の掛けられ方を選んでいるのである。▽KFEndなら潔く投了しそうな局面だが、人間相手ではここでの投了は時期尚早と言えるかも知れない。


さて、実際にはどこから必至が掛かるのかといえば、左図の桂を外した局面からのようだ。謎電の解図結果では、▲41角▽32香▲12歩成▽同金▲21竜▽22香▲32角成▽13玉▲24桂▽同玉▲12竜▽23桂▲22馬まで13手必至。解図パラメタ{5,11}で解ける。この局面で先手が激指なら、必至手順を恐らく秒の単位で読み切っていると思われる。



AD

置換表 (6)

テーマ:

今日現在の謎電では、詰探索関数を複数のスレッドから排他的にしか実行出来ないように詰探索関数の冒頭でロックを掛け誤魔化しながら動いている。このようなやり方は序盤では殆ど問題にならないが、終盤ではどちらか一方のCPUしか殆ど働いていない状況に陥り、並列化の意味がなくなる。とはいえ、通常探索での置換表レコードロックは巧く働いていることは確認できたので、前回の続きとCraftyの「ロックしない手法」について私見を書く。


謎電の置換表レコード上にはセマフォとは別に、探索中は「探索中フラグ」を立てるのと同じ意味で「スレッド番号」を記録している。このフィールドが0であればその局面を探索しているスレッドはなし、0以外であればその識別番号を持つスレッドが探索中、という意味を示す。そのような区別を行っているのは、ノード再入(千日手)検出の誤った判断を防ぐ為でもあるし、重複探索を避けて効率を上げる為だ。特に後者の場合、単に別スレッドの探索が終了するのを待つのではなく、一旦(そのノードから見て)親のノードに戻り、別の手以下を先に探索[*1]するようにしている。


また、謎電の置換表は2つのテーブル(主表/副表)で構成される為、並列探索時は微妙に排他制御が複雑になっている。主表上のレコードついてのみ参照・更新を行う場合は、単にそのレコードをロックするだけだが、副表へレコードを移す時や追加する時は、副表をまるごとロックするような仕掛け[*2]になっている。また主表側のロックされているレコードを副表側へ移さなければならない状況が生じた場合は、当然ながらそのレコードのロックが解除されるまで待ち、自スレッドがそのレコードをロック出来たことを確認してから副表側へ移すようにしている。


以下Craftyの「ロックしない手法」に対する私見を述べる。


置換表(5)でも書いたが、レコードの情報を更新する際は勿論、read onlyで参照するだけであってもロックを行ってからでなければ整合性を保てない可能性がある。複数のスレッドが、そのレコードを単に読んでいるだけなら問題は生じない。しかしながら、一方が読んでいる時に他方が書き換えに行けば、そのタイミングによっては破壊されたデータを読み出すことになりかねないからだ。Craftyの「ロックしない手法」は、そのような事態の対処を考慮されていないように思う[*3]


例えばある矢倉の序盤で、2つのスレッドが▲37銀以下と▲79玉以下を探索する並列処理が行われたとする。具体的には▲37銀▽64角▲79玉、と手順前後で▲79玉▽64角▲37銀で同一の局面を探索することになるが、この時一方のスレッドでヒットし、排他的論理和演算で情報を可逆スクランブルしようとする直前に他方のスレッドが既にヒットしていて、データを読み出すタイミングがスクランブルされた直後ならば、そのデータは破壊されていることになる[*4]。そのようなメカニズムで進歩5のp.5の「最善手が壊れる」現象が起きるわけだ。特にスレッド(CPU)数が増え、1つのレコードに対して同じような時期にアクセスする頻度が高くなるほど、このような問題が起き易くなると考えられる。


[*1] これを謎電の作者は「問題先送り探索」と呼んでいる。実装法についてはいろいろ考えられるので、現在はまだ試行錯誤段階である。

[*2] これは現仕様で、将来もっと巧い方法が発見できれば変更の予定。

[*3] データが破壊されていないかどうかのチェックは行えるのかも知れないが、復元が確実に出来るわけではない。なぜなら、いつ他スレッドからそれがまた書き換えられるか判らないからだ。結局、ロックしない手法には無理がある。なお、xchg al, byte ptr [semaphore] のレイテンシはAMD64系プロセッサでは16[clocks]となっている。

[*4] これは、フリテンなしで九蓮宝燈9面待ちをツモ上がりするより遥かに高い確率で起き得る。なぜそう言えるのか、その根拠は全くない。

AD

このことは、選手権参加者には秘密だ。


指将棋(通常)探索だけなら大きな問題はないのだが、そこから呼び出す詰探索関数のアーキテクチャが根本的におかしいので作り変えなければならない状態になってしまっている。要はマルチスレッドを意識した関数になってないのが問題。TLSを用意すれば済むというレベルではなく、スレッド毎に完全に独立した専用の詰探索関数を用意して呼び出すことにしないと拙そうなのである。


その昔、Pen2/300MHz×2(クロックアップして375MHz×2)under WindowsNT4.0でSP3の頃に実験的に動かしていた時は、詰探索を通常探索から呼び出さなかったし、その上置換表自体実装してなかった。ぶっちゃけ根局面の手を分散・並列化するという単純な手法で、これだと効率は平方根程度しか稼げない。そんなことは、今や猿でも猫でも兎ですらも常識として知っているとか知らないとか。このあたりの改良作業も未だ残っているのだ。


そういう理由でライエル問題集のベンチが取れない。今月中にライエルに対して一泡吹かせてやる更にプレッシャ~を掛けるつもりだったのだが。3月下旬はケツカッチン[*1]で何も出来なくなるので、並列探索の完成は4月以降になりそうである。


再度繰り返すが、このことは絶対内緒だ(爆) なお、このアーティクルは自動的に消滅する。


[*1] 既に古い業界用語らしいので解説する。一言で言えば「絶対納期」という意味である。

なんか変だ (2)

テーマ:

コンピュータチェスはともかく、どうしても計算機将棋の探索速度については気になる。例の「Craftyの解析メモ」から少し引用する。


> Pentium3M-730MHzで探索速度は
>
> Crafty 109,000 leaves/s 308,000 nodes/s ... YSSの3倍も速い。
> YSS 71,000 leaves/s 111,000 nodes/s
> (leaves/sは評価関数を毎秒呼んだ回数、nodes/sは途中の手も含む)


よくよく数字を見るとちょっと不思議なことに気がつく。leaves/nodes比率の違いである。計算してみると、

・Craftyの場合:109,000/308,000=約0.35

・YSSの場合:71,000/111,000=約0.64

となる。静的評価関数を呼ぶ頻度は、YSSがCraftyより倍近く多いという点が気になる。そこで、謎電での指将棋探索速度の厳密なプロファイルを行ってみることにした。その結果は次の通りである。


___________nodes______leaves
< 1>         510[*1]       0   0   0 (   0    0)[‰]
< 2>         915          59   0   0 (   0    0)[‰]
< 3>       9,185          30   0   0 (   0    0)[‰]
< 4>      13,484          62   0   0 (   0    0)[‰]
< 5>      87,270         799   1   0 (   2    0)[‰]
< 6>     131,773       1,358   2   0 (   5    0)[‰]
< 7>     543,305       7,645  11   0 (  17    1)[‰]
< 8>     931,837      17,439  20   1 (  37    3)[‰]
< 9>   2,301,548      65,584  50   7 (  87   10)[‰]
<10>   4,568,361     184,382  99  20 ( 187   30)[‰]
<11>   7,089,423     177,339 154  19 ( 342   50)[‰]
<12>  10,418,679   1,487,498 227 165 ( 569  215)[‰]
<13>   9,891,791   1,330,426 216 147 ( 785  363)[‰]
<14>   3,077,330   1,865,504  67 207 ( 853  571)[‰]
<15>   2,735,389   1,351,040  59 150 ( 912  721)[‰]
<16>   1,211,112     682,517  26  75 ( 939  797)[‰]
<17>   1,367,060     510,159  29  56 ( 969  853)[‰]
<18>     500,498     432,934  10  48 ( 980  901)[‰]
<19>     463,787     354,333  10  39 ( 990  941)[‰]
<20>     173,175     215,695   3  23 ( 993  965)[‰]
<21>     125,086     129,270   2  14 ( 996  979)[‰]
<22>      73,222      78,528   1   8 ( 998  988)[‰]
<23>      37,610      53,571   0   5 ( 999  994)[‰]
<24>      22,883      24,470   0   2 ( 999  997)[‰]
<25>       7,964      15,755   0   1 ( 999  998)[‰]
<26>       5,445       5,366   0   0 ( 999  999)[‰]
<27>       2,128       3,027   0   0 ( 999  999)[‰]
<28>       1,338       1,567   0   0 ( 999  999)[‰]
<29>         433         686   0   0 ( 999  999)[‰]
<30>         271         318   0   0 ( 999  999)[‰]
<31>         107         126   0   0 ( 999  999)[‰]
<32>          53          80   0   0 ( 999  999)[‰]
<33>           8          21   0   0 ( 999  999)[‰]
<34>           6           7   0   0 (1000 1000)[‰]
総数: 45,792,986   8,997,595    探索時間: 27.314[秒]
速度:  1,676,538     329,413
平均探深度 12.33  端深度14.61[手]
分散        5.70      7.26
標準偏差    2.38      2.69

上のデータは、Toledo/4800+を使って平手初手局面を30秒程度(指将棋用のシングルスレッド通常探索で反復深化17回迄)読ませて、「局面を進めた時にインクリメント」と「静的評価関数を呼んだ時にインクリメント[*2]」を、深さ毎に行った結果である。この結果から謎電のleaves/nodes比率は、

・謎電の場合:329,413/1,676,538=約0.20

と、静的評価関数を呼ぶ割合が、CraftyやYSSより低く、特にYSSとは3倍以上も違うのである。これか、これなのか、謎電の序盤がヘロヘロになってる原因は!? てか、評価関数を呼んでいる回数を基準とするのが指将棋の探索速度なの??


すみません、謎電の探索速度は毎秒33万局面くらいでした、ごめんなさい。


[*1] 深さ1のノード数が510になっている。何故こういう数字になるのかと言えば、平手初手の合法手は30手(謎電は1手目と2手目が全幅)で、それを反復深化によって17回繰り返し通ることになる為(30*17=510)である。

[*2] あくまで評価関数を呼んだ純粋な回数で、置換表にヒットして結論値を引用している場合、そのカウントは行ってない。またNullMoveの時も、手番が反転しただけで局面を進めたわけではないのでカウントしてない。

なんか変だ (1)

テーマ:

おかしい。掲示板などでも探索速度の話が時々出てたりするが、謎電の探索速度とえらく差がありすぎる。謎電のノードカウント法はJuniorやFritzのそれと同じだと思う、多分。実際、指将棋での探索速度は、Juniorは勿論Fritzにも勝てない。てか、コンピュータチェスと計算機将棋を比べて探索速度が1桁近くも違うとは思い難いのである。


pn系探索ではカウント法がいろいろあるようだが、私の感覚では「局面を進めた時点でインクリメント」であるし、謎電では詰将棋も指将棋もそのようになっている。因みに、打歩詰を除く合法局面しかカウントしていない(例えば、王手放置や自爆局面はカウントしてない、という意味)。気になるので、再度カウントしている部分のコードを調べなおしてみたがおかしいところはない。謎電って速い方なの? いや、速くしているつもりだけど、差がありすぎてなんか不安になってきた(汗)


【追記 06/03/07 23:30】 さて、DeepJuniorの、あの異常な探索速度は、恐らく次のような理由で叩き出せるのではなかろうか、という結論に達した。

1) 探索処理の要となるコード+データは、全てL1内(64KB+64KB)に収まる大きさしかない

2) 更に、置換表はL2キャッシュサイズほどの大きさ(1MB)しか用意してない

3) そして、涙なしでは語れない探索エンジンの完全アセンブラでの開発、そのデバグ(風の中の昴~)


まさに、軽量化に勝るチューニングなし である。


私の世代なら、苦しくったって/悲しくったって/マシンの前では/平気なの/GPF(一般保護例外)が起きると/胸が弾むわ/アセンブル・リンク・アンドゴー/ワンツーワンツー(オチがミエミエなので省略) つまりは気合insideだ。上記1)は、コンピュータチェスなら可能かもしれない。2)については計算機将棋では効率の犠牲が大きくなる。3)はスポ根過ぎて真似出来ない。というわけで、謎が解けたことにして以後考えないことにする。


【私信 06/03/09 22:30】 小宮日記(2006/03/08) >そういえば、いずれ私もFPGAなんかやってみたいなあとか思ってるんですが、詰め将棋ルーチンだけFPGAで作って、メインのコードから呼び出して並列処理するとかいいかも~とかとか。

ソフト探索と巧く並列化できれば、次の一手(終盤)問題集だと驚異的に正答率が上がると思います。がんばってくださいね。ってか、好敵手現る(笑) で、話は逸れるのですが、


劇指


って巧い表現ですね、「激指」より。劇薬って感じで。いやツッコミじゃなくてマジで。

置換表 (5)

テーマ:

1つの置換表を用いて並列探索を行う場合、置換表に対して排他的にアクセスが行えるようにする必要がある。そのアルゴリズムはいろいろ考えられるが、一般的にはレコード上にセマフォを設けて一方のスレッドがアクセス(データ参照・更新)している時、レコード単位でロックし他のスレッドはそのセマフォを除いてレコードをアクセス出来ないようにして情報の整合性を保つ、ということである。


進歩5のp.6にはYSSのコードが紹介されている。また作者である山下さんのCraftyの解析メモ の中でも示されている[*1]。Craftyの解析メモではセマフォがdwordで、この点無駄だと思っていたのだが、進歩5ではbyteに変更、ブラシアップされたのだと思われる。このレコードロック手法は謎電でも同様だが、進歩5で示されているコードに関して少し思うところを書くことにする。


まず直ぐに目につくのは、パーシャルレジスタアクセスが行われている点である。最近のプロセッサなら問題はない[*2]のかも知れないが、前世代のIntel系プロセッサだと、1つのレジスタに対してデータ幅の異なるアクセスを交互に行おうとするとストール(ペナルテイ)が発生するので気になるところである。ここはbyteアクセスで統一し、test al,al と書いた方が無難、付け加えて冒頭の xor eax,eax が不要になる[*3]


ここからは余談。test命令は、and命令とフラグの変化は同じで演算結果は捨てられる、というインストラクションである。使うニモニックとしてはandでも、仮にorを使ったとしてもzフラグを見るだけだから正しく動く。しかしながら省電力の観点から見ると、ALU-レジスタ間データ転送が(場合によってはレジスタリネーミングも)行われないので、test命令を用いるのがこの際ベストと言える。


また、何かしらのレジスタに0を代入したい時、xor reg,regとかsub reg,regと書くよりも、現在のx86系プロセッサではmov reg,0と素直に書いた方が低消費電力(ALUを駆動しないので)と考えられるしスルプットも変わらない[*4]。以前は、高速化プログラミングこそ絶対正義だったが、現代のトレンドは省電力だ。


省電力プログラミングこそ、絶対正義 [*5]


エネルギ問題が深刻化している昨今、[Ws(ワット秒)]あたり何局面を探索するかが問われる時代になるかも知れない[*6]


[*1] Craftyの手法は面白そうだが、そのやり方でCraftyが動いている方が不思議だと私は思っている。実際にYSSでは採用を止めたようで賢明な判断ではないかと感じる。

[*2] ない筈だが、エラッタとして存在することを否定できない。昔の話だが、Intelの前科Errata59や初代Pentiumのfp除算には私は泣かされた。

[*3] と、掲示板に書こうと思いつつ、気の小さい謎電の作者はちょービビって書けなかった。

[*4] 但し、mov reg,0 のregがbyteレジスタの時コードサイズは2バイトでも、dwordレジスタならコードサイズは5バイトになる。従って、0クリアに限りbyte型を除いて省コードを目的とするならxor命令を使うことは有効である(例えば、xor eax,eax の総コード長は2バイト、当然32bitモードでの話)。

[*5] (c)2006 謎電の作者。結果として同じなら消費電力の少ない命令を使う方が望ましい。これはコア自体の熱の発生を抑え、熱暴走の危険を減らすことにも繋がる。省電力プログラミングの基本は、プロセッサ内部の実行器および周辺の回路資源を意味なく使わない、ということである。

[*6] んなこと本気で言ってるのは私だけかもしれない(笑)

ホテルの予約 (2)

テーマ:

選手権2ヵ月前になり、そろそろ怪しくなくなってきたので予約した。無論最寄の例のホテルである。去年は廻りに迷惑を掛けた上に自分自身も面白くはなかったので、結果的に損になるかもしれないが後で慌てることになるよりマシだと判断したためである。因みに、直接予約して御一名様一泊¥17,000-(朝食・サービス料・消費税込み)だ。


よし、前日は夕食抜いて、朝食でモトをとってやる[*1]


そう固く心に誓った謎電の作者なのだった。てか、毎度そうなのだが(笑)
[*1] 更に付け加えて、かずさアーク会場で私が昼食を摂っているところを見たことのある者は、未だかつていない。つまりは、そういう理由だったのか!!