"Mapreduce"에서 "감소"를 병렬화

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

문제

맵이 쉽게 병렬화 가능한 방법을 이해합니다. 각 컴퓨터/CPU는 배열의 작은 부분에서만 작동 할 수 있습니다.

reting/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의 Combine Phase를 확인하십시오

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

어떤 플랫폼/언어를 생각하고 있는지 확실하지 않지만 이와 같이 운영자를 줄일 수 있습니다.

// 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의 대답.)

기술적으로 감소는 폴드 (왼쪽 왼쪽)와 동일하지 않으며, 이는 또한 축적으로 설명 될 수 있습니다.

Jules가 제공 한 예는 조작 감소를 잘 보여줍니다.

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

이제 분명히 이들은 모두 동일한 결과를 생성하지만, 폴드는 비 연관 연산자 (예 : subtraction)를 제공 할 때 잘 정의 된 결과를 얻지 만 운영자는 감소하지 않습니다.

그것은 당신의 감소 단계에 따라 다릅니다. MapReduce의 Hadoop 스타일 구현에서 Reder는 한 번 호출됩니다. 키 당, 모든 행이 해당 키와 관련이 있습니다.

예를 들어, Mapper는 정렬되지 않은 웹 서버 로그를 많이 가져 와서 메타 데이터 (예 : 지오 코딩)를 추가하고 쿠키 ID를 키로 쿠키 ID를 가진 [키, 레코드] 쌍을 방출합니다. 그런 다음 쿠키 ID 당 한 번 한 번 호출되며 해당 쿠키의 모든 데이터를 공급하고 방문 빈도 또는 방문 당 평균 페이지와 같은 집계 정보를 계산할 수 있습니다. 또는 지오 코드 데이터를 키우고 지리에 따라 집계 통계를 수집 할 수 있습니다.

키 당 골재 분석을 수행하지 않더라도 - 실제로 전체 세트를 통해 무언가를 계산하더라도 계산을 청크로 나누는 것이 가능할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top