Orz日記 by Akio Morita

_ [WWW]X-tDiary/X-Hikiアップデート

遅ればせながら、X-tDiary-0.16/X-Hiki-0.18へプラグインを更新 MathMLライブラリは 0.5aを採用

_ [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を提供することも 意味があると思われる。

_ [SAD]Map1/Scan1実装

Joinに続き、Map1/Scan1の実装完了

で、データ操作系の典型的なユースケースを試していると以下のケースで、スタックを踏み抜く

• MapThread[f, {long-list, long-list}]
  • Map[f@@#&, Thread[{long-list, long-list}]]はOK
  • 多分、Threadは、いきなりリストコンテナを組み立てているからOKの模様
  • ScanThreadはテストしていないが、おそらくスタックに積み上げた出力列が溢れている
• f@@long-list (fは、Reduction operator)
  • fの評価式をApplyで組み立てる際に、引数列としてlong-listをスタック上に展開する(式をスタック上に展開して評価する関数評価呼び出しシステム上の問題)
  • Applyが、fがReduction演算であることを知っていれば、イテレータ処理に移譲できるが、ユーザー定義のReduction演算子には無力
    • 評価器のスタックベースの評価を止める or sequence containerによる式評価を導入する
      • 関数評価時の引数参照インターフェースの変更が必要
        • Apply等からの運用を想定すると、Head + Argument Containter渡しが現実解か？
      • 実装過渡期は、引数列参照渡しとStack渡しの両方をサポートする必要有り
        • 関数テーブルに引数型式属性を持たせて、評価時の呼び出しプロトタイプをDispatchさせる
    • Reduction演算を行う高階関数を導入する
      • 例えば、左再帰なReduction演算 LeftReduce[f, {arg1, arg2, args...}] := LeftReduce[f, {f[arg1, arg2], args...}] := f[f[...f[f[arg1, arg2], arg3]...], argn]
        • LeftReduce[f, {}] := f[], LeftReduce[f, {arg1}] := f[arg1] == f[f[], arg1] であるべきか…
      • 浮動小数点処理の場合、評価木の組み方で処理結果が異なる
      • 短縮評価可能な論理演算の場合、評価木の組み方で処理時間が異なる
      • n要素に分岐する再帰的な評価木もありえる