Mitchell Hashimoto의 Everyone Should Know SIMD 이해하기
Mitchell Hashimoto의 글 Everyone Should Know SIMD는 SIMD를 특정 분야의 어려운 최적화 기법이 아니라, 반복적인 데이터 처리를 빠르게 만드는 실용적인 도구로 설명한다.
이 글은 해당 블로그 글을 읽으면서 이해되지 않았던 부분을 찾아보고, 필요한 개념을 보충해 가며 이해한 과정을 정리한 글이다.
SIMD의 핵심 개념
SIMD(Single Instruction, Multiple Data)는 하나의 CPU 명령어로 여러 개의 데이터를 같은 방식으로 동시에 처리하는 방식이다.
스칼라 코드는 한 번에 하나의 값을 처리한다.
for (std::size_t i = 0; i < n; ++i) {
output[i] = input[i] * 2.0f;
}이 반복문은 논리적으로 다음과 같이 동작한다.
input[0] * 2 → output[0]
input[1] * 2 → output[1]
input[2] * 2 → output[2]
input[3] * 2 → output[3]SIMD에서는 여러 값을 하나로 묶어 같은 연산을 적용한다.
input: { 1, 2, 3, 4 }
factor: { 2, 2, 2, 2 }
result: { 2, 4, 6, 8 }여기서 여러 값을 묶은 것이 vector이고, vector 안의 각각의 값이 lane이다. 한 번의 SIMD 반복에서 처리하는 데이터 묶음은 chunk라고 부를 수 있다. 4-lane SIMD라면 한 chunk에는 네 개의 값이 들어간다.
SIMD는 여러 스레드를 만드는 방식과 다르다. 여러 스레드로 작업을 나누는 대신, CPU가 하나의 명령어로 여러 lane에 같은 연산을 적용한다.
이상적인 조건에서는 4-lane SIMD가 한 번에 네 개의 값을 처리하므로 해당 연산의 처리량이 최대 네 배에 가까워질 수 있다. 하지만 이것이 전체 프로그램이 항상 네 배 빨라진다는 뜻은 아니다. 메모리 접근, 분기, 결과 처리, 함수 호출과 같은 주변 비용도 함께 고려해야 한다.
하시모토가 말한 공통적인 다섯 단계
하시모토는 원문에서 일반적인 SIMD 코드의 구조를 다음 다섯 단계로 설명한다.
- Broadcast any constants you need and initialize vector accumulators, if any.
- Loop over input one vector-width chunk at a time.
- Perform the comparison or arithmetic across all lanes in parallel.
- Reduce or store the vector result as needed.
- Handle the remaining elements with a scalar tail. A scalar tail is just your normal loop from before vectorizing, but it only processes the remainder that doesn’t fit into a full vector.
하나씩 단계를 이해해보자.
1단계. 상수 broadcast와 vector 준비
배열의 모든 값을 2배로 만드는 예제에서는 상수 2.0을 모든 lane에 복사한다.
여러 값을 하나로 묶은 데이터가 vector이고, vector 안의 각각의 값이 lane이다. 이 예제의 { 1.0, 2.0, 3.0, 4.0 }는 네 개의 lane을 가진 vector다. 스칼라 상수 하나를 모든 lane에 복사하는 작업을 broadcast 또는 splat이라고 한다.
시각적으로 보면 다음과 같다.
하나의 vector
┌────────┬────────┬────────┬────────┐
│ lane 0 │ lane 1 │ lane 2 │ lane 3 │
│ 1.0 │ 2.0 │ 3.0 │ 4.0 │
└────────┴────────┴────────┴────────┘vector는 상자 전체이고, lane은 그 안의 각각의 칸이다.
메모리의 연속된 원소 네 개를 하나의 chunk로 읽어 vector에 담는다.
메모리
input: [ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ] ...
└──────────────┘
첫 chunk
load
↓
vector: { 1, 2, 3, 4 }첫 번째 반복이 끝나면 다음 chunk로 이동한다.
i = 0 → input[0] ~ input[3]
i = 4 → input[4] ~ input[7]
i = 8 → input[8] ~ input[11]SIMD는 여러 스레드를 만드는 것이 아니다. 하나의 vector 안에 들어 있는 여러 lane에 같은 연산을 적용하는 방식이다.
{ 1.0, 2.0, 3.0, 4.0 }
× { 2.0, 2.0, 2.0, 2.0 }
→ { 2.0, 4.0, 6.0, 8.0 }2단계. vector width만큼 반복
4-lane SIMD라면 반복문은 한 번에 네 개씩 이동한다. 한 번의 SIMD 반복에서 처리하는 데이터 묶음을 chunk라고 부른다. 4-lane SIMD에서는 한 chunk에 네 개의 값이 들어간다. vector가 처리할 수 있는 lane 수를 vector width라고 한다.
입력 메모리에서 vector로 데이터를 가져오는 작업을 load라고 한다.
for (std::size_t i = 0; i + 4 <= n; i += 4) {
// input[i]부터 input[i + 3]까지 처리
}스칼라 loop의 i += 1이 SIMD loop에서는 i += 4가 된다.
3단계. 모든 lane에서 같은 연산
{ 1, 2, 3, 4 } × { 2, 2, 2, 2 }
→ { 2, 4, 6, 8 }논리적으로는 네 번의 곱셈과 같지만, vector 연산으로 여러 lane을 한 번에 처리한다.
4단계. 결과 저장 또는 reduction
배열 변환에서는 결과 vector를 출력 배열에 store한다. vector에서 메모리로 결과를 옮기는 작업을 store라고 한다. 반대로 메모리에서 vector로 데이터를 가져오는 작업은 load다. store의 흐름은 반대다.
vector: { 2, 4, 6, 8 }
│
store
↓
output: [ 2 ][ 4 ][ 6 ][ 8 ]예를 들어 입력이 10개이고 vector width가 4라면 다음처럼 나뉜다.
입력: [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ]
└──────────────┘ └──────────────┘ └──────┘
SIMD chunk SIMD chunk scalar tail합계처럼 하나의 값이 필요하면 vector를 하나의 값으로 합친다.
{ 1, 2, 3, 4 }
↓ reduction
10검색 문제에서는 비교 결과를 mask로 바꾸어 특정 lane을 찾을 수 있다. 이 단계가 알고리즘에 따라 가장 크게 달라진다.
5단계. Scalar tail
vector width로 처리하지 못한 나머지는 기존 scalar loop로 처리한다. 이처럼 vector width의 배수가 아닌 나머지를 처리하는 일반 반복문을 scalar tail이라고 한다.
for (; i < n; ++i) {
output[i] = input[i] * 2.0f;
}SIMD 구현에서 scalar loop는 단순한 예외 처리가 아니다. vector로 나누어지지 않는 나머지와 SIMD를 사용할 수 없는 환경의 fallback을 함께 담당한다.
Ghostty 구현 이해하기
Ghostty의 예제는 배열의 모든 값을 변환하는 문제가 아니다. 디코딩된 codepoint 배열을 읽다가 0x0F 이하인 첫 번째 값을 만나면 멈추는 검색 문제다.
0x0F는 모든 제어 문자를 완벽하게 판별하는 기준이 아니다. 빠른 경로에서 일반 문자 구간과 추가 처리가 필요한 구간을 나누는 임의로 결정한 threshold다.
스칼라 구현
원래 구현은 한 번에 하나의 codepoint를 확인한다.
while (end < cps.len and cps[end] > 0xF) {
end += 1;
}다음과 같은 값이 있다고 하자.
0x41 0x42 0x43 0x0A 0x44비교는 다음 순서로 진행된다.
0x41 > 0x0F → true
0x42 > 0x0F → true
0x43 > 0x0F → true
0x0A > 0x0F → false따라서 end는 0x0A가 있는 위치에서 멈춘다. 스칼라 구현은 단순하고 이해하기 쉽지만, 출력 가능한 codepoint가 매우 많이 이어지면 값을 하나씩 비교해야 한다.
SIMD 구현
SIMD 구현은 같은 작업을 여러 codepoint에 한 번에 적용한다.
if (simd.lanes(u32)) |lanes| {
const V = @Vector(lanes, u32);
const threshold: V = @splat(0xF);
while (end + lanes <= cps.len) : (end += lanes) {
const values: V = cps[end..][0..lanes].*;
const greater_than_threshold = values > threshold;
if (@reduce(.And, greater_than_threshold)) continue;
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
}
}
while (end < cps.len and cps[end] > 0xF) end += 1;Step 1. Vector type과 threshold 준비
if (simd.lanes(u32)) |lanes| {
const V = @Vector(lanes, u32);
const threshold: V = @splat(0xF);simd.lanes(u32)는 대상 CPU에서 사용할 vector의 lane 수(한 번에 몇 개를 처리할 수 있는지 구하기 위함)를 얻는다. @Vector(lanes, u32)는 그 lane 수를 가진 vector type을 만든다.
@splat(0xF)는 하나의 threshold를 모든 lane에 복사한다.(Broadcasting)
{ 0x0F, 0x0F, 0x0F, 0x0F }Step 2. Vector chunk load
while (end + lanes <= cps.len) : (end += lanes) {
const values: V = cps[end..][0..lanes].*;end + lanes <= cps.len은 완전한 vector를 읽을 수 있을 때만 loop에 들어가도록 한다. 현재 위치부터 lane 수만큼 데이터를 읽어 values vector에 넣는다.
이 코드는 한 번에 세 가지 일을 한다. cps[end..]는 end 위치부터 배열 끝까지를 가리키는 slice이고, [0..lanes]는 그중 앞의 lanes개만 잘라낸다. 마지막의 .*는 이 lanes개짜리 배열 값을 vector로 읽어오는 동작이다. 따라서 전체 입력 배열을 복사하는 것이 아니라, 현재 위치의 연속된 chunk 하나만 V에 load한다.
예를 들어 lanes = 4, end = 8이면 다음처럼 해석할 수 있다.
cps[end..] → cps[8], cps[9], cps[10], cps[11], ...
[0..lanes] → cps[8], cps[9], cps[10], cps[11]
.* → values = { cps[8], cps[9], cps[10], cps[11] }반복문의 : (end += lanes)는 본문이 끝날 때 실행된다. 방금 end부터 end + lanes - 1까지 읽었으므로, 다음 반복에서는 건너뛰지 않도록 end를 정확히 lanes만큼 앞으로 옮긴다. 즉 end가 0, 4, 8, ...처럼 이동한다.
입력 길이가 10이고 lanes = 4라면 반복은 0..3, 4..7을 읽고, 8..9는 4개가 되지 않으므로 이 loop에 들어가지 않는다. 남은 두 원소는 뒤의 scalar tail이 처리한다. 이 경계 조건이 없으면 마지막에 존재하지 않는 원소까지 vector로 읽으려 할 수 있다.
스칼라 코드가 codepoint 하나를 읽었다면, SIMD 코드는 다음과 같은 chunk를 읽는다.
values = {
cps[end],
cps[end + 1],
cps[end + 2],
cps[end + 3]
}Step 3. 모든 lane에서 비교
const greater_than_threshold = values > threshold;예를 들어:
values:
{ 0x41, 0x42, 0x43, 0x0A }
threshold:
{ 0x0F, 0x0F, 0x0F, 0x0F }
result:
{ true, true, true, false }values > threshold는 각 대응 lane을 비교한 boolean vector를 만든다. 명시적인 내부 loop를 작성하지 않아도 vector 연산이 각 lane에 적용된다.
Step 4. Vector 결과 처리
먼저 모든 lane이 조건을 만족했는지 확인한다.
if (@reduce(.And, greater_than_threshold)) {
continue;
}@reduce(.And, ...)는 모든 boolean lane을 AND로 결합한다.
{ true, true, true, true }
→ true
{ true, true, false, true }
→ false모든 lane이 true라면 이 chunk에는 멈춰야 할 값이 없으므로 다음 chunk로 이동한다. 하나라도 false라면 정확한 실패 위치를 찾아야 한다.
const mask: std.meta.Int(.unsigned, lanes) =
@bitCast(greater_than_threshold);
end += @ctz(~mask);
break;여기서 각 문법은 다음 역할을 한다.
@reduce(.And, ...)
→ 모든 lane이 true인가?
@bitCast(...)
→ boolean vector를 bit mask로 변환
~mask
→ 실패한 lane을 1로 표시
@ctz(...)
→ 첫 번째 실패 lane의 위치 계산예를 들어 비교 결과가 다음과 같다고 하자.
{ true, true, true, false }이를 mask로 바꾸면:
{ 1, 1, 1, 0 }mask를 반전하면:
{ 0, 0, 0, 1 }@ctz는 낮은 자리부터 연속된 0 bit를 센다. 따라서 이 경우 결과는 3이다. 현재 위치에서 3만큼 이동하면 첫 번째 조건 실패 lane에 도착한다.
즉, 이 세 표현은 하나의 과정으로 연결된다.
vector 비교 결과
→ 모든 lane이 성공했는지 reduction
→ bit mask 변환
→ 실패 lane 표시
→ 첫 실패 위치 계산배열 변환에서는 결과 vector를 store하면 끝날 수 있지만, Ghostty의 검색 문제에서는 vector 결과를 다시 “첫 번째 실패 위치”라는 scalar 정보로 바꾸어야 한다.
Step 5. Scalar tail
SIMD loop 뒤에는 원래의 scalar loop가 남아 있다.
while (end < cps.len and cps[end] > 0xF) {
end += 1;
}이 loop는 vector width로 나누어지지 않고 남은 원소를 처리한다. 또한 SIMD를 사용할 수 없는 환경에서는 전체 입력을 처리하는 fallback이 된다.
스칼라 구현과 SIMD 구현의 대응
| 스칼라 구현 | SIMD 구현 |
|---|---|
| codepoint 하나 읽기 | vector chunk load |
cps[end] > 0xF | values > threshold |
| 하나씩 이동 | end += lanes |
| 조건 실패 시 종료 | boolean vector에서 실패 lane 탐색 |
| 하나의 loop로 처리 | SIMD loop와 scalar tail로 분리 |
Ghostty 예제의 핵심은 단순히 여러 값을 동시에 비교하는 데 있지 않다.
SIMD는 여러 값을 동시에 비교한 뒤, vector 결과를 다시 프로그램이 필요한 순서 있는 정보인 “첫 번째 실패 위치”로 변환해야 한다.
SIMD를 다른 코드에 적용할 때의 판단 기준
Ghostty 구현을 이해했다고 해서 모든 반복문을 SIMD로 바꿀 수 있는 것은 아니다. 다른 코드에 적용할 때는 먼저 반복문의 구조를 확인해야 한다.
반복 간 데이터 의존성
각 반복이 서로 독립적이어야 한다.
독립적인 변환:
output[i] = input[i] * 2다음처럼 이전 반복의 결과가 필요하면 SIMD 적용이 어려워진다.
sum[i] = sum[i - 1] + input[i]메모리 접근 패턴
연속적이고 규칙적인 배열 접근은 SIMD에 유리하다.
연속된 배열
규칙적인 stride
cache에 잘 맞는 데이터간접 인덱싱, 포인터를 따라가는 연결 리스트, 여러 객체로 흩어진 데이터는 SIMD의 이점을 줄일 수 있다.
데이터 크기
데이터가 너무 작으면 vector 준비와 tail 처리 비용이 이점보다 클 수 있다. SIMD는 보통 반복 횟수가 많고 동일한 연산을 반복하는 hot loop에서 더 큰 의미가 있다.
분기와 조기 종료
lane마다 다른 분기를 수행하거나 첫 번째 일치 항목에서 즉시 종료해야 한다면 SIMD 결과를 다시 해석하는 작업이 필요하다. Ghostty 예제가 바로 이 경우다.
자동 벡터화
명시적인 SIMD를 작성하기 전에 최적화 옵션으로 scalar 코드를 컴파일하고 생성된 코드나 compiler optimization report를 확인해야 한다. 이미 자동 벡터화되었다면 수동 SIMD가 필요하지 않을 수 있다.
반대로 중요한 hot loop에서 자동 벡터화가 실패하고 benchmark에서 개선 가능성이 확인된다면 명시적인 SIMD를 고려할 수 있다.
Benchmark
이론적인 lane 수와 실제 성능은 다르다.
이론적 처리량 ≠ 실제 loop 성능 ≠ 전체 프로그램 성능SIMD 적용 전후를 실제 입력과 실제 실행 환경에서 측정해야 한다.
마무리
SIMD의 핵심은 반복문을 vector 단위로 재구성하고, 여러 lane에 같은 연산을 적용한 뒤, 그 결과를 프로그램이 필요한 형태로 다시 처리하는 데 있다.
다만, SIMD를 적용하기 위해서는 먼저 자료구조와 메모리 접근 패턴, 반복 간 의존성, 분기 구조를 확인해야 한다. 그다음 컴파일러의 자동 벡터화와 실제 benchmark를 확인하고, 필요한 경우에만 명시적인 SIMD를 작성하는 것이 안전하다.