3
데이터 분산 모델을위한 병렬 알고리즘을 설계하는 동안 모범 사례를 파악하려고합니다. 블록 분포에 대한 찬성과 반대가 될 수있는 것은 메모리에있는 데이터의 주기적 분포에 대한 것입니다. 어떤 도움을 주시면 감사하겠습니다.병렬 알고리즘 설계
A
답변
1
Quinn의 "MPI 및 OpenMP가있는 C의 병렬 프로그래밍"은 병렬 프로그래밍에서 데이터를 배포하는 여러 가지 방법의 많은 예제를 제공합니다. 사용자의 필요에 따라 어느 방법이 가장 편리한 지 파악하는 데 도움이되는 의사 결정 트리도 있습니다.
1
공유 메모리의 블록 배포는 알고리즘 실행 중에 동기화가 거의 필요없는 청크로 작업을 중단하는 알고리즘에 가장 적합합니다.
병렬 알고리즘 설계에서는 프로세스 간의 동기화 병목 현상을 최소화해야합니다. 예를 들어, 그리드가 스트립 (프로세서 당 1 개)으로 분할되고 동기화가 수행되지 않는 2-D 그리드에 대한 Gauss-Seidel 완화 방법이 있습니다. 각 프로세서는 독립 수렴 값을 계산하고 그 수에 도달하면 종료합니다.
또한 병렬 및 순차 알고리즘에 큰 영향을 미칠 수있는 참조의 데이터 지역을 고려해야합니다.
"공유 메모리에서의 블록 배포는 알고리즘을 실행하는 동안 동기화가 거의 필요없는 청크로 작업을 중단하는 알고리즘에 가장 적합합니다." -이 문장은 필연적 인 것은 아니지만, 필자가 독립적 인 작업 세트를 제공하는 순환 분해를 찾을 수 있기 때문에, 블록에서는이를 수행 할 수 없다. –
@Artem Barger : 정확합니다. 내가 기본 토폴로지, 즉 그리드, 토러스 등을 언급 했어야했다. –
Gauss-Seidel은 병렬 적으로 "수행"하는 병적으로 나쁜 알고리즘이다. 당신이 제안하고있는 것은 각각의 스트립 내에 Gauss-Seidel과 함께 라인 - 자코비 (Line-Jacobi)입니다. 알고리즘은 매우 가파르게 수렴합니다 (이미 가끔 끔찍한 적절한 Gauss-Seidel과 비교할 때). – Jed