병렬 계산 합계

Question

이것은 인터뷰 질문입니다.

N 개의 노드로 구성된 각 노드는 몇 개의 필드와 메소드로 구성됩니다. 이들은 :

// Every node has an ID. All of these IDs are sequential, and begin with 0. 
// i.e. all ids are uniquely in the range of 0 t N-1 
int id; 
int val; // Every node has a value 
int max; // max = N. Every node knows how many nodes are in the system. 

void send(int idTo, int payload) 
int recv(int idFrom) 

동시에 모든 노드에서 실행되는 코드의 한 조각을, 쓰기 등이이 시스템의 모든 노드가 시스템의 모든 노드의 값의 합을 알고 실행이 완료 될 때.

Answer 1

한 용액 :

모든 노드는이 시스템에서 다음 노드로 수신 된 합을 보낸다. 처음에는 모든 노드가 이전 노드에서 번호를받습니다. 다음 번에는 숫자를받습니다 -> 이전 숫자에서 해당 숫자를 뺀 것이 합계입니다.

시스템에 이전 노드에서 번호를 받고 보내기 다음 이전 노드에서 다른 입력을 기다리는받는 시스템에서 다음 노드로 전송됩니다 여기에 자신의 번호를 추가합니다받을

Answer 2

모든 노드에 값을 브로드 캐스팅하고 다른 모든 노드에서 값을 수신 할 수 있습니다. 그런 식으로 모든 노드가 추가 작업을 수행하고 결과를 알 수 있습니다. 비록 이것이 매우 비효율적 일 수 있다고 생각합니다.

나는 이전 노드의 부분 합계를받는 이전 아이디어에서 더 좋은 아이디어를 좋아하고, 자신의 값을 더하고 다음 노드에 새로운 합계를 전달합니다. 그런 다음 최종 결과를 다른 방향으로 전송해야하므로 모든 노드가 끝에 답을 알고 있습니다.

그러나 모든 노드가 동시 적으로 실행될 수 있다는 사실을 이용하려면 양쪽 끝에서 첫 번째 전달을 시작하고 가운데에서 최종 결과를 가져 와서 두 번째 방향으로 두 번째 탐색을 수행 할 수 있습니다. 이렇게하면 시간의 절반을 절약 할 수 있습니다. 더 좋은 점은, 같은 생각에 따라, 당신은 쌍으로 그 합을 만들 수 있고, 네 번째 노드로, 그리고 나서 네 번째 노드로 부분 결과를 보낼 수 있습니다. 이 전략은 중간에 도달하기 위해 O (lg n) 만 사용합니다.