並列プログラムのサンプルを与えるので、 それを元に課題5で作成したプログラムの 並列化を行う。 逐次版のプログラムと速度比較ができるよう にする。速度比較は課題5と同様に行う
すくなくとも1種類のアルゴリズムをベースにして POSIX スレッドライブラリを利用して マスタ・ワーカ方式により 並列化することを必須とする。 余力がある場合、ワークスティール方式による並列化、 共有メモリ向けマクロの利用を試みること。
-a N
」の指定で
並列版の選択もできるようにすること-p P
」の指定で
スレッド数 P を選択できるようにすること-a N
」のN を 101〜として並列版としたときの
P のデフォルト値は 2 とする.
-a N
」が未指定の場合は
逐次版で一番高速と期待できるものにしておく。
ただし,「-p P
」の指定でスレッド数 P
を2以上とした場合には
並列版で一番高速と期待できるものにする.
+----------------------------------+ | master | +----------------------------------+ ↓↑ ↓↑ ↓: 仕事(タスク)の割り当て ↑: 結果の回答 +---------+ +---------+ | worker0 | | worker1 | ..... +---------+ +---------+しかし, Pが小さすぎる場合はワーカが少なくて台数効果が悪くなり, Pが大きすぎる場合はマスタがボトルネックとなって台数効果が悪くなる. Pが小さすぎる場合はワーカのスレッドをPプロセッサ分作成し, マスタの処理をワーカ処理の合間に行うようにすればよい.このとき:
+----------------+ +---------+ +---------+ | master/worker0 | | worker1 | | worker2 | ..... +----------------+ +---------+ +---------+ ・タスクの無くなった(アイドルになった)worker は、他の worker からタスクを盗む ・n女王問題ならmaster に結果を回答 (一般にはタスク間で同期が必要)