diff options
Diffstat (limited to 'docs/design')
| -rw-r--r-- | docs/design/024-batch-executor.md | 2 | ||||
| -rw-r--r-- | docs/design/025-batch-programs.md | 9 |
2 files changed, 7 insertions, 4 deletions
diff --git a/docs/design/024-batch-executor.md b/docs/design/024-batch-executor.md index 0605c4d..a0f9ce0 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배로 보인다. 레지스터 타일(값을 NEON 레지스터에 두는 해석기)을 시제품으로 재니 산수의 사슬(roots)은 C보다 빠르지만 모으기가 있는 몸체(배낭 4배, BFS 2.4배)에서 졌고, 같은 자리에서 꽉 짠 훑기는 BFS 1.2배·배낭 0.4배였다([133](../research/133-register-tiles-measured.md)): 꼴은 옳고, 묶음 프로그램을 로드 때 한 번 만들고 루프를 타입·폭·보폭으로 꽉 짜는 것이 길이다. 묶음마다의 값을 다시 재니 배낭에서 0.90 µs, 시간의 38%이고(132의 "6,500 명령"은 세 배로 잘못 나눈 수였다), 블록의 모양에서 나오는 사실은 로드 때 한 번, 값에서 나오는 사실만 묶음마다 보는 묶음 프로그램을 다섯 단계로 설계했다([025](025-batch-programs.md)). 그 1–4단계를 만들었다(134–137: knapsack 11.46 → 8.25 ms로 기계어의 1.04배, matmul 40.0 → 26.3, roots 8.97 → 8.28; 남은 큰 틈은 matmul의 안쪽 회차마다의 해석과 BFS의 후보 꼬리). +작성일: 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)): 꼴은 옳고, 묶음 프로그램을 로드 때 한 번 만들고 루프를 타입·폭·보폭으로 꽉 짜는 것이 길이다. 묶음마다의 값을 다시 재니 배낭에서 0.90 µs, 시간의 38%이고(132의 "6,500 명령"은 세 배로 잘못 나눈 수였다), 블록의 모양에서 나오는 사실은 로드 때 한 번, 값에서 나오는 사실만 묶음마다 보는 묶음 프로그램을 다섯 단계로 설계했다([025](025-batch-programs.md)). 다섯 단계를 모두 만들었다(134–138: knapsack 11.45 → 8.19 ms로 기계어의 1.04배, matmul 40.0 → 25.8, roots 8.97 → 8.29, join 117.9 → 110.5, BFS 24.2 → 23.2; 남은 큰 틈은 matmul의 안쪽 회차마다의 해석과 BFS로, 이 해석기 꼴의 바닥이다). [023](023-optimizing-tier.md)의 계층은 루프 묶음을 SSA로 올려 AArch64 기계어를 실행 시간에 만든다. 일곱 가지 일의 기하 평균을 C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-steps.md)), 실행 가능한 메모리에 코드를 쓰고 리눅스 AArch64에서만 diff --git a/docs/design/025-batch-programs.md b/docs/design/025-batch-programs.md index 994e52e..b5190b0 100644 --- a/docs/design/025-batch-programs.md +++ b/docs/design/025-batch-programs.md @@ -15,7 +15,10 @@ matmul ≤ 21 ms). 4바이트 곱하기 뒤 matmul은 26.57 ms다(명령 −20%) 일이고, 이 설계는 합친 연산을 두지 않는다(133과 같은 결론). 4단계를 닫았다([137](../research/137-batch-executor-stage-four.md): 열을 제자리에서 읽고(보기, `pass`를 넘어 남는 여섯 자리는 복사) 비교가 레인을 세어 knapsack 10.07 → 8.25 ms(막대 ≤ 8.6, 기계어의 1.04배). 남은 차는 커널이 아니라 묶음마다의 해석(약 3 ms)이다. 남은 큰 틈은 matmul의 안쪽 회차마다의 해석(루프마다 미리 짠 프로그램의 일)과 BFS의 후보 -꼬리(5단계)이고, 어느 쪽으로 갈지는 사용자의 몫이다). [024](024-batch-executor.md)가 처음에 적고 만들지 않은 단계("묶음 프로그램은 루프마다 한 번 +꼬리(5단계)이고, 어느 쪽으로 갈지는 사용자의 몫이다). 5단계를 닫아 이 설계를 마쳤다([138](../research/138-batch-executor-stage-five.md): 칸에 더하기를 정수로 한 번에(join 116.0 → +110.5, 막대 ≤ 108 못 미침: 남은 것은 같은 칸의 메모리 이어짐), `decide`의 비트를 한 번(BFS 23.2, 막대 ≤ 21.5 못 미침: 꼬리의 시간은 +명령보다 메모리), 묶음 실행기의 루프 정렬(커밋마다 6% 흔들리던 놓인 자리를 멈춤). b9 대비 matmul −36%, knapsack −28%, roots −7.6%, +join −6.2%, BFS −3.9%; 실행기, 은행 질의, TPC-C는 그대로). [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). @@ -177,9 +180,9 @@ matmul은 j를 레인 200개로 묶고 k를 레인이 함께 돈다. 묶음은 2 |---|---:|---:|---:|---:|---:|---:|---:|---:| | knapsack | 11.5 ms | ≤ 10.3 (10.34) | ≤ 9.2 (10.51) | 3단계 10.07, 4단계 ≤ 8.6 | | 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 | ≤ 21.5 (b16에서 다시) | 10.3 (꽉 짠 9.8) | 7.7 | 9.9 | +| BFS | 24.0 | ≤ 24 | ≤ 22 | ≤ 21 | ≤ 21.5 (b16에서 다시; 23.21) | 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 | | ≤ 108 (b16에서 다시) | 57.8 | 84.6 | 31.7 | +| join | 117 | ≤ 116 | ≤ 115 | | ≤ 108 (b16에서 다시; 110.5) | 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 | | | | | | |
