diff options
Diffstat (limited to 'docs/design')
| -rw-r--r-- | docs/design/025-batch-programs.md | 32 |
1 files changed, 22 insertions, 10 deletions
diff --git a/docs/design/025-batch-programs.md b/docs/design/025-batch-programs.md index 6f2c7fe..cbb125f 100644 --- a/docs/design/025-batch-programs.md +++ b/docs/design/025-batch-programs.md @@ -100,6 +100,14 @@ matmul은 j를 레인 200개로 묶고 k를 레인이 함께 돈다. 묶음은 2 ### 2단계: 값의 꼴을 로드 때, 리스트의 사실은 묶음에 한 번 +(1단계 뒤에 다시 정한 꼴, 134.) 2단계는 `pass`를 다시 쓰지 않는다. 계획이 균일·아핀만으로 된 조각을 찾아 두고, 묶음이 그 조각의 +첫 명령에 닿으면 조각을 스칼라 걸음으로 한 번에 돈다. 걸음은 명령마다의 길과 같은 규칙(`number_op`, `affine_of`, 같은 검사)을 +쓰고, 어느 하나라도 맞지 않으면(지역 변수가 레인이다, 아핀이 정수가 아니다, 고르기나 펼친 걷기 안이다) 아무것도 쌓지 않고 명령마다의 +길이 그 조각을 그대로 돈다. 그래서 뜻은 바뀌지 않는다. 조각에 드는 명령은 상수, LOAD, 필드, 블록이 쓰지 않는 지역 변수, 루프 변수, +앞에서 조각이 쓴 지역 변수(중첩 루프의 변수도), 행(걷기의 항목), 균일한 행의 항목 읽기, 산수와 비교다. 조각이 `LOCAL_STORE`로 +끝나면 지금의 `local_store`를 부른다. 같은 코드의 값, 모으기의 앞, 점화식과 칸에 더하기의 자리는 조각에 넣지 않는다. 리스트의 +칸(`pure_list_cells`)은 묶음마다 리스트에 한 번 가져온다(미룬 쓰기가 끝에 있어 `pass` 동안 바뀌지 않는다). + - **정적 꼴.** 블록의 pc마다 결과가 균일·아핀·레인 가운데 무엇인지 로드 때 셈한다. 루프 변수는 아핀, 블록이 쓰지 않는 지역 변수와 LOAD·필드·상수는 균일, 균일과 아핀의 더하기·빼기는 아핀, 양수 균일과 아핀의 곱은 아핀(부호는 값이라 묶음을 열 때 확인하고, 아니면 지금처럼 레인), 레인에서 읽은 것은 레인. 지금 `pass`가 묶음마다 하는 꼴의 셈과 같은 규칙이다. @@ -147,19 +155,23 @@ matmul은 j를 레인 200개로 묶고 k를 레인이 함께 돈다. 묶음은 2 | 일 | 지금 (`b9`) | 1단계 | 2단계 | 3–4단계 | 5단계 | 천장 (041) | 기계어 | C | |---|---:|---:|---:|---:|---:|---:|---:|---:| -| knapsack | 11.5 ms | ≤ 10.3 | ≤ 8.0 | ≤ 6.0 | | 4.55 (꽉 짠 두 훑기 1.87) | 7.9 | 6.25 | -| matmul | 40.0 | ≤ 39 | ≤ 30 | ≤ 17.75 | | 17.75 | 14.2 | 7.6 | +| knapsack | 11.5 ms | ≤ 10.3 (10.34) | ≤ 9.2 | ≤ 6.0 | | 4.55 (꽉 짠 두 훑기 1.87) | 7.9 | 6.25 | +| matmul | 40.0 | ≤ 39 (38.2) | ≤ 33 | ≤ 17.75 | | 17.75 | 14.2 | 7.6 | | BFS | 24.0 | ≤ 24 | ≤ 22 | ≤ 21 | ≤ 18 | 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 | | ≤ 110 | 57.8 | 84.6 | 31.7 | -| 묶음마다 (배낭) | 0.90 µs | ≤ 0.60 | ≤ 0.15 | | | | | | -| 묶음마다 (sum0, `icount`) | 2,330 명령 | ≤ 1,550 | ≤ 600 | | | | | | - -- **knapsack.** 1단계는 블록 다시 읽기(묶음마다의 3분의 1 남짓, 약 1.5 ms)를 없애 약 10.0 ms다. 2단계는 묶음마다를 0.15 µs(0.7 ms)로 해서 - 11.5 − 4.4 + 0.7 = 7.8 ms다. 4단계의 훑기 셋은 요소마다 약 6 ms를 약 3.5로 줄여 약 5.3 ms다. 막대는 그보다 조금 느슨하다. - 131에서 생긴 10%(b7 10.32)는 1단계에서 되찾는다. -- **matmul.** 안쪽 회차마다의 디스패치 약 13 ms 가운데 1단계는 찾기(`pass`의 몫 일부)만, 2단계가 꼴과 리스트의 사실을 없애 약 - 3 ms로 한다(≤ 30). 3단계는 곱과 더하기를 4바이트로 해서 연산 약 22 ms를 약 9 ms로 한다(요소 8M × 약 2.5 사이클). 막대는 041의 +| 묶음마다 (배낭) | 0.90 µs | ≤ 0.60 (0.68) | ≤ 0.45 | | | | | | +| 묶음마다 (sum0, `icount`) | 2,330 명령 | ≤ 1,550 (1,822) | ≤ 1,300 | | | | | | + +- **knapsack.** 1단계는 블록 다시 읽기(묶음마다의 3분의 1 남짓, 약 1.5 ms)를 없애 약 10.0 ms라 셈했고, 10.34 ms였다(134: + `pass`의 명령마다 머리를 찾기로 셈한 탓). 2단계(1단계 뒤에 다시 셈했다): 안쪽 루프의 명령 24개 가운데 조각이 덮는 것은 + 10–12개다(용량에서 k 빼기, `c - it.weight`, `it.worth`). 키로 찾기 셋, 레인 연산, 미룬 쓰기는 그대로다. 명령 하나 약 50 + 사이클을 조각의 걸음 약 5 사이클로 바꾸면 묶음마다 약 500 사이클, 칸을 한 번에 가져오면 약 100 사이클이 준다. 0.68 → 약 + 0.43 µs, 배낭은 10.34 − 4,886 × 0.25 µs ≈ 9.1 ms다. 기계어(7.9)에 닿으려면 4단계의 훑기 셋이 있어야 한다: 요소마다 약 6 ms를 + 약 3.5로 줄여 약 6.5 ms다. +- **matmul.** 안쪽 회차마다의 디스패치 약 13 ms 가운데 1단계는 찾기(`pass`의 몫 일부)만 없앴다(시간은 38.2 ms지만 명령 수가 + 같아 놓인 자리다). 2단계: 안쪽 회차의 몸체 약 16 명령 가운데 `i * go.n + k`, `k * go.n + j`, `a[..].v`의 10–12개가 조각이라, + 회차마다 약 500 사이클 × 4만 회차 ≈ 8 ms가 줄 수 있다. 막대는 그 절반을 남겨 ≤ 33이다. 3단계는 곱과 더하기를 4바이트로 해서 연산 약 22 ms를 약 9 ms로 한다(요소 8M × 약 2.5 사이클). 막대는 041의 천장이다. - **BFS.** 간선당 112 명령에서 노드마다 20을 약 10으로(1–2단계), 비교와 세기를 합쳐 약 5를(4단계), 후보의 26을 약 10으로(5단계) 줄이면 약 80 명령, 약 17 ms다. |