MPI_Allgather가 코드 병목 현상입니까? 어떻게 수정합니까?

Question

하나의 메인 어레이에 특정 데이터를 추가하는 것을 목적으로하는 프로그램이 있습니다. 난수 테스트 passesTest(randomNumber)은 매초마다 수백만 번 수행되며, 때로는 테스트가 통과되고 난수가 배열의 끝으로 푸시됩니다. 그래서 대부분의 경우 계산은 계속 진행되는 동안 배열이 그곳에 그냥 앉아 있습니다.

나는 무작위 수 테스트를 수행하는 1000 개의 프로세서가 큰 속도 향상이 될 것이라고 생각했기 때문에이 절차를 MPI와 병렬 처리하기로 결정했으며 메모리 쓰기가 매우 드물기 때문에 MPI가 작업에 적합해야합니다. 많은 당황 스럽지만, 내 프로그램은 mpirun -np 1으로 가장 빠르며 내가 추가 한 각 프로세스에서 상당히 느려집니다. passesTest(randomNumber)이 포함되어 내 while 루프의 끝에서

, 나는 배열에 밀어 필요가 새로운 임의의 숫자가 있는지 여부를 나타내는 각 프로세스에서 플래그를 수집 MPI::COMM_WORLD.Allgather() 있습니다. 플래그가 true 인 경우 Allgather()을 실제로 수행하여이 데이터를 각 프로세스의 로컬 사본에 푸시합니다. 테스트가 거의 통과되지 않기 때문에이 두 번째 Allgather()도 매우 드물게 수행됩니다.

그래서 나는 병목 현상이 각 MPI 프로세스의 모든 플래그를 수집하여 새로운 데이터가 있는지 확인하고 있습니다. 각 난수의 테스트가 빨리 수행되므로 여러 프로세스에서 데이터를 수집하는 오버 헤드로 인해 초당 수십억 개의 while 루프가 현저히 줄어들 었다고 가정합니다. 이것은 좋은 추측입니까? 저는 MPI를 처음 사용하기 때문에 Allgather()과 어떤 종류의 시간대가 연관되어 있는지 알지 못합니다.

이것이 이유 인 경우 테스트 통과시 다른 프로세스와 어떻게 "상호 작용"할 수 있습니까? 이것은 내가 정말로하고 싶은 모든 것입니다. 즉, 임의의 숫자가 테스트를 통과하면 다른 모든 프로세스에 메시지를 보내 자신이 수행중인 작업을 중단하고 그 번호를 배열에 추가합니다.

Answer 1

처음에는 Voo 's와 Hristo Iliev의 의견을 강력히 뒤졌습니다.

패스를 확인하기 위해 MPI_Allreduce으로 시작하는 것이 분명히 빠릅니다. 훨씬 적은 양의 데이터를 전송해야합니다. 그러나 Allreduce는 여전히>2 * log2(n) * latency이 필요합니다. 1000 프로세스의 경우 시스템에 따라 100 초 정도 걸릴 수 있습니다. 초당 수백만 건의 테스트가 수행된다면 각 테스트마다 100 초의 나노 초 밖에 걸리지 않으므로 개별적인 통신 단계가 어떻게 설계되어 있더라도 상관없이 각 테스트 이후의 공동 작업으로 인해 실적이 저하 될 수 있습니다.

종속성에 대해 알지 못하면 근본적인 개선을 제안하기가 어렵습니다. 당신은 히트작이 없다고 판단한 후에 무효 한 것을 버리고, 히트가 없다고 가정하고 반복적으로 여러번 실행하는 것에 대해 생각할 수 있습니다.

이상 추가 할 필요가있는 가장 높은 난수를 결정하기 위해 MPI_Allreduce을 MAX으로 제안합니다. 모든 것이 추가 될 때까지 반복하십시오. 일반적으로 추가가 거의없는 경우에만 분명히 잘 작동합니다.