데이터 수준 병렬성

데이터 수준 병렬성(DLP)은 같은 연산을 많은 데이터 원소에 반복 적용할 때 나타납니다. 이미지의 모든 픽셀에 필터를 씌우거나, 행렬 원소들을 곱하고 더하거나, 배열 전체에 같은 수식을 적용하는 일이 그렇습니다. 명령어 하나하나는 단순하지만 데이터가 산처럼 많습니다. 이럴 때는 똑똑한 한 명보다 같은 동작을 맞춰 하는 많은 실행 유닛이 이깁니다.

DLP가 잘 보이는 코드

DLP는 “서로 다른 원소가 서로를 거의 기다리지 않는 반복문”에서 잘 보입니다. 아래 루프에서 i번째 계산은 i+1번째 계산과 대체로 독립입니다. 이런 코드는 한 번에 여러 원소를 처리하기 좋습니다.

for (int i = 0; i < n; i++) {
  y[i] = a * x[i] + y[i];
}

반대로 앞 원소의 결과가 다음 원소에 필요한 누적 합 같은 코드는 조심해야 합니다. 병렬화가 불가능한 것은 아니지만, 연산 순서를 다시 설계해야 하고 동기화나 단계적 축약이 끼어듭니다. DLP의 첫 질문은 늘 단순합니다. 각 데이터 원소가 독립적으로 움직일 수 있는가?

벡터 아키텍처

벡터 아키텍처는 긴 데이터 묶음을 한 명령어로 처리합니다. 스칼라 명령어가 “값 하나 더해”라면, 벡터 명령어는 “이 배열 조각 전체를 더해”에 가깝습니다. 벡터 레지스터는 여러 원소를 담고, 벡터 길이 레지스터는 이번에 몇 원소를 처리할지 알려줍니다.

LV    V1, R1      // x 벡터 로드
LV    V2, R2      // y 벡터 로드
MULVS V3, V1, F0  // V3 = a * V1
ADDV  V4, V3, V2  // V4 = V3 + V2
SV    R2, V4      // y 벡터 저장

벡터 방식의 장점은 명령어 인출과 해독 부담을 크게 줄인다는 점입니다. 명령어 하나가 많은 원소의 작업을 대표하므로 프런트엔드가 바쁘게 뛰지 않아도 됩니다. 또 메모리 접근 패턴이 규칙적이면 하드웨어가 미리 길을 닦기 좋습니다.

SIMD 확장

SIMD는 하나의 명령어가 여러 데이터 lane에 동시에 적용되는 방식입니다. 범용 CPU의 AVX, NEON 같은 확장이 여기에 속합니다. 벡터 아키텍처가 길이 가변적인 큰 벡터 기계를 떠올리게 한다면, SIMD는 고정 폭 레지스터 안에 여러 값을 포장해 한 번에 처리하는 느낌에 가깝습니다.

256-bit SIMD register
float 8개  = [f0 f1 f2 f3 f4 f5 f6 f7]
double 4개 = [d0 d1 d2 d3]

SIMD의 성능은 데이터 정렬, 메모리 연속성, 컴파일러 자동 벡터화에 크게 좌우됩니다. 루프에 포인터 alias가 있거나 조건문이 복잡하면 컴파일러가 “이거 정말 안전한가요?” 하며 물러날 수 있습니다. 그래서 고성능 코드에서는 데이터 배치와 루프 모양이 알고리즘만큼 중요해집니다.

GPU 실행 모델

GPU는 DLP를 아주 노골적으로 밀어붙인 장치입니다. 많은 스레드를 만들고, 비슷한 명령 흐름을 가진 스레드 묶음을 함께 실행합니다. CUDA식 용어로 보면 스레드는 블록으로 묶이고, 블록은 그리드를 이룹니다. 하드웨어는 그 안에서 워프 또는 웨이브프런트 같은 작은 묶음을 실제 실행 단위로 다룹니다.

GPU는 메모리 지연을 줄이기보다 숨기는 쪽에 가깝습니다. 어떤 워프가 메모리를 기다리면 다른 준비된 워프를 실행합니다. 그래서 충분한 스레드가 있어야 GPU가 배부르게 일합니다. 작업량이 작거나 분기가 복잡하면 거대한 병렬 장치가 어색하게 서성일 수 있습니다.

워프와 분기 발산

워프는 여러 스레드가 같은 명령어를 함께 실행하는 묶음입니다. 이상적으로는 워프 안의 스레드들이 모두 같은 길을 갑니다. 그런데 조건문에서 일부 스레드는 if 쪽으로, 일부는 else 쪽으로 가면 분기 발산(branch divergence)이 생깁니다. GPU는 두 경로를 차례로 실행하고, 해당 경로에 속하지 않는 스레드는 마스크로 꺼 둡니다.

if (x[tid] > 0) {
  y[tid] = sqrt(x[tid]);
} else {
  y[tid] = 0;
}

위 코드는 간단하지만, 한 워프 안에서 양수와 음수가 섞이면 실행 효율이 떨어집니다. 모든 스레드가 같은 쪽으로 가면 한 번에 끝날 일을, 갈라진 경로만큼 나눠 처리해야 하기 때문입니다. 그래서 GPU 코드는 계산량뿐 아니라 스레드들이 비슷한 제어 흐름을 갖도록 데이터와 작업을 배치하는 일도 중요합니다.

Coalescing과 메모리 접근

GPU에서 전역 메모리 접근은 비쌉니다. 다행히 워프 안의 스레드들이 연속된 주소를 읽거나 쓰면 하드웨어가 접근을 묶어서 처리할 수 있습니다. 이것을 coalescing이라고 부릅니다. 반대로 스레드마다 멀리 떨어진 주소를 건드리면 메모리 트랜잭션이 늘고 대역폭이 낭비됩니다.

공유 메모리나 캐시를 이용해 데이터를 재사용하면 전역 메모리 왕복을 줄일 수 있습니다. 행렬 곱에서 타일링을 쓰는 이유도 여기에 있습니다. 작은 블록을 빠른 메모리에 올려 여러 번 재사용하면, 같은 바이트로 더 많은 연산을 할 수 있습니다.

산술 강도

산술 강도(arithmetic intensity)는 메모리에서 가져온 바이트당 얼마나 많은 연산을 하는지 나타냅니다. 값이 낮으면 메모리 대역폭에 묶이고, 값이 높으면 연산 유닛 성능에 가까워질 수 있습니다.

Arithmetic intensity = operations / bytes transferred

예를 들어 단순 벡터 덧셈은 원소 두 개를 읽고 하나를 쓰면서 연산은 덧셈 하나뿐입니다. 바이트는 많이 오가는데 계산은 적습니다. 반면 타일링된 행렬 곱은 한 번 가져온 값을 여러 곱셈과 덧셈에 재사용할 수 있어 산술 강도를 높이기 좋습니다.

루프라인 모델

루프라인(roofline) 모델은 성능의 천장을 두 개로 봅니다. 하나는 계산 피크, 다른 하나는 메모리 대역폭이 허용하는 성능입니다. 산술 강도가 낮을 때는 대역폭 선이 천장이고, 산술 강도가 충분히 높아지면 계산 피크가 천장이 됩니다.

Attainable performance =
  min(peak compute performance,
      memory bandwidth × arithmetic intensity)

이 모델의 힘은 단순함입니다. 최적화가 필요한 코드가 메모리 바운드인지 계산 바운드인지 빠르게 가늠할 수 있습니다. 메모리 바운드라면 coalescing, 타일링, 데이터 재사용, 압축된 표현을 봐야 합니다. 계산 바운드라면 더 나은 명령 선택, 벡터화, 점유율, 파이프라인 활용을 봐야 합니다. 지붕을 보고 사다리를 고르는 셈입니다.