2008-02-11

テスト

o-cell-o

細かい機能の最適化をあきらめて、探索アルゴリズムを実装してhttp://www.radagast.se/othello/ffotest.html FFO endgame test suiteにある終盤解析を実際にやってみた。
最前手は正解を出力したが、そこまでの時間は以下の通りだった。

手の順位付けを最低限の事しかしていない上に効率性よりバグが入らないようにしているだけだが、あまりにも見劣りするのでどうしたものかと思う。せめてZebraの６倍以内の時間に収まっていればSPUの並列化で手が届くような気になれるのだが。

Zebraのソースコードを読むと、配置のパターンから解析を行っているのだが、そのために膨大なテーブルをメモリ上に持ち、良い手から探索を行っていた。
この方法は

1. SPUにはそのようなメモリはない
2. オセロ自体に興味がないのでパターンをつくる気がしない

ということで、とても私にはやろうと思えない。

まあ他人の手法をパクるだけではつまらないので、もともとそのままコピーする気はないのだが。

2008-02-11

Min-Maxとαβカット

o-cell-o

このプログラムのアルゴリズムには標準的な手法のみを使用しているのだが、一つの配置を128bitの値一つで示すことで白番と黒番を64bitシフトで簡単に入れ替える事ができる。
そのためMaxノードとMinノードで関数を分ける必要はない。
ゲームが終了したかどうかは着手可能手を真面目に数えて、自分が置ける場合で相手が置ける場合はスキップ、両方置けない場合は石数の差を返す。

探索の順序は以下のような評価を行って並べ替えをし、次のノードを探索する

1. 第一手の場合、モンテカルロ法で評価する
2. それ以外の場合、(自分の着手可能手)-(相手の着手可能手)+(自分の４角の石の数)-(相手の４角の石の数)

非常に単純だが、最初のスタートしては複雑でない方がよい。

2008-02-06

本当の原因

o-cell-o

昨日条件分岐が問題ではないかと言ったが、実際は条件分岐を削ると特定の（軽い）パターンを繰り返すために速くなったように見えただけだった。
そして考えてみれば、5Mnpsというのは1ノードあたり640クロックの消費ということになる。
着手可能位置の検出が200クロック前後ということを考えると、現実的にはこれ以上は難しいのではないだろうか。
少なくとも今のデータ構造とアルゴリズムのままでは10Mnpsにする事は不可能だと思う。

それでもしつこく速くする手段として、石の反転を石の位置によって最適化する方法を試みてみた。
しかしこのためには石の位置を判定して分岐しなければならない。
盤を５つのブロックに分け、それぞれの関数を作成して計測したところ、元の方法よりも１割遅くなってしまった。
昨日の見積もりは間違っていたとはいえ、条件分岐が遅いことには変わりないようだ。
関数ポインタを使えば速くなるのだろうか？あまり期待はできないが、粘ってみたい。

2008-02-05

再帰関数は地雷？

o-cell-o

一生懸命最適化したつもりでまたベンチマークをとってみたが，やはり非常に遅い．
4-5Mnps程度の速度しかでない．
この原因として思い当たるのが，探索関数の再帰呼び出しだ．
関数を再帰的に呼び出すと，そのとき使用していた変数をメモリに待避させなければならない．
この操作がSPUでは重いのではないかと予想した．
先日擬似乱数関数を書いた理由は，いきなり再帰呼び出しでない形に変更するより，再帰呼び出しでない場合どの程度のパフォーマンスがでるかを調べるため，ランダムに盤面を生成する速度を見るためだった．
その結果，1Mのランダムな盤面を初期配置から終了まで生成した場合，かかる時間は12-13secであった．
各盤面ごとに60手が作成されるので，この場合5Mnps程度となり，同じような速度となる．
ところがこの関数には内部で条件分岐があるので，それを除いてみると，この速度は8-9Mnpsになった．
従って，むしろ性能の足かせになっているのは，以前から感じていた通り条件分岐であり，プログラムを複雑にしてまで再帰呼び出しを内部化するよりも，いかに条件分岐を減らすかということを考えた方がよいようだ．

条件分岐のヒントを明示的に与える方法として__builtin_expectがあるのだが，これを使ってこれまで性能が1%向上したことはまれだ．しかし分岐ミスは16cycle程度だと聞くので，どうしてここまで重くなってしまうのか腑に落ちない気持ちが残っている．

といってもこれは非常に難しい．現在でも最低限のことしか行っていないのにこれ以上の単純化をしろと言われてもかなり無理がある．
やはりこの程度であることは諦めて，並列化による効率化を目指すしかないのだろうか．

2008-02-04

乱数

o-cell-o

以前SPUで乱数を使うためにメルセンヌツイスターを実装した．
この時はただコードを書いただけで全く効率化していないものだったので，少し調べてみたらMMXを使用したSFMTというものがあるそうで，速いらしいとソースコードをダウンロードしてみた．
しかし驚いた事にメモリの使用量が半端ではなく，とてもSPUで使う気にはならなかった．

そこでSPUに適した擬似乱数発生関数としてXorShiftというものがあるということが分かったので，このSPU版を作成した．
MTと違ってXorShiftはここに全て書くこともできるほどコンパクトだ．



vector unsigned int xor128() {

    static vector unsigned int x = (vector unsigned int){1914768229,1813631753,1066933042,123456789};

    static vector unsigned int y = (vector unsigned int){1924991794,322169939,401805720,362436069};

    static vector unsigned int z = (vector unsigned int){676781941,650659395,136964893,521288629};

    static vector unsigned int w = (vector unsigned int){1450727136,97311992,63449669,88675123};

    vector unsigned int t; 

    t = spu_xor( x, spu_sl( x, 11 ) );

    x = y;

    y = z;

    z = w;

    w = spu_xor( spu_xor( w, spu_rlmask( w, -19 ) ), spu_xor( t, spu_rlmask( t, -8 ) ) ); 

    return w;

}

この関数は1E9の乱数発生に3.139secかかるが，これは上記のサイトのCore 2 Duoと同程度の速度だが，一度に128bitの乱数が得られるので，使い方によってはその４倍の効率とも言える．

2008-02-04

spu-gccによる最適化

o-cell-o

以前やったN-Queen問題では，コードのコンパクトさを期待してCで全て書いていた．
しかし，現在は全てC++で書くようにしている．
なぜかというと，単純に表記が自由だということもあるが，128-bit代入で警告を出さないことと，参照を用いた関数をインライン化すると，きちんとレジスタにしてくれるということが分かったからだ．
今書いているコードでは，８方向への効きを８つの変数に代入するのだが，最初の非効率的な実装は



void get_mobilities( vector unsigned int assembly, vector unsigned int* mobilities );

という定義だった．

これはメモリアクセスが発生するので大変効率が悪い．そこで



vector unsigned int get_mobitlity_0( vector unsigned int assembly );

という関数を８つ書いたのだが，この場合，共有できる計算を無駄に繰り返していること，そしてより重要なことに，効きを取得する場所全てで８行分コードを書かなければならないということが問題だった．
効率は重要だが，コードを読みにくくなるとデバグもしにくい．

そこで恐る恐る



vector unsigned int get_mobilities( vector unsigned assembly, vector unsigned int&m0, ... );

という形で参照を使った関数として-finline-functionsオプションでコンパイルしたところ，ちゃんとレジスタのまま計算してくれていた．
インライン化をせずに実行すると，この関数は３倍近い時間を消費した．

関数の呼び出しもSPUでは非常にコストがかかるので，できるだけ減らすべきだし，インライン化の効果が高い．
また変数定義をできるだけ遅らせることができるので，うまく最適化をしてくれれば呼び出し前に退避するレジスタの数も減らせる．
こういったことから，効率面からもC++を使用した方がよいし，どうせCellBE以外の使い回しのできないコードなのだからCで書く必要はないというのが現在の結論だ．
ただし，バイナリサイズが膨らむようなことがあったら考えなければならないだろう．

2008-01-28

Load/Store

o-cell-o

いろいろと基本的なところから細かいベンチマークをとりながら再構築をしてみたが、最初に思っていたよりもずっとLoad/Storeが遅い事に気がついた。
今回、駒の効きが八方向にあるので８要素の配列を使っていたのだが、コンパイラの最適化でレジスタに格納してくれると期待していたが、そういううまい話はなかったようだ。
そのため丁寧にメモリに書き出しているため、「どこか一つでも効きのある位置」の情報を取得することと比べて「８方向に分離した、効きのある位置」を取得することは数倍の時間がかかっていた。
非常に面倒でデバグもしにくい形になるが、８方向を別の関数に分けて、配列に格納しないで済むようにやり直すことにした。

また、spu_shuffleが思っていた以上に効率的な命令である事を知ったので、積極的に使ってみることにした。
IBMのCBE Handbookによると、SHUFB命令はレイテンシが4でストールは0とローテートを示すROTと同じコストしかかからない。しかも論理演算やローテーションとは逆のパイプライン1で実行されるため、うまく配置すればIPCを高めることも期待できる。
プログラムの見通しが悪くなるし、書き換えるとなるとほぼ根本的に作り直しだが、元々CellBEの理解のためにやっている事なので、飽きるまでは最適化を施したい。