콘텐츠로 이동

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
  [1, 256]     each of the 256 columns is reused down every row
+ [256, 256]
-----------
  [256, 256]

[4, 3] + [4, 5]는 허용되지 않습니다. 마지막 차원이 둘 다 1보다 크면서 서로 다르기 때문입니다.

Legato는 +, *와 그 밖의 element-wise 연산자, 그리고 matmul의 batch 차원에 같은 규칙을 씁니다.

Legato에서 Broadcasting의 두 가지 의미

Legato에서 Broadcasting은 서로 관련된 두 가지 컴파일러 작업을 가리킵니다. 하나는 위에서 설명한 NumPy 방식의 shape 규칙이고, 다른 하나는 rank가 N인 Core 연산을 백엔드가 lowering할 수 있는 더 작은 단위인 leaf로 쪼개는 작업입니다.

  1. Shape broadcast. 이항 연산과 matmul batch 차원은 *broadcast 호환*이어야 합니다. 프론트엔드는 shape이 맞지 않다는 것이 확실하면 컴파일을 거부하고, 통과하면 Core IR이 결과 shape을 추론합니다.
  2. Rank 분해(rank decomposition). 두 피연산자의 shape가 이미 같더라도 --legato-perform-broadcast가 연산을 다른 형태로 변환(rewrite)할 수 있습니다. 예를 들어 rank 3 layer_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
# 행 4개. 마지막 차원은 논리 70이며, 폭 256인 행에 저장
x: (4, (70, 256))

[logical, physical) 구간은 hole(물리 영역 중 논리 범위 밖의 빈 구간)입니다. 컴파일러는 이 구간의 바이트를 실제 원소로 취급해서는 안 됩니다. 마지막 차원이 padding된 add를 긴 벡터 하나로 flatten할 수 없는 것도 이 때문입니다. flatten하면 hole이 계산에 섞여 들어가기 때문입니다.

컴파일러의 처리 과정

1
2
3
4
5
6
7
8
9
Python  legato.math.*  /  a + b
   ↓
Core IR
   ↓
AssignExecutor / AssignMemory / InferPhysicalShape
   ↓
PerformBroadcast     ← Flatten | PrefixLoop | None
   ↓
backend (Bertha: CoreToBertha → HiToLo)

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
y = a + b  # a는 [1, 256], b는 [256, 256]

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
y = legato.math.conv_1d(x, w, None, (1,), (1,), (1, 1), "zeros")
# x: [8, 64]        → leaf 하나
# x: [2, 8, 64]     → [8, 64] leaf 두 개의 반복

y = legato.math.dwconv_1d(x, w)
# x: [2, 19, 64], w: [4, 64] → [19, 64] leaf 두 개, 같은 w

y = legato.math.avg_pool_1d(x, (2,), (2,))
# x: [8, 64]        → leaf 하나

마지막 축의 행 단위 연산 — LayerNorm, RMSNorm, softmax

이 연산들은 **축 하나**에 대해 reduction하거나 정규화를 수행합니다. 대상이 마지막 축이면 leaf는 rank 1이 되며, 이때 axis가 0으로 다시 쓰입니다. [4, 128] LayerNorm은 [128] leaf 네 개로 분해됩니다. affine weight / bias는 rank 1 [D]이며 행마다 적용됩니다.

1
2
3
y = legato.math.layer_norm(x, w, b)   # x: [4, 128]
y = legato.math.rms_norm(x, w)        # x: (4, (70, 256)) — 나누는 수는 256이 아니라 70
y = legato.math.softmax(x, -1, row_max)

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
y = lhs @ rhs  # lhs: [2, 32, 64], rhs: [1, 64, 64] → 공유 RHS
공유되는 RHS를 백엔드가 스트리밍 버퍼에서 **다시 읽어(replay)**써도 되는지는 Core 규칙이 아니라 대상(target)별 규칙입니다. Bertha의 규칙은 Bertha에서의 Broadcasting에 있습니다.