"Mapreduce"에서 "감소"를 병렬화
-
11-07-2019 - |
문제
맵이 쉽게 병렬화 가능한 방법을 이해합니다. 각 컴퓨터/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를 확인하십시오
어떤 플랫폼/언어를 생각하고 있는지 확실하지 않지만 이와 같이 운영자를 줄일 수 있습니다.
// 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 당 한 번 한 번 호출되며 해당 쿠키의 모든 데이터를 공급하고 방문 빈도 또는 방문 당 평균 페이지와 같은 집계 정보를 계산할 수 있습니다. 또는 지오 코드 데이터를 키우고 지리에 따라 집계 통계를 수집 할 수 있습니다.
키 당 골재 분석을 수행하지 않더라도 - 실제로 전체 세트를 통해 무언가를 계산하더라도 계산을 청크로 나누는 것이 가능할 수 있습니다.