Broadcasting¶
Broadcasting을 이용하면 shape이 서로 정확히 일치하지 않는 텐서끼리도 하나의 연산으로 계산할 수 있습니다.
이 페이지는 하드웨어와 무관한 내용, 즉 shape, Core IR, PerformBroadcast 패스를 다룹니다.
그 결과가 Bertha(VPU, MPU, SRAM과 mpu_buffer)에서 어떻게 실행되는지는 Bertha에서의 Broadcasting에 있습니다.
그대로 복사해 쓸 수 있는 커널 예제는 예제: Broadcasting에 있습니다.
Broadcasting이란¶
NumPy와 PyTorch에서 a + b는 a와 b의 shape이 같지 않아도 됩니다.
런타임은 두 shape을 오른쪽 끝(마지막 차원)부터 맞춰 비교합니다.
크기 1인 차원은 상대 피연산자의 크기에 맞춰 늘어나고, 앞쪽에 없는 차원은 크기 1로 간주합니다.
256개 열 각각이 모든 행에 반복해서 쓰임
| a | b | a + b |
| --- | --- | --- |
| [256] | [256] | [256] |
| [1, 256] | [256, 256] | [256, 256] |
| [4, 128] | [128] | [4, 128] |
1 2 3 4 | |
[4, 3] + [4, 5]는 허용되지 않습니다.
마지막 차원이 둘 다 1보다 크면서 서로 다르기 때문입니다.
Legato는 +, *와 그 밖의 element-wise 연산자,
그리고 matmul의 batch 차원에 같은 규칙을 씁니다.
Legato에서 Broadcasting의 두 가지 의미¶
Legato에서 Broadcasting은 서로 관련된 두 가지 컴파일러 작업을 가리킵니다. 하나는 위에서 설명한 NumPy 방식의 shape 규칙이고, 다른 하나는 rank가 N인 Core 연산을 백엔드가 lowering할 수 있는 더 작은 단위인 leaf로 쪼개는 작업입니다.
- Shape broadcast. 이항 연산과 matmul batch 차원은 *broadcast 호환*이어야 합니다. 프론트엔드는 shape이 맞지 않다는 것이 확실하면 컴파일을 거부하고, 통과하면 Core IR이 결과 shape을 추론합니다.
- Rank 분해(rank decomposition). 두 피연산자의 shape가 이미 같더라도
--legato-perform-broadcast가 연산을 다른 형태로 변환(rewrite)할 수 있습니다. 예를 들어 rank 3layer_norm은 rank 1 행 연산 네 개로 분해가 가능합니다. batch가 있는conv_1d는 batch 없는[X, C]conv를 반복하는 루프로 바뀝니다. 마지막 차원이 padding된 텐서의 element-wise add도 같은 방식으로 처리합니다.
한 문장만 요약한다면 다음과 같습니다.
shape broadcast는 프로그램이 유효한지를 정하고,
rank 분해는 컴파일러가 더 낮은 rank의 연산을 몇 개 생성할지를 정합니다.
Shape 규칙¶
차원은 오른쪽부터 비교하며, 각 차원 쌍에 다음 규칙을 적용합니다.
- 크기
1이면 어떤 크기와도 호환됩니다. (1인 쪽이 늘어납니다). - 한쪽에 없는 차원은
1로 취급합니다. - 둘 다 1보다 큰 정적 크기라면, 서로 같아야 합니다.
- 동적 크기(
-1)는 허용됩니다. 단, 다른 정적 차원 쌍에서 이미 불일치가 확인된 경우는 제외합니다.
프론트엔드 검사는 shapes_have_proven_broadcast_mismatch
(legato/src/legato/diagnostics/validation.py)입니다.
Core IR은 isBinaryOpCompatible / inferBinaryOpShape
(legato/csrc/Sources/Utils/ShapeUtils.cpp)를 씁니다.
matmul은 마지막 두 차원 앞의 차원에 같은 규칙을 적용합니다 ([N*, M, K] @ [N*, K, N]).
행렬 쌍 (M, K) / (K, N)은 broadcast하지 않고, 앞쪽 N* batch만 broadcast합니다.
다음 shape는 아직 지원하지 않습니다.
- 마지막 차원이 물리적으로 padding되어 있을때의 열 방향 broadcast
[N, 1] + [N, C]. 앞쪽 차원이 1인[1, C] + [N, C]는 지원합니다.
**broadcast**라는 단어의 다른 용법,
즉 request_load가 버퍼 하나를 여러 코어에 보내는 것이나
SplitCoreBroadcastFunctions가 코어마다 함수를 복제하는 것은
이 페이지에서 다루지 않습니다.
데이터 load 요구 사항은 Bertha 메모리 가이드를 참고하십시오.
논리 크기와 물리 크기¶
Core IR에서 차원 하나는 (logical, physical) 쌍으로 표현됩니다.
- **논리(logical) 크기**는 연사에 실제로 사용되는 크기입니다.
- **물리(physical) 크기**는 레이아웃에 따라 할당된 저장 공간의 크기입니다.
Python에서는 (70, 256) 또는 (-1, 4)(동적 논리 크기, 물리 상한 4)로 씁니다.
1 2 | |
[logical, physical) 구간은 hole(물리 영역 중 논리 범위 밖의 빈 구간)입니다.
컴파일러는 이 구간의 바이트를 실제 원소로 취급해서는 안 됩니다.
마지막 차원이 padding된 add를 긴 벡터 하나로 flatten할 수 없는 것도 이 때문입니다.
flatten하면 hole이 계산에 섞여 들어가기 때문입니다.
컴파일러의 처리 과정¶
1 2 3 4 5 6 7 8 9 | |
PerformBroadcast(--legato-perform-broadcast)는 compute model을 참조하지 않고, shape과 레이아웃만 봅니다.
분해 방식은 legato/csrc/Includes/Dialects/Core/Compute/ShapeDecomposition.hpp의 정의된 DecompositionKind로 나타냅니다.
| 종류 | 의미 |
|---|---|
None |
이미 leaf이거나(rank가 leaf rank 이하), 연산을 쪼갤 수 없음. |
Flatten |
packed 상태인 prefix(앞쪽 차원들)를 rank 1 벡터 하나(또는 rank 2 matmul 하나)로 재해석. leaf를 한 번만 호출. |
PrefixLoop |
앞쪽 차원을 hscf.for로 순회하며 반복마다 suffix(뒤쪽 차원) leaf를 실행. hscf는 이후나 hscf → scf.for로 변환됨. |
연산 종류별로 실행되는 분석기는 다음과 같습니다:
| 분석기 | 연산 | leaf |
|---|---|---|
analyzeElementwiseDecomposition |
+, *, cast, exp, … |
rank 1 |
analyzeLastAxisRowDecomposition |
마지막 축 softmax, RMSNorm, LayerNorm, keepdim reduce_sum |
rank 1 행 |
analyzeSpatialBatchDecomposition |
conv, pool, dwconv | [X, C] 또는 [H, W, C] |
analyzeMatmulBatchDecomposition |
matmul / grouped matmul | rank 2 행렬 |
prefix가 동적이거나 padding이 되어 있으면 반드시 PrefixLoop로 처리해야 합니다.
Flatten은 합치려는 모든 차원이 정적이고 packed 상태일 때 (logical == physical이고 logical >= 0)만 허용됩니다.
rank 1 element-wise 벡터도 마지막 차원이 packed여야 합니다.
동적 크기는 합치지 않습니다. 런타임 크기가 다른 피연산자와 맞는지 알 수 없기 때문입니다.
affine 피연산자(RMSNorm / LayerNorm의 weight와 bias, softmax의 max)는 행마다 slice**됩니다. spatial 연산의 **weight와 bias에는 batch prefix가 없으므로, 같은 SSA 값이 모든 leaf에 그대로 전달됩니다. 여기서 affine은 정규화 연산에서 정규화한 결과에 곱하는 값(weight)과 더하는 값(bias)을 가리킵니다. 수학의 affine 변환(y = a·x + b, 곱하고 더하는 변환)에서 온 말입니다. 예를 들어, LayerNorm을 예로 들면 계산이 두 단계입니다.
- 입력 정규화
- 그 결과에 weight를 곱하고 bias를 더함 (이 단계가 affine 변환)
Shape 예제 풀이¶
아래 코드 조각은 연산 부분만 보여줍니다.
request_load까지 포함한 전체 커널은 Bertha에서의 Broadcasting와
예제: Broadcasting에 있습니다.
앞쪽 차원이 1인 add — [1, 256] + [256, 256]¶
오른쪽 정렬: 마지막 차원 256 == 256, 첫 차원 1이 256으로 늘어납니다.
결과는 shape은 [256, 256]입니다.
rank 2는 element-wise leaf의 rank(1)보다 높으므로,
PerformBroadcast는 rank 1 add를 반복하는 prefix 루프를 생성합니다(모든 차원이 packed이면 flatten합니다).
1 | |
shape이 같은 packed add와, 마지막 차원이 padding된 add¶
모든 차원에서 logical == physical인 [4, 128] + [4, 128]은
길이 512인 rank 1 add 하나로 **Flatten**할 수 있습니다.
(4, (128, 256)) + (4, (128, 256))은 flatten할 수 없습니다.
마지막 차원에 hole이 있으므로 **PrefixLoop**으로 처리합니다.
논리 길이 128인 rank 1 add 네 개로 분해되고, hole은 계산 대상 벡터에 포함되지 않습니다.
Spatial N* — conv, dwconv, pool¶
channels-last입니다. 하드웨어 leaf는 batch 없는 suffix입니다.
- 1D:
[X, C](conv / dwconv / pool) - 2D:
[H, W, C]
N*은 앞쪽에 붙는 0개 이상의 차원을 뜻합니다. [8, 64] conv는 이미 leaf입니다(None).
[2, 8, 64]는 leafRank=2인 PrefixLoop로 처리되어 leaf를 두 번 호출합니다.
weight의 shape은 [KX, Cin, Cout] 또는 [KX, C] 그대로이며, batch에 따라 slice되지 않습니다.
1 2 3 4 5 6 7 8 9 | |
마지막 축의 행 단위 연산 — LayerNorm, RMSNorm, softmax¶
이 연산들은 **축 하나**에 대해 reduction하거나 정규화를 수행합니다. 대상이 마지막 축이면 leaf는 rank 1이 되며, 이때 axis가 0으로 다시 쓰입니다.
[4, 128] LayerNorm은 [128] leaf 네 개로 분해됩니다. affine weight / bias는 rank 1 [D]이며 행마다 적용됩니다.
1 2 3 | |
RMSNorm / LayerNorm의 나누는 수는 논리 길이입니다.
padding [70, 256)은 계산에 영향을 주지 않는 0이지, 추가 채널이 아닙니다.
Matmul batch prefix¶
[B, M, K] @ [K, N]처럼 RHS의 batch가 1이거나 없으면, weight 행렬 하나를 왼쪽의 B개 tile이 공유합니다. [B, M, K] @ [B, K, N]은 두 prefix를 함께 순회합니다. leaf는 rank 2 matmul입니다.
1 | |