path: root/docs/design/025-batch-programs.md

# 025 — 묶음 프로그램: 블록은 로드 때 한 번 읽고, 묶음마다는 값만 본다

작성일: 2026-10-08. 상태: 1단계를 만들었다([134](../research/134-batch-plans-stage-one.md): 배낭의 묶음마다 0.90 → 0.68 µs, 11.48 →
10.34 ms. 막대 ≤ 0.60 µs와 ≤ 10.3 ms에 못 미쳤다. 남은 것은 명령마다 `Val`을 다루는 해석으로, 2단계의 몫이다). 2단계(균일·아핀
조각)를 만들었다([135](../research/135-batch-plans-stage-two.md): matmul 38.18 → 36.10 ms, 명령 −4.5%; 배낭의 묶음마다 0.63 µs, 배낭
10.51 ms(놓인 자리); 막대 ≤ 9.2 ms, ≤ 0.45 µs, ≤ 33 ms에 못 미쳤다. 조각은 중첩 회차의 수단이고, 묶음마다 값은 키로 찾기와 레인
연산의 준비에 있어 이 꼴로는 약 0.6 µs에서 멈춘다. 리스트의 칸 캐시는 3%라 하지 않았다). 다음은 요소마다다(3단계: 4바이트 곱하기,
matmul ≤ 21 ms). 4바이트 곱하기 뒤 matmul은 26.57 ms다(명령 −20%). 막대의 셈은 "실수 연산 22 ms 밖은 14 ms 그대로"였는데, 그 밖은
안쪽 회차마다의 해석 약 15 ms와 행렬 만들기(점화식과 덧붙이기 8만 개) 약 4–5 ms였다: 26.6 ≈ 커널 8 + 회차마다 15 + 만들기 4–5. 3단계를
닫았다([136](../research/136-batch-executor-stage-three.md): 곱하기, 레인 없이 시작하는 모으기(sum0 6.09 → 1.01 ms, 막대 ≤ 1.5),
리스트의 칸을 묶음에 한 번; b9 대비 matmul −35%, knapsack −12%, roots −7.6%; 실행기, 은행 질의, TPC-C는 그대로). 다음은 4단계(knapsack의
훑기 여섯을 셋으로). [024](024-batch-executor.md)가 처음에 적고 만들지 않은 단계("묶음 프로그램은 루프마다 한 번
만든다")이고, [132](../research/132-batch-executor-floor-and-the-way-past.md)의 A, [133](../research/133-register-tiles-measured.md)이
정한 길이다. 사용자의 방향: 범용 장치로, 합친 연산의 표 없이, 기계어 없이, 메모리를 적게(2026-10-05, 2026-10-08).

## 쉬운 말로

- 묶음 실행기는 묶음 하나를 열 때마다 루프의 블록을 처음부터 다시 읽는다. 어느 지역 변수를 쓰는지, 점화식과 칸에 더하기가
  어디 있는지, 이 `LOCAL_LOAD`가 모으기의 앞인지, 같은 코드의 값이 어디서 오는지를 다시 찾고, 명령마다 값의 꼴(균일·아핀·레인)을
  다시 묻는다. 블록은 바뀌지 않으니 답도 매번 같다.
- 배낭에서 이 값이 묶음 하나에 0.90 µs, 시간의 38%다(11.5 ms 가운데 4.4). matmul은 같은 일을 묶음이 아니라 안쪽 회차(k)마다
  한다(메시지 하나에 4만 번). 132는 이 값을 "묶음마다 6,500 명령"이라 적었는데, 세 번 돈 수를 한 번의 묶음 수로 나눈 것이었다.
  고쳤다: 작은 블록에서 약 2,300 명령(0.33 µs)이다.
- 그래서 사실을 둘로 가른다. **블록의 모양에서 나오는 것**은 로드 때 루프마다 한 번 셈해 둔다(묶음 프로그램). **값에서 나오는
  것**(레인이 4바이트에 드는지, 열의 폭, 경계, 의존 거리, 고를 레인)만 묶음마다 본다.
- 그 위에서 연산을 꼴과 폭에 맞춘 루프로 돌리고(예: 균일한 값을 더하는 모으기는 레인을 돌지 않고 `v × n`, 4바이트 곱하기),
  읽기를 피연산자로 받아 훑기의 수를 줄인다(배낭 6에서 3).
- 합친 연산의 표, 레지스터 타일, 기계어는 쓰지 않는다. 메모리는 루프마다 블록 길이쯤의 표가 는다.

## 잰 것: 값이 어디에 있는가

방법. `b9`의 코어(`735ba81`; 그 뒤의 커밋은 문서와 헤더 하나)를 묶음 레인 1024와 256으로 빌드해(gcc `-O2 -g`, `module-batch.c`는
`-O3`), `suite-run`을 `PURE_JIT=0`으로 돌리며 2 kHz로 표본을 떴다. 줄마다의 표본을 같은 프로세스에서 도는 C(6.24 ms)의 표본으로
ms로 바꾸고, 두 빌드의 차를 묶음 수의 차로 나눴다. 원본은 `041-batches/2026-10-08-batch-costs.jsonl`이다.

### 배낭: 묶음마다 0.90 µs, 시간의 38%

배낭은 메시지 하나에 회차 4,949,075개를 레인 1024로 4,886 묶음, 256으로 19,376 묶음에 돈다. 시간은 11.49와 24.56 ms다.
(24.56 − 11.49) / 14,490 = **0.90 µs**가 묶음마다이고, 1024 레인에서 4,886 × 0.90 = 4.4 ms다. 그 13.6 ms(표본의 합)를 나누면:

| 갈래 | 무엇 | 몫 |
|---|---|---:|
| 블록 다시 읽기 | `recurrences` 1.58, `sums` 0.82, `batch_run`의 쓰는 지역 변수 훑기와 앞뒤 약 1.1, `pass`의 명령마다 찾기(칸에 더하기·점화식·같은 코드의 값·기록) 1.34, `local_load`의 모으기 앞 검사 0.12, 걸러내기 버퍼 놓기 0.30 (`batch_run`의 몫 가운데 일부는 남는다) | **약 39%** |
| 값의 꼴 | `whole`·`whole32` 0.75(`floor`를 PLT로 부른다), `word_op`·`binary`·`affine_op` 1.15, `local_load`·`local_store` 1.0, `item_get` 0.37, `branch`·`arrive` 0.35 | 약 26% |
| 리스트의 사실과 의존 | 리스트 쪽(`pure_list_cells`, 키 찾기) 0.80, `rows_in` 0.57, `find` 0.53, `read_of` 0.47, `settle` 0.39, `reads_set`·`cells_at` 0.28 | 약 22% |
| 명령 디스패치 | `pass`의 나머지 1.40, 그 밖 | 약 14% |

하나하나는 작고, 다 "블록을 읽어 정해진 사실을 다시 셈하기"이거나 "묶음에 한 번이면 될 것을 명령마다 하기"다. 배낭의 요소마다
(훑기 여섯)는 회차당 약 2.9 사이클로 이미 꽉 짠 루프에 가깝다(나머지 7.1 ms 가운데 약 1 ms는 항목과 표를 만드는 일).

### sum0: 묶음마다 0.33 µs

`costs/sum0`(`total = total + 1`, `let` 둘)을 4M 회차로 돌리면 1024와 256 레인이 8.63과 12.54 ms다. 묶음 11,718개의 차로 나누면
0.33 µs다(`icount`로는 2,330 명령, 805 사이클). 블록 다시 읽기(`recurrences` 훑기, 쓰는 지역 변수 훑기, `pass`의 찾기, 모으기 앞
검사)가 약 34%, `whole`이 8%다. 점화식이 없는 블록도 점화식을 찾느라 블록을 두 번 훑는다.

같은 프로파일이 다른 것도 보인다. 이 루프 시간의 약 80%가 모으기다. `total = total + 1`에 레인마다 부분합을 놓고(`reduction`),
더하고(`reduce_step`), 크기와 함께 접는다(`fold`). 훑기 셋이다. 기계어는 더하기 하나다.

### matmul: 안쪽 회차마다의 디스패치와 실수 검사

matmul은 j를 레인 200개로 묶고 k를 레인이 함께 돈다. 묶음은 200개뿐이지만 `pass`가 안쪽 회차마다 몸체를 다시 해석한다(4만 번).
표본으로 `pass` 16%, `sweep` 4.6%, `find` 2.7%, `affine_of` 2.2%, 리스트의 사실 1.5%, `nested` 1.3%, 합 약 13 ms(안쪽 회차마다
약 0.3 µs)다. 나머지 큰 몫은 연산이다. 1바이트 열에서 읽은 값을 곱하고 더하는데, `words_op`에 곱하기가 없어 8바이트 실수로
바꾸고(`numbers` 3 ms) 유한 검사를 하는 실수 연산으로 간다(`binary` 약 17 ms).

### 다른 일

- **BFS**(24.0 ms): 묶음마다의 값이 작다((26.0 − 24.3)/3 = 0.6 ms). 간선당 112 명령은 레인 훑기 약 45, 노드마다 약 20, 후보마다
  약 26이다(131).
- **roots**(8.97): 묶음마다 약 0.6 ms((10.8 − 8.97)/3).
- **join**(117): 묶음마다 약 3 ms. 점화식 `x`를 회차마다 해석하는 값이 약 20%(차례가 있는 사슬이라 바닥에 가깝다), 칸에 더하기의
  꼬리가 약 10%(회차마다 열의 폭을 가른다), 키로 찾기(리스트 쪽)가 약 13%다.
- **sort**와 **words**는 리스트 쪽 정렬과 텍스트라 이 설계 밖이다.

## 사실의 두 갈래

| 블록의 모양에서 (로드 때 한 번) | 값에서 (묶음마다) |
|---|---|
| 블록이 쓰는 지역 변수와 쓰는 자리, 항목을 쓰는지 | 레인 값이 4바이트에 드는지(넘치면 8바이트로, 지금처럼 커널이 알린다) |
| 점화식: 갱신과 걸음, 걸음의 피연산자가 어디서 오는지, 기록과 그 짝 | 점화식의 처음 값, LOAD·필드·바깥 지역 변수의 값 |
| 칸에 더하기의 자리(again, add, set) | 열의 폭(묶음 끝에서 넓어질 수 있다), DENSE인지, 개수 |
| 모으기: 어느 `LOCAL_LOAD`가 `x = x op e`의 앞인지 | 균일 값의 부호(아핀 곱), 경계 안인지, 읽기와 쓰기의 의존 거리 |
| 같은 코드의 값(다시 쓰기, 쥐기), 걸러내기, 가드, 펼치기 | 고를 레인(¼ 아래인지), 가드가 허락하는 회차 |
| 명령마다 결과의 꼴: 균일·아핀·레인 (값이 정하는 자리는 "아핀 또는 레인") | 그 꼴에서 고를 커널(꼴 × 폭) |

## 설계

### 1단계: 블록의 사실을 로드 때 (`PureBatchPlan`)

모듈을 읽을 때 `plan_folds`가 묶음 루프(`PLAN_BATCH`)를 정한 뒤 루프마다 계획 하나를 만든다. 계획은 모듈에 있고(루프의 `LOOP`
명령의 pc로 찾는다), 만든 뒤에는 읽기만 하므로 보기의 스레드들이 함께 쓴다.

- 블록이 쓰는 지역 변수(비트 256개)와 항목을 쓰는지. `batch_run`의 훑기가 없어진다.
- 점화식: 갱신마다 (from, set, x)와 걸음 (op, a, c). 걸음의 피연산자는 "자리"로 적는다: 상수(값까지 로드 때), 필드, LOAD, 블록이
  쓰지 않는 지역 변수, 루프 변수, x, 앞 걸음. 묶음을 열 때는 자리에 값만 채운다. `recur`의 `actions[]`도 계획에 있다. 점화식의
  다른 읽기(기록)의 pc와 함께 쓰는 짝도.
- 칸에 더하기: (again, add, set, 리스트, 필드).
- **블록의 pc마다 몫 한 바이트**: 보통, 칸에 더하기의 again·add·set, 점화식의 from, 기록, 같은 코드의 값(다시 쓰기·쥐기), 모으기의
  앞(`pure_batch_reduces`의 답은 따로 pc 하나). `pass`는 선형 찾기 넷 대신 이 바이트 하나를 본다.
- 작은 손질: `whole`이 `floor`를 부르지 않게(같은 뜻을 정수 변환으로), 걸러내기 버퍼는 쓴 묶음만 놓는다.

묶음마다 남는 일: 값 채우기, 버퍼와 마스크, 미룬 효과, 검사. 메모리는 루프마다 블록 길이의 바이트와 점화식 걸음(최대 96개) 등
수 KB 아래다.

**맞음.** 1단계는 같은 사실을 다른 때 셈할 뿐이다. 만드는 동안 시험 빌드에서 묶음을 열 때 옛 셈을 함께 하고 계획과 견줘 다르면
멈추게 한다(`PURE_BATCH_CHECK`). 무작위 시험과 고정 소스가 이 견줌을 다 지나면 옛 셈을 지운다. 두 길을 남기지 않는다.

### 2단계: 값의 꼴을 로드 때, 리스트의 사실은 묶음에 한 번

(1단계 뒤에 다시 정한 꼴, 134.) 2단계는 `pass`를 다시 쓰지 않는다. 계획이 균일·아핀만으로 된 조각을 찾아 두고, 묶음이 그 조각의
첫 명령에 닿으면 조각을 스칼라 걸음으로 한 번에 돈다. 걸음은 명령마다의 길과 같은 규칙(`number_op`, `affine_of`, 같은 검사)을
쓰고, 어느 하나라도 맞지 않으면(지역 변수가 레인이다, 아핀이 정수가 아니다, 고르기나 펼친 걷기 안이다) 아무것도 쌓지 않고 명령마다의
길이 그 조각을 그대로 돈다. 그래서 뜻은 바뀌지 않는다. 조각에 드는 명령은 상수, LOAD, 필드, 블록이 쓰지 않는 지역 변수, 루프 변수,
앞에서 조각이 쓴 지역 변수(중첩 루프의 변수도), 행(걷기의 항목), 균일한 행의 항목 읽기, 산수와 비교다. 조각이 `LOCAL_STORE`로
끝나면 지금의 `local_store`를 부른다. 같은 코드의 값, 모으기의 앞, 점화식과 칸에 더하기의 자리는 조각에 넣지 않는다. 리스트의
칸(`pure_list_cells`)은 묶음마다 리스트에 한 번 가져온다(미룬 쓰기가 끝에 있어 `pass` 동안 바뀌지 않는다).

- **정적 꼴.** 블록의 pc마다 결과가 균일·아핀·레인 가운데 무엇인지 로드 때 셈한다. 루프 변수는 아핀, 블록이 쓰지 않는 지역
  변수와 LOAD·필드·상수는 균일, 균일과 아핀의 더하기·빼기는 아핀, 양수 균일과 아핀의 곱은 아핀(부호는 값이라 묶음을 열 때
  확인하고, 아니면 지금처럼 레인), 레인에서 읽은 것은 레인. 지금 `pass`가 묶음마다 하는 꼴의 셈과 같은 규칙이다.
- **균일과 아핀의 조각은 스칼라 걸음으로.** 키의 셈(`c - it.weight`, `i * go.n + k`)처럼 균일과 아핀만으로 된 조각을 점화식의
  걸음처럼 스칼라 목록으로 만들어 묶음마다 한 번 돈다. 명령마다 `Val`을 만들고 꼴을 묻는 일이 없어진다.
- **리스트의 사실은 묶음에 한 번.** 칸의 자리와 폭, DENSE인지, 개수, 키의 첫 행은 묶음을 열 때 리스트마다 한 번 가져온다. 읽기의
  기록(`read_of`, 의존 검사에 쓰는 것)도 계획에 자리가 있다.
- **커널은 묶음을 열 때 고른다.** 레인 연산은 지금의 커널을 쓰되, 어느 것인지는 (정적 꼴 × 그 묶음의 폭)으로 정한다. 4바이트
  커널이 넘침을 알리면 지금처럼 8바이트로 다시 한다.
- **버퍼.** 값마다의 버퍼 자리를 로드 때 정해 `fresh`·`release`·`sweep`이 빈 버퍼를 찾지 않게 한다. 고르기와 같은 코드의 값이
  버퍼를 쥐는 규칙과 맞물리므로 1단계를 잰 뒤에 정한다.

### 3단계: 꼴과 폭에 맞춘 커널

표가 아니라 연산 하나하나의 타입 변형이다.

- **4바이트 곱하기.** `words_op`에 곱하기(64비트 곱으로 넘침 검사). matmul의 곱과 더하기가 4바이트 레인에 머문다.
- **모으기.** 균일한 e를 모든 레인에서 더하면 `result += e × n`(e가 정수이고 크기가 2^53 아래일 때. 아니면 지금처럼 레인마다).
  4바이트 레인의 e는 64비트 정수로 더한다(크기 검사 없이 정확).
- **좁은 열.** 1·2바이트 열을 4바이트 레인으로 바로 읽는다(8바이트로 거치지 않는다).
- 점화식은 차례가 있는 사슬이라 그대로 둔다.

### 4단계: 훑기의 수

- **보폭 읽기를 피연산자로.** 열(시작, 보폭, 폭)을 값의 꼴 하나로 두고, 그것을 받는 연산이 열에서 바로 읽는다. 레인 배열로
  옮기는 훑기가 없어진다.
- **비교가 레인을 센다.** 가르기 앞의 비교가 가는 레인의 수를 같은 루프에서 센다(`branch`의 세는 훑기가 없어진다).
- 배낭은 훑기 6에서 3이다(더하기, 비교와 세기, 마스크 쓰기). 컴파일러가 합친 2(1.87 ms, `042-tiles`)는 천장으로 둔다.

### 5단계: 꼬리 (132의 E)

- 걸러내기 후보의 꼬리(후보당 약 250 명령: 기록 50, 결정 90, 넣기 110)를 리스트 쪽에서 한 번에 한다(폭 검사 한 번, 비트와 칸을 함께).
- 칸에 더하기의 꼬리(join): 열의 폭을 묶음에 한 번 정하고 회차마다의 폭 가르기를 뺀다.

## 하지 않는 것

- 합친 연산의 표(사용자, 2026-10-08), 레지스터 타일(133: 모으기가 있는 몸체에서 진다), 기계어.
- **레인 늘리기.** 묶음마다의 값을 레인 수로 나누는 쉬운 길이지만, 레인 버퍼가 스레드마다 24 × 1,048 × 8 B = 201 KB이고 4096이면
  805 KB다. 메모리를 적게 쓰는 Pure의 생각과 맞지 않고, 묶음마다의 값을 없애면 필요 없다.

## 막대

단계마다 같은 방법으로 잰다(`041-batches/runs.sh`, 11번의 중앙값, 세 길과 명령 수). 묶음마다의 값은 레인 1024와 256 빌드의 차로 잰다.
막대는 위의 몫에서 셈한 것이다.

| 일 | 지금 (`b9`) | 1단계 | 2단계 | 3–4단계 | 5단계 | 천장 (041) | 기계어 | C |
|---|---:|---:|---:|---:|---:|---:|---:|---:|
| knapsack | 11.5 ms | ≤ 10.3 (10.34) | ≤ 9.2 | ≤ 6.0 | | 4.55 (꽉 짠 두 훑기 1.87) | 7.9 | 6.25 |
| matmul | 40.0 | ≤ 39 (38.2) | ≤ 33 (36.1) | ≤ 21 (곱하기 뒤 26.57) | | 17.75 | 14.2 | 7.6 |
| BFS | 24.0 | ≤ 24 | ≤ 22 | ≤ 21 | ≤ 18 | 10.3 (꽉 짠 9.8) | 7.7 | 9.9 |
| roots | 8.97 | ≤ 9.0 | ≤ 8.6 | | | 6.8 | 9.57 | 6.86 |
| join | 117 | ≤ 116 | ≤ 115 | | ≤ 110 | 57.8 | 84.6 | 31.7 |
| 묶음마다 (배낭) | 0.90 µs | ≤ 0.60 (0.68) | ≤ 0.45 | | | | | |
| 묶음마다 (sum0, `icount`) | 2,330 명령 | ≤ 1,550 (1,822) | ≤ 1,300 | | | | | |

- **knapsack.** 1단계는 블록 다시 읽기(묶음마다의 3분의 1 남짓, 약 1.5 ms)를 없애 약 10.0 ms라 셈했고, 10.34 ms였다(134:
  `pass`의 명령마다 머리를 찾기로 셈한 탓). 2단계(1단계 뒤에 다시 셈했다): 안쪽 루프의 명령 24개 가운데 조각이 덮는 것은
  10–12개다(용량에서 k 빼기, `c - it.weight`, `it.worth`). 키로 찾기 셋, 레인 연산, 미룬 쓰기는 그대로다. 명령 하나 약 50
  사이클을 조각의 걸음 약 5 사이클로 바꾸면 묶음마다 약 500 사이클, 칸을 한 번에 가져오면 약 100 사이클이 준다. 0.68 → 약
  0.43 µs, 배낭은 10.34 − 4,886 × 0.25 µs ≈ 9.1 ms다. 기계어(7.9)에 닿으려면 4단계의 훑기 셋이 있어야 한다: 요소마다 약 6 ms를
  약 3.5로 줄여 약 6.5 ms다.
- **matmul.** 안쪽 회차마다의 디스패치 약 13 ms 가운데 1단계는 찾기(`pass`의 몫 일부)만 없앴다(시간은 38.2 ms지만 명령 수가
  같아 놓인 자리다). 2단계: 안쪽 회차의 몸체 약 16 명령 가운데 `i * go.n + k`, `k * go.n + j`, `a[..].v`의 10–12개가 조각이라,
  회차마다 약 500 사이클 × 4만 회차 ≈ 8 ms가 줄 수 있다. 막대는 그 절반을 남겨 ≤ 33이다. 3단계는 곱과 더하기를 4바이트로 해서 연산 약 22 ms를 약 9 ms로 한다(요소 8M × 약 2.5 사이클). 막대는 041의
  천장이다.
- **BFS.** 간선당 112 명령에서 노드마다 20을 약 10으로(1–2단계), 비교와 세기를 합쳐 약 5를(4단계), 후보의 26을 약 10으로(5단계)
  줄이면 약 80 명령, 약 17 ms다.
- **roots, join**은 묶음마다의 몫(0.6, 3 ms)과 join의 칸 꼬리(약 12 ms의 절반)만큼이다. join의 점화식(약 23 ms)은 그대로다.
- **지키는 것.** 묶음 루프가 없는 모듈의 실행기는 명령 수가 그대로(`rounds` 길), TPC-C와 은행 질의는 기준(3%, 1%) 안.

## 맞음과 단계마다의 시험

단계마다 같은 묶음을 돈다: 무작위 프로그램 시드 1, 2, 3, 5, 23(기본과 `PURE_SELECT=all`), 고정 소스 여섯(`BATCH`, `NESTED`,
`RECUR`, `APPEND`, `FRONT`, `GRAPH`)의 세 길, 단위 시험 세 모드와 ASan, sanitized `pure-run`, aup의 검사 두 모드, `make check`,
스위트의 세 길과 명령 수. 1단계는 `PURE_BATCH_CHECK`의 견줌을 더한다. 2단계는 정적 꼴이 지금의 동적 꼴과 같은지를 같은 방법으로
견준다(시험 빌드에서 둘 다 셈하고, 다르면 멈춘다). 견줌은 단계가 끝나면 지운다.

## 단계의 차례

1단계는 뜻을 바꾸지 않고 묶음마다의 3분의 1을 없앤다. 2단계가 이 설계의 몸통이고, 1단계의 계획 위에 선다. 3–4단계는 커널과
값의 꼴을 늘리는 일이라 2단계의 정적 꼴이 있어야 깔끔하다. 5단계는 독립이라 언제든 할 수 있다. 1단계를 잰 뒤 2단계의 버퍼와
조각의 자리를 다시 정하고, 이 문서에 적는다.