Orz日記 by Akio Morita

_ [SAD]並列Map

プロトタイプ実装した際の並列制御の実装メモと問題点への考察をまとめておく

子プロセス使い捨てモデル

Frok[]した子プロセスで評価した値をShared[]経由で親プロセスが回収。 子プロセスとの同期には、SetPGID[]で割り当てたプロセスグループIDを 使ってブロッキングモードのWait4[]で待ち受ける。(子プロセス達の どれかが計算終了するまで親プロセスは休眠する) 子プロセスを回収後に新たな子プロセスをFrok[]する。

Shared[]の使いまわし可。

制御は比較的簡単に実装できるが、評価毎に Fork[]のコストが必要。

子プロセス再利用モデル

Fork[]した子プロセスとShared[]経由で評価すべき内容と結果をやりとりする。 Fork[]した時点で、評価関数と評価対象のリスト全体が複製されているので 評価の指示は、リスト上の位置情報で十分である。 プロセス間の相互の同期は、SYSV IPCや POSIX Semaphoreへの インターフェースが未実装なので、Pipe[](pipe(2))と SelectUnit(select(2))を使って同期を実装する。

子プロセスは親プロセスからパイプに合図が送られてくるのを selectで ブロッキングしながら待機し、合図が来たら Shared[]から評価要求を 受け取り、評価結果を Shared[]へ書き込み親プロセスへのパイプに 1byteの合図を書き込んで待機状態に戻る。

親プロセスは、旗下の子プロセス達のパイプから合図がくるのを selectで ブロッキングしながら待機し、合図が来たら Shared[]から評価結果を 受け取り、次の評価要求を Shared[]へ書き込んだ後、子プロセスへのパイプに 1byteの合図を書き込んで待機状態に戻る。

エラーハンドリングとしては、子プロセスが異常終了した場合に備えて、 ノンブロッキングモードのWait4[]で子プロセスを指定して生存を確認し、 死亡している場合は、パイプを再生成して Fork[]する。

Flush[]と Close[]の動作に要注意！ パイプをFlush[]すると LFが送られることがあるので、 Flush[]の使用は避けること！

また、Close[]が、パイプを閉じるときに LFを送ることがある。 したがって、受信側のプロセスが死亡する前に送信側のパイプを Close[]しておかないと、Close[]実行時のLF送出に失敗して Broken pipeでアボートしてしまう。 (おそらく、Fortran I/Oライブラリ内で発生している)

問題点

• 並列評価時の評価関数の実行速度が単体実行時と比較して劣化する
  • 劣化の度合いは、評価の進行とともに悪化する
  • VM/RM内のフラグメント化や Copy on Writeに伴うページ単位のコピーが原因か？(特に multi pageにまたがるオブジェクトの生成＆更新時)
• 階数指定子の付いた Mapの並列評価
  • 最上位階のみを並列化する実装は比較的簡単だが、もっとも深い階層を評価する部分が律速になる
  • 並列Mapの入れ子で実装すると、最大同時実行数を制御できない(過多な評価器の多重起動はスワップによる性能低下を発生させる)
  • Level[]による階数木にそって評価する場合(細粒度並列化)は、評価順序依存性による制御を行う必要がある。
  • 子プロセスは、階数木の葉や部分枝の評価値を知らないので、再利用モデルでは評価値の通知か子プロセスの再Forkが必要