[GPGPU Series 8] Branch Divergence

GPU는 Thread를 32 또는 64개씩 묶어서 하나의 같은 Instruction을 수행한다. Branch Divergence는 Warp에 속한 Thread가 서로 다른 연산을 수행해야 하는 경우 발생한다. 예를 들어 Warp에 속한 짝수 ID를 가진 Thread는 IF 문에 해당하는 코드를 실행해야 하고, 홀수 ID를 가진 Thread는 ELSE에 해당하는 코드를 실행해야 하는 경우 Branch Divergence가 발생한다. 아래 코드는 Thread ID의 홀수 짝수 여부를 확인하여 서로 다른 코드를 실행하는 예제이다 (실제 실행 여부를 확인하지 않았습니다).

__global__ void mkTest(){
	int threadID = threadIdx.x
	if((threadIdx.x % 2) == 0){
		짝수 Thread 코드 ...
	}
	else{
		홀수 Thread 코드 ...
	}
}

그림 1은 Branch Divergence가 발생하면 Warp가 실행되는 순서를 표시한 그림이다. 간단히 설명하면 Warp는 IF에 해당하는 코드와 ELSE에 해당하는 코드를 순차적으로 수행한다. IF에 해당하는 코드 연산을 수행할 때는 IF 연산이 필요 없는 Thread를 연산에서 제외한다. 반대로 ELSE에 해당하는 연산을 수행할 때는 ELSE 연산이 필요 없는 Thread를 연산에서 제외한다. 연산에서 제외하는 정확한 방법은 모른다. 연산을 완전히 수행하지 않는 방법도 있을 수 있고 반대로 연산을 수행하나 Register에 결과 값을 쓰지 않는 방법도 있다. 효율적인 방법은 연산 자체를 수행하지 않는 것이다.

그림 1: Branch Divergence가 발생하면 Warp가 실행되는 순서

결과적으로 Branch Divergence가 발생하면 GPU는 IF/ELSE에 해당하는 코드를 순차적으로 수행한다. Warp의 모든 Thread가 동시에 연산을 수행하지 않기 때문에 GPU의 Utilization이 하락한다. 그렇기 때문에 GPU 프로그래밍을 할때는 Branch Divergence를 최소화하는 것이 좋다. 특히 Thread ID/Block ID/Grid ID 등으로 IF/ELSE를 나누는 경우 한 ~ 두개의 다른 연산을 추가하여 Branch Divergence를 제거하는 것이 좋다. GPGPU 초창기(2010년 정도)에는 Branch Divergence를 HW단에서 제거하는 연구를 많이 진행하였다. 예를 들어 Branch Divergence가 발생하면 Warp의 Thread를 다른 Warp의 Thread과 변경하는 것이다. 대학원에서 논문을 읽을 때는 정말 멋진 아이디어라고 생각했다. 하지만, 지금 생각해보면 성능적으로 큰 이득이 없을 것 같다. 가장 큰 이유는 Register 값을 읽는 속도가 급격히 느려지기 때문에 아마 실제 성능은 논문에서 말하는 것보다 현저히 좋지 않았을 것 같다. 이와 더불어 Branch Divergence 문제를 Compile 단에서 해결하는 연구도 많이 발표되었다. 많은 논문이 나왔다는 이야기는 그만큼 Branch Divergence가 GPU에 성능에 큰 영향을 준다는 의미이기도 하다.

GPGPU-Sim에 따르면 SIMT Stack이란 하드웨어 로직을 사용하여 Branch Divergence를 Handling 한다 (출처 1). 각 Warp는 SIMT Stack이란 저장 공간을 가지고 있다. SIMT Stack은 여러 개의 Entry로 구성되어 있다. 논문에 따르면 SIMT Stack은 4개의 Entry로 구성되어 있다고 한다 (출처2). 각 Entry는 PC (Program Counter) + 32Bit 저장 공간으로 구성되어 있다. 만약 PC가 64 Bit인 경우 각 Entry는 92 Bit로 구성되어 있다. PC 뒤에 있는 32 Bit는 Warp에 속해 있는 Thread가 PC에 해당하는 Instruction을 실행할지 아니면 실행을 하면 안되는지를 True/False 값을 저장하기 위해 사용한다. NVIDIA GPU의 경우 Warp가 32개의 Thread로 구성되기 때문에 32 Bit를 사용하여 Thread의 Instruction 실행 여부를 체크한다. 하지만, 만약 Warp가 64개의 Thread로 구성되어 있으면 64 Bit를 사용해서 Thread Instruction 실행 여부를 체크해야 한다.

그림 2: SIMT Stack 동작 순서

동작 원리를 어떻게 설명해야 할지 고민을 했는데 예제를 사용하여 설명하는 것이 가장 효율적인 것 같다. 그림 2는 Branch Divergence가 발생하는 경우 SIMT Stack을 사용하여 Instruction을 실행하는 방법을 보여준다. 편의를 위해서 Warp는 8개의 Thread로 구성되어 있다고 가정하였다. 앞 예제 코드와 같이 짝수 ID를 가진 Thread는 IF 문을 홀수 ID를 가진 Thread는 ELSE 문을 실행한다고 가정하였다.

  • Step 1: IF/ELSE 이전에는 SIMT Stack은 하나의 Entry를 가지고 있다. 해당 Entry에 PC 값 + 11111111 값이 저장되어 있다. PC 값은 Warp가 실행해야 하는 다음 Instruction 위치 값을 저장한 것이다. 그 뒤에 저장된 “11111111”은 현재 속해 있는 모든 Thread가 해당 PC 값에 해당하는 Instruction 연산을 수행해야 한다는 의미이다.
  • Step 2: IF/ELSE 구문을 만나게 되면 총 3개의 Entry가 생성한다. 제일위에 IF문에 해당하는 IF Instruction PC 값 + “10101010” 값을 저장하여 짝수 Thread가 연산이 필요하다는 것을 표시한다 (0 부터 시작하기 때문에 제일 처음 Thread가 1로 표시되어 있다). 다음 Entry는 ELSE문 Instruction에 해당하는 PC 값 + “01010101” 값 저장한다. 마지막으로 IF/ELSE에 해당하는 Instruction 연산이 끝나는 PC 값 (RPC) + “111111111”을 저장한다. IF/ELSE문이 끝나서 Warp의 모든 Thread가 다시 같은 Instruction을 실행하기 위해 합쳐지는 것을 “Reconverge”라고 한다.
  • Step 3: Stack이란 이름에서 알 수 있듯이 POP 연산을 사용하여 SIMT Stack에 저장된 Entry값을 사용한다. 먼저 SIMT Stack에서 POP 연산을 수행하면 IF문에 해당하는 Entry가 나온다. IF 문에 해당하는 PC 값과 Warp의 Instruction 연산 필요 여부를 판단하여 연산을 수행한다. “1”로 표시된 Thread는 해당 Instruction 연산을 수행하고, 반대로 “0”으로 표시된 Thread는 해당 Instruction을 수행하지 않는다.
  • Step 4: Step 3 동일하게 다음 Entry에 해당하는 연산을 수행한다. 다음 Entry는 ELSE에 해당하는 Instruction 연산이다.
    • 만약 IF/ELSE에 Instruction의 개수가 1개 이상이면 PC 값을 업데이트하여 실행가능한 Thread 정보를 다시 SIMT Stack에 저장한다. Stack의 경우 Last-In-First-Out (LIFO) 순서를 따르기 때문에 IF연산에 해당하는 Instruction연산을 모두 수행하고 ELSE에 해당하는 Instruction을 순서대로 연산을 수행한다.
  • Step 5: IF/ELSE에 해당하는 Instruction을 모두 수행하면 SIMT Stack에는 Reconverge PC  (RPC) 값을 가진 Entry만 남게 된다. 해당 Entry를 POP 하여 Warp의 모든 Thread는 같은 연산을 수행한다.

위의 설명과 같이 Branch Divergence가 발생하면 SIMT Stack을 사용하여 순차적으로 Instruction 연산을 수행한다. Branch Divergence가 발생하면 Warp에 속한 Thread가 같은 Instruction을 수행하지 못하기 않기 때문에 GPU의 Utilization이 하락한다. 이와 더불어 IF/ELSE등에 해당하는 모든 Instruction을 실행하기 때문에 GPU가 수행해야 하는 Instruction의 개수도 증가한다. 정리하면 프로그래밍을 하는 과정에서 Branch Divergence가 발생하지 않도록 하는 것이 가장 중요하다.

출처

  1. http://www.gpgpu-sim.org/
  2. Stack-less SIMT Reconvergence at Low Cost

3 thoughts on “[GPGPU Series 8] Branch Divergence”

Leave a Reply to Admin Cancel reply