12

「Parallel and Concurrent Programming」のこのグラフ: http://chimera.labs.oreilly.com/books/1230000000929/ch03.html#fig_kmeans-granularity最初は、スパークが多すぎるために深刻なオーバーヘッドがあることを示しているようです。しかし、y 軸を注意深く見ると、興味深いセクションが拡大されていることがわかります。実際、示されている最良のケースと最悪のケースのパフォーマンスの比率は約 80% であり、それほど悪くはありません。

一般に、どのように、どのくらいチャンクするかを理解することは難しく、エラーが発生しやすく、非常にアプリケーション固有であり、来年、より処理能力の高い新しいコンピューターを購入すると変更される可能性があります。私は常に rpar を可能な限り細粒度のアイテムで使用し、25% のオーバーヘッドで生活することを望んでいます。

一般に、スパーキングのオーバーヘッドは、このグラフに示されているよりもはるかに悪いコストになる可能性がありますか? (特に、リストではなく二分木を常に折りたたんでいる場合は、「順次作業の量」に関する 2 番目の箇条書きは適用されません)

Don Stewart の回答に応じて質問を更新しました。

スパーク プールは、すべてのプロセッサがアクセスするのに苦労する 1 つのキューだけで構成されていますか? それともたくさんありますか？

たとえば、無限のプロセッサとバイナリ ツリーを備えたコンピューターがあり、次のようにすべての葉の合計を取得したい場合:

data Node = Leaf Int | Branch Node Node

sumL (Leaf x) = x
sumL (Branch n1 n2) = let (x,y) = (sumL n1, sumL n2) in (x `par` y) `seq` (x + y)

このプログラムは O(#leaves) 時間で実行されますか? またはO（深さ）時間？これを書く良い方法はありますか？

抽象化しすぎて満足のいく答えが得られない場合はお知らせください。Haskell の並列処理がどのように機能するかについての私のメンタル モデルは、まだ非常にあいまいです。

4

1 に答える 1

9

単一のスパークは非常に安価です。

  • スパーク プール。を呼び出すたびpar a bに、サンク a が (現在の HEC の) Spark プールに追加されます。このサンクは「火花」と呼ばれます。[1]

いずれかの HEC がアイドル状態になると、プールをチェックして、上部のサンクの評価を開始できます。

したがって、スパークは大まかにポインタをキューに追加することです。

Spark の配布をより安価に、より非同期にするために、各 HEC の Spark プールを制限付きのワークティーリング キューとして再実装しました (Arora et al. 1998; Chase and Lev 2005)。ワークティーリング キューは、いくつかの魅力的なプロパティを備えたロックフリーのデータ構造です。キューの所有者は、同期せずに一方の端からプッシュおよびポップできます。一方、他のスレッドはキューのもう一方の端から「盗む」ことができ、1 つのアトミック命令のみが発生します。 .

[1]にも

問題は、何十億もの火花を簡単に作成できることです。その時点では、単にプログラムをキュー ビルダーに変えているだけです。すべての時間が、コードへのポインターを使用してスパーク プールを更新することに費やされます。

適切なアドバイスは、プロファイリングを行い、実際に仕事に変わったスパークの数を決定し、それを使用してスパークを停止するタイミングのしきい値を導くことです。

于 2014-05-27T07:30:04.930 に答える