2008-01-24

条件分岐という重し

o-cell-o

ひっくり返す関数が悪い訳ではなかったようだ。
とにかく条件分岐のコストが高過ぎるのが原因らしい。
一生懸命最適化したつもりの関数も全く速くならなかったが、関数内の条件分岐を削っただけで５倍速くなった。
枝刈りはどうしても条件分岐を使わない訳にはいかないのだが、スコアの更新やその他の部分でなんとか条件分岐を使わずにすむように考えることにする。

2008-01-19

ベンチマーク２

o-cell-o

とりあえずαβカットを入れた1SPU版の探索プログラムまで作成してどの程度の効率か調べてみた。
しかし中間評価も手の善し悪しによる並べ替えも入れていないにも関わらずScrZebraの半分以下の探索性能だった。
これは一度全ての場所でおけるかどうかを調べ、その後動かすという方式が二度手間になっていることと符合している。
現状ではCellBEでやる利点が何もない（おそらく6 SPUにしても2-3倍にしかならないだろうから）ので、一からやり直す必要があるだろう。
かなり遠回りになるが、やってみるつもり。

2008-01-15

反転と置ける数の数え方

o-cell-o

反転の方法を考えていたが、今ひとつよいアイデアがないので前回の置ける位置の走査時に、すべての方向の結果の論理和をとるのではなく、8要素のベクトルに格納して利用することにした。
例えば上方向へひっくり返すには以下のようにした。



    vector unsigned int stop = spu_xor( spu_rlqwbyte( board, 8 ), mask_reverse );

    vector unsigned int stone_active = spu_and( mobilities[ 0 ], stone );

    vector unsigned int flipper = spu_or( stone_active, spu_rlqwbyte( stone_active, 8 ) );

    stop = spu_sel( spu_rlqwbyte( stop, 8 ), stop, pattern_select );

    for ( int i = 0; i < 6; i++ ) {

        flipper = spu_and( stop, spu_rlqwbyte( flipper, 1 ) );

        board = spu_xor( board, flipper );

    }

このコードでは、まず対象となる石を入力とし、同じ色の石にたどり着いたらひっくり返すという行為が効果を持たないようにstopを生成する。盤面とXORをとることで白黒両方を変化させ、効果の最大値まで繰り返している。
この方法は一見無駄のように見える。オセロで8方向とも反転させられることなどまずないのだから、無駄な場合は操作を行わない方が合理的だ。
しかし実際に測定してみたところ、ここで条件分岐を入れ、必要のない場合は演算をしないようにすると、-funroll-loopsオプションをつけてコンパイルすると逆に遅くなってしまった。これは__builtin_expect__を使っても改善されない。
SPUはパイプラインの段数が深いため、条件分岐の予測ミスのペナルティが非常に大きい。そのため無駄なループを回す方が条件分岐を挿入するよりも合理的なこともあるということがよく分かった。

また、置かれている石と、次に置くことのできる石の数を数える関数は以下のように実装した。



vector unsigned short count_stones_and_mobility( vector unsigned int board,

                                                 vector unsigned int mobility ) {

    vector unsigned char cnt_b = spu_cntb( (vector unsigned char)board );

    vector unsigned char cnt_m = spu_cntb( (vector unsigned char)mobility );

    vector unsigned short summed = spu_sumb( cnt_m, cnt_b );

    return spu_add( summed, spu_rlqwbyte( summed, 4 ) );

}

ここではSPUの命令であるspu_cntbとspu_sumbを利用して5回の演算だけで白黒の両方について石の数と置ける石の数の両方を数えている。spu_cntbやspu_sumbがint型のベクトルにも対応していたらもっと効率的だったのにと思うが。
この関数の返り値はshort型の8要素のベクトルで、半分の要素は未定義で、残り半分に結果が入っている。
もう少し考えれば白と黒の差もベクトルに入れられるのではないかと思うが、思いついたら改善したい。

2008-01-12

ベンチマーク

o-cell-o

このコードがどれくらいの効率を持っているかだが、Zebraの日本語訳のサイトには「200-300クロック」と書いてあったように記憶している。
前回のコードを８方向分に膨らませ（全てのステップで直前のビット演算への依存が高いので、IPCを稼ぐために２方向分ずつバンドルした）、配置をわずかに変えながら1x10^8の計算を行ったところ、実行時間は6.335秒であった。
これから単純計算で、

6.335 x 3.2 x 10^9 x 10^-8 = 202.72

から、一度の関数の呼び出しあたり203クロック程度消費していることになる。
この結果から、それ以外の処理も含めているのでほぼ200クロックで次に置ける石の位置を特定できたと言ってよい。これはZebraの下限に近い値であり、十分な速度を有していると言えるだろう。とはいえ、SSEのレジスタが拡張された最近のx86プロセッサに最適化されたコードには負けそうだが。

なお、前回書き忘れたのだが、この課題は「強いオセロプログラムをつくる」ことを目的とはしていない。
あくまでも「高速にオセロの盤面配置を検索するプログラム」が目的である。

次に手を付けるべきは実際に手を打ったときに石をひっくり返す部分だが、どうやれば高速にできるかなかなかアイデアがないので、時間がかかりそうだ。

2008-01-12

CellBEによるオセロ解法プログラム

o-cell-o

N-queen問題を解いてみる事で、SPUを128bitの論理回路として用いる事で、ある程度の速度のプログラムが書ける事は分かった。
次にどのような目標を立てるかということだが、以前から少し興味のあった話題として、オセロのプログラムを作成してみたい。
最初に言ったように途方もない目標としては囲碁のプログラムがあるので、まずは単純なものからやってどのような問題があるかを洗い出しておく必要がある。とはいえこういった積極的な意図だけではなくて、以前からアルゴリズムだけは分かっている気になっていたαβカットを自分で実装してみようという興味本位や、ボードゲームの探索プログラムではあまり並列処理の効果がでないと言われているので、私がやればもうちょっとましなことができるのではないか？という不遜な考えがあるからでもある。そして何より重要だったのは、オセロの盤の大きさは8x8=64で、二色の石をそれぞれ64bitで表すと、SPUのレジスタのサイズである128bitにちょうど合うのでうまくはまるだろうという期待ができたからである。

いくつか簡単にオセロプログラムのサイトを読んでみたが、結局盤面をどれだけ高速に読めるかで勝負が決まってきているというのが私の印象だ。
プログラムは見ていないが、Zebraというプログラムがビット演算で次に石が置ける位置を計算する事で高速に処理しているらしいというので、これをSPU用に自分で実装してみる。

今、白の配置を全て格納した変数をX, 黒の配置を格納した変数をYとして、連結した128it変数を(X||Y)と表す。
このとき、ある変換Rを定義すると、Rが示す方向へ他の石をひっくり返す事ができるかをA, その可能性があるかをDで示すと、以下の操作で石を置きうる全ての位置をAに格納することができる。またEは現在石が置かれていない空白のマスである。



1. D = E = ~( (X||Y) | (Y||X) ) # 現在石の置かれていない場所をEとDに格納

2. (X||Y) = R( (X||Y) )         # 一マス分動かす

3. A = A | ( (Y||X) & (X||Y) )  # 一つ前と違う色の石が置かれている場所は置く事ができる

4. D = D & (X||Y)               # 同じ色が続いている場合のみ置く可能性が残る

5. if not end then goto 2       # 7回繰り返す

6. A = A & E                    # 最初に空白の場所のみを提示

これをSPUのコードで表すと以下のようになる。このコードでは下方向にひっくり返す事ができるかを調べている。



    const static vector unsigned int mask 

      = (vector unsigned int){ 0xffffffff, 0xffffff00, 0xffffffff, 0xffffff00 };

  A  = (vector unsigned int){ 0, 0, 0, 0 };

  E  = spu_orc( board, spu_rlqwbyte( XY, 8 ) );

  XY = spu_and( mask, spu_rlqwbyte( XY, 1 ) );

  D  = XY;

  for ( i = 0; i < 6; i++ ) {

      XY = spu_and( mask, spu_rlqwbyte( XY, 1 ) );

      A  = spu_or( A, spu_and( XY, spu_rlqwbyte( D, 8 ) ) );

      D  = spu_and( D, XY );

  }

  A = spu_and( A, E );

ここで得られるAは黒白両方が次に置ける場所を表現している。

2008-01-05

他のプロジェクトとの比較

N-queens problem

さて、ここまで伏せてきたが賢明な方は薄々気がついていたと思う。
今回N-queens問題を例題として使ったのは

電通大がN-Queens問題の最高記録を更新

という記事をうっすらと覚えていたからである。
この記事で紹介されていたサイトはリニューアルされてunreachableになっているのだが、その結果は68ノードのPentium4 Xeon 2.8GHzで以下のようになった。比較のため私のコードの結果も加えた。

この結果と比較すると、ざっと1/20の速度ということになる。
CellBEは3.2GHzなので、クロック数を揃えると、1CPUあたり3倍の計算速度ということになる。
1スレッドからの概算では、私の手元にあるCore Duo 2GHz MacBookで、最高の並列化を行ったとしてもCellBE 1CPUはCore Duo 2GHz 1CPUの3倍弱の速度を出せそうである。
そうなると最新のクアッドコアにほぼ匹敵する速度程度にまで達すると言えるのではないだろうか。
1年以上前に出荷されたCPUと同スペックであることを考えればまずまず健闘していると言ってもよいと思う。CellBEには8つSPUが搭載されており、全て利用可能であれば更に効率が上がる事を考えれば、可能性としては高い評価を与えられると思う。

結論としては、ロジックの実装でも工夫次第で、最新CPUを遥かにしのぐほど、というところまではいかないものの、それに負けない程度の効率を得る事ができるということが分かった。
この結果に勇気を得て、できれば更に複雑なロジックに挑戦してみたい。

2008-01-05

パフォーマンス

N-queens problem

それでは実際のベンチマークを見てみる。
盤の大きさを12から18まで変化させ、SPUスレッド数を1から6まで変化させた場合の経過時間を計測した。単位は秒である。

またこの表を、スレッド数1に対して何倍速くなったかとして表現した。

同じようなアルゴリズムによる実装で、Core Duoの1スレッドでの計測ではサイズが16で12.0秒、17で90.0秒、18で624.6秒であった。
今回面白いのは、盤のサイズが小さいとき、スレッド数が多くなると計算速度が加速されて、SPUスレッドの数が増えた以上に効率化される事だ。これはSPUに仕事を投げた後にその計算が早く終わりすぎるため、計算するよりもDMA転送が総計算時間に占める割合が多くなってしまうことにあると考えられる。この場合SPU数が多いと他のスレッドがDMA転送でビジーなときに新しい仕事を受け取って計算することができるので効率化されることになる。
SPUだけで動作するプログラムの場合と比べて、盤のサイズが小さいほど遅くなっていることから上記のように考察される。

そうなると問題サイズが大きくなるほど、実際の並列化効率に近づくと期待されるが、18のとき、プログラムの効率はほぼSPU数に比例する。今回のコードは必ずしも完全な平等ではなく、ある程度の仕事の余りが出てしまうのだが、問題サイズが大きいとほぼ無視できるようであり、期待以上の効率と言える。