二分検索

このようにしてパターンの評価値を得た後、使用しなければ意味がないのだが、その評価値の検索で無駄な処理をしてしまっては意味がない。
広大なメモリがあればO(1)でデータを得られるようテーブルをメモリ上に持っておけばよいが、それは無理なのでO(log(N))で検索できる二分検索を用いた。

二分検索の場合、SPUでの使用でためらわれるのは一度の比較ごとに条件分岐を挟むことにある。できるだけ条件分岐をしたくないSPUでのコーディングを考えれば、あまり好ましいアルゴリズムではない。
しかしもしテーブルのサイズが一定であれば、ループの最大数は一定であり、ループアンローリングで条件分岐を排除する事ができる。またどうせ常に見つかる回数だけループするならば、一度に複数の検索をやってしまってもよい。

そこで使用するテーブルのサイズが512より大きく、1024以下である場合として、以下の関数で検索を行うようにした。

inline vector unsigned int binary_search_4( vector unsigned int code, unsigned int data_start, unsigned int data_end, unsigned int* data ) {

    vector unsigned int start = spu_splats( data_start );

    vector unsigned int end = spu_splats( data_end );

    static const vector unsigned int mask_code = (vector unsigned int){ 0xffff, 0xffff, 0xffff, 0xffff };

    static const vector unsigned int not_found = (vector unsigned int){0,0,0,0};

    vector unsigned int target = spu_and( code, mask_code );

    vector unsigned int probe = zerovector;// = spu_splats( (unsigned short)0 );

    vector unsigned int center;

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

        // 4つの値について比較対象の位置を設定

        center = spu_rlmask( spu_add( start, end ), -1 );

        // それぞれの場所の値を代入

        for ( int j = 0; j < 4; j++ ) {

            probe = spu_insert( data[ spu_extract( center, j ) ], probe, j );

        }

        // 最上位ビットは白黒反転のフラグなのでクリア

        probe = spu_and( probe, mask_code );

        // 目的とする値より大きいか小さいかを判定

        vector unsigned int sel2 = spu_cmpgt( (vector unsigned int)probe, (vector unsigned int)target );

        // 条件分岐を使わず、検索位置の更新

        start = spu_sel( center, start, sel2 );

        end = spu_sel( end, center, sel2 );

    }

    // 真の値をみつけたかどうか確かめ、違ったら0を返す

    center = spu_rlmask( spu_add( start, end ), -1 );

    for ( int j = 0; j < 4; j++ ) {

        probe = spu_insert( data[ spu_extract( center, j ) ], probe, j );

    }

    probe = spu_and( probe, mask_code );

    vector unsigned int pos = spu_sel( not_found, center, spu_cmpeq( (vector unsigned int)probe, (vector unsigned int)target ) );

    return pos;

}

最後の念押しの判定が無駄なのでどうにかしたいのだが、とりあえず条件分岐の排除と４スロットの同時検索はできたのでこれでよしとしている。