Irregular FMA Dependency Shape Probe

1. 목적

이 probe는 동일한 FFMA instruction count에서 dependency structure만 바꿨을 때 warp progress가 어떻게 달라지는지 확인하기 위해 설계되었다.

비교 대상은 두 가지다.

variant구조의도

dependent_fma_chain_N	하나의 accumulator에 FFMA가 길게 연결됨	strict dependency chain 형성
independent_fma_N	여러 accumulator를 교차 갱신	ready instruction 공급 증가

핵심 질문은 다음이다.

같은 FFMA 수라도, single accumulator chain과 multi-accumulator interleave는 warp progress에 다른 signature를 만드는가?

---

2. 실험 설정

이번 실험은 chain length를 규칙적인 power-of-two sweep으로 두지 않았다.

3, 7, 13, 29

이 선택의 목적은 1, 2, 4, 8, 16, 32 같은 정돈된 sweep에서 가려질 수 있는 irregular lowering/tail effect를 드러내는 것이다.

실험 설정은 다음과 같다.

항목값

threads_per_block	256
warps_per_block	8
repeat	10
clock_budget_cycles	10,000,000
비교 role	dependent / independent pair
chain lengths	3, 7, 13, 29

---

3. 결과 요약

role평균 progress해석

dependent_fma_chain_3	60,543	짧은 dependency chain
independent_fma_3	61,643	dependent보다 약 +1.8%
dependent_fma_chain_7	50,663	independent_7보다 높음
independent_fma_7	44,666	예상과 반대로 낮음
dependent_fma_chain_13	37,199	independent_13보다 낮음
independent_fma_13	40,110	dependent보다 약 +7.8%
dependent_fma_chain_29	26,580	크게 낮음
independent_fma_29	35,549	dependent보다 약 +33.7%

비율로 정리하면 다음과 같다.

independent_3  / dependent_3  ≈ 101.8%
independent_7  / dependent_7  ≈  88.2%
independent_13 / dependent_13 ≈ 107.8%
independent_29 / dependent_29 ≈ 133.7%

관찰된 핵심 패턴은 다음이다.

chain 3  : independent > dependent, 아주 약함
chain 7  : dependent > independent, 역전
chain 13 : independent > dependent
chain 29 : independent >> dependent

---

4. SASS 관찰

4.1 dependent variant

Dependent path는 단일 accumulator에 가까운 strict chain으로 lowering되었다.

예를 들어 29-chain 쪽에서는 다음과 같은 형태가 관찰된다.

FFMA R13, R11, R12, R10
FFMA R13, R11, R13, R10
FFMA R13, R11, R13, R10
...
FFMA R12, R11, R13, R10

중간 accumulator가 R13으로 이어지며 긴 dependency chain을 형성한다. 즉, 다음 instruction이 이전 FFMA 결과를 기다리는 구조다.

dependent: single accumulator chain

4.2 independent variant

Independent path는 여러 accumulator를 번갈아 갱신하는 형태로 lowering되었다.

예시는 다음과 같다.

FFMA R13, R11, R8,  R10
FFMA R9,  R11, R9,  R10
FFMA R15, R11, R4,  R10
FFMA R5,  R11, R5,  R10
FFMA R13, R11, R13, R10
FFMA R9,  R11, R9,  R10
FFMA R15, R11, R15, R10
FFMA R5,  R11, R5,  R10

여러 accumulator lane이 교차되므로, 한 accumulator의 결과가 아직 준비되지 않았더라도 다른 accumulator에 대한 FFMA가 ready 상태가 될 수 있다.

independent: multiple accumulator lanes

---

5. 해석

5.1 chain 29: dependency 분산 효과가 강하게 드러남

chain_29에서는 independent variant가 dependent variant보다 약 33.7% 높은 progress를 보였다.

dependent_fma_chain_29 ≈ 26,580
independent_fma_29     ≈ 35,549

이 결과는 가장 문서화 가치가 높다.

같은 FFMA instruction count라도 하나의 accumulator에 길게 묶인 dependency chain은 progress를 강하게 제한한다. 반면 여러 accumulator로 분산하면 warp 내부에서 ready instruction 공급이 늘어나고, scheduler가 고를 수 있는 instruction이 많아진다.

codegen 관점에서는 다음 결론으로 연결된다.

긴 accumulation을 single accumulator로 밀어붙이는 것은 위험하다. partial accumulator를 여러 개로 나누어 dependency depth를 낮추는 편이 유리할 수 있다.

5.2 chain 13: 중간 길이에서도 효과가 나타남

chain_13에서도 independent variant가 dependent variant보다 약 7.8% 높았다.

dependent_fma_chain_13 ≈ 37,199
independent_fma_13     ≈ 40,110

이는 dependency chain이 충분히 길어지면, 29-chain처럼 극단적으로 길지 않아도 accumulator 분산 효과가 나타날 수 있음을 보여준다.

5.3 chain 3: 차이가 거의 없음

chain_3에서는 independent variant가 dependent variant보다 약 1.8% 높았다.

dependent_fma_chain_3 ≈ 60,543
independent_fma_3     ≈ 61,643

이 정도 차이는 dependency structure의 강한 효과라기보다는 짧은 chain에서 loop/control overhead, role dispatch, scheduler noise가 섞인 결과로 보는 편이 안전하다.

짧은 chain에서는 dependency penalty가 작고, 주변 비용이 상대적으로 크게 보인다.

5.4 chain 7: anomaly

가장 중요한 예외는 chain_7이다.

dependent_fma_chain_7 ≈ 50,663
independent_fma_7     ≈ 44,666

independent variant가 오히려 약 11.8% 낮았다.

이 결과는 “independent accumulator가 항상 좋다”는 단순 결론을 막아준다. 가능한 원인은 다음이다.

1. independent_7의 instruction shape가 불균형하다.
2. 4개 accumulator에 7개 instruction을 분산하면서 tail이 생긴다.
3. dependent_7은 더 compact한 SASS path로 lowering되었을 수 있다.
4. role dispatch 또는 branch table 위치가 role별로 다르게 작동했을 수 있다.
5. independent path는 최종 sink 계산에서 여러 accumulator live range를 유지해야 한다.
6. register pressure 또는 live value 수가 dependent보다 커졌을 수 있다.

특히 independent_7은 구조적으로 애매하다.

a0, a1, a2, a3,
a0, a1, a2

a3만 한 번 적게 갱신되는 비대칭 tail이 생긴다. 이 tail shape가 SASS scheduling, register allocation, live range에 영향을 줬을 가능성이 있다.

---

6. 핵심 결론

이번 probe의 결론은 다음처럼 정리할 수 있다.

independent accumulator variant가 항상 빠른 것은 아니다. 그러나 dependency chain이 길어질수록 single accumulator chain은 progress를 강하게 제한할 수 있고, multi-accumulator 분산은 ready instruction 공급을 회복시킬 수 있다. 다만 그 효과는 chain length, accumulator distribution, tail shape, SASS lowering, live range에 의해 비선형적으로 나타난다.

이번 실험에서 중요한 점은 비정규 chain length를 사용했다는 것이다.

규칙적인 1, 2, 4, 8, 16, 32 sweep만 사용했다면 결과가 더 깔끔해 보였을 수 있다. 하지만 3, 7, 13, 29를 사용하면서 dependency effect가 단조롭고 선형적인 곡선으로만 나타나지 않는다는 점이 드러났다.

즉, codegen 관점에서 봐야 할 것은 단순히 accumulator 개수만이 아니다.

instruction count
accumulator count
dependency depth
tail distribution
register live range
SASS lowering shape

이 요소들이 함께 최적점을 만든다.

---

7. Codegen implication

이 결과는 accumulation-heavy kernel의 lowering 전략과 직접 연결된다.

7.1 피해야 할 형태

acc = fma(x0, y0, acc)
acc = fma(x1, y1, acc)
acc = fma(x2, y2, acc)
...

긴 single accumulator chain은 dependency depth를 증가시키고, warp 내부 ready instruction 공급을 줄인다.

7.2 선호할 수 있는 형태

acc0 = fma(x0, y0, acc0)
acc1 = fma(x1, y1, acc1)
acc2 = fma(x2, y2, acc2)
acc3 = fma(x3, y3, acc3)

acc0 = fma(x4, y4, acc0)
acc1 = fma(x5, y5, acc1)
...

partial accumulator를 여러 개 유지하면 dependency chain이 분산된다.

하지만 accumulator 수를 무조건 늘리면 안 된다. accumulator가 늘어나면 live range와 register pressure도 증가한다. 따라서 codegen heuristic은 다음 trade-off를 함께 봐야 한다.

more accumulators
→ shorter dependency depth
→ more ready instructions
→ but more live registers
→ possible register pressure / occupancy loss

---

8. 후속 실험

다음 실험은 chain_7 anomaly를 분리해야 한다.

추천 probe는 다음이다.

balanced_vs_unbalanced_interleave_probe

비교 대상은 다음처럼 잡는다.

chain_8 independent balanced:
a0 a1 a2 a3 a0 a1 a2 a3

chain_7 independent tail:
a0 a1 a2 a3 a0 a1 a2

chain_9 independent tail:
a0 a1 a2 a3 a0 a1 a2 a3 a0

목적은 명확하다.

chain_7 역전이 dependency 구조 때문인지, 아니면 unbalanced accumulator distribution / tail shape / live range 때문인지 분리한다.

이 후속 실험까지 연결하면 이번 결과는 단발성 anomaly가 아니라, “dependency depth와 instruction shape를 분리해 측정하는 흐름”으로 정리된다.