벡터 모델
벡터 모델(vector model)은 Guy Blelloch가 정리한 데이터 병렬 계산 모델이다. 스칼라 하나가 아니라 벡터 전체를 한 번의 연산으로 다루는 것을 기본 단위로 삼는다.
핵심 주장은 이렇다. 병렬 프로그램을 “프로세서 P개가 서로 통신한다”로 짜면 프로세서 수에 코드가 종속되어 이식성이 없어진다. 대신 “길이 n짜리 벡터에 연산 하나”를 원시 연산으로 두면, 알고리즘은 P와 무관하게 기술되고 P에 맞추는 일은 구현체가 한다.
모델의 기계는 일반 RAM에 벡터 메모리와 벡터 프로세서를 붙인 형태의 V-RAM(vector RAM)이다.
스칼라 메모리 벡터 메모리 [ x ][ y ][ n ] [ 3 1 4 1 5 9 2 6 ] | | 스칼라 프로세서 ----- 벡터 프로세서- 스칼라 메모리: 값 하나씩. 제어 흐름(루프, 분기)은 여기서 돈다.
- 벡터 메모리: 길이가 제각각인 벡터들. 길이에 상한이 없다.
- 벡터 명령 하나 = 벡터 전체에 대한 연산 = 1 스텝.
벡터 길이에 상한이 없다는 게 중요하다. SIMD 레지스터가 128비트든 512비트든, GPU가 워프 32개든, 그건 모델 아래의 구현 문제로 밀어둔다. 그래서 벡터 모델은 SIMD 하드웨어와 같은 말이 아니며, 하드웨어에 얹는 것은 그 다음 단계이다.
벡터 모델의 비용은 크게 두 개로 나눌 수 있다. (Blelloch는 각각 element complexity, step complexity라고 부름)
- work(W): 벡터 명령들이 건드린 원소 수의 총합. 순차로 돌렸을 때의 총 연산량.
- depth(D): 벡터 명령의 개수. 즉 의존성 사슬의 길이. 원소가 무한히 많아도 줄지 않는 시간.
프로세서 P개짜리 실제 기계에서 걸리는 시간은 Brent의 정리로 묶인다.
T(P) ≤ W/P + DP가 커지면 W/P는 줄지만 D는 안 줄어든다. 그러니 알고리즘을 고를 때 봐야 할 건 D이고 동시에 W가 순차 알고리즘의 연산량보다 커지면 안 된다. W가 순차와 같은 차수면 work-efficient하다고 이야기한다.
work-efficient하지 않으면 실제 성능이 오히려 떨어질 수 있다. depth가 O(log n)이어도 work가 O(n log n)이면, P가 작을 때 W/P 항이 순차 알고리즘보다 log n배 크기 때문이다.
벡터 모델에서의 원시 연산은 아래와 같은 것들이 있다.
1. elementwise: 원소별 산술/비교. W=O(n), D=O(1)
A = [3 1 4 1 5]B = [2 7 1 8 2]A + B = [5 8 5 9 7]A > B = [1 0 1 0 1]2. permute: 인덱스 벡터대로 자리 옮기기. W=O(n), D=O(1)
A = [a b c d]index = [2 0 3 1]permute(A, index) = [b d a c] // A[i]가 index[i] 자리로 감3. reduce: 벡터 전체를 값 하나로. W=O(n), D=O(log n)
4. scan(prefix sum): 누적. W=O(n), D=O(log n)
A = [3 1 4 1 5 9 2 6]exclusive +scan = [0 3 4 8 9 14 23 25]5. pack(compaction): 플래그가 켜진 원소만 모으기
A = [a b c d e f]flag = [1 0 1 1 0 0]pack = [a c d]scan이 원시 연산인 이유
Section titled “scan이 원시 연산인 이유”벡터 모델의 가장 중요한 주장이 이 부분이다. scan은 누적 계산이므로 순차로 생각할 수 있지만, 실제론 O(log n) depth로 계산할 수 있으니 하드웨어 원시 연산으로 취급할 수 있게 된다.
계산은 트리를 두 번 훑는 방식이다.
up-sweep (reduce 트리를 만들면서 부분합 저장)
[3 1 4 1 5 9 2 6][ 4 5 14 8 ][ 9 22 ][ 31 ]
down-sweep (루트에 0을 넣고 내려오면서 왼쪽 자식 = 부모, 오른쪽 자식 = 부모 + 왼쪽 부분합)
[ 0 ][ 0 9 ][ 0 4 9 23 ][0 3 4 8 9 14 23 25]각 레벨이 한 스텝이니 D=O(log n), 원소를 건드린 총 횟수는 2n이므로 W=O(n)이다. work-efficient하다.
scan은 결합법칙이 성립하는 연산이면 모두 적용 가능하다. +, max, min, xor, 행렬곱, 심지어 함수 합성도 가능하다. 상태 기계의 전이를 함수로 보고 scan하면, 순차 루프처럼 보이는 것들이 병렬로 풀리는 것이다.
예시로 lexer 구현을 살펴볼 수 있따. lexer에서 “이 위치가 문자열 리터럴 내부인가”를 판별하는 코드는 순차 루프로 짜면 자연스럽다. 하지만 벡터 모델에서는 이렇게 된다.
src = a " b c " d " eis_q = [0 1 0 0 1 0 1 0]xor-scan(is_q, exclusive) = [0 0 1 1 1 0 0 1] ^^^^^^^^ ^^ 문자열 내부따옴표 플래그에 xor prefix scan을 걸면 끝나므로 시간복잡도는 D=O(log n)이다. 이스케이프 문자 처리도 앞단에 마스크를 하나 더 두면 같은 틀에서 해결된다.
segmented scan
Section titled “segmented scan”segmented scan는 벡터 하나를 여러 구간으로 쪼개고 각 구간 안에서만 scan하는 변형이다. 구간 경계를 플래그 벡터로 준다.
A = [3 1 4 | 1 5 | 9 2 6]flag = [1 0 0 1 0 1 0 0]segmented +scan = [0 3 4 | 0 1 | 0 9 11]비용은 평범한 scan과 같다. 이게 있으면 “각 구간마다 따로 처리”가 필요한 알고리즘이 통째로 벡터 모델에 들어온다. 중첩 병렬성(nested parallelism)을 평평한 벡터 연산으로 내리는 flattening의 핵심 도구다. 재귀마다 구간이 쪼개지는 quicksort, 정점마다 인접 리스트 길이가 다른 그래프 알고리즘이 다 여기 해당한다.
벡터 모델은 일렬로 늘어선 것에만 강하다. 트리에는 앞/뒤가 없고 위아래가 있어서 “이 노드는 루트에서 몇 층 아래인가” 같은 질문은 전원에게 동시에 물을 수가 없어 보인다.
여기서 오일러 경로 테크닉(Tarjan & Vishkin, 1985)을 사용해 문제를 해결할 수 있다. 트리를 DFS로 한 바퀴 돌아 방문 순서대로 펴면, 트리 질문 상당수가 펴진 배열 위의 scan으로 바뀐다.
내려갈 때 +1, 올라갈 때 −1을 적으면 깊이는 그냥 prefix sum이고, 서브트리는 진입 시각 ~ 이탈 시각 구간이 된다. 즉 서브트리 합계는 구간 합, 서브트리 갱신은 구간 갱신이다. 이 방식으로 scan하면 벡터 모델로 동일하게 적용할 수 있게 되는 것이다
1 투어 : 1 2 4 4 5 5 2 3 3 1 / \ 방향 : ↓ ↓ ↓ ↑ ↓ ↑ ↑ ↓ ↑ ↑ 2 3 ±1 : +1 +1 +1 -1 +1 -1 -1 +1 -1 -1 / \ +scan : 1 2 3 2 3 2 1 2 1 0 4 5 ^^ ^^ 깊이 3 깊이 3pack의 비용
Section titled “pack의 비용”벡터 모델에서 pack은 scan 한 번(D=O(log n), W=O(n))이지만 실제 하드웨어에서는 명령어 셋에 따라 성능이 크게 달라질 수도 있다.
값 판정 [1 0 1 1 0 0 1 0] ← 이건 진짜로 동시에 됨 ↓명단 만들기 [a c d g] ← 각자 어디로 갈지가 앞의 개수에 달림x86에는 이걸 명령 하나로 하는 VPCOMPRESS(AVX-512)가 있지만 ARM NEON에는 대응 명령이 없다. (SVE의 COMPACT는 32/64비트 원소만 지원해서 바이트 단위 렉싱에는 그대로 못 쓴다.) 그래서 ARM에서는 판정은 순식간인데 추려내는 단계가 전체 시간의 대부분을 먹는 일이 생긴다. 앞단을 10배 빠르게 만들어도 여기서 다 까먹는다.
우회법은 simdjson의 구현이 사용하는 것처럼 8개씩 끊어 LUT 조회하는 것이다. 8비트 마스크는 경우의 수가 256개뿐이니, 각 마스크에 대응하는 셔플 패턴 8바이트를 미리 표로 만들어두고 찾아 사용한다. 표가 2KB라 L1에 상주하고 조회 자체는 상수 시간이다
// mask의 켜진 비트에 해당하는 바이트만 앞으로 모으는 셔플 패턴static const uint8_t thintable[256][8] = { ... }; // 2KB
uint8_t m = movemask8(flags); // 8바이트 → 8비트 마스크uint8x8_t sh = vld1_u8(thintable[m]);uint8x8_t packed = vtbl1_u8(data, sh);out += popcount(m); // 다음 쓰기 위치참고
- Guy E. Blelloch, Vector Models for Data-Parallel Computing, MIT Press, 1990
- Guy E. Blelloch, “Scans as Primitive Parallel Operations”, IEEE Trans. Computers, 1989
- R. E. Tarjan, U. Vishkin, “An Efficient Parallel Biconnectivity Algorithm”, 1985
- https://github.com/simdjson/simdjson