10

Map が簡単に並列化できることを理解しています。各コンピューター/CPU は配列のごく一部で動作します。

Reduce/foldl は並列化可能ですか? 各計算は前の計算に依存しているようです。特定のタイプの関数に対してのみ並列化できますか?

4

6 に答える 6

14

削減の基礎となる操作が連想的*である場合は、操作の順序と局所性を試すことができます。したがって、「収集」フェーズではツリーのような構造になることが多いため、対数時間で数回のパスでそれを行うことができます。

a  +  b  +  c  +  d
 \   /       \   /
 (a+b)       (c+d)
     \       /
   ((a+b)+(c+d))

（（（a + b）+ c）+ d）の代わりに

操作が可換である場合、異なる順序で収集できるため、さらに最適化することができます（たとえば、これらの操作がベクトル操作である場合、データの整列に重要な場合があります）。

[*]もちろん、floatのような効果的なタイプの演算ではなく、実際に必要な数学演算です。

于 2008-11-30T22:01:04.647 に答える
6

あり (オペレータが関連付けられている場合)。たとえば、数値のリストの合計を並列化できます。

step 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
step 2:   3   +   7   +   11  +   15
step 3:       10      +       26
step 4:               36

(a+b)+c = a+(b+c) であるため、これが機能します。つまり、加算が実行される順序は重要ではありません。

于 2008-11-30T22:25:24.330 に答える
3

Hadoop の結合フェーズを確認してください

http://wiki.apache.org/hadoop/HadoopMapReduce

于 2008-11-30T23:00:52.637 に答える
1

考えているプラ​​ットフォーム/言語はわかりませんが、次のようにreduce演算子を並列化できます。

// Original
result = null;
foreach(item in map) {
    result += item;
}

// Parallel
resultArray = array();
mapParts = map.split(numThreads);
foreach(thread) {
    result = null;
    foreach(item in mapParts[thread]) {
        result += item;
    }
    resultArray += result;    // Lock this!
}
waitForThreads();
reduce(resultArray);

ご覧のとおり、並列実装は簡単に再帰的です。マップを分割し、独自のスレッドで各パーツを操作し、それらのスレッドが完了したら、別のリデュースを実行してピースをまとめます。

（これは、 Piotr Lesnickの答えの背後にあるプログラム的な推論です。）

于 2008-11-30T22:00:17.190 に答える
1

技術的には、reduce は foldl (fold-left) と同じではなく、accumulate とも言えます。

Jules が示した例は、reduce 操作を非常によく示しています。

step 1: 1 + 2 + 3 + 4 
step 2:   3   +   7   
step 3:       10

各ステップで、結果は配列であり、1 つの項目の配列である最終結果を含むことに注意してください。

左折は次のようなものです。

step 0: a = 0
step 1: a = a + 1 
step 2: a = a + 2 
step 3: a = a + 3
step 4: a = a + 4
step 5: a

明らかに、これらは両方とも同じ結果を生成しますが、非結合演算子 (減算など) が指定された場合、foldl は明確に定義された結果を持ちますが、reduce 演算子はそうではありません。

于 2010-02-09T02:10:23.303 に答える
0

これは、Reduce ステップによって異なります。MapReduce の Hadoop スタイルの実装では、Reducer がキーごとに 1 回呼び出され、すべての行がそのキーに関連します。

そのため、たとえば、マッパーは多数の順序付けられていない Web サーバー ログを取り込み、いくつかのメタデータ (ジオコーディングなど) を追加し、Cookie ID をキーとして [キー、レコード] ペアを出力する可能性があります。その後、Reducer は Cookie ID ごとに 1 回呼び出され、その Cookie のすべてのデータが供給され、訪問頻度や訪問ごとに表示された平均ページなどの集計情報を計算できます。または、ジオコード データをキーにして、地理に基づいて集計統計を収集することもできます。

キーごとの集計分析を行っていない場合でも、実際、セット全体で何かを計算している場合でも、計算をチャンクに分割して、それぞれを Reducer に供給することができる場合があります。

于 2009-01-08T18:43:21.140 に答える