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
|
# 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`로 다시 만들 수 있다).
|
