ail3 parallel programming

課題6: n女王プログラムの並列化

並列プログラムのサンプル（後述の２つの例）を与えるので、それを元にWeb課題5で作成したプログラムの並列化を行う。逐次版のプログラムと速度比較ができるようにする。速度比較は課題5と同様に行う

すくなくとも1種類のアルゴリズム（ビットマップ版: Web課題5を進めた後の Makefile nq.c）をベースにして POSIX スレッドライブラリを利用してマスタ・ワーカ方式により並列化することを必須とする。余力がある場合、ワークスティール方式による並列化、共有メモリ向けマクロの利用を試みること。また、他の種類のアルゴリズム（配列版: Web課題5を進めた後の Makefile nq_a.c）の並列化を試みるのもよい。特に配列版については，ビットマップ版とは別に提出すれば非ビットマップ版の「上位ランキング」の候補となる．

n女王問題のプログラムは「場合の数(個数)」を出力すること．たとえば「パズルの解」をメモリに保存しておく必要はない． (それでも保存する場合は，並列プログラミングにおいては， pthread_mutex_lock/pthread_mutex_unlock 等で正しく相互排他する必要がある．なお，相互排他は各スレッドから「まとめて」表示する場合にも必要)
できるだけ高速化を試みること
逐次版は残しておき、「-a N」の指定で並列版の選択もできるようにすること
N は 101～を用いること。
「-p P」の指定でワーカスレッド数 P を選択できるようにすること
「-a N」のN を 101～として並列版としたときの P のデフォルト値は 2 とする．
「-a N」が未指定の場合は逐次版で一番高速と期待できるものにしておく。ただし，「-p P」の指定でワーカスレッド数 P を2以上とした場合には並列版で一番高速と期待できるものにする．
Pプロセッサ（コア）を用いて並列化するとき，問題を解くのに必要な計算を，計算量(計算時間)の等しいP個の部分にうまく分割できれば理想的な台数効果が得られることが多い．LU分解のように計算が規則的な場合，そのような分割は比較的容易であった．
n女王問題のような不規則な問題の場合，あらかじめ必要な計算を量が等しいP個の仕事(タスク)に分割することは不可能といえる．そのような計算に対しては:
- マスタ・ワーカ方式
- ワークスティール方式
などの手法が用いられる．
マスタ・ワーカ方式による並列化
- n女王問題のような不規則な問題の並列化についての説明を参考にしてマスタ・ワーカ方式による並列化を行う．
- pthreads ライブラリの利用すること．共有メモリ向けマクロの利用してマスタを兼ねるワーカスレッドを作ることも可能だが，プログラムは複雑になるためである．(余裕があれば試みてよい)
ワークスティール方式による並列化
- ワークスティール方式の説明を参考にしてワークスティール方式による並列化を行う。
- 共有メモリ向けマクロを利用する。
- 説明した方式では、タスクは他のワーカで処理できるようにあらかじめ生成しておく必要があった。つまり、部分解の内容のコピーを行っているといえる。部分解の内容のコピーを避けるために部分解のデータの変更と，変更の取り消しを行うような場合に説明した方式は対応できていない。改良案としては、タスクキューを使わずに、タスク要求があったときにはじめて、渡すためのタスクを作成する (と同時に渡した部分の計算を二重にしないようにする)方式が考えられる。凝った方式であるが、余裕があれば試みてよい。この場合、渡すためのタスクを作成するためには、変更の取り消しが必要であり、課題5で述べた明示的なスタックを用いる必要があると考えられる。

マスタ・ワーカ (master-worker) 方式

マスタ・スレーブ方式とも呼ばれる．「主人-奴隷」という表現を避けて，近年はマスタ・ワーカと呼ぶことが多い．
マスタは，仕事(タスク)の分割とワーカへの割り当て，結果のとりまとめを行う．
ワーカは割り当てられた仕事(タスク)を終えると，再度マスタから仕事(タスク)を割り当ててもらう．
プロセッサ（コア）数Pにおいて，典型的には，1台のプロセッサ（コア）がマスタをし，残りのP-1プロセッサ（コア）がワーカを行うことが多い．
```
	
+----------------------------------+
|            master                |
+----------------------------------+
   ↓↑         ↓↑                ↓: 仕事(タスク)の割り当て  ↑: 結果の回答
+---------+  +---------+
| worker0 |  | worker1 | .....
+---------+  +---------+
```
しかし， Pが小さすぎる場合はワーカが少なくて台数効果が悪くなり， Pが大きすぎる場合はマスタがボトルネックとなって台数効果が悪くなる． Pが小さすぎる場合はワーカのスレッドをPプロセッサ（コア）分作成し，マスタの処理をワーカ処理の合間に行うようにすればよい．このとき:
- マスタスレッドを作成し，マスタの処理を行うプロセッサ（コア）は固定せず，次の仕事(タスク)を待つワーカスレッドが再開待ちで休眠する間に，マスタスレッドが動作するようにする．
- ある特別なワーカスレッドがマスタの処理も行う．
という2通りの方式が考えられる． 1つ目の方式は，pthreads ライブラリで有効， 2つ目の方式は，共有メモリ向けマクロで有効と思われる．
一般には、あるタスクを処理した結果を他のタスクが利用するために同期が必要であるが、 n女王問題のような解の数を求めるような問題では、計算結果はマスタで集計すればよいので、タスクの処理は他のタスクの結果に依存することなく計算できる。
マスタが仕事(タスク)をどのサイズに分割するかも問題である．多数のあまりに小さな仕事(タスク)に分割した場合は，割り当てなどにかかるオーバヘッド(間接経費)が無視できなくなり，あまりに少数の大きな仕事(タスク)に分割した場合は，ワーカが処理するタスクの仕事量のアンバランスにより，台数効果が悪くなる．割り当てにかかるオーバヘッドが無視できる程度のサイズのタスクに分割するとよい．もちろん，n女王問題のような不規則な問題の場合，タスクの仕事量をあらかじめ見積もることはできないので，かなり大雑把に近似するほかない．たとえば，
- ある自然数の定数Cについて，「C行目以降の探索」を割り当て単位とする方式，
- ある実数Dについて(0<D<1)，「n * D行目以降の探索」を割り当て単位とする方式，
などが考えられる．
nが小さい場合は，どうやっても並列化は難しいが，広い範囲のnについてうまく並列化できるのがうまい方式といえる．
マスタスレッドを用いる場合，マスタ・ワーカ間の通信・同期は生産者消費者型同期と似ている．マスタが準備したデータを使って，ワーカは計算をし，逆に，ワーカの計算結果を使って，マスタはとりまとめの計算をする．ただし，仕事のない(アイドルな)ワーカがいないのに，先に仕事の分割を進めてしまうと，その記憶場所に困るので分割はワーカから仕事(タスク)の要求があってから進めるぺきであり，そのための通信・同期も必要である．また，仕事(タスク)の要求と，計算結果の報告はひとまとめにできるかもしれない．
一般には，仕事(タスク)の分割を待つ間，ワーカが遊ぶのは無駄であるので，仕事のキュー(バッファ)を用いて，キューのサイズ分だけ常にすぐに割り当て可能な仕事(タスク)を準備しておくと良い．キュー(バッファ)のサイズは1で十分であるかもしれない．その場合は，タスクを置いておく場所を用意しておき，ワーカは処理中の仕事がなくなったらそこからタスクを取り出し，マスタはタスクを補充しておくことになる．ただし，Pが小さいために，タスクを待つワーカスレッドが再開待ちで休眠する間にマスタスレッドが動作するようにするのであれば，あまり得ることはないかもしれない．なお，どちらにしても，タスクの置き場所は通信するために最低1つ必要である．
終了検出について考える必要がある。一つには
- タスクの分割、割り当てがすべて終わっている。
- 全ての結果の回答が終わっている。
ことを確認すればよい。2番目の条件は、いくつ回答待ちかのカウンタを用いることで確認可能。
マスタ・ワーカ (master-worker) 方式の例
- 2^n を計算する例

ワークスティール(work stealing)方式

マスタ・スレーブ方式では、分割するタスクサイズの調整が難しい。
ワークスティール方式では、タスクの再分割を(再帰的に)行う。
タスクの再分割を積極的に行う方式と、ぎりぎりまで遅らせる方式がある。
ワークスティール方式では、他のワーカからもタスクを得る (スティールする/盗む)。
一般には、あるタスクを処理した結果を他のタスクが利用するために同期が必要であるが、 n女王問題のような解の数を求めるような問題では、計算結果はマスタで集計すればよい。なお、カウンタを一つのみ準備したのでは、共有しているためのキャッシュ無効化などのため、アクセスが遅くなってしまう。これを避けるにはワーカ毎にカウンタを設けることが考えられる。

一般にはワーカのみとし、並列計算をはじめる前と終わった後とで、あるワーカがマスタの役割を果たせばよい。

+----------------+  +---------+  +---------+
| master/worker0 |  | worker1 |  | worker2 | .....
+----------------+  +---------+  +---------+
・タスクの無くなった(アイドルになった)worker は、他の worker からタスクを盗む
・n女王問題ならmaster に結果を回答 (一般にはタスク間で同期が必要)

生成済のタスクは、ワーカスレッド毎のタスクキューを用いて管理する。
- タスクキューは先頭(head)と末尾(tail)を持つ両端キューとする。
- 各ワーカスレッドは、生成したタスクを自分のタスクキューの末尾に追加する。
- 各ワーカスレッドは、一つのタスクの処理が完了したら、タスクを末尾から取り出して処理する。もし、タスクキューが空っぽになっていたら、他のワーカスレッドのタスクを盗む。
- タスクを盗む場合は、タスクキューの先頭から盗む。
  一般に先頭のタスクのほうがサイズが大きいことが期待でき、ワークスティールの回数を低く抑えることが期待できる。
(注) ここでは，「タスク」を分割した計算の開始時に必要な入力データ(オブジェクト) の意味で用いている．一般には，「タスク」とはプロセッサ（コア）上のスケジューリングや負荷分散(並列実行)の単位をさすことが多く，実行途中のことも多い．その場合のタスクは，複数の関数フレームを伴ったり，その関数フレームを保持する実行スタックを伴ったりする．
ワーカがタスクキューの末尾からタスクを取り出すのと，他のワーカがタスクキューの先頭からタスクを取り出すのとは競争になる可能性があり，間違って両方が取り出せたり，両方が取り出せなかったりすると問題である．これを防ぐには，スレッド間の相互排他が必要である． pthreadsでは，pthread_mutex_lock などを利用しなくてはならないが，タスクキューの操作の度にロックの獲得と解放をしていたのではオーバヘッドが大きすぎる．そこで，各ワーカは他のワーカからのタスク要求をときどきチェックする(ポーリングする)ことにする．要求が届いている場合には，タスクキューの先頭からタスクを取り出して渡すことにする．
終了検出について考える必要がある。一つには
- 全ての結果の回答が終わっている。
ことを確認すればよい。この条件は、いくつ回答待ちかのカウンタを用いることで確認可能。重み付きカウンタを使えば、カウンタ値を増やさなくてもタスク分割時には重みを分けるだけでよい。全ての重みが返却されたら終了である。
ワークスティール方式の例
- 2^n を計算する例 (日本語コメント足しました)

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

Masahiro Yasugi