موازنة "التخفيض" في "MapReduce"

Question

أفهم كيف يمكن موازاة Map بسهولة - يمكن لكل كمبيوتر/وحدة معالجة مركزية أن تعمل فقط على جزء صغير من المصفوفة.

هل يمكن تقليل/foldl بالتوازي؟يبدو أن كل حساب يعتمد على الحساب السابق.هل هي قابلة للتوازي فقط مع أنواع معينة من الوظائف؟

Answer 1

إذا خفض الخاص بك العملية الأساسية هو * النقابي، يمكنك ان تلعب مع ترتيب العمليات والمكان. لذلك كنت غالبا ما يكون لها هيكل شجرة تشبه في مرحلة "جمع"، لذلك يمكنك أن تفعل ذلك في عدد من الممرات في وقت لوغاريتمي:

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

وبدلا من (((أ + ب) + ج) + د)

إذا عملية الخاص بك هو تبادلي، مزيد من التحسين والممكنة كما يمكنك جمع في ترتيب مختلف (قد يكون من المهم للمحاذاة البيانات عند تلك العمليات هي عمليات ناقلات على سبيل المثال)

[*] الحقيقية المرجوة العمليات الحسابية، وليس تلك الموجودة على أنواع فعالة مثل العوامات بطبيعة الحال.

Answer 2

نعم، إذا كان المشغل النقابي. على سبيل المثال، يمكنك parallelise بجمع قائمة من الأرقام:

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

ويعمل هذا لأن (أ + ب) + ج = من + (ب + ج)، أي الترتيب الذي يتم تنفيذ إضافات لا يهم.

Answer 3

وتحقق من مرحلة الجمع في Hadoop

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

Answer 4

ولست متأكدا ما منصة / لغة كنت تفكر في، ولكن يمكنك بشكل مواز لحد من المشغلين مثل هذا:

// 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);

وكما ترون، والتنفيذ المتوازي هو عودي بسهولة. يمكنك تقسيم خريطة لأعلى، وتعمل على كل جزء في موضوع خاص بها، ثم نفذ آخر لحد من مرة واحدة تتم هذه المواضيع لجلب القطع معا.

(وهذا هو المنطق وراء برنامجي بيوتر يسنيك في الإجابة .)

Answer 5

ومن الناحية الفنية تقليل ليست هي نفسها كما foldl (أضعاف اليسرى) والتي يمكن أيضا وصفه بأنه تتراكم.

والمثال الذي قدمه جول يوضح للحد من عملية بشكل جيد للغاية:

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

لاحظ أن في كل خطوة والنتيجة هي صفيف، بما في ذلك النتيجة النهائية وهي مجموعة من عنصر واحد.

وهناك أضعاف اليسار هو كما يلي:

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 له نتيجة واضحة المعالم عند إعطاء المشغل غير النقابي (مثل الطرح) في حين أن الحد من المشغل لا.

Answer 6

ذلك يعتمد على خطوة التصغير الخاصة بك.في تطبيق MapReduce على غرار Hadoop، يتم استدعاء المخفض الخاص بك مرة واحدة لكل مفتاح، مع كافة الصفوف ذات الصلة بهذا المفتاح.

لذلك، على سبيل المثال، قد يستقبل مصمم الخرائط الخاص بك الكثير من سجلات خادم الويب غير المرتبة، ويضيف بعض البيانات الوصفية (على سبيل المثال، الترميز الجغرافي)، ويصدر أزواج [مفتاح، سجل] مع معرف ملف تعريف الارتباط كمفتاح.سيتم بعد ذلك استدعاء المخفض الخاص بك مرة واحدة لكل معرف ملف تعريف الارتباط وسيتم تغذيته بجميع البيانات الخاصة بملف تعريف الارتباط هذا، ويمكنه حساب المعلومات المجمعة مثل تكرار الزيارة أو متوسط ​​الصفحات التي يتم عرضها لكل زيارة.أو يمكنك إدخال بيانات الترميز الجغرافي وجمع الإحصائيات الإجمالية بناءً على الجغرافيا.

حتى إذا كنت لا تقوم بتحليل إجمالي لكل مفتاح - في الواقع، حتى إذا كنت تحسب شيئًا ما على المجموعة بأكملها - فقد يكون من الممكن تقسيم العمليات الحسابية الخاصة بك إلى أجزاء، يمكن تغذية كل منها إلى المخفض.