インテル® Cilk™ Plus ソルバーによるチェスパズルの例: 高速否定

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Cilk Plus Solver for a Chess Puzzle or: How I Learned to Love Fast Rejection」の日本語参考訳です。

---

高速否定 (Fast Rejection) アルゴリズムは、時間と労力を節約します。この記事では、高速否定を利用したチェスパズル解読用の並列アルゴリズムを紹介します。これは、基本的なインテル® Cilk™ Plus プログラミングによってチェスパズルを解く実装例です。

このパズルは、プレイヤーの (ポーンを除く) 8 つの駒でチェスボードのすべてのマス目を攻撃できるかどうかを判定します。2 つのビショップは異なる色のマス目に配置する必要があります。私たちは、1989 年にこの問題のシリアル・アルゴリズムを発表しました。このアルゴリズムは、検索領域の大部分を高速に否定する否定テストに基づいています。まず、ボードに 8 つ以上の駒を配置し、各駒のブロッキング効果を無視して、すべてのマス目が攻撃できるかどうかを確認します。攻撃できない場合、それらの駒のサブセットではすべてのマス目を攻撃できません。この論文の冒頭の Skiena の枝刈り (pruning) に関する部分は一読する価値があるでしょう。

この論文では、オリジナルプログラムは 1988 年に Sun 3/360 システムで 75 分かかったことが報告されています。現在では、マシンは大幅に速くなっています。オリジナルコードは見つかりませんでしたが、私は論文の内容を参考にすることなく、並列バージョンを一から書き直すことができました。並列バージョンは、同じ問題を 16 コアのハイエンドマシン (2 ソケット インテル® Xeon® プロセッサー E5-2670L) で 2 秒未満で解くことができます。

では、アルゴリズムの並列化について説明しましょう。ここでは、読者の皆さんが少なくとも論文の 2-3 節に目を通し、シリアル・アルゴリズムを理解されていることを前提とします。

添付のソースファイルを例に使用します。一通り目を通してください。この例は、2 つのマクロが動作に影響します。

• シリアルコードとしてコンパイルするには、–DPARALLEL=0 を指定してコンパイルします。
• オリジナルの問題を解くには、-DBISHOPS_CAN_BE_ON_SAME_COLOR=0 を指定してコンパイルします。

ビショップの動きに関する制限をなくすと、作業はほぼ倍になります。プログラムがいくつかのソリューションを示せるように、そして最近のマシンは高速に問題を解くことができるため、より困難な問題 (ビショップの制限なし) を作成しました。

並列化

インテル® Cilk™ Plus で並列化を行うには、シリアルコードを少し変更する必要があります。この後のセクションで、変更点を説明します。

fork-join

このアルゴリズムは、再帰分割統治を実行します。詳細は、論文 (英語) を参照してください。主要ルーチンは次のとおりです。

 void Search( const Board& b ) {
    if( !b.reject() ) {
        int i = b.chooseAxis();
        if( i<0 ) {
            // Found a weak solution
            ++WeakCount;
            if( b.strongAttacks().isAll() )
                // Found a strong solution
                if( !b.hasSuperposition() )
                    // Found solution with no superposition.  Print it.
                    Output << b << std::endl;
        } else {
            // Unfold on axis i and search both halves in parallel
            cilk_spawn Search( Board(b,i,0) );
            Search( Board(b,i,1) );
        }
    }
    // implicit cilk_sync
} 

このルーチンを並列化するには、Search の 2 つの再帰呼び出しを並列実行できることを示す必要があります。このため、最初の Search 呼び出しに cilk_spawn を追加して、呼び出し先からリターンするのを待たずに呼び出し元が処理を続行できるようにしました。2 つの呼び出しの後に、(スポーンされた呼び出し先からリターンするまで待つ) cilk_sync を挿入することもできますが、この例では挿入していません。インテル® Cilk™ Plus では、常にルーチンの最後に暗黙の cilk_sync があります。

レデューサー

Search ルーチンには、いくつかの並列化手法が適用されています。“++WeakCount;” と “Output << b << std::endl;” の 2 つの行に注目してください。どちらの行も、ロックで保護されていないグローバル変数を処理しています。よくあるマルチスレッド・コードでは、これらの行で WeakCount が誤って更新され、出力には決定論性がありません。しかし、ここでは WeakCount と Output をレデューサーとして宣言しているため、決定論性のある出力が得られます。

レデューサーは、各スレッドに個別の「ビュー」が割り当てられるインテル® Cilk™ Plus のオブジェクトであり、ビューは等価なシリアルプログラムと同じ結果になるように自動的にマージされます。WeakCount のビューは部分和を表し、正確な合計を得るために自動的に集計されます。このプログラムは、合計が論文 (ビショップの制限あり) で報告された値 (8715) と一致するかを確認します。レデューサー Output は、最終的な出力がプログラムのシリアルバージョンの出力と同じになるように部分出力をマージすることを除いて、std::ostream と同様に動作します。

スケーリング

このコードは、多くの並列スラック (過度の並列性) があり、メモリー集約型ではないため、スケーリングに優れています。インテル® Cilk™ Plus を利用可能であれば、コードのシリアルバージョンと並列バージョンの時間を測定してみてください。Linux* または Windows* 環境でインテル® コンパイラーでコンパイルする場合、推奨するコマンドオプションは次のとおりです。

	Linux*	Windows*
シリアル	icc -O2 -xHost chess-cover.cpp –lrt –DPARALLEL=0	icl /O2 /QxHost chess-cover.cpp /DPARALLEL=0
並列	icc -O2 -xHost chess-cover.cpp –lrt	icl /O2 /QxHost chess-cover.cpp

このプログラムは、時間計測にインテル® スレッディング・ビルディング・ブロック (インテル® TBB) の機能を使用しているため、インテル® TBB へのパスが設定されていることを前提にしています。-xHost オプションは、ホスト・マシン・プロセッサー用に最適化するようコンパイラーに指示します。このオプションを指定することで、約 15% もパフォーマンスが向上しました。並列バージョンのスピードアップを理論的に解析 (http://software.intel.com/en-us/articles/what-the-is-parallelism-anyhow-1) するには、次の 2 つの数値が重要です。

• ワーク: 実行された命令の総数
• スパン: クリティカル・パスの命令の数

ワーク/スパンの比率は、プログラムの並列性の指標です。例えば、ワーク=スパンの場合、並列性は 1、つまりプログラムはシリアルです。

このプログラムは比較的小さな作業 (平均 1,832 命令) を行うため、同期オーバーヘッドを考慮した「Burdened span (負荷スパン)」と呼ばれる手法が適しています。

探索木の葉の深さが異なるため、スパンの予測にはやや注意が必要です。インテル® Cilk™ Plus SDK (http://www.cilkplus.org/download からダウンロード可能) に含まれる Cilkview Scalability Analyzer ツールで予測してみましょう。ビショップの制限なしで問題を解いた場合のレポートを次に示します。

   Work :                                162,169,367,032 instructions
   Span :                                58,705 instructions
   Burdened span :                       1,123,705 instructions
   Parallelism :                         2762445.57
   Burdened parallelism :                144316.67
   Number of spawns/syncs:               129,851,246
   Average instructions / strand :       416
   Strands along span :                  43

ストランドは、同期操作 (スポーンまたは同期操作) 間のシリアル命令のシーケンスです。平均ストランドは、わずか 416 命令です。少ない命令数でも、インテル® Cilk™ Plus の低コストな fork/join は効果的です。“Burdened parallelism” は、“Work”/“Burdened span” の比率です。上記の値は、このプログラムが理想マシン上で 10 万ハードウェア・スレッドまで理論的にスケーリングできることを示しています。もちろん、この値は理想マシンでの予測にすぎませんが、このプログラムは 40 コアのマシンで 28 倍速度が向上したことをお伝えしておきます。

まとめ

インテル® Cilk™ Plus を利用することで、わずかな変更でパズルソルバーの速度が向上しました。生成されたプログラムは適切にスケーリングし、決定論性のある動作をします。

インテル® Cilk™ Plus に関する詳細は、http://cilkplus.org を参照してください。
インテル® Cilk™ Plus に関する質問や意見交換は、フォーラム (http://software.intel.com/en-us/forums/intel-cilk-plus (英語)) を参照してください。
インテル® Cilk™ Plus に関する日本語記事は、https://www.isus.jp/article/intel-cilk-plus/ を参照してください。

添付ファイル	サイズ
chess-cover.cpp	18.97KB

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。