Song song với "Giảm" trong "MapReduce"

Question

Tôi hiểu cách Map dễ dàng song song - mỗi máy tính/CPU chỉ có thể hoạt động trên một phần nhỏ của mảng.

Giảm/gấp song song? Dường như mỗi phép tính phụ thuộc vào lần tính toán trước. Là nó chỉ song song đối với một số loại chức năng?

Answer 1

Nếu giảm của hoạt động cơ bản là kết hợp *, bạn có thể chơi với thứ tự của các hoạt động và địa phương. Vì vậy, bạn thường có một cấu trúc cây như trong 'thu thập' giai đoạn, vì vậy bạn có thể làm điều đó trong một vài đường chuyền trong thời gian logarit:

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

thay vì (((a + b) + c) + d)

Nếu hoạt động của bạn là giao hoán, tiếp tục tối ưu hóa có thể xảy ra khi bạn có thể thu thập theo thứ tự khác nhau (có thể là quan trọng đối với sự liên kết dữ liệu khi những hoạt động đang hoạt động vector ví dụ)

[*] thực mong muốn các hoạt động toán học của bạn , không phải những loại hiệu quả như phao nổi.

Answer 2

Không chắc nền tảng những gì/ngôn ngữ mà bạn đang nghĩ đến việc, nhưng bạn có thể parallelize giảm khai thác như thế này:

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

Như bạn có thể thấy, việc thực hiện song song là một cách dễ dàng đệ quy. Bạn phân chia bản đồ lên, vận hành trên từng phần theo chủ đề riêng của nó, sau đó thực hiện một lần giảm khác khi các chuỗi đó được thực hiện để đưa các phần lại với nhau.

(Đây là lý do chương trình đằng sau Piotr Lesnick's answer.)

Answer 3

Có, nếu toán tử liên kết. Ví dụ, bạn có thể parallelise cách tổng hợp một danh sách các số:

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

này hoạt động vì (a + b) + c = a + (b + c), tức là thứ tự mà những bổ sung được thực hiện không thành vấn đề .

Answer 4

Kiểm tra giai đoạn kết hợp trong Hadoop

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

Answer 5

Nó phụ thuộc vào Giảm bước của bạn. Trong triển khai kiểu MapReduce của Hadoop, Reducer của bạn được gọi một lần cho mỗi khóa, với tất cả các hàng có liên quan đến khóa đó. Ví dụ: Ví dụ: Người lập bản đồ có thể đang lấy nhiều nhật ký máy chủ web không theo thứ tự, thêm một số siêu dữ liệu (ví dụ: mã hóa địa lý) và phát các cặp khóa, ghi với ID cookie làm khóa. Reducer của bạn sau đó sẽ được gọi một lần cho mỗi ID cookie và sẽ được cung cấp tất cả dữ liệu cho cookie đó và có thể tính toán thông tin tổng hợp như tần suất truy cập hoặc các trang trung bình được xem mỗi lượt truy cập. Hoặc bạn có thể khóa dữ liệu mã hóa địa lý và thu thập số liệu thống kê tổng hợp dựa trên địa lý.

Thậm chí nếu bạn không thực hiện phân tích tổng hợp khóa - thực sự, ngay cả khi bạn đang tính toán thứ gì đó trong toàn bộ tập - có thể chia tính toán thành từng phần, mỗi phần có thể được cấp cho Giảm.

Answer 6

Về mặt kỹ thuật, mức giảm không giống như nếp gấp (gấp trái) cũng có thể được mô tả dưới dạng tích lũy.

Ví dụ do Jules minh họa một giảm hoạt động rất tốt:

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

Lưu ý rằng tại mỗi bước kết quả là một mảng, trong đó có kết quả cuối cùng mà là một mảng của một mục.

Một lần bên trái là như sau:

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 

Bây giờ rõ ràng là những cả hai tạo ra kết quả tương tự, nhưng một foldl có một kết quả rõ ràng khi được một nhà điều hành không kết hợp (như phép trừ) trong khi một nhà điều hành giảm không.