ail3 parallel programming

課題5: 逐次版n女王プログラムの高速化

Web課題4で完成させたプログラムの高速化を試みる。元の関数等は消さずに残しておき、速度比較ができるようにする。速度比較は盤面のサイズ n の変化に対し，全解探索に要する時間がどう変化するか調べること。

以下にはさまざまな高速化手法を示すが、部分解の内容のコピーを避ける形で高速化を行うことを必須とする。すべての高速化手法を試す必要はない。余力がある場合、他の実験履修者の速度を上回りたい場合などに参考にすること。

本課題(Web課題5)は，配布資料では課題4に含まれていた．本演習では，時間の関係でWeb課題5の時間がとれないため， Web課題5を進めた後（従って上記で必須とした課題を進めた後）のサンプルプログラム（ビットマップ版: Makefile nq.c）（配列版: Makefile nq_a.c）を準備しているので、Web課題6のベースとしてよい。

試みの過程ではさまざまなバージョンの関数を作成することになるが，それらをコマンドラインの「-a N」の指定で切り替えられるようにする。「-h」とした場合に，「-a N」でどのバージョンが動作するかなどの説明を表示するようにしておく。
問題サイズ n の変化に対し，全解探索に要する時間がどう変化するか調べること。
高速化手法には以下のようなものがある，これらは，ある場合には独立に，ある場合にはある順序で適用可能である:
- 部分解のデータ構造の工夫・拡張可能判定の高速化
- 部分解の内容のコピーを避ける
- 枝刈り
- 再帰呼出しの代わりに明示的なスタックを利用
もちろん高速化手法はこれらに限らない。計算結果が正しければよいので，他の人より速いものを目指し，頭を使って高速化を試みてほしい。コンパイラがやるべき最適化が，最適化の適用条件を満たすか判断できないために適用できないことも多い。コンパイラによる最適化の「基本的な考え方」に基づくと新たな着想が得られるかもしれない。

部分解のデータ構造の工夫・拡張可能判定の高速化

拡張(の試み)の列を，

まず1行目(行番号0)のある桁(桁番号0からn-1)に1つ駒を置く拡張(の試み)
次に2行目(行番号1)のある桁(桁番号0からn-1)に1つ駒を置く拡張(の試み)
以降，n行目(行番号n-1)までくりかえし

と考える．

すでに使った桁の管理
- 行番号iについて置いた桁番号をa[i]とする配列だけを用いる場合
  このままでは，ある桁に置くのにすでに使った桁ではないかを判定するのに，これまで置いた行について繰り返して，その桁に置かれていないか判定する必要がある．
- 高速化案として「桁番号をインデックスとする，その桁にすでに置かれているかの真偽値の配列」を用いれば繰り返すことなく判定できる．
- 別の高速化案として，まだ使っていない桁番号のリストが管理できれば，判定することなく桁番号を取り出すことができる．例えば問題サイズ4の場合，配列a を桁番号で: [0, 1, 2, 3] のように初期化しておく． 1行目に関して各桁への拡張を試みる場合は: [0, 1, 2, 3], [1, 0, 2, 3], [2, 1, 0, 3], [3, 1, 2, 0] のように，他の行の桁と入れ替える．次に，[1, 0, 2, 3] の2行目に関して拡張する場合は， [1, 0, 2, 3], [1, 2, 0, 3], [1, 3, 2, 0] のように残りの行との間でのみ入れ替えを行えば，自動的に3通りのみ拡張を試みることができる．
ボードを左上や，右上から斜めに見た場合を考える．
例えば，問題サイズ 4 なら，以下で同じ数が書かれている場所に，同時に2つ以上の駒を置くことは許されないので，「斜めライン番号をインデックスとする，斜めラインにすでに置かれているかの真偽値の配列」を用いれば高速に判定できる
```
左上から右下に       右上から左下に
見た場合             見た場合
3 2 1 0              0 1 2 3
4 3 2 1              1 2 3 4
5 4 3 2              2 3 4 5
6 5 4 3              3 4 5 6
```
ビットマップの利用 (これを試みる場合，配列版と分けて管理すること．この方式は極端に速くなるので，配列版は配列版で評価する)
- 上記の3つの真偽値配列，つまり使った桁のビットマップ，使った斜めライン(左上-右下方向，右上-左下方向の2種類) のビットマップの3つを，int型の整数(32ビットのことが多い)の 2進数表現(ビット表現)を用いて表せば，「~」，「|」，「&」などの論理演算や，「<<」，「>>」などのシフト演算を利用しての高速な処理が可能である．
- ちょっとした技として，int型のビットマップ bm から，最下位の1ビットを取り出すには -bm & bm とすればよい．例えば，bm = (00000000000000000000000001101000)₂ なら，
  -bm = (11111111111111111111111110011000)₂ となるので (つまり，bm + (-bm) のすべてのビットは 0)，
  -bm & bm = (00000000000000000000000000001000)₂ となる．

部分解の内容のコピーを避ける

逐次処理であれば，部分解の内容をコピーせずポインタのみを渡すことで，以下のようにもできる．

traverse(部分解 *a) {
  if(*aは解) return;
  forall (拡張方向 i) {
    if( *a を i方向に拡張可能 ) {
       *a そのもの(内容)を変更し，i方向に一段階拡張;
       traverse(a);
       *a への変更(i方向に一段階拡張)を元に戻す; 
    }
  }
}

同様の変更と，変更の取り消しは上記の3つの真偽値配列などにも適用できる．ただし， int型のビットマップについてはコピーしたほうが速いと予想される．

枝刈り

バックトラック探索木を用いるような探索問題のアルゴリズムのオーダはよくわからないことが多い． (ほとんどの場合は指数オーダではある)
アルゴリズムのオーダの改良が一番の高速化につながり，ルートノードから部分解までの拡張の順序や，枝刈りによって大きく変化することが多い． (ただし，n女王問題ではオーダ上の工夫の余地はあまりなさそうではある)
枝刈りとは，探索の途中までの状況から，その先の探索を続けてもある基準以上に良い解が期待できないなら，その枝の先の探索を打ち切ることをいう．
- 通常は「組み合わせ最適化問題」のある種の解法で用いる．最適化問題とは「目的関数」で各解を評価したとして，最も結果のよいものを(1つあるいはすべて)選ぶものである．場合によっては，最適な目的関数適用結果が求まればよい．
- n女王問題の全解探索問題のように，解が存在するかどうかだけが問題なら，目的関数適用結果はすべての解で等しく，枝刈りはその先の探索を続けても解の存在が期待できないときに行えばよい．
- n女王問題の全解探索問題についてはうまい枝刈りはなさそうである．
- ただし対称解を除去する場合の探索問題のほうについては，「目的関数」で各解を評価した結果，残る解が除かれる解より良いという最適化問題になっている．よっておそらく枝刈りができる場合がある．例えば n = 5 の場合:
```
+---+---+---+---+---+
|   |   | Q |   |   |
+---+---+---+---+---+
|   |   |   |   | Q | <= いまここに置いた
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
```
  と2行目に駒を置いた時点で，これを左回転した
```
+---+---+---+---+---+
|   | Q |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
| Q |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
```
  を考えると，この先，解まで拡張できたとしても，この先の置き方によらず，左回転した解のほうが小さいことがわかるので，2行目をこのように置いた先の探索を打ち切ればよい． (なお，この場合は，左右反転した解も小さいのでそれで打ち切ることも可能)
  これは，対称解の除去に用いる順序関係を考慮して対称解の除去を探索と同時に行うことに相当する．

再帰呼出しの代わりに明示的なスタックを利用

深さ優先のバックトラック探索では再帰呼出しにより部分解の木を渡り歩く説明をした．しかし，場合にもよるが，明示的なスタックを用いたほうが高速になることも多い．また，後に行う並列化のうちワークスティールに基づく並列化も，明示的なスタックを用いたほうが簡単になる．

例えば:

int f(int k, int *a){
  if(k == 0)
    {
      return *a;
    }
  else
    {
      int i, s = 0;
      for(i=0;i<k;i++){
        (*a) += i;
        s += f(k-1, a);
        (*a) -= i;
      }
      return s;
    }
}

という再帰呼出しを用いた計算は，明示的なスタックを用いることで

int f2(int k, int *a){
  int st[10000];
  int s = 0;
  int k0 = k;
 Ls:
  if(k == 0)
    {
      s += *a;
    }
  else
    {
      int i;
      for(i=0;i<k;i++){
        (*a) += i;
        st[k--] = i;
        goto Ls;
      Lc:
        i = st[++k];
        (*a) -= i;
      }
    }
  if(k == k0) return s;
  goto Lc;
}

のように変更することができる．

並列プログラミング, 先頭ページへ

Masahiro Yasugi