분기 발산, CUDA 및 키네틱 몬테카를로

Question

그래서 시뮬레이션을 위해 격자에 키네틱 몬테 카를로 (Kinetic Monte Carlo)를 사용하는 코드가 있습니다. 나는 내 GPU에서이 코드를 실행하기 위해 CUDA를 사용하고있다. (같은 질문이 OpenCl에도 적용된다고 생각하지만).

이것은 내 격자를 작은 하위 격자로 나눕니다. 각 스레드는 그 중 하나에서 작동합니다.

While(condition == true){ 
    *Grab a sample u from U[0,1]* 
     for(i = 0; i < 100;i++){ 
     *Do some stuff here to generate A* 
      if(A > u){ 
       *Do more stuff here, which could include updates to global memory* 
       break(); 
      } 
     } 
    } 

A가 다른 스레드에 대한 다른 그래서 U를하고 (100)는 임의의 숫자입니다 : 내가 KMC를하고있는 중이 야하기 때문에, 각 스레드는이 코드를 가지고있다. 코드에서이 값은 1000 또는 10000 일 수 있습니다.

그래서 스레드가 통과 할 때 분기가 발생하지 않습니까? 이것이 성능에 얼마나 나쁜 영향을 줄 수 있습니까? 대답은 if 절 안에있는 코드에 따라 다르지만 더 많은 스레드를 추가 할 때이 배율은 어떻게 될까요?

성능 손실/손실을 예측할 수있는 방법에 대한 언급도 환영합니다.

감사합니다.

Answer 1

GPU는 스레드를 워프 (warps)라고하는 32 개의 스레드 그룹으로 실행합니다. 발산은 워프 내에서만 발생할 수 있습니다. 따라서 if 조건이 전체 워프에서 동일한 방식으로 평가되는 방식으로 스레드를 정렬 할 수 있다면 차이가 없습니다.

개념적으로 if에 분기가있는 경우 GPU는 if 조건이 거짓 인 스레드의 결과 및 메모리 요청을 무시합니다.

따라서 if은 특정 경사에서 10 개의 스레드에 대해 true으로 평가됩니다. 그 if 안에있는 동안, if에 의해 사용 불능으로 된 22 개의 스레드가 작업을 수행 할 수 있었으므로 이제는 워프의 잠재적 인 컴퓨팅 성능이 100 %에서 10/32 * 100 = 31 %로 감소하지만 지금은 워프.

일단 if을 종료하면 비활성화 된 스레드가 다시 활성화되고 워프는 100 % 잠재적 인 컴퓨팅 성능으로 진행됩니다.

if-else은 거의 동일한 방식으로 작동합니다. 뒤틀림이 else이되면 if에서 활성화 된 스레드는 비활성화되고 비활성화 된 스레드는 활성화됩니다.

워프의 각 스레드에 대해 다른 횟수의 루프를 반복하는 루프에서 반복 횟수가 설정된 횟수에 도달하면 스레드가 비활성화되지만 전체적으로 워프는 반복 횟수가 가장 많은 스레드 카운트가 완료되었습니다.

잠재적 인 메모리 처리량을 살펴볼 때 상황은 좀 더 복잡합니다. 알고리즘이 메모리 바운드이면, 메모리 트랜잭션의 수가 감소 될 수 있기 때문에 워프 발산으로 인해 성능 손실이나 성능이 저하되지 않을 수 있습니다. 워프의 각 스레드가 전역 메모리에서 완전히 다른 위치에서 읽는 경우 (GPU의 상황이 좋지 않은 경우), 메모리 트랜잭션을 수행 할 필요가 없으므로 비활성화 된 각 스레드에 대해 시간이 절약됩니다. 반면에 스레드가 GPU가 액세스하도록 최적화 된 배열에서 스레드를 읽는 경우 여러 스레드가 단일 트랜잭션의 결과를 공유하게됩니다. 이 경우 비활성화 된 스레드에 대한 값은 메모리에서 읽은 다음 비활성화 된 스레드에서 수행 할 수있는 계산과 함께 폐기됩니다.

이제 워프 차이가 얼마나 성능에 영향을 미치는지에 관해 판단 할 수있는 충분한 개요가있을 것입니다. 최악의 경우는 워프에있는 단일 스레드 만 활성화 된 경우입니다. 그러면 컴퓨팅 성능에 잠재적 인 1/32 = 3.125 %가됩니다. 가장 좋은 경우는 31/32 = 96.875 %입니다. 완전 무작위 인 if의 경우 50 %를 얻습니다. 그리고 위에서 언급 한 것처럼 메모리 바운드 성능은 필요한 메모리 트랜잭션 수의 변경에 따라 달라집니다.