共有メモリ並列プログラミング (特にマルチコア) で、Cilk スタイルのソリューション (つまり、コアごとのワーク スティーリング タスク デキューによるネストされたデータ並列処理) を使用しても解決できない、または効率的に解決できない課題は何ですか?
1 に答える
6
Cilk のモデルは、ネストされたタスクの並列処理 (データの並列処理を実装するために使用できます) だと思います。かなりかわいいですが...
Cilk は、SIMD データ並列処理またはストリーミング並列処理をサポートしていません。
Cilk はネストされた並列処理しか提供しないため、タスクの部分的な順序をうまく処理していないようです。次の並列タスクのセットをコーディングしてみてください: A、B、C、D の順序制約を付けて、A を B の前に、A を D の前に、C を D の前に配置します。直接エンコードします）。これをネストされた並列処理で実装すると、並列処理がいくらか失われます。並列処理は貴重なので、並列処理の機会を無駄にしたくありません。
スレッド境界を越えた（AFAIK）例外処理は処理しません。これは、非常に大規模で複雑なシンボリック アプリケーションを構築する場合に必要です。投機的に計算したい場合にも役立ちます。
また、Cilk プログラムの AFAIK は、OS が提供するスレッドと同じ数のライブ並列計算しか行えないため、Cilk が計算粒度間の対話 (同期イベントの待機) の大規模なセットを処理できるとは思いません。これは、ほとんどのワークステーションでスレッドごとに 1 つの大きなスタック モデルを使用する、標準の C/C++ コンパイラとそのスタック モデルの上にあるという Cilk 実装の選択によるものです。10 または 100 に到達する可能性がありますが、10,000 には到達しません。これは、非常に大きなグラフを処理する場合に重要です。[Cilk が計算粒度の同期を許可するという事実についてはわかりませんが、大規模なスタック モデルを放棄した場合に同期できなかった技術的な理由はわかりません]。
2 つ目の意味は、Cilk アプリケーションは巨大なデータ構造を再帰できないということです。これは、選択したスタックのサイズに制限があり、スタックが不足する例がいくつかあるためです。(これは Cilk の設計上の欠陥ではなく、実装上の問題です)。巨大なものは並列処理が必要な場所の 1 つであるため、これは残念です。
別の方法として、 PARLANSEを参照してください。これは、任意に多数の計算粒度を提供し、ワークスティーリングを使用しますが、ヒープ割り当て粒度とアクティベーション レコードを使用します。各グレインには独自のコンテキストがあります (したがって、イベントを待機する必要があるときにグレインの状態を保存するのは簡単なので、相互作用する大規模な一連のグレインを実装できます。PARLANSE 同期プリミティブには、フューチャー、セマフォ、および重要な関数の結果が含まれます (以下を参照)。 )
PARLANSE は、抽象化として明示的な「チーム」(計算粒度のセット) を提供します。例外は、関数から計算粒度の先頭に伝播し (Java はこれを「未定義」と定義していますが、これはばかげています)、チームの親に戻ります。他のすべてのチームの子を非同期のアボート例外 (try 句でキャッチ可能) として処理し、他の子がクリーンアップできるようにします。
一部のアクション (非同期アボート例外など) は任意の時点で発生する可能性があるため、PARLANSE ではクリティカル関数の概念が提供されます。この関数の結果は呼び出し元にアトミックに返されることが保証されているため、関数は結果を確実に返すか返さないかのいずれかになります。また、関数は非同期アボート ハンドラで安全にリソースをクリーンアップできます。
特別な「半順序」チームにより、半順序が既知の計算をエンコードできます。大量のセットがある場合、これは Cilk のネストされた並列処理よりも効率的だと思います。
(大規模なプログラム分析/変換ツールを実装するために PARLANSE を使用します。PARLANSE はこれをサポートするために発明されました。処理するアーティファクトは、数百万行のコードを表す巨大なツリーとグラフであるため、並列処理が必要です)。
(PARLANSE はストリームも SIMD も行いませんが、言語の範囲外ではありません。ストリームと SIMD を C と C++ に追加することはほぼ間違いありませんが、かなり難しい可能性があります)。
于 2010-10-20T23:47:25.590 に答える