2 개의 정수를 병렬로 추가

Question

2 개의 배열 a, b에 2 개의 부호없는 정수 n 개의 숫자가 있다고 가정하고, 각각 두 자리를 더할 수 있고 carry가있는 경우 p 개의 프로세서가 있다고 가정합니다. O + (p + n/p) 시간에 a + b를 계산할 수 있습니까? 나는 (n/p) p 인터벌로 입력을 나눠 봤지만 캐리를 처리하는 방법을 모른다.

Answer 1

나는 그것이 가능하다고 믿습니다. 나는 n >= p이라고 가정하고 p 프로세서는 메시지 전달을 통해 프로세서가 통신하는 비공유 아키텍처에 배치됩니다.

자릿수가 p 프로세서간에 아직 분배되지 않았지만 계산에 참여하지 않는 하나의 마스터 프로세서에서 수집 된 경우 a와 b를 분리하여 p 개의 인접한 연속 된 블록 블록을 작성한 다음 보내십시오. 각 프로세서. 메시지의 복잡성은 O(p)입니다.

그런 다음 각 프로세서는 숫자의 블록에 대해 두 개의 합계를 계산합니다. 즉, 이전 프로세서에서 캐리 1을 수신한다는 가정하에 하나의 합계를 계산합니다. 즉, 다음 유효 숫자 자릿수 블록을 가진 프로세서와 캐리 0이 될 것입니다. 또한 두 시나리오 각각에 대해 송신 캐리를 계산합니다. 각 프로세서는 정수의 정수를 보유해야하므로 연산은 시간 복잡성 O(ceil(n/p))입니다.

물론 최하위 숫자 블록이있는 프로세서는 합계를 하나만 계산하면됩니다. 계산이 완료 되 자마자 결과 자리수의 몫을 마스터로 보내고 다음 자리의 더 큰 자릿수를 보유한 프로세서로 전송을 보냅니다. 다음 프로세서는 두 결과 시나리오 중 어느 것이 참이되었는지를 결정하고, 적절한 결과 디지트를 마스터로 보내고, 그 결과를 다음 프로세서로 전송합니다. 등등.

결과에 대한 추가 p 메시지와 반송에 대한 p-1 메시지가 필요합니다. 따라서 메시지의 복잡도는 여전히 O(p)입니다. 시간 복잡도는 O(p + ceil(n/p))이 될 것이며, 마지막 프로세서는 전임자 중 p-2이 두 결과 중 어느 것을 전달할지 결정할 때까지 기다려야하기 때문입니다. n 자리가 p 프로세서에 균등하게 분배 될 수 있다고 가정하면 (n은 p의 배수 임) 제안 된 시간 복잡도 인 O(p + n/p)을 사용해도됩니다.

이 두 가지 가능한 결과를 추론하는 방법은 Carry-select adder의 작동 방식과 매우 유사합니다.