Orz日記 by Akio Morita

_ [SAD]並列マップ

フロントエンドラッパーともっとも単純なfork/wait4ベースの並列実装 (子プロセスを評価毎に生成して使い捨てる)をamorita branchの develに commitした。

使用例

Library@Require["Algorism/Parallel"];	(* ライブラリ要求 *)

$ParallelMethod = "Fork";		(* デフォルトの並列化実装を Forkに設定 *)

l = GaussRandom[100, 100];

result = Parallel@Map[Fourier, l, SharedSize->1024, Multiplicity->5];

通信バッファサイズを1024bytes、並列度を5で、 リストlの各要素にFourier[]並列に作用させる。

デフォルトオプションは、{SharedSize->256,Multiplicity->NPARA}

現時点の実装では、階数1へのMapのみをサポート (つまり、階数指定子無しのMapやMap演算子と同じ)

注意点

並列にすれば早くなる訳ではなく、 リストの各要素に作用させる評価関数が十分に重い＆返却データのコピーコストが十分に小さい等の 条件が成り立たないと早くならない。 また、fork/wait4システムコールの呼び出し負荷やスケジュラーへの負荷が あるので、混雑したシステム上での過度な並列化は全体の性能を低下させる。

改良すべき点

1. SharedSizeの自動決定
2. Map[]関数相等の階数指定子サポート

(1)に関しては、部分的に実装済みで、子プロセスが共有メモリ経由で 結果を返送出来ない場合は必要な共有メモリサイズを親プロセスに通知、 親プロセスは受け取れなかった結果を自分で計算すると同時に 以降の通信バッファのサイズを通知に基づいて更新する。

最悪のケースは必要な通信バッファの量が評価順序にそって増えた場合で、 このケースは救えない。

結果を回収するには別チャンネルで、子プロセス-親プロセス間の通信を 行う必要がある。案としては...

1. データ分割プロトコルを定義してShared[]経由で転送する
2. 一時ファイルに書き出して、一時ファイル名を通知する
3. 新たにShared[]を生成する

(1)は、通信に際して親プロセスと子プロセスの相互同期が必要であり、 データエンコードスキームとしては Shared[]が内部的に使っている uni-byte stream encoder/decoderの相当品が必要 (ToString[]によるASCII変換は、ToExpression[ToString[#]]&が 恒等変換で無いので使用できない)であり、実装し難い。 (2)は、ファイルに格納するデータエンコードに(1)と同様の問題有り。 (fork/wait4モデルでは、ファイルシステムの名前空間の断絶を考慮する必要はない) (3)は、現状のOpenShared[]が無名の共有メモリしか扱えないので無理。

多分、性能面での筋が良さそうなのは、OpenShared[]とそのバックエンドとなる mapalloc内部APIを拡張して、ファイル上に共有メモリを確保 出来るようにして、共有メモリとして使う一時ファイル名を受け渡すのが 妥当と思われる。

別の応用(数値計算結果の正確な保存と復元)を考えると、Shared[]が内部的に 持っているuni-byte stream encoder/decoderの外部APIを提供することも 意味があると思われる。