＆＃8220; Reduce＆＃8221;の並列化＆＃8220; MapReduce＆＃8221;

StackOverflow https://stackoverflow.com/questions/329423

質問

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

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

役に立ちましたか？

解決

リダクションの基礎となる操作が関連性*の場合、操作の順序と局所性を試すことができます。そのため、「収集」段階ではツリー状の構造を持っていることが多いため、対数時間で複数のパスを実行できます。

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

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

操作が可換である場合、さまざまな順序で収集できるため、さらなる最適化が可能です（たとえば、これらの操作がベクトル操作である場合、データのアライメントにとって重要な場合があります）

[*]もちろん浮動小数点数のような効果的な型の演算ではなく、実際に必要な数学的演算。

他のヒント

はい、演算子が結合性の場合。たとえば、数値のリストの合計を並列化できます。

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）、つまり、追加が実行される順序が重要ではないために機能します。

Hadoopの結合フェーズを確認する

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

どのプラットフォーム/言語を考えているのかわからないが、次のように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の答えの背後にあるプログラム的な推論です。）

技術的には、reduceはfoldl（fold-left）と同じではありません。foldl（fold-left）は、蓄積としても説明できます。

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演算子にはありません。

Reduceステップに依存します。 MapReduceのHadoopスタイルの実装では、Reduceがキーごとに1回呼び出され、そのキーに関連するすべての行が含まれています。

したがって、たとえば、マッパーは順序付けられていないWebサーバーログを大量に取得し、メタデータ（ジオコーディングなど）を追加し、Cookie IDをキーとして[key、record]ペアを発行します。次に、ReducerがCookie IDごとに1回呼び出され、そのCookieのすべてのデータが供給され、訪問頻度や訪問ごとの平均ページ数などの集計情報を計算できます。または、ジオコードデータに基づいて、地理に基づいて集計統計を収集することもできます。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top