1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
# 139 — 루프마다 미리 짠 프로그램: 무엇이 남고, 어디까지 내려가는가 (연구)
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`을 쌓고 꼴을 묻기),
리스트의 사실 2.2(회차마다 다시 찾기), 행렬 만들기 약 3.6, 검사 0.2 ms다. 묶음마다·회차마다의 뜻의 검사는 작다. 041의 시제품은 같은
몸체를 C에서 커널 셋을 바로 불러 17.8 ms였는데(8바이트 레인), 그 C는 균일 값과 행의 시작을 스칼라로 셈하고 해석이 없었다. 지금의 4바이트
커널은 041보다 빠르다. 틈은 해석이다.
- **물음.** 레지스터 꼴의 프로그램(로드 때 짬)이, 041의 C가 공짜로 한 것(균일·아핀 걸음, 묶음에 한 번 찾는 리스트의 사실, 로드 때 정한
버퍼)을 하면서 실행기의 검사와 되돌아가기를 지키면, 회차마다의 일이 얼마나 싸지는가.
- **막대**(지금의 갈래에서 셈). matmul = 커널 8.7 + 만들기 3.6 + 검사 0.2 + 묶음에 한 번의 리스트 사실 약 0.3 + 해석 ≤ 2 ms(안쪽 회차마다
≤ 50 ns, 걸음 약 8에 약 120 사이클) → **≤ 15 ms**(기계어 14.2, 그것도 만들기를 포함한다). knapsack = 커널 4.1 + 만들기 0.9 + 검사 0.66 +
리스트 사실 약 0.3 + 해석 ≤ 0.5 → **≤ 6.5 ms**(기계어 7.9, C 6.25). 둘 다 "기계어에 닿는다"이고, 026이 약속할 것은 이것이다.
## 잰 것: b20의 갈래
방법: `b20`(`3e76a60`) `suite-run`, `PURE_JIT=0`, 2 kHz 표본, 같은 프로세스의 C로 ms를 내고 잰 시간에 맞췄다. 줄을 갈래로 나눴다:
커널(레인 루프), 해석(`pass`, 조각, 지역 변수, `uniform`, `sweep`, `word_op`의 준비, 정수 검사 …), 리스트의 사실(`find`, `cells_at`의 준비,
`rows_in`, `read_of`), 검사(`settle`, 가르기, 묶음의 앞뒤), 만들기(점화식, 덧붙이기, 리스트 쪽).
| 갈래 | matmul (25.8 ms) | knapsack (8.19 ms) |
|---|---:|---:|
| 커널 | 8.7 | 4.1 |
| 해석 | **11.1** | 1.9 |
| 리스트의 사실 | 2.2 | 0.6 |
| 검사 | 0.2 | 0.7 |
| 만들기(점화식, 덧붙이기, 리스트 쪽) | 3.6 | 0.9 |
matmul의 해석 11.1 ms(안쪽 회차 4만 번, 회차마다 약 660 사이클): 조각의 스칼라 걸음 2.0, `sweep` 2.0, `pass`의 머리 1.6, `word_op`의 준비
1.2, `uniform` 0.9, 필드 읽기 0.5, 정수 검사 0.5, 지역 변수 쓰기 0.4 ms. 모두 회차마다 같은 답을 다시 셈한다.
**025에 남은 것 하나.** `sweep`(회차마다 버퍼를 거두기)이 2.0 ms다. 025의 2단계가 "값마다의 버퍼 자리를 로드 때 정해 `fresh`·`release`·
`sweep`이 빈 버퍼를 찾지 않게" 하자고 적고, 1단계를 잰 뒤에 정한다며 미뤘다가 돌아오지 않았다. 이 연구가 그것이 어디에 들지를 정한다.
041을 이 기기에서 다시 돌렸다(`041-batches/batch.c`, 레인 256): matmul `batch_j` 17.76 ms, knapsack `u32_ops`(연산 목록을 `run()`으로
해석) 4.54 ms.
## 범위
철학 안: 루프마다 로드 때 한 번 짠 프로그램, 걸음마다 고른 C 커널, 실행 시간에 코드를 만들지 않음(024의 문장, 132의 A). 철학 밖이고 하지
않음: 합친 연산의 표, 실행 시간의 코드 만들기, 데이터에 따라 맞고 틀리는 기록-되풀이(기계어 없는 JIT). 026은 앞의 것이다.
## 결정할 실험
`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`도 돌려 견주고, 단계가 끝나면 견줌을 지움)을 그대로 쓰되, 이번에는 스칼라가
아니라 레인 배열을 비트까지 견줘야 하므로 더 무겁다.
|
