.NET4.0 の並列処理を試してみた その2 : 再帰と並行性

id:siokoshou:20090721 のつづき。前回は並列化したのに微妙に速くなっただけで、Parallel.For 使えばそれでおしまい。じゃないことがわかったところまで。今回はもっと速くします。
ここでちょっとおわびです。前回は気づいてなかったんだけど、ベータのベンチマーク結果を公表するなとEulaに書いてあったので、これからは相対的な割合だけ書きます。並列化に関してはそこが知りたいところだろうけど、しょうがないです。

本題。小さい処理のタスクを大きくまとめたら速くなったので、この路線をもっと進めてみます。このことは既に MSDN ライブラリの How to にありました。How to: Speed Up Small Loop Bodies。でも今回は再帰で繰り返す回数が実行してみないとわかんないので(こういうときに再帰はきれいに書ける)、この記事のようにはできません。
困ったのでパラレルチームの blog をぐぐってみるとありました。Recursion and Concurrency。長いのでちょっとしか読んでません。前の How to も元はパラレルチームの blog 記事みたい。
最後に載ってるコードで、木を降りていくときにある程度の深さまでは並列、その先は逐次と処理を切り替えています。これ、ハードコーディングしなくてもやってくれればいいのに！たまってるタスクの数かスレッドの状況か何かよくわからないけど、現在の状況をみて逐次か並列か、というかタスクを作るか作らないかかな？とにかく、よきにはからってほしい。

というわけでまねしてみました。B(4,2)では以下のように 3 または 4 のときが速いようです。B(3,3)のときは 5 にすると速いです。マジ自動化してほしい…。手動じゃ無理…。
ともかく、こうすると7/15の逐次コードより2倍ちょっと速くなりました！パチパチパチパチ。まー、2倍でももの足りないけど1.4倍よりはいいか。

private void SearchCore( int[] array )
{
    // 重複判定
    if ( !IsUnique( array ) ) return;

    // 完成判定
    if ( IsComplete( array ) )
    {
        Output( array );
        return;
    }

    // 次の反復へ
    if ( 3 < array.Length )
    {
        for ( int i = 0; i < this.k; i++ )
        {
            SearchCore( array.Concat( new int[] { i } ).ToArray() );
        }
    }
    else
    {
        Parallel.For( 0, this.k, i => SearchCore( array.Concat( new int[] { i } ).ToArray() ) );
    }
}

つづく