diff options
Diffstat (limited to 'docs/research')
| -rw-r--r-- | docs/research/139-batch-programs-at-load.md | 51 |
1 files changed, 49 insertions, 2 deletions
diff --git a/docs/research/139-batch-programs-at-load.md b/docs/research/139-batch-programs-at-load.md index ba4a0c9..dbfaef1 100644 --- a/docs/research/139-batch-programs-at-load.md +++ b/docs/research/139-batch-programs-at-load.md @@ -3,6 +3,18 @@ 2026-10-09. 025를 마친 뒤 남은 큰 틈(matmul의 안쪽 회차, knapsack의 묶음마다)이 무엇인지 재고, 루프마다 로드 때 짠 프로그램(026이 될 것)이 그것을 얼마나 줄일 수 있는지 시제품으로 정한다. 사용자의 말: "헷갈리는 것이 있으면 연구부터" (2026-10-09). +## 결과 (2026-10-09) + +- **막대를 넘었다(시제품).** 로드가 짤 프로그램을 손으로 옮겨 한 걸음씩 해석하면 matmul의 본 루프가 10.36 ms(같은 커널을 바로 부르면 + 7.17), knapsack이 4.16 ms(바로 3.76)다. 만들기를 더하면 matmul 약 14 ms(막대 ≤ 15, 기계어 14.2), knapsack 약 5.4 ms(막대 ≤ 6.5, + 기계어 7.9, C 6.25)다. 지금의 실행기는 25.8과 8.19 ms다. matmul의 안쪽 회차 하나에 해석이 약 82 ns(지금 약 280 ns)이고, knapsack의 + 묶음 하나에 약 0.08 µs(지금 약 0.6 µs)다. +- **짤 수 있는 범위.** 스위트의 몸체 가운데 matmul, knapsack, join의 주문 루프는 곧은 줄(스칼라 걸음과 레인 걸음, 균일한 횟수의 중첩 + 루프, 가린 쓰기, 끝의 칸에 더하기)이라 그대로 짜인다. roots(레인마다 다른 회차에 나가는 중첩 루프)와 BFS(레인 공간이 바뀌는 펼친 걷기, + 걸러내기)는 곧은 줄 밖이다. +- **그래서 026은 "곧은 줄의 프로그램, 나머지는 지금의 `pass`"다.** 2단계의 조각을 레인 걸음, 균일한 중첩 루프, 미룬 쓰기로 넓힌 꼴이다. + join은 거의 움직이지 않는다(그 110 ms는 점화식 38, 해시 찾기 19, 칸에 더하기 12로 모두 커널이다). + ## 쉬운 말로 (실험 전에 적은 것) - **남은 값은 뜻의 검사가 아니라 해석이다.** b20에서 matmul(25.8 ms)의 값은 커널 8.7, 해석 11.1(명령을 읽고 `Val`을 쌓고 꼴을 묻기), @@ -45,8 +57,43 @@ matmul의 해석 11.1 ms(안쪽 회차 4만 번, 회차마다 약 660 사이클) ## 결정할 실험 -(아래에 채운다) +`research/experiments/043-programs/programs.c`. 몸체를 바이트코드 그대로의 걸음으로 옮겼다. 스칼라 걸음(필드, 지역 변수, 루프 변수, +곱·더하기·빼기를 실행기의 규칙으로: 수는 유한, 아핀은 정수 검사; DENSE 키의 칸 읽기)과 커널 걸음(4바이트 레인: 열 읽기(4바이트면 보기, +1바이트면 넓혀 복사), 곱하기, 더하기, 비교와 1의 수)을 하나의 `switch`로 한 걸음씩 돈다. 레인 레지스터는 로드 때 정한다. 리스트의 칸은 +묶음에 한 번, 행의 범위는 양 끝, 2^32 너머는 묶음의 실패, 미룬 쓰기는 끝에서 거리를 본 뒤 가린 채로 쓴다. 작업량도 센다. 같은 커널을 +C에서 바로 부르는 길(해석 없음)과 natural.h의 C와 견줬다. 답은 모두 같았다. + +| 몸체 | 프로그램 | 바로 | 실행기 (b20) | 기계어 | C | +|---|---:|---:|---:|---:|---:| +| matmul (만들기 빼고) | **10.36 ms** | 7.17 | 약 22.2 | | 4.9 (n 상수) | +| knapsack (만들기 빼고) | **4.16** | 3.76 | 약 7.3 | | 6.23 | + +- 명령(3번): matmul 프로그램 2.58억 대 바로 1.72억(안쪽 회차마다 약 715 명령, 걸음 12개에 걸음당 약 60), knapsack 1.51억 대 1.41억. +- 걸음당 약 60 명령의 대부분은 스칼라 걸음이 아핀 값마다 정수 검사를 세 번씩 다시 하는 값이다. 로드가 범위를 아는 값(루프 변수의 + 양 끝, 필드가 정수인지, `i*n`이 2^52 안인지)은 로드 때 증명할 수 있으니, 바닥은 이보다 낮다. 막대는 그것 없이 넘었다. + +**두 번 돌아간 길이 설계의 내용이다.** 처음에는 matmul의 프로그램이 20 ms였다. 하나는 `s = s + e`를 제자리에서 해서(결과가 피연산자와 +같은 버퍼) 컴파일러의 겹침 검사가 벡터 루프를 버렸고, 하나는 레인 레지스터가 정확히 4 KB씩 떨어져 있었다. 실행기가 이미 하는 대로(결과를 +피연산자에 쓰지 않음, 버퍼를 2의 거듭제곱 간격에 두지 않음) 바꾸자 10.4 ms가 됐다. 그래서 026의 버퍼 배정 규칙은 이렇다: 레인 레지스터를 +로드 때 정하고, 레지스터마다 버퍼 둘을 두어 결과가 피연산자에 떨어지지 않게 번갈아 쓰고, 버퍼는 24 레인씩 어긋나게 둔다. 025가 미뤄 둔 +"버퍼 자리를 로드 때"(`sweep` 2.0 ms)가 이 규칙으로 풀린다. ## 짤 수 있는가: 스위트의 몸체 다섯 -(아래에 채운다) +| 몸체 | 걸음 | 곧은 줄로 짜이는가 | +|---|---|---| +| matmul 안쪽 (j 레인, k 함께) | `i*n+k`, `k*n+j`(스칼라), DENSE 칸 읽기, 1바이트 열 읽기, 곱하기, 더하기; k는 균일한 횟수; 끝에 `total += s`(레인 모으기), `last = s` | 예 | +| knapsack (항목마다) | `c = cap - k`(아핀), 열 보기 둘, 더하기, 비교와 1의 수, 가린 미룬 쓰기와 거리 검사 | 예 | +| join 주문 루프 | 점화식 `x`(회차마다, 지금의 동작 목록), 레인 산수(나누기, 내림), 레인 행의 칸 읽기, HASHED 키 찾기(레인마다), 칸에 더하기(끝에) | 예 (점화식과 해시 찾기는 지금의 커널 그대로) | +| roots (i 레인, 뉴턴 걸음) | 레인마다 다른 회차에 나가는 중첩 루프(`break`), 가린 지역 변수 쓰기, 가린 모으기, 실수 나누기 | 아니오: 레인마다의 나감 마스크가 있어야 한다 | +| BFS 프런티어 | 가드, 행마다의 조각 걷기를 간선 레인으로 펼치기(레인 공간이 바뀜), 걸러내기(`has`, 덧붙이기, 끝의 결정) | 아니오: 레인 공간 둘과 걸러내기 | + +**026의 범위(제안이 아니라 연구가 보인 꼴).** 곧은 줄의 블록(갈래가 없거나 가린 쓰기로 끝나는 갈래, 균일한 횟수의 중첩 루프, 끝의 모으기와 +칸에 더하기)을 로드 때 걸음으로 짜고, 묶음을 열 때 꼴(폭, 경계)이 맞으면 그 걸음을 돌고, 아니면 지금의 `pass`가 돈다. 2단계 조각의 자리를 +레인 걸음까지 넓힌 것이다. 셈: matmul 25.8 → 약 14 ms, knapsack 8.2 → 약 5.5 ms. join, roots, BFS는 이 범위에서 움직이지 않는다. roots와 +BFS는 그 다음 단계(레인마다의 나감 마스크; 레인 공간 둘과 걸러내기)의 일이고, 수는 아직 없다. + +**위험.** 곧은 줄의 걸음에 대해서는 지금 `pass`가 하는 뜻을 다시 짜게 된다: 묶음마다 폭으로 고르는 커널, 넘치면 4바이트에서 수로 다시, +미룬 쓰기와 의존 검사, 읽기의 기록, 작업량, 결함의 회차. 한 뜻에 두 구현이 서는 것은 025가 `pass`를 고쳐 나가며 피한 위험이다. 2단계에서 +통한 방법(견줌 빌드에서 프로그램을 마른 채로 돌리고 `pass`도 돌려 견주고, 단계가 끝나면 견줌을 지움)을 그대로 쓰되, 이번에는 스칼라가 +아니라 레인 배열을 비트까지 견줘야 하므로 더 무겁다. |