CUDA : 서브 행렬에서 극한치 인덱스를 찾는 방법은 무엇입니까?

Question

GPU 메모리에 NxM의 큰 직사각형 행렬이 있고 행 단위로 1 차원 배열로 저장됩니다. 이 행렬은 실제로 크기 nxm의 부분 행렬로 구성되어 있다고 가정 해 보겠습니다. 간단히하기 위해, N은 n의 배수이고 M과 m과 같다고 가정합니다. 배열의 데이터 유형은 float 또는 double입니다.

각 부분 행렬에서 극한치의 색인을 찾는 효율적인 방법은 무엇입니까? 예를 들어, 각 서브 매트릭스의 최대 요소의 1 차원 인덱스를 찾고 그 인덱스를 일부 배열에 기록하는 방법을 예로들 수 있습니다.

Answer 1

나는 거의 그렇게 자신감 로 상상할 수있는 (또는 오만?) 하나 개의 특정 솔루션이 무엇인가를 할 수있는 "가장 효율적인 방법"이라고 말할 수 있습니다.

그러나, 몇 가지 생각 (주장하지 않고는 "가장 효율적인"솔루션을 포함합니다) :

을 나는 모든 하위를 들어이

• 에 접근이 "직교"방법이 기본적으로 생각 병렬 행렬은 모든 서브 행렬들에 순차적 극한치 순차적
• 찾기 : 찾기 어느 평행

문제의 극한치를 아마 매트릭스의 크기에 따라 더 적절합니다. "N은 n의 배수" (M 및 m과 유사)이라고 말씀하셨습니다. 크기 의 행렬을 a*b 크기의 서브 행렬 m x n으로 구성 해 봅시다.

첫 번째 방법의 경우, 하나는 단순히 각 스레드가

for (all elements of my sub-matrix) max = element > max ? element : max; 

여기에 전제 조건이 a*b는 "합리적으로 큰"이라고처럼 사소한 루프, 하나의 서브 매트릭스 알아서 할 수있다. 즉,이 커널을 10000 개의 하위 행렬에 대해 실행할 수있게되면, 이는 이미 좋은 속도 향상을 가져올 수 있습니다.

이와 대조적으로, 두 번째 방법에서 각 커널 (모든 스레드와 함께)은 하나의 부분 행렬을 처리합니다. 이 경우 커널은 표준 "감소"커널이 될 수 있습니다. (축소는 종종 "배열 요소의 합/곱을 계산"에 대한 예제로 제시되지만 모든 이진 연관 연산에서 작동하므로 합이나 곱을 계산하는 대신 기본적으로 컴퓨팅에 동일한 커널을 사용할 수 있습니다 최소 또는 최대). 그래서 커널은 각 부분 행렬에 대해 시작될 것이며, 부분 행렬이 "합리적으로 커"경우에만 의미가 있습니다.

그러나 모두 경우에는 일반 성능 지침을 고려해야합니다. 특히,이 경우 작업은 분명히 메모리 바인딩 (및 계산 대상이 아닌)이므로 전역 메모리 (즉, 행렬 자체)에 대한 액세스가 병합되었는지, 커널에 의해 생성되는 것은 가능한 한 높습니다.

EDIT : 물론이 접근법을 어떻게 든 결합 할 수는 있지만 적어도 사용 가능한 옵션 공간의 가장 중요한 방향을 보여주고 있다고 생각합니다.