Lec 10 part2 · 2-bit predictor 예제, global history·two-level·tournament predictor 와 return address stack

1.12-bit saturation·hysteresis counter 를 두 예제로 비교 — 패턴에 따라 우열이 뒤집힌다.

1.2Amdahl's law 에도 deep·superscalar pipeline 의 큰 misprediction penalty 때문에 고급 predictor 가 쓰인다.

1.3global history(Gshare), two-level predictor(GAg…PAp), Alpha 21264 tournament predictor.

1.4JALR target 은 BTB 로 못 맞혀 return address stack 을 쓴다: push/pop, RAS vs BTB 선택, overflow 처리.

상황·문제지난 강의의 1-bit predictor 복습. 직전 branch 결과를 기록해 다음 결과로 예측.

원인state 0 이면 not taken 예측, 실제 taken 이면 state 1 로 전이 — 결과가 한 번 바뀌면 바로 예측이 뒤집혀 부정확할 때가 있다.

해결state 를 2 bit 로 늘린다.

상황·문제2 bit 로 4 state: strongly/weakly taken, weakly/strongly not taken.

원인strongly taken 에서는 not taken 예측으로 바꾸는 데 wrong prediction 이 더 필요 — 가끔의 반대 결과에 덜 흔들린다.

해결saturation counter 는 한 칸씩 이동, hysteresis counter 는 weak 에서 틀리면 반대쪽 strong 으로 이동. 나머지 전이는 같다.

상황·문제같은 outcome 열 T T N N … 에 두 2-bit predictor 를 적용(초기 counter 0, not taken).

원인saturation: counter 0→1→2→1→0, 마지막 N 만 맞음. hysteresis: 0→1→3→2→0, 한 번도 못 맞힘.

해결정확도 saturation 25%, hysteresis 0%. 같은 패턴도 predictor 설계에 따라 결과가 다르다.

상황·문제outcome T T N T N T … 에 대해 학생에게 다음 state 를 묻는 방식으로 풀이.

원인saturation 은 counter 1·2 를 오가며 매번 반대로 예측. hysteresis 는 3·2 를 오가며 항상 taken 예측.

해결saturation 0%, hysteresis 50% — 앞 예제와 우열이 뒤집힌다. 패턴마다 잘 맞는 predictor 가 다르다.

상황·문제2-bit predictor 는 약 90% 정답, misprediction penalty 2 cycle 이면 IPC 개선(slide 0.96, 음성은 0.996).

원인branch 의 약 80% 는 같은 동작을 반복 — 1-bit·2-bit 동일. 가끔 한 번 반대로 가는 branch 는 1-bit 가 2번, 2-bit 가 1번 틀림.

해결나머지 복잡한 동작은 더 고급 predictor 가 필요.

상황·문제Amdahl's law 는 common case 에 집중하라 — common case 는 이미 2-bit 가 잡는다. 남은 10% 중 30% 를 더 맞히려면 훨씬 복잡한 hardware.

원인그런데도 현대 processor 가 고급 predictor 를 쓰는 이유: 30-stage pipeline 에서 10번째 stage 에 resolve 하면 misprediction 마다 9개 flush.

해결superscalar(병렬 pipeline 여러 개)이면 36개 instruction 을 버리게 되어 penalty 가 매우 커 → 고급 predictor 가치가 있다.

상황·문제지금까지 BHT·BTB 는 현재 branch 의 PC 만으로 index — 다른 branch 정보를 쓰지 않는다.

원인B1 not taken(aa=1), B2 taken(bb=0) 이면 B3 (aa==1 && bb==0) 는 반드시 taken — 다른 branch 결과와 상관관계.

해결M-bit BHSR 에 최근 branch 결과를 shift 로 기록하고 PC 의 n bit 와 XOR 해 table 을 index(Gshare). 같은 PC 도 history 에 따라 다른 entry.

상황·문제패턴이 더 복잡하면 global register 하나로는 부족. 여기서는 direction 예측만 다룬다.

원인BHT(새로 등장)는 PC(또는 hash)로 index 해 branch 결과 pattern(예 1=T, 0=NT)을 저장, 그 pattern 으로 PHT(2-bit counter 등 state)를 index.

해결이전의 BHT 가 여기서는 PHT 라는 이름 — 혼동 주의. BHT·PHT 각각 global/per-set/per-address 로 9가지 조합.

상황·문제그림으로 조합 비교. 강의 중 'global PHT = 2-bit predictor 하나' 라는 설명을 '모든 address 가 공유하는 table 하나' 로 정정.

원인GAg: global BHR 하나로 table 하나 index. GAp: 현재 branch address 로 여러 PHT 중 선택. GAs: set 단위(opcode, compiler 분류, PC 일부 bit)로 선택.

해결PAg: per-address BHT 의 history 로 global PHT index. PAp: history 로 entry, PC 로 PHT 선택.

상황·문제질문: set 과 per-address 차이, 5-stage 에서 어느 stage 에서 예측·resolve 하나, PHT 의 index·output, update 방법.

원인resolve 는 설계에 따라 EX(ALU 결과) 또는 ID(register 값 비교). 빠를수록 성능은 좋지만 comparator 등 자원과 energy 증가.

해결server CPU 는 공격적으로 빨리 resolve, mobile 은 energy 효율 위해 늦게. PHT 는 pattern 으로 index 해 predictor state 를 내고, 사용한 entry ID 를 pipeline register 로 넘겨 resolve 때 update.

상황·문제predictor 마다 잘 맞는 패턴·program 이 다르다.

원인local predictor(PAg 형태, 3-bit counter)와 global predictor(12-bit global history → 4,096 entry × 2-bit, GAg)를 둘 다 둔다.

해결global history 로 index 하는 choice predictor 가 둘 중 어느 쪽을 믿을지 고른다 — 97% 이상 정답.

상황·문제'Trust, but verify' — 예측으로 fetch 하고 실제 outcome 을 계산해 predictor 를 update.

원인out-of-order CPU 에서는 wrong path 의 branch 로 predictor 를 잘못 update 할 수 있고, 이전 값을 보관하지 않으면 복구 불가 → 정확도 저하.

해결강의자가 적절한 예제로 다음 강의에서 다시 설명하겠다며 중단.

상황·문제BTB 슬라이드(p7)로 돌아가 JALR 의 target 이 '??' 였던 점을 다시 짚음.

원인branch·JAL target 은 PC+offset 으로 고정이지만 JALR 은 register 값 + offset — 실행할 때마다 target 이 바뀌어 BTB 로 못 맞힌다.

해결return address stack 으로 target 을 예측.

상황·문제history 기반 predictor 는 JALR 에 통하지 않지만 function call·return 패턴은 stack 으로 잡힌다.

원인JAL 이 return address 를 x1 에 쓰고 JALR 이 그 값으로 return — JAL 실행 시 push, JALR 에서 pop 해 target 으로 사용. nested call 도 순서대로 pop.

해결fetch 때는 PC 만 알므로 RAS/BTB 선택도 PC 기반 예측. 추측으로 pop 하면 진짜 JALR 의 target 을 잃을 수 있어, 틀리면 다시 push 하는 방안 등 주의.

상황·문제RAS 가 4 entry 인데 call 깊이가 4 를 넘으면 무엇을 버릴까 (학생 답: 가장 오래된 것).

원인main→func1→…→func4 이후 깊은 곳에서 call/return 을 반복 — 가까운 시간에 쓰이는 것은 최근 entry, 오래된 것은 한참 뒤에 return.

해결가장 최근 return address 를 유지하고 오래된 것을 버린다. 다음 강의(목요일)에서 계속.

4 state 를 한 칸씩 이동, MSB 로 taken 예측. strongly 상태는 방향 전환에 2번 틀려야 한다.

weak 상태에서 틀리면 반대쪽 strong 으로 이동. 패턴에 따라 saturation 보다 좋기도 나쁘기도.

최근 M 개 branch 결과를 shift 로 기록하는 M-bit register.

PC 의 n bit 와 BHSR 을 XOR 해 predictor table 을 index [McFarling].

BHT(branch 결과 pattern) → PHT(predictor state). Yeh & Patt 의 GAg/GAp/PAg/PAp 등 9 조합.

local·global predictor 를 두고 choice predictor 가 선택. Alpha 21264, 97% 이상.

여러 병렬 pipeline 으로 동시에 fetch·decode·execute. misprediction 시 flush 량이 배로 늘어난다.

JAL 시 return address push, JALR 시 pop 해 target 예측. overflow 시 최근 entry 유지.

4.1T T N N 반복에서 2-bit saturation 과 hysteresis 의 정확도는?

4.2T/N 교대 패턴에서는?

4.3Amdahl's law 에도 불구하고 고급 predictor 를 쓰는 이유는?

4.4Gshare 는 PC 와 global history 를 어떻게 결합하나?

4.5two-level predictor 에서 PHT 는 무엇으로 index 되나?

4.6RAS overflow 시 무엇을 버리나, 왜?