CUDA 알고리즘 계단식

Question

CUDA에서 C 프로그램을 최적화하는 맥락에서 this slide을 읽었으며 계단식 알고리즘에 대해 이야기합니다. 나는 그것이 무엇인지 이해하지 못한다. 심지어 총알 점을 읽은 후에도. 누구 알고리즘 계단식 CUDA 알고 무엇입니까? 다른 자원에 대한 예 또는 링크가 도움이 될 것입니다.

Answer 1

여러 알고리즘 (방법론)을 사용하여 모든 요소를 ​​합산하는 아이디어를 나타냅니다.

첫 번째 알고리즘은 여러 스레드에서 수행되는 병렬 순차 합계입니다. 각 스레드는 합계 될 전체 배열의 요소 서브 세트의 부분 합계를 누적합니다. 이 알고리즘은 본질적으로 순차적이며 스레드 코드의 관점에서 볼 때 개념적으로 for-loop 또는 while-loop와 같습니다. 각 스레드는 개별적으로 작동하며 스레드 간에는 명시 적 협력이 없습니다. 이 알고리즘 (병렬 순차 합계)은 슬라이드 33에서 다룹니다.

첫 번째 알고리즘은 결과 (여러 스레드에 걸쳐 누적 된 부분 합계)를 부분 합계 그룹을 함께 누적하는 두 번째 알고리즘으로 캐스케이드하여 상대적으로 작은 수를 생성합니다. 부분 합계. 이 알고리즘은 스레드 블록 내에서 작동하여 각 스레드의 부분 합계를 슬라이드 5 (녹색 막대)에 그림으로 표시된 병렬 정리 축소 방식 (고전적 병렬 축소)으로 누적합니다. 슬라이드 5의 녹색 막대 맨 위에있는 각 요소는 이전 (순차적) 단계에서 누적 된 한 스레드의 부분 합계를 나타냅니다.

개념적으로 위에서 설명한 두 번째 알고리즘과 유사한 최종 수준의 축소 (슬라이드 5의 파란색 막대)를 사용할 수도 있습니다. 이전 단계의 부분 결과가이 단계에 계단식으로 연결되어 부분 결과의 최종 합계를 수행하여 단일 최종 결과를 생성합니다.

이 연쇄 과정을 사용하면 첫 번째 알고리즘과 두 번째 알고리즘은 그림과 코드의 수준에서 매우 다르게 보이지만 함께 결합하면 임의의 크기의 배열과 임의 크기의 격자 (배열 스레드).