diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/025-batch-programs.md | 6 | ||||
| -rw-r--r-- | docs/research/135-batch-plans-stage-two.md | 66 |
2 files changed, 71 insertions, 1 deletions
diff --git a/docs/design/025-batch-programs.md b/docs/design/025-batch-programs.md index cbb125f..f6a310e 100644 --- a/docs/design/025-batch-programs.md +++ b/docs/design/025-batch-programs.md @@ -1,7 +1,11 @@ # 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단계의 몫이다). [024](024-batch-executor.md)가 처음에 적고 만들지 않은 단계("묶음 프로그램은 루프마다 한 번 +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). [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). diff --git a/docs/research/135-batch-plans-stage-two.md b/docs/research/135-batch-plans-stage-two.md new file mode 100644 index 0000000..bb7de19 --- /dev/null +++ b/docs/research/135-batch-plans-stage-two.md @@ -0,0 +1,66 @@ +# 135 — 묶음 프로그램 2단계: 균일·아핀 조각은 중첩 회차의 수단이었다 + +2026-10-08. [025](../design/025-batch-programs.md)의 2단계다. 묶음 루프의 블록에서 균일·아핀 값 하나를 만드는 명령의 줄(조각)을 +로드 때 찾아 두고, 묶음이 그 첫 명령에 닿으면 스칼라로 한 번에 돈다. 코드는 `c81f65e`(조각과 견줌)와 견줌을 지운 커밋이다. +잰 것은 `b11` = `c81f65e`를 `b10`(1단계)과 번갈아 돈 것이다(134와 같은 방법). + +## 쉬운 말로 + +- **막대에 못 미쳤다.** 배낭은 10.35에서 10.51 ms다(막대 ≤ 9.2). 묶음마다 값은 0.68에서 0.63 µs다(막대 ≤ 0.45). matmul은 + 38.18에서 36.10 ms다(막대 ≤ 33). sum0의 묶음마다 명령은 1,822에서 1,743이다(막대 ≤ 1,300). +- **셈이 틀렸다.** 025는 조각이 덮는 명령(필드, 지역 변수, 균일한 행의 항목 읽기, 산수)을 명령 하나에 약 50 사이클로 셈했다. + 명령 수로 보면 조각은 명령 하나에 약 25 명령을 덜 낸다. 배낭의 묶음마다 값은 조각이 건드리지 않는 곳에 있다. 키로 찾기 셋, + 경계, 읽기의 기록, 4바이트 연산의 준비, 가르기의 마스크, 미룬 쓰기의 확인이다. +- **조각은 중첩 회차의 수단이다.** matmul은 j를 레인으로 묶고 k를 레인이 함께 도는데, 안쪽 회차마다 몸체를 해석한다(메시지 하나에 + 4만 번). 그 몸체의 `i * go.n + k`, `k * go.n + j`, `a[..].v`가 조각이라 명령이 4.5% 줄었고, 시간도 5.4% 줄었다. +- **배낭이 느려진 것은 놓인 자리다.** 명령은 1% 적다. 묶음마다 값은 줄었는데(0.05 µs × 4,886 = 0.25 ms), 조각이 건드리지 않는 + 요소마다의 부분이 0.4 ms 늘었다. 같은 소스의 루프가 다른 자리에 놓였다(`words_op`의 더하기 루프가 64바이트 줄의 28에서 60으로). +- **뜻.** 이 해석기의 꼴로는 배낭 같은 블록의 묶음마다 값이 약 0.6 µs에서 멈춘다. 그 아래는 루프마다 미리 짠 프로그램(값의 꼴과 + 리스트의 사실과 의존 검사를 다 미리 정한 것)이 있어야 하고, 그것은 다른 값과 위험이다. 그래서 다음 노력은 요소마다로 간다. + 배낭은 요소마다에 약 6 ms, matmul은 실수 연산에 약 22 ms가 있다. 묶음마다는 배낭에서 약 3 ms다. + +## 잰 것 + +| 일 | `b10` | `b11` | 레인 256 (`b11`) | 명령 (`b10` → `b11`) | 사이클 | +|---|---:|---:|---:|---:|---:| +| knapsack | 10.35 ms | 10.51 | 19.64 (`b10` 20.24) | −0.96% | +1.1% | +| matmul | 38.18 | **36.10** | | −4.52% | −4.9% | +| roots | 8.81 | 8.82 | 10.47 | +0.24% | 0.0% | +| join | 117.19 | 115.92 | 119.91 | −0.33% | +1.9% | +| BFS | 24.25 | 24.17 | 25.62 | +0.43% | +1.9% | + +- **배낭의 묶음마다**: (19.64 − 10.51) / 14,490 = 0.63 µs(`b10` 0.68). +- **sum0과 ops0의 묶음마다**(`icount`): sum0 1,822 → 1,743 명령, ops0 1,658 → 1,561 명령. sum0의 블록(`let f = i + 1`, 모으기, + `let z = f`)에서 조각은 첫 줄 하나다. +- 실행기만의 길은 명령이 그대로다(사이클은 join +3.5%, BFS −3.1%: 놓인 자리). + +원본: `041-batches/2026-10-08-pairs.jsonl`, `2026-10-08-counts.jsonl`. + +## 만든 것 + +- **조각**(`plan_segments`, 로드 때). 계획의 다른 몫(칸에 더하기, 점화식, 모으기의 앞, 같은 코드의 값)이 없고, 안에 점프가 떨어지지 + 않는 명령의 줄로, 두 개 이상이고, 스스로 만든 값만으로 값 하나를 만든다. 넣는 명령: 상수, LOAD, 필드, INDEX_LOAD, 행(루프 자신의 + 걷기와 블록 안의 걷기가 아닌 것), 블록이 쓰지 않는 지역 변수, 루프 변수, 중첩 세는 루프의 변수(그 블록 안), 앞에서 조각이 한 번 + 쓴 지역 변수, 균일한 행의 항목 읽기(FIND에 붙은 읽기는 빼고), NEG·NOT(JZ 앞은 빼고)·FLOOR, 산수와 비교. 문장이 거기서 끝나면 그 + `LOCAL_STORE`도. +- **조각 돌기**(`segment`). 값마다 스칼라(균일, 또는 아핀의 첫 레인과 보폭)로 명령마다의 길과 같은 규칙(`number_op`, `affine_op`, + `affine_of`, 같은 경계)을 쓴다. 값이 계획과 다르면(지역 변수가 레인이다, 정수가 아니다, 결함, 리스트 끝 너머) 아무것도 하지 않고 + 명령마다의 길이 그 줄을 돈다. 고르기 안과 펼친 걷기 안에서는 돌지 않는다. 항목 읽기의 기록(`read_of`)은 조각이 끝까지 간 뒤에만 한다. +- **견줌**(`PURE_BATCH_CHECK`). 만드는 동안 조각을 값만 셈하고(마른 걸음), 명령마다의 길이 같은 줄을 돈 뒤 쌓인 값과 견줬다. 시드 + 23의 프로그램을 돌린 650번 가운데 213번이 조각을 지났고, 조각 312,249번이 모두 같았다. 다 지난 뒤 지웠다. +- **하지 않은 것: 리스트의 칸을 묶음마다 한 번.** `pass` 안에서 칸을 가져오는 곳은 둘(`item_get`, `find`)이고, 묶음마다 2–3번, + 약 50 사이클(3%)이다. 하지 않았다. + +## 뜻과 맞음 + +- 견줌 빌드에서 시드 1, 2, 3, 5, 23의 무작위 프로그램(기본과 `PURE_SELECT=all`), 고정 소스 여섯의 세 길(두 모드), 단위 시험 세 + 모드가 지났다. +- 견줌을 지운 빌드에서 단위 시험 세 모드, ASan 단위 시험(기본과 실행기 모드), sanitized `pure-run`의 고정 소스(두 모드)와 시드 23의 + 프로그램(두 모드), Pure의 `make check`, aup의 검사 두 모드가 지났다. TPC-C와 은행 질의는 재지 않았다(실행기는 그대로, 명령 수 같음). + +## 다음 + +3단계부터 요소마다로 간다. 첫째는 `words_op`의 곱하기다. matmul은 1바이트 열에서 읽은 값을 곱하는데, 4바이트 레인에 곱하기가 없어 +8바이트 실수로 바꾸고 유한 검사를 한다(`binary` 16.7, `numbers` 3.0, `cells_at` 2.1 ms). 64비트 곱으로 넘침을 보는 4바이트 +곱하기면 요소 800만 개에 약 1.5–2 사이클, 5–7 ms다. 막대는 matmul ≤ 21 ms다(041의 천장 17.75는 4단계의 몫). 그다음 모으기의 균일한 +e(sum0의 80%), 그다음 배낭의 훑기(4단계). |
