Thread Coarsening과 Control Divergence

tiling을 적용해도 kernel이 항상 빨라지는 것은 아니다. shared memory를 너무 자주 읽거나, warp 안 thread들이 서로 다른 분기를 타면 GPU가 기다리는 시간이 늘어난다.

Thread coarsening

thread coarsening은 thread 하나가 output 하나만 계산하지 않고, 여러 output을 맡게 하는 기법이다.

before:
thread 0 -> C[0]
thread 1 -> C[1]
thread 2 -> C[2]

after:
thread 0 -> C[0], C[1]
thread 1 -> C[2], C[3]

왜 도움이 될 수 있을까?

tiling된 matmul에서는 여러 thread가 shared memory에서 값을 반복해서 읽는다. 그런데 shared memory 접근 자체도 공짜는 아니다. 너무 많은 shared memory instruction이 생기면 warp가 MIO pipeline을 기다리며 stall될 수 있다.

thread 하나가 여러 output을 계산하면, 한 번 가져온 값을 더 많이 재사용할 수 있다.

fewer threads
fewer shared memory accesses
more work per thread

하지만 trade-off가 있다.

좋은 점:
shared memory pressure 감소
instruction overhead 감소 가능

나쁜 점:
thread당 register 사용량 증가
parallelism 감소 가능
occupancy 감소 가능

그래서 thread coarsening은 항상 정답이 아니라 profile 결과를 보고 적용하는 최적화다.

Control divergence

NVIDIA GPU는 warp 단위로 thread를 실행한다.

1 warp = 32 threads

warp 안 thread들은 같은 instruction을 동시에 실행하는 것이 가장 효율적이다.

문제는 같은 warp 안에서 thread마다 다른 branch를 타는 경우다.

if (x < 0) {
    y = exp(x) - 1;
} else {
    y = x;
}

만약 warp 안 일부 thread는 if로 가고, 다른 thread는 else로 가면 GPU는 둘을 진짜 동시에 실행하지 못한다. 한쪽 path를 실행하는 동안 다른 쪽 thread들은 쉬고, 그 다음 반대 path를 실행한다.

warp path split
-> execute branch A with branch B lanes inactive
-> execute branch B with branch A lanes inactive
-> effective parallelism drops

이것이 control divergence다.

어떻게 줄이나

목표는 같은 warp 안 thread들이 가능한 한 같은 실행 path를 타게 만드는 것이다.

branch를 줄인다
데이터 배치를 바꿔 비슷한 조건의 원소가 같은 warp에 오게 한다
짧은 조건문은 predication이나 select 형태로 바꾼다
boundary check가 warp 대부분에 영향을 주지 않게 block/grid를 설계한다

예를 들어 elementwise op에서는 if/else 대신 mask/select 형태가 유리할 수 있다.

y = condition ? a : b;

컴파일러가 이를 predicated instruction으로 바꾸면 branch serialization을 줄일 수 있다.

확인

thread coarsening은 왜 shared memory pressure를 줄일 수 있는가?
thread 하나가 너무 많은 일을 맡으면 어떤 문제가 생길 수 있는가?
control divergence는 thread별 분기가 아니라 어떤 단위에서 문제가 되는가?
warp 안 thread들이 서로 다른 branch를 타면 왜 직렬화되는가?

Thread Coarsening과 Control Divergence