Lec 11 · Branch target·return stack·LSQ 와 VLIW 도입

1.1ca_L08 후반: BTB·BHT 결합, JR 과 return address stack, in-order/OoO mispredict recovery(mask bit, rename snapshot).

1.2fetch bandwidth: Alpha 21264 line/way prediction·tournament predictor, branch address cache, trace cache.

1.3memory: speculative store buffer, load bypass, in-order queue → conservative OoO load → address speculation.

1.4ca_L09 도입: OoO control logic ∝ W×(W×L), sequential ISA 의 정보 손실, VLIW 의 slot 구조(p1-5).

상황·문제BHT 는 방향만 예측해 taken 이어도 target 이 계산될 때까지 fetch 를 redirect 못 한다.

원인target 은 decode 후에 나오고, JR 처럼 register 를 읽어야 하면 penalty 가 더 크다 (UltraSPARC-III fetch pipeline).

해결BTB: PC 로 index, entry PC 비교·valid 면 target 으로, 아니면 PC+4. BTB 는 앞단에서 redirect, 뒤의 BHT 가 BTB miss 를 교정.

상황·문제JR(indirect jump)은 switch, 동적 함수 호출(C++ virtual function), subroutine return 에 쓰인다.

원인target 이 register 값이라 매번 바뀔 수 있다. 여러 곳에서 호출되는 함수의 return 은 BTB 로 맞히기 어렵다.

해결switch·동적 호출은 같은 case·함수가 반복되면 BTB 가 잘 맞는다. return 은 별도 구조가 필요.

상황·문제fa→fb→fc→fd 처럼 중첩 호출 후 차례로 return 한다.

원인call/return 여부는 decode 에서야 알 수 있어, decode 후 push/pop 하면 fetch stream 에 큰 bubble.

해결call 때 호출 주소 push, return 때 pop (k=8-16). BTB 비슷한 구조에 target 대신 push/pop bit 만 두어 decode 전에 수행, 나중에 확인.

상황·문제in-order 는 speculative fetch 만, OoO 는 branch 뒤 명령어를 speculative execute 해 branch 보다 먼저 완료할 수 있다.

원인완료 값은 in-order 는 bypass network, OoO 는 ROB 나 unified PRF 에 commit 전까지 보관된다.

해결in-order: branch resolve 전 write-back 금지 후 뒤를 kill. OoO: 뒤 명령어 효과를 되돌려야 하며 precise trap 방식은 naive 한 방법.

상황·문제ROB 에 unresolved branch 가 여럿 있고 branch 자체도 out-of-order 로 resolve 된다.

원인branch 는 execute stage(mid-pipeline)에서 resolve 되어, trap 처럼 commit 에서 전부 flush 할 수 없다. 앞 명령어는 계속 실행돼야 한다.

해결R10K: 4 mask bit 로 최대 4개 speculative branch 의존 명령어 표시, branch 별 rename snapshot 4개. Alpha 21264: ROB 명령어당 1개, snapshot 80개.

상황·문제speculative OoO 성능은 fetch bandwidth 에 자주 제한된다. commit 보다 2-3배 많이 fetch 할 수 있다.

원인mispredict penalty 는 instruction window 재충전 시간이 좌우하고, taken branch 는 fetch 흐름을 끊는다.

해결21264 I-cache 가 명령어마다 next line·way 를 예측(BTB 역할)해 tag check·decode·branch prediction 을 critical loop 밖으로. 2-bit hysteresis 로 overtraining 방지.

상황·문제branch 마다 local pattern 이 맞는 것과 global correlation 이 맞는 것이 다르다.

원인한 종류 predictor 로는 다양한 branch 행동을 다 잡지 못한다.

해결local(PC→local history table→local prediction)과 global(12-bit global history) 예측을 따로 하고 choice predictor 가 선택.

상황·문제integer code 는 6-9 명령어마다 taken branch, basic block 이 짧고 control flow 가 불규칙하다.

원인cycle 당 여러 branch 예측과 비연속 block fetch 가 필요. multi-port cache 는 비싸고 banking 은 bank conflict.

해결branch address cache: BTB entry 에 target 여러 개. trace cache: 비연속 basic block 을 한 line 에 pack, 시작 PC + 다음 n 개 prediction 으로 index.

상황·문제control hazard 다음 병목은 memory 를 통한 data hazard. register 는 RS·ROB·renaming 으로 해결했지만 memory 는 아직.

원인store 는 commit 전 memory 를 바꾸면 안 되므로 address·data 를 buffer 에 보관해야 한다.

해결decode 때 program order 로 slot 할당, oldest 가 되면 L1 D-cache 로 commit, abort 시 valid clear. load 는 store buffer 와 cache 둘 다 있으면 buffer, 여럿이면 load 보다 오래된 것 중 최신.

상황·문제sd x1,(x2) 뒤 ld x3,(x4): store 주소를 모르는데 load 주소는 알 때 load 를 언제 실행하나.

원인x4 == x2 면 load 가 store 값을 읽어야 하므로 순서를 어기면 program semantics 위반.

해결in-order queue: 이전 load/store 완료까지 대기(다른 명령어와는 OoO). conservative: 주소가 알려지고 x4 != x2 면 load 먼저, 미확정 store 가 있으면 대기.

상황·문제conservative 방식은 대부분 주소가 달라도 기다려 성능을 잃는다.

원인x4 != x2 로 추측해 store 주소 전에 load 실행, 나중에 x4 == x2 면 load 와 이후 명령어 squash.

해결squash 된 load 는 store-wait bit 로 이후 실행 시 이전 store 완료까지 대기, 주기적으로 clear. 틀리면 penalty 가 커서 conservative 보다 나빠질 수도.

상황·문제issue width W, instruction lifetime L 이면 새 명령어마다 W×L 개와 dependence check → hardware ∝ W×(W×L).

원인OoO 는 L 에 instruction buffer·ROB 대기 시간까지 포함, W 를 늘리면 window 도 커져 L 증가.

해결OoO control logic 은 W² 보다 빠르게(~W³) 증가. MIPS R10000 die 에서 control logic 면적이 크다. 이 overhead 를 datapath·cache 로 돌리고 싶다.

상황·문제compiler 는 연산 간 독립성을 알지만 sequential machine code 로 내리며 그 정보를 잃는다.

원인processor 는 register 이름만으로 dependence 를 다시 찾고 다시 schedule 한다.

해결VLIW: 한 instruction 에 연산 6개(Int 2·Mem 2·FP 2), slot 별 고정 기능·고정 latency, dependence 는 compiler 가 보장해 hardware 단순화.

PC 로 index 해 entry PC 가 맞으면 저장된 target 으로 fetch, 아니면 PC+4. taken branch·jump 만 저장.

call 때 호출 주소 push, return 때 pop. k=8-16 entry, return JR 을 BTB 보다 정확히 예측.

R10K 는 4 bit 로 명령어가 어느 speculative branch 에 의존하는지 표시, mispredict 시 해당 명령어만 kill.

local·global predictor 를 함께 두고 choice(meta) predictor 가 branch 별로 선택.

비연속 basic block 을 한 line 에 저장, 시작 PC + 다음 n 개 branch prediction 으로 index.

commit 전 store 의 address·data 보관. oldest 가 되면 cache 로 쓰고, abort 시 valid clear.

store 주소를 모를 때 다르다고 가정해 load 를 먼저 실행, 겹치면 squash 후 store-wait bit 로 대기.

compiler 가 독립 연산을 한 instruction 의 고정 slot 에 묶어 hardware dependence check 를 없앰.

4.1BTB 가 BHT 보다 앞 stage 에서 쓸 수 있는 이유는?

4.2return stack 을 decode 전에 push/pop 하려면 무엇을 저장하나?

4.3branch mispredict recovery 가 trap recovery 와 다른 점은?

4.4store buffer 에 같은 주소 store 가 둘이면 load 는 어느 값을 쓰나?

4.5address speculation 이 conservative OoO 보다 나쁠 수 있는 경우는?

4.6OoO dependence check hardware 가 W 에 대해 W² 보다 빨리 커지는 이유는?