PS3 LinuxによるN-queens問題

N-queens problem

CellBEに限らない、一般的な話をすると、並列計算を行う際に重要な事は、

  • シングルスレッドで高い性能を出すコードを書く事
  • アーキテクチャに最適な並列化を行う事

である。前者は意外と忘れられがちで、特にコンパイラやOSなどシステムに密接に関係している部分に興味のある者にとってはスレッド数とパフォーマンスが比例するかどうかが第一目標になってしまうことがある。
しかし、求めるべき結果が存在する、ソフトウェアを書く立場からすると、100スレッドで100倍の並列性を持ったコードよりも、100スレッドで2倍にしかならないが1スレッドのパフォーマンスが100倍のコードの方が、2倍速く計算できることができる、優秀なコードということになる。
次に、並列化による効率も、1スレッドからNスレッドまでスケーラブルなコード、というのはコンピュータ科学的には美しく魅力的だが、ユースケースがはっきりすればするほど無意味になる。
PS3 Linuxから見えるSPUの数は6に固定されている。極言すれば6SPUで最大のパフォーマンスを出せる並列化こそがPS3 Linuxに最適なコードだと言えよう。（もちろんある種の極端である事は承知だが）

何よりも、ある入力から対応した出力に到達するまでの、実際のパフォーマンスこそが指標であるということを忘れてはいけない。

釈迦に念仏はいい加減にして、実際のプログラミングに移ろう。
N-queens問題はビット演算で処理する事で処理の高速化が行える。一行に一つしかクイーンをおいてはいけないことは自明なので、一行ずつそれまでの条件からクイーンをおいてよい場所、おけない場所にビットを立てる（あるいは外す）、斜めの効きはビットシフトで表現し、そのため二つの方向の斜め効きと縦方向の効きは別のバッファに保存することにする。
SPUにはベクトルのそれぞれの要素を別々にローテートする関数(spu_rl)がある。これを用いる事で二つの方向の効きを次の行のために変換する事が1命令（＋1命令）でできる。（注1）

また新しく置かれたクイーンを縦と斜めの効きに反映させることもspu_orやspu_andによって1命令でできる。（注2）
こういった工夫をすることで1ステップで複数の計算をまとめる事ができ、ベクトル演算による効率化をパズルの解法のようなロジックで用いることができる。

具体的に私が記述したコードで示そう。以下の関数はN-queens問題を処理するための本体である。
N-queens問題を解くコードとして実行するためには初期値を設定してこの関数を呼び出すルーチンが必要なのでこれだけでは動作しない。



unsigned long long solve( int size_problem, 

                          int y, 

                          int line,

                          vector signed int board[32] ) {

    unsigned long long answers = 0;

    static vector signed int shift = (vector signed int){ 0, 0, 1, -1 };

    static vector signed int diagonal_mask = (vector signed int){ 0xffffffff, 0xffffffff, 0x7fffffff, 0x7fffffff };

    for ( ;; ) {

        if ( line ) { /* If a stone can be placed on any cell. */

            /* next_line contains all information for the patterns.

              0: saved state for this row, 1: not iterated, 0: iterated or not usable

              1: vertical vertical direction

              2: diagonal direction (right to left)

              3: diagonal direction (left to right)

             */

            vector signed int next_line; 

            vector signed int next_mask; /* 0:placable 1:not placable*/

            signed int next_position;  /* 0:current trial 1:the others */

            next_position    = ( -line ) & line;

            /* generate mask with current stone */

            next_mask = spu_splats( next_position );

            /* change pattern with banning mask */

            next_line = spu_insert( line, board[ y ], 0 );

            /* column:   0 0 -> 0 (still filled), 0 1 -> 1 (impossible!!)

                         1 0 -> 1 (still not filled), 1 1 -> 0 (placed)

               diagonal: 0 0 -> 0 (still not filled), 0 1 -> 1 (placed)

                         1 0 -> 1 (still filled), 1 1 -> 0 (impossible!!)

             */

            next_line = spu_xor( next_line, next_mask );

            /* rotate mask for diagonal moves */

            next_line = spu_rl( next_line, shift );

            next_line = spu_and( next_line, diagonal_mask );
            board[ ++y ] = next_line;

            line = spu_extract( next_line, 1 ) & ~( spu_extract( next_line, 2 ) | spu_extract( next_line, 3 ) );

        } else { /* any stone cannot be placed  */

            line = spu_extract( board[ y-- ], 0 );

            if ( y == 0 ) break; /* no left pattern */

            if ( __builtin_expect( y == size_problem, 0 ) ) { /* find an answer */

                answers ++;

            }

        }

    }   

    return answers;

}

この関数を用いたN-queens問題の計算（1 SPUのみ）は、いくつかのパラメタを設定したところ、同一のルーチンを用いたx86用プログラムで、Core Duo 2GHz 1コアより5%遅い程度であった。
IPCの差がかなりあることを考慮すればまずまずの効率ではないかと考える。

*1

*1:注1 実装上盤の大きさが条件に入ってこなければいけないので、縦の効きはビットが1が｢クイーンを置ける場所」ビット0が「置けない場所」を表し、斜めの効きは逆にしている。そのためspu_andやspu_orではなく、spu_xorを用いている。 注2 spu_slというシフト命令がリファレンスには書いてあるのだが、libspe2には実装されていないようだ。spu_rlmaskは正方向と負方向のローテートを混ぜることができない。そのためローテートをした上でマスクをとって計算している。そのため非効率だが2命令を消費している。