diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/024-batch-executor.md | 2 | ||||
| -rw-r--r-- | docs/research/132-batch-executor-floor-and-the-way-past.md | 8 | ||||
| -rw-r--r-- | docs/research/133-register-tiles-measured.md | 82 |
3 files changed, 90 insertions, 2 deletions
diff --git a/docs/design/024-batch-executor.md b/docs/design/024-batch-executor.md index 2ed21f5..26a4fb7 100644 --- a/docs/design/024-batch-executor.md +++ b/docs/design/024-batch-executor.md @@ -1,6 +1,6 @@ # 024 — 묶음 실행기: 기계어 없이 루프를 C 가까이 -작성일: 2026-10-05. 상태: 제안과 시제품([041](../../research/experiments/041-batches/)). 1단계를 만들었다([126](../research/126-batch-executor-stage-one.md): knapsack이 실행기에서 1,041 ms → 13.6 ms, 안쪽 루프는 계층의 1.17배로 기준 미달). 2단계(중첩 루프를 함께, 모으기)를 만들었다([127](../research/127-batch-executor-stage-two.md): roots 9.13 ms로 계층 9.57보다 빠름, matmul 50 ms). 4단계의 앞 절반(덧붙이기), 5단계(점화식), 칸에 더하기, 걷기를 만들었다([128](../research/128-batch-executor-tables-and-costs.md): join이 실행기의 423에서 161 ms, 계층 74). 남은 값은 덧붙이기 하나 약 100 ns, join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 아직 묶이지 않는다(바뀌는 개수, 커지기만 하는 걸러내기, 중첩 걷기가 필요하다). 그 셋을 줄였다([129](../research/129-batch-executor-costs-cut.md): 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기; knapsack 10.8, matmul 36.4, join 118 ms, roots 8.87로 계층 9.57보다 빠름). BFS를 셈하니 차례대로 할 꼬리가 간선의 약 10%라, 꼬리를 묶음의 C로 하고 간선을 레인으로 펼치면 계층과 겨룰 만하다(약 6–7 ms 예상). 가드, 묶음 안의 걷기(함께, 펼치기), 걸러내기를 만들어 BFS가 묶음으로 돈다([130](../research/130-batch-executor-frontiers.md): 93 → 41 ms, 계층 7.7). 간선당 명령은 211개(계층 38.5)이고, 후보만 골라 돌게 해도 연산마다 레인을 훑는 꼴의 바닥이 약 50개라, 계층을 넘으려면 합친 연산의 표가 필요하다. 사용자는 범용의 길을 택했다(2026-10-08). 같은 코드의 값 다시 쓰기, `if !c`의 분기 하나, 고르기(적은 레인의 갈래를 그 레인만), 비트로 묻기, 아핀 `first + i`로 BFS가 간선당 112개, 24.0 ms가 됐다([131](../research/131-batch-executor-general-cuts.md)); 범용의 바닥은 계층의 약 2배로 보인다. +작성일: 2026-10-05. 상태: 제안과 시제품([041](../../research/experiments/041-batches/)). 1단계를 만들었다([126](../research/126-batch-executor-stage-one.md): knapsack이 실행기에서 1,041 ms → 13.6 ms, 안쪽 루프는 계층의 1.17배로 기준 미달). 2단계(중첩 루프를 함께, 모으기)를 만들었다([127](../research/127-batch-executor-stage-two.md): roots 9.13 ms로 계층 9.57보다 빠름, matmul 50 ms). 4단계의 앞 절반(덧붙이기), 5단계(점화식), 칸에 더하기, 걷기를 만들었다([128](../research/128-batch-executor-tables-and-costs.md): join이 실행기의 423에서 161 ms, 계층 74). 남은 값은 덧붙이기 하나 약 100 ns, join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 아직 묶이지 않는다(바뀌는 개수, 커지기만 하는 걸러내기, 중첩 걷기가 필요하다). 그 셋을 줄였다([129](../research/129-batch-executor-costs-cut.md): 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기; knapsack 10.8, matmul 36.4, join 118 ms, roots 8.87로 계층 9.57보다 빠름). BFS를 셈하니 차례대로 할 꼬리가 간선의 약 10%라, 꼬리를 묶음의 C로 하고 간선을 레인으로 펼치면 계층과 겨룰 만하다(약 6–7 ms 예상). 가드, 묶음 안의 걷기(함께, 펼치기), 걸러내기를 만들어 BFS가 묶음으로 돈다([130](../research/130-batch-executor-frontiers.md): 93 → 41 ms, 계층 7.7). 간선당 명령은 211개(계층 38.5)이고, 후보만 골라 돌게 해도 연산마다 레인을 훑는 꼴의 바닥이 약 50개라, 계층을 넘으려면 합친 연산의 표가 필요하다. 사용자는 범용의 길을 택했다(2026-10-08). 같은 코드의 값 다시 쓰기, `if !c`의 분기 하나, 고르기(적은 레인의 갈래를 그 레인만), 비트로 묻기, 아핀 `first + i`로 BFS가 간선당 112개, 24.0 ms가 됐다([131](../research/131-batch-executor-general-cuts.md)); 범용의 바닥은 계층의 약 2배로 보인다. 레지스터 타일(값을 NEON 레지스터에 두는 해석기)을 시제품으로 재니 산수의 사슬(roots)은 C보다 빠르지만 모으기가 있는 몸체(배낭 4배, BFS 2.4배)에서 졌고, 같은 자리에서 꽉 짠 훑기는 BFS 1.2배·배낭 0.4배였다([133](../research/133-register-tiles-measured.md)): 꼴은 옳고, 묶음 프로그램을 로드 때 한 번 만들고 루프를 타입·폭·보폭으로 꽉 짜는 것이 길이다. [023](023-optimizing-tier.md)의 계층은 루프 묶음을 SSA로 올려 AArch64 기계어를 실행 시간에 만든다. 일곱 가지 일의 기하 평균을 C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-steps.md)), 실행 가능한 메모리에 코드를 쓰고 리눅스 AArch64에서만 diff --git a/docs/research/132-batch-executor-floor-and-the-way-past.md b/docs/research/132-batch-executor-floor-and-the-way-past.md index c526f05..dafb7d8 100644 --- a/docs/research/132-batch-executor-floor-and-the-way-past.md +++ b/docs/research/132-batch-executor-floor-and-the-way-past.md @@ -151,7 +151,13 @@ A와 E를 만들고 기계어를 남긴다.** 반나절이다. 결과가 기준을 넘으면 B의 설계(025)를 쓰고, 넘지 못하면 그 수를 적고 A와 E로 간다. -## 추천 +## 결과 (2026-10-08, [133](133-register-tiles-measured.md)) + +실험을 돌렸다. roots는 기계어의 0.71배로 기준을 넘었고, 배낭은 4배, BFS는 2.4배로 넘지 못했다(NEON에 모아 읽기가 없어 레인마다 +꺼내고 넣는 값). 같은 실험에서 지금의 꼴(연산마다 훑기)을 꽉 짜면 BFS가 기계어의 1.2배, 배낭이 0.4배였다. 그래서 B는 접고 A를 +끝까지 간다: 꼴이 아니라 구현이 3배였다. + +## 추천 (실험 전에 적은 것) A는 어느 길에서나 필요하고 범용이므로 먼저 만들어도 된다. B는 실험 뒤에 정한다. 지금 가진 수로 보면 B가 유일한 근본적인 길이고, 문헌(Gubner & Boncz의 레지스터 집계, Sompolski의 "벽돌")은 값을 레지스터에 두는 것이 벡터 해석의 남은 길이라는 데 모인다. diff --git a/docs/research/133-register-tiles-measured.md b/docs/research/133-register-tiles-measured.md new file mode 100644 index 0000000..de478da --- /dev/null +++ b/docs/research/133-register-tiles-measured.md @@ -0,0 +1,82 @@ +# 133 — 레지스터 타일을 재다: 산수에는 이기고 모으기에는 지며, 훑기의 꼴은 옳았다 + +2026-10-08. [132](132-batch-executor-floor-and-the-way-past.md)가 정한 실험. 런타임은 건드리지 않고 +`research/experiments/042-tiles/`의 C 시제품으로 세 몸체(배낭의 안쪽, BFS의 프런티어, roots의 뉴턴)를 레지스터 타일로 돌려 +요소당 사이클을 기계어와 견줬다. 기준은 "셋 모두 기계어의 1.3배 안". 결과는 **roots는 0.71배로 넘고, 배낭은 4배, BFS는 2.4배로 +못 넘는다.** 같은 실험이 덤으로 보인 것이 더 중요하다. **지금의 꼴(연산마다 레인을 훑기)을 꽉 짜면 BFS가 기계어의 1.2배, 배낭은 +0.4배다.** 묶음 실행기의 3배는 꼴의 값이 아니라 구현의 값이다. + +## 쉬운 말로 + +- **레지스터 타일은 범용의 답이 아니다.** 값을 NEON 레지스터에 두면 산수의 사슬(roots)은 C보다 빨라진다. 그러나 레인마다 다른 + 자리를 읽고 쓰는 일(배낭의 표, BFS의 `to`와 비트)은 레인 하나씩 꺼내고 넣어야 한다. 이 기기(Cortex-A76)의 NEON에는 모아 + 읽기(gather)가 없다. 그래서 모으기가 있는 몸체는 레지스터를 거치는 것이 메모리의 배열을 스칼라로 훑는 것보다 느리다. +- **그 자리에서 잰 "꽉 짠 훑기"가 기계어에 닿았다.** BFS의 프런티어를 훑기 셋(`to` 모으기, 비트 묻기, 후보 고르기)과 꼬리로 돌리면 + 9.8 ms다. 기계어 7.7, C 8.6, 지금의 묶음 실행기 24.0이다. 배낭을 4바이트 레인과 보폭 읽기의 훑기 둘로 돌리면 2.9 ms다(clang). + 기계어 7.9, C 6.2, 묶음 실행기 11.4다. +- **그러니 근본적인 길은 꼴을 바꾸는 것이 아니라 꼴을 끝까지 짜는 것이다.** 묶음 프로그램을 로드 때 한 번 만들어 묶음마다의 + 고정 값을 없애고, 레인의 타입과 폭과 보폭이 정해진 꽉 짠 루프를 묶음마다 고르고, 검사를 요소에서 묶음으로 올린다. 132의 + A다. 레지스터 타일은 산수의 사슬에만 쓸 수 있는 선택지로 남긴다. + +## 시제품 + +- **첫 꼴**(`make.py`): 함수 하나 안의 계산된 goto. 슬롯 여섯(벡터 변수)에 깊이마다 레이블. GCC가 레이블 사이에서 슬롯을 모두 + 스택에 내렸다(`ldp q.. [sp]`, `stp`). 연산마다 적재·저장이 돌아와 훑기보다 느렸다(배낭 43 ms, roots 11.6, BFS 15.6). 간접 + 분기 뒤에서 레지스터를 지키지 않는 컴파일러의 값이다. +- **둘째 꼴**(`make2.py`): 연산마다 함수, 슬롯은 인자(동질 벡터 집합: AAPCS64가 v0–v7에 넘긴다), 다음 연산으로 꼬리 호출 + (clang `musttail`, GCC 형제 호출). 연산이 벡터 명령 몇 개, 다음 주소 적재, 분기로 끝난다(`fadd, fadd, ldr, br`). 슬롯 넷에 + 레지스터 둘씩(레인 4, `2 4`), 또는 슬롯 여덟에 하나씩(레인 2, `1 8`). 연산은 슬롯을 이름으로 부르는 3주소 꼴이라 (연산, 슬롯들) + 마다 함수를 만든다(프로그램이 쓰는 것만). +- 몸체 셋은 Pure의 뜻 그대로다(수는 double, 레인마다의 결함 검사는 뺐다). 답을 C와 견줘 같았다. + +## 잰 것 + +Pi 5, 3번 중 가장 짧은 것. 기계어는 스위트의 수다(배낭 7.9 ms, roots 9.57, BFS 7.7). + +| 몸체 | 타일 (레인 4, clang) | 타일 (레인 4, gcc) | 타일 (레인 2) | 꽉 짠 훑기 | C | 기계어 | 묶음 실행기 | +|---|---:|---:|---:|---:|---:|---:|---:| +| roots | **5.8 ms** | 6.7 | 9.7 | — | 6.9 | 9.57 | 8.97 | +| knapsack | 29.4 | 41.6 | 35.8 | **2.9** (gcc 9.6) | 6.2 | 7.9 | 11.4 | +| BFS | 18.1 | 23.7 | 19.6 | **9.8** | 8.6 | 7.7 | 24.0 | + +요소당(명령/사이클, `icount`, 11번과 1번의 차): + +| 몸체 | 타일 (레인 4, clang) | 기계어 | 묶음 실행기 | +|---|---:|---:|---:| +| roots, 뉴턴 걸음 하나 | — / 13 | — / 18.6 | — / 17.4 | +| knapsack, 회차 하나 | 35 / 15 | 8 / 3.8 | — / 5.7 | +| BFS, 간선 하나 | — / 47 | 38.5 / 19 | 112 / 57 | + +- **roots가 이기는 이유.** 레인 넷의 나눗셈 사슬이 레지스터 둘에서 함께 돌아 나눗셈의 지연을 겹친다. C는 사슬 하나씩이다. + 디스패치는 걸음마다 10번, 4레인이라 걸음당 2.5번이고 한 번이 명령 4개다. +- **배낭이 지는 이유.** `GATHER4` 하나가 레인 넷에 명령 18개다. 벡터에서 꺼내(`fmov`, `mov`), 정수로 바꾸고(`fcvtzu`), 읽고, + 다시 넣는다(`ucvtf`, `mov v.d[1]`). 회차마다 모으기 둘과 마스크 쓰기 하나라 회차당 35개다. 기계어는 스칼라 8개다. +- **BFS가 지는 이유.** 같다. `to` 모으기, 비트 묻기, 후보 고르기가 레인마다 꺼내고 넣는다. 꽉 짠 훑기 셋은 스칼라 루프라 컴파일러가 + 잘 짜고, 간선당 약 23 사이클이다(기계어 19). +- **꽉 짠 훑기가 배낭에서 C를 이기는 이유.** 4바이트 레인을 보폭 −1로 읽어 더하는 훑기 하나, 읽어 견줘 큰 쪽을 쓰는 훑기 하나. + clang이 둘 다 벡터로 짠다(gcc는 거꾸로 가는 색인을 벡터로 짜지 못해 9.6 ms: 묶음 실행기가 레인을 거꾸로 번호 매기는 까닭이 + 여기 있다). 묶음 실행기는 같은 회차를 훑기 여섯으로 하고 묶음마다 6,500 명령을 더 내서 5.7 사이클이다. + +## 뜻 + +1. **꼴은 옳다.** 연산마다 레인을 훑는 묶음 실행기의 꼴은 이 기기에서 모으기가 있는 몸체에 가장 알맞다. 레지스터 타일은 산수의 + 사슬에만 낫다(roots). 그러나 roots는 묶음 실행기도 이미 기계어보다 빠르다. 타일을 두 번째 기계로 더할 까닭이 지금은 없다. +2. **3배는 구현이다.** 같은 훑기라도 범용 루프(값의 꼴을 레인마다 묻고, 범위를 레인마다 보고, 8바이트로 넓히고, 마스크를 따로 + 만드는)와 꽉 짠 루프(타입·폭·보폭이 정해진)의 차가 2–4배다. 그 위에 묶음마다의 고정 값(6,500 명령)과 훑기의 수(배낭 6 대 2, + BFS 10여 대 3)가 얹힌다. +3. **합치기 없이 어디까지.** 꽉 짠 훑기의 배낭 2.9 ms는 컴파일러가 연산 둘셋을 훑기 하나에 합친 값이다. 합치지 않으면 훑기 여섯에 + 회차당 약 5–6 사이클로 기계어의 1.5배다. BFS는 훑기 셋이 이미 연산 셋이라 1.2배다. 범용의 길로는 "기계어의 1.2–1.5배"가 + 배낭과 BFS의 바닥이고, roots처럼 사슬이 있는 일은 기계어 아래다. + +## 다음: 132의 A를 끝까지 + +- **묶음 프로그램을 로드 때 한 번.** 블록을 묶음마다 다시 읽지 않는다. 명령마다 피연산자의 꼴(균일·아핀·레인)과 폭, 읽기의 보폭, + 쓰기의 마스크, 미룬 효과의 차례, 검사(2^53, 범위, 유한)의 자리를 정해 둔다. 묶음을 열 때는 그 프로그램대로 꽉 짠 루프를 고른다. +- **꽉 짠 루프.** 타입과 폭과 보폭이 정해진 루프를 빌드 때 C로 둔다(표가 아니라 연산 하나하나의 타입 변형이다). 범위 검사는 레인의 + 최소·최대로 묶음에 한 번. 거꾸로 가는 읽기는 레인의 번호를 거꾸로 매겨 메모리의 차례로(이미 한다). +- **훑기의 수.** 즉시 피연산자(`ADDK`), 보폭 읽기를 피연산자로(열에서 바로), 비교를 마스크로 바로 쓰기(이미 한다), 고르기(이미 + 한다). 합친 연산의 표는 두지 않는다. +- **후보의 꼬리**(132의 E)는 그대로 유효하다. +- **레지스터 타일**은 접어 둔다. 산수의 사슬이 긴 일이 기계어보다 느려지면 그때 꺼낸다. + +측정의 원본은 `042-tiles/2026-10-08-tiles.jsonl`이다(`make.py`와 `make2.py`로 다시 만들 수 있다). |