cuda병렬 감소 (예 : 배열을 합하는 방법)


비고

병렬 축소 알고리즘은 일반적으로 요소 배열을 결합하여 단일 결과를 생성하는 알고리즘을 나타냅니다. 이 범주에 속하는 일반적인 문제는 다음과 같습니다.

  • 배열의 모든 요소 합계
  • 배열에서 최대 값을 찾는 것

일반적으로 병렬 감소는 모든 이진 연상 연산자 , 즉 (A*B)*C = A*(B*C) 적용될 수 있습니다. 이러한 연산자 *를 사용하면 병렬 감소 알고리즘이 반복적으로 배열 인수를 쌍으로 그룹화합니다. 각 쌍은 다른 단계와 병렬로 계산되어 한 단계로 전체 배열 크기를 절반으로 줄입니다. 이 과정은 하나의 요소가 존재할 때까지 반복됩니다.

연산자가 연관성 외에도 교환 가능 하다면 (즉, A*B = B*A ) 알고리즘은 다른 패턴으로 쌍을 이룰 수 있습니다. 이론적으로 볼 때 아무런 차이가 없지만 실제로는 더 나은 메모리 액세스 패턴을 제공합니다.

모든 연관 연산자가 교환 가능하지는 않습니다. 예를 들어 행렬 곱셈을 취하십시오.

병렬 감소 (예 : 배열을 합하는 방법) 관련 예