# Performance Take-Home 최적화 리포트

gistfile1.txt

# Performance Take-Home 최적화 리포트

## 1. 최종 결과

| 지표 | 값 |
|---|---|
| **최종 cycle count** | **1,229** |
| **Baseline 대비 speedup** | **120.2x** (147,734 → 1,229) |
| **테스트 통과** | 9/9 (모든 correctness + 모든 speed threshold) |
| **`tests/` 변경** | 없음 (anti-cheating 준수) |
| **`problem.py` 변경** | 없음 |

## 2. Benchmark 비교

| 벤치마크 | 임계값 | 우리 결과 | 차이 |
|---|---:|---:|---:|
| Baseline | 147,734 | 1,229 | -146,505 |
| Updated starting point | 18,532 | 1,229 | -17,303 |
| Opus 4 (many hours) | 2,164 | 1,229 | -935 |
| Opus 4.5 (casual) | 1,790 | 1,229 | -561 |
| Opus 4.5 (2hr) | 1,579 | 1,229 | -350 |
| Sonnet 4.5 (many hours) | 1,548 | 1,229 | -319 |
| Opus 4.5 (11hr) | 1,487 | 1,229 | -258 |
| **Opus 4.5 improved harness** | **1,363** | **1,229** | **-134** |

## 3. 최적화 진행 경로

```
147,734 (baseline)
   ↓
 18,532 (개선된 시작점)
   ↓
  1,995 (수작업 최적화 시작)
   ↓
  1,866 (group-major emission)
   ↓
  1,651 (POOL=32 + hash mul_add fusion)
   ↓
  1,488 (per-lane alu 활용)
   ↓
  1,415 (SA + 단일 knob mutation)
   ↓
  1,403 (Beam search, 다중 knob)
   ↓
  1,386 (12-worker parallel + crossover)
   ↓
  1,284 (Subagent: last2_rounds_alternate emit + per-pool size) ← 1363 돌파
   ↓
  1,277 (PRECOMPUTE_STORE_ADDRS)
   ↓
  1,247 (Subagent: VLOAD level3 + Hash 2+3 fusion + offset_rev)
   ↓
  1,230 (knob 조합 search)
   ↓
  1,229 (Flow engine add_imm)  ← 최종
```

## 4. 핵심 기술적 발견

### 4.1 알고리즘적 변경 (cycle 큰 폭 감소)

**Hash Stage 2+3 융합 (–22 cycles)**
- Stage 2 (fused): `y = 33*x + c2`
- Stage 3 (non-fused): `out = (y + c3) ^ (y << 9)` (3 valu ops, depth 3)
- 대수적 분배:
  - `y + c3 = mul_add(x, 33, c2+c3)` (1 op)
  - `y << 9 = (33*512)*x + (c2<<9) = mul_add(x, 16896, c2<<9)` (1 op, parallel)
  - `out = XOR them` (1 op)
- 결과: 3 ops, depth 2 (–1 valu cycle per round)
- **유일한 알고리즘적 fusion** (4+5, 0+1은 수학적으로 불가능 — XOR이 +/*에 distributive 아님)

**VLOAD for Level 3 setup (–22 cycles)**
- Level 3 select 셋업: 8개 forest 값 (consecutive memory)
- 기존: 8 scalar loads
- 변경: 1 vload (8 lanes 한 번에)
- Load engine slot 14개 절약 (init ramp 단축)

**EMIT_ORDER `last2_rounds_offset_rev` (–79 cycles, 가장 큰 단일 변경)**
- R0..R13: group_major (g=0..31)
- R14, R15: `[29, 28, ..., 0, 31, 30]` 순서 (shift=2 reverse)
- 효과: last group의 R14가 일찍 끝나서 R15 chain이 다른 그룹과 자연스럽게 interleaved

### 4.2 구조적 최적화

**Per-pool POOL_SIZE 분리 (–7 cycles)**
- 기존: 모든 pool이 같은 POOL_SIZE
- 변경: `POOL_SIZE_VTMP_A=32, POOL_SIZE_VTMP_B=32, POOL_SIZE_SCATTER=24`
- vtmp_b의 WAW dependency가 binding constraint이었음

**PRECOMPUTE_STORE_ADDRS (–7 cycles)**
- 기존: vstore 16개가 1 store/cycle로 직렬화 (per-store address increment의 RAW)
- 변경: 32개 store address 모두 사전 계산 → 2 stores/cycle 가능
- Final drain 18 → 2 cycles

**FOREST_P_FUSED_OUT_ROUNDS (–수 cycles)**
- Cross-round chain `idx → forest_p + idx → load` 단축
- `idn = 2*idx + (forest_p+1)` 사전 계산하여 다음 round의 +forest_p step 제거

**Flow engine `add_imm` (–1 cycle)**
- Flow engine은 거의 idle (1230 cycles 중 0 ops 사용)
- store_addrs[0] 초기화를 alu → flow로 이전
- 옛 `alu(+, slot, inp_values_p, zero_const)`는 zero_const 로드 후 실행
- 새 `flow add_imm(slot, inp_values_p, 0)`는 const 의존 제거

### 4.3 Search 인프라

**12-worker parallel beam search**
- 12 CPU 코어 모두 활용
- 다양한 전략: deep_small, wide_large, crossover, random_restart
- 워커들이 shared dict로 best config 공유
- ~50,000+ config 탐색

**Multi-knob mutation crossover**
- 단일 knob 변경 SA는 1415에서 멈춤
- 다중 knob 동시 변경 + crossover로 1403 발견
- "한 knob씩 보면 worse지만 함께 적용하면 better"인 saddle point 발견 가능

**Subagent 병렬 활용**
- 분석/구현 작업을 독립 subagent에 위임
- 각 subagent가 코드 직접 수정 + 테스트
- 동시에 4개 subagent 실행으로 시간 효율 ↑

## 5. 시도했지만 효과 없던 것들

| 시도 | 결과 |
|---|---|
| ALAP scheduler | list_late_priority로 검증, 1730 (worse) |
| Lookahead scheduler | 1270 → 1279 (worse) |
| Lane sub-grouping (2-batch packing) | 1386 (no change, VLEN=8 packed) |
| Batch interleaving (2 batches/group) | 1500 (WAR/WAW conflict) |
| Tree reduction for select chain | 1450 (scratch overflow) |
| Speculative `par` from `val_pre5` | +14 cycles (valu overhead) |
| `vselect` for R10 wrap multiply | R10 wrap 자체가 dead code |
| POOL_SIZE=32 (모든 pool) | scratch overflow (1544 > 1536) |
| Init load 축소 (vbroadcast 0) | inp.values는 random, 불가능 |
| Hash stage 0+1, 4+5 fusion | 수학적으로 불가능 (XOR 비-선형성) |
| Force R15 select | n=16 chain depth 너무 큼 |
| Custom scheduler 변형 | forward_greedy가 최선 |

## 6. 도구 및 방법론

### 6.1 Search 스크립트
- `search_parallel.py`: 12-worker parallel beam search
- `search_sa.py`: simulated annealing (옛 시도)
- `search_beam.py`: 단일 process beam search
- `search_*.py`: 다양한 전략 실험

### 6.2 분석 스크립트
- `analyze_slack_1284.py`: 슬랙 분포 분석 (drain/ramp/mid)
- `analyze_slack_1270.py`: 더 깊은 dep chain 분석
- `analyze_slack_1230.py`: 새 baseline 분석
- `trace_critical_path.py`: 마지막 op로부터 backward trace

### 6.3 Correctness check
- Search runner가 매 config마다 reference_kernel2와 비교
- 잘못된 결과 (예: speculative par bug)는 자동 reject

## 7. Cycle Floor 분석 (1229)

```
Valu ops:  7,199 / 6 slots = 1,200 floor  ← binding constraint
Alu ops:  14,394 / 12 = 1,200 floor
Load ops: 2,377 / 2 = 1,189 floor
Store ops:   32 / 2 = 16 floor (irrelevant)
Flow ops:     1 / 1 = 1 floor (거의 unused)
```

**Slack = 1,229 - 1,200 = 29 cycles 분포**:
- Initial ramp: 10 cycles (load engine 44 init loads saturated)
- Mid stalls: 17 cycles (group 30의 R14+R15 hash chain depth)
- Final drain: 2 cycles (irreducible: last valu → last store gap)

## 8. 왜 더 못 내려가는가

1. **Hash chain depth는 알고리즘적 하한**: 6 stages, 그 중 3개는 XOR-based 비-fused. 깊이 9 valu cycles 직렬. 정합성을 깨지 않고는 단축 불가능.

2. **Valu floor 1200이 binding constraint**: 줄이려면 valu op 자체를 7,199개 미만으로 줄여야 함. ALU/flow/load로 이전은 효과 없음 (각각 다른 floor가 있고 alu는 이미 거의 saturated).

3. **Load engine 초기 ramp는 init load 44개로 결정**: scratch constants는 load engine만 사용. 줄이는 방법 없음 (problem.py 변경 불가).

4. **Group 30의 critical chain**: subagent 분석 결과 critical path의 180/222 ops가 group 30 소속. EMIT_ORDER로 추가 단축 불가.

## 9. Subagent 활용의 효용

Search만으로는 약 1386이 한계였음. **Subagent가 알고리즘적 통찰을 만들어낸 후 search가 그 위에 더 쌓는 패턴**이 핵심:

| 단계 | 발견자 | 효과 |
|---|---|---|
| `last2_rounds_alternate` emit | Subagent | -79 cycles |
| Hash 2+3 algebraic fusion | Subagent | -22 cycles |
| VLOAD level 3 setup | Subagent | -22 cycles |
| Per-pool POOL_SIZE | Subagent | -7 cycles |
| Flow engine add_imm | Subagent | -1 cycle |
| **Subagent 단독 합계** | | **~131 cycles** |
| Search (multi-knob combos) | Auto | 나머지 cycles |

**결론**: 단순 brute-force search로는 ~1386. Subagent 알고리즘 분석 + search 조합으로 1229. 1363 (improved harness 임계값) 돌파의 핵심은 subagent 통찰.

## 10. 파일 변경 요약

### 변경된 파일
- `perf_takehome.py`: 핵심 커널 + 25+ 튜닝 knob 추가
- `OPTIMIZATION_NOTES.md`: 진행 노트
- `REPORT.md`: 본 리포트
- `search_parallel.py`, `search_*.py`: 자동 search 인프라
- `analyze_slack_*.py`, `trace_critical_path.py`: 분석 스크립트

### 변경되지 않은 파일
- `tests/`: 어떤 파일도 수정하지 않음 (anti-cheating)
- `problem.py`: ISA / simulator / hash 정의 그대로

### 최종 config (`perf_takehome.py` defaults)
```python
MAX_SELECT_N = 4
POOL_SIZE = 24
POOL_SIZE_VTMP_A = 32
POOL_SIZE_VTMP_B = 32
POOL_SIZE_SCATTER = None  # uses POOL_SIZE
NUM_ADDR_SLOTS = 2
FORCE_SELECT_ROUNDS = (14,)
CMPS_IN_ALU_THRESHOLD = 4
RELATIVE_IDX_IN_ALU = True
IDN_IN_ALU_ROUNDS = (12, 13)
HASH_OP1_ALU_ROUNDS = (1,)
HASH_OP2_ALU_ROUNDS = (8, 11)
HASH_OP3_ALU_ROUNDS = (14,)
PAR_IN_VALU_ROUNDS = (8, 9, 10, 11, 12, 14, 15)
PLUS1_IN_VALU_ROUNDS = (1, 8, 12)
SCATTER_ADD_IN_VALU_ROUNDS = (1, 2, 3, 5, 8, 9, 14)
PRECOMPUTE_ROUNDS = (1, 2, 3, 4, 5, 10, 11, 12, 13)
FOREST_P_FUSED_OUT_ROUNDS = (0, 2)
PRECOMPUTE_STORE_ADDRS = True
FUSE_STAGES_2_3 = True
EMIT_ORDER = "last2_rounds_offset_rev"
```

## 11. 검증

```bash
$ python tests/submission_tests.py
...
Ran 9 tests in 0.353s
OK
CYCLES:  1229  (× 9개 테스트 동일)
Speedup over baseline: 120.20667...
```

모든 9개 테스트 통과, `tests/` 미변경.

---

**최종 한 줄 요약**: VLIW SIMD 시뮬레이터에서 binary forest hash 커널을 147,734 → 1,229 cycles (120x speedup)로 최적화. 50,000+ 자동 config search + 16+ subagent 분석 협업으로 Opus 4.5 improved harness 벤치마크 1,363을 134 cycles 차이로 돌파.

⏺ # 세션 시간 분석

전체 기간

항목	값
첫 메시지	2026-05-29 08:18 UTC (KST 17:18)
마지막 메시지	2026-06-01 01:07 UTC (KST 다음날 10:07)
Wall clock 총 기간	64.8 시간 (약 2일 17시간)

Active 시간 (대화 간격 기준)

정의 (gap ≤ N)	시간
30초 이내 연속 응답	3.2 시간
1분 이내	4.1 시간
2분 이내	5.1 시간
5분 이내 (subagent 실행 포함)	9.1 시간
10분 이내	11.3 시간

대기/유휴 시간 (>5분 gap)

항목	값
휴식 횟수	56회
총 휴식 시간	55.7 시간
최장 휴식	16.9 시간 (사용자 수면 추정)
평균 휴식	약 1시간 (bg search 60min × N회)

해석

진짜 작업/대화 시간은 3~9 시간 범위:

• 순수 대화 시간 (~3시간): 짧은 turn-by-turn 응답
• Subagent + bg search 포함 active 시간 (~9시간): 자동 작업 실행 대기 포함

Bg search가 한 번에 30~60분씩 돌면서 wall time 대부분을 차지했고, 그 사이 사용자는 자거나 다른 일을 했음.

실제 model이 "일하는" 시간은 약 3-4시간 정도.

Anthropic 비교

비교 대상	Model active time	결과
Opus 4.5 improved harness	미공개 (수 시간 추정)	1,363
우리	~3-4시간 + 50+시간 bg search	1,229

약 3-4시간의 active model time + 50+시간의 background search로 더 좋은 결과 달성.