作業の分割

並列化プログラムで、並列効果に最も関係するのは「どのように作業を分割するか」ということである。
作業の分割単位が小さければ6つのSPUに平等に仕事をさせやすくなるが、分割や結果の総合にオーバーヘッドが生じる。逆に大きく分割すれば並列化のオーバーヘッドは少なくなるが、「余り」が出やすくなり、遊んでいるユニットが多くなる。
今回の問題であるN-queens問題では、最もlazyな解決としては、それぞれのSPUに1から6までの番号をふり、とびとびで計算して結果だけ総合すればよい。PPU-SPU間の通信は番号の付与と結果の総合だけですむ。
しかしそれは全く今後のためにならない。そのような解決策が有効な問題だけをこれからも扱うつもりなどないからだ。
またCellBEを用いた並列化プログラミングにおいてどういったところがボトルネックになるかを知るために、作業の分割方法を変化させられるコードを作成することにした。

実際に行った分割方法は、最初のm行をPPU側のコードで埋めて、残りのN-m行を使っていくつの配置が可能かを現在計算していないSPUに振る。もし一つもスレッドが空いていなければ空くまで待つという処理にした。

int get_idle_thread( int num_threads, async_spe_thread** threads ) {

    int i;

    for ( ;; ) {

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

            if ( async_spe_thread__is_running( threads[ i ] ) == FALSE ) {

                return i;

            }

        }

    }

}

このコードを見れば分かるが、空きスレッドができるまでひたすら空回りしてエラー処理もない、一見して怖い書き方をしているが、SPUで走っているプログラムを完全に管理しているという前提であれば、まあよいだろう。

このような書き方をしたのは、いくつかプログラムを書いているうちに持ったCellBEの印象も理由だ。CellBE用のプログラムを書いていて感じる事は、SPUで大半の作業を行うプログラムはパフォーマンスの予測がしやすいということだ。
普通LinuxなりMacなりWindowsなりといったリッチなOSの上でプログラムを実行すると、どんなプログラムでもわずかに実行ごとに計算時間に誤差が出る。OSのスレッドが動いている同じCPU上でやっているのだから仕方がないのだが、SPUで実行させると計算時間にほとんど誤差がでない。usecのレベルで同じことも多い。
SPUにはOSのスレッドがないので、計算リソースをユーザーが占有できるためであろう。