Lec 7 · Speculative execution: ROB, in-order commit, register renaming

1.1Lec6 정정(분기 미해소 시 'dispatch' 금지) 후 speculation 의 동기와 imprecise interrupt 문제.

1.2ROB 로 in-order commit 을 강제해 precise exception·오예측 복구, speculative Tomasulo 4단계와 7-명령어 예제.

1.3memory hazard 처리, OoO design space(RS 위치·분산/중앙) 토론.

1.4renaming 두 방식: Data-in-ROB vs unified physical register file, physical register 해제 시점. p24 이후(관리 예제·superscalar renaming)는 다음 강의로.

상황·문제project proposal 채점·코멘트 메일 발송(재제출 불필요, progress presentation 에서 반영). paper critique #1 KLMS 게시, 마감 다음 주 화요일 11:59 p.m.(슬라이드: Oct. 19).

상황·문제Lec6 'Dynamic Loop Unrolling Example' 의 'FP instructions do not start execution until all prior branches are resolved' 를 정정하겠다고 약속했던 부분.

원인reservation station 에 들어간 뒤에는 entry 사이에 program order 정보가 없어 '실행 시작'만 막아서는 순서를 보장할 수 없음.

해결'start execution' 을 지우고 'should not be dispatched' 로 판서 정정. 분기 결과가 불확실하면 이후 명령어를 RS 로 dispatch 하지 않음.

상황·문제Tomasulo 는 RS 로 register renaming·OoO 실행을 주지만 branch prediction 너머로 실행을 이어갈 수 없음.

원인결과가 확정되지 않은 branch 뒤 명령어가 architectural state 를 바꾸면, 예측이 틀렸을 때 올바른 상태로 복구할 방법이 없음.

해결speculation: branch prediction 이 항상 맞고 exception 이 없다고 가정하고 fetch·issue·execute + 틀리면 복구하는 mechanism. dynamic scheduling + speculation ≈ data flow execution model.

상황·문제99.99% 맞는 branch predictor 라도 가끔 틀림. IBM 360/91 은 branch 는 speculate 하지 않았지만 앞선 명령어에 exception 이 없다고 speculate.

원인RS 안에서 일부 명령어가 부분 실행되어 '여기까지 commit, 이후는 영향 없음'인 PC 하나를 특정할 수 없음 → imprecise interrupt.

해결debugging 이 어렵고 page fault 처럼 해당 명령어에서 재시작해야 하는 trap 은 사실상 구현 불가. 따라서 틀린 speculation 지점에서 recover·restart 하는 mechanism 필요.

상황·문제Tomasulo 에서는 먼저 끝난 명령어가 register file 을 먼저 갱신(out-of-order commit)해 이전 상태로 되돌릴 수 없음.

원인architectural state 갱신 순서가 program order 와 다름.

해결in-order fetch/decode/dispatch → RS 에서 OoO issue → OoO completion(결과는 ROB) → ROB head 부터 in-order commit. exception·오예측은 commit 에서 감지해 newer 명령어를 kill 하고 handler PC(또는 correct PC)에서 fetch.

상황·문제Tomasulo 구조에 ROB 를 추가할 때 결과 보관·operand 공급·tag 를 어떻게 바꾸는가.

원인결과가 commit 전까지 ROB 에 머물므로 newer 명령어의 operand 공급원이 되어야 함.

해결CDB tag 를 RS 번호 대신 ROB 번호로. RS 는 ROB 에 최신 값이 있으면 ROB 에서, 없으면 register file 에서 operand 를 받음. ROB 가 store buffer 를 대체. entry = instruction type·destination·value·ready.

상황·문제Tomasulo 3단계에 commit 단계를 추가.

원인ROB entry 가 없으면 결과를 둘 곳이 없음.

해결1 Dispatch: RS 와 ROB slot 이 모두 비어야, destination 의 ROB 번호 전달. 2 Issue&Execute: 두 operand 준비 시 실행(RAW 확인). 3 Write result: CDB 로 RS·ROB 에 기록. 4 Commit(graduation): head 가 완료되면 갱신, 오예측이면 ROB flush.

상황·문제LD F0 → ADDD F10 → DIVD F2 → BNE F2 → (예측 경로) LD F4 → ADDD F0 → ST F4 를 ROB1~7 에 넣어 추적.

원인BNE 는 DIVD 의 F2 를 기다려(RAW) 미해결, 그 뒤 명령어는 branch prediction 에 따른 speculative.

해결RS 는 값 대신 producer ROB 번호(ROB1, ROB2, ROB5)를 기록. LD F4 완료 시 M[10] 이 ROB5 와 ST·ADDD 로 전달되나 oldest 가 아니면 commit 불가. 오예측이면 BNE 가 commit 될 때 뒤 entry 를 flush 만 하면 됨.

상황·문제ROB 또는 RS 가 가득 차면 어떻게 되는가 (채팅 질문).

원인dispatch 에는 RS entry 와 ROB entry 가 모두 필요.

해결FP op queue 에서 dispatch 를 stall, commit 으로 entry 가 비면 재개. 요즘 고성능 프로세서 ROB 는 100개 이상, 때로 200개 이상.

상황·문제register 가 아닌 memory 주소를 통한 hazard 는 어떻게 지키는가.

원인store 와 load 가 같은 주소를 접근할 수 있음 (예: ST F4,0(R3) 와 LD F4,0(R3)).

해결WAW·WAR: store 는 ROB head 에서만 memory 갱신 → 앞선 load/store 가 남아 있을 수 없음. RAW: load 주소를 program order 로 계산하고 ROB 의 앞선 store 와 주소가 같으면 memory 접근 금지, 값은 ROB/CDB 에서 받음.

상황·문제RS 를 ROB 일부로 둘지 별도 issue window 로 둘지, FU 별 분산인지 중앙 집중인지.

원인두 축 모두 ILP 발견 능력과 배선·면적 비용이 맞바뀜.

해결분산/별도 RS: FU 와 가깝고 짧은 배선. ROB=RS: 한 구조에서 tag 비교, 더 큰 window 로 ILP↑ 이지만 완료된 명령어에도 operand field 가 남아 면적 낭비. 중앙 RS: 연산 종류 편중에도 활용도↑. 분산된 ROB+RS 조합은 가능하나 oldest 판별 비용.

상황·문제renaming 방식 1: source·result data 를 ROB 에 두고 별도 architectural register file 유지.

원인ROB 가 circular buffer 로 program order 를 유지, tag = ROB index(free pointer).

해결dispatch: ARF 값을 Src 에 복사하고 p set, 아니면 producer tag 복사·p clear. CDB write 시 tag 검색해 복사. commit: exception 이면 trap, 아니면 ARF 갱신. trap 시 free=oldest 로 flush. rename table <p,tag,value>, commit 시 <1,_,Result>.

상황·문제renaming 방식 2: ROB 에 data 없이 모든 값을 하나의 physical register file 에.

원인decode 때 architectural register 를 physical register 로 rename 만 하고 값은 읽지 않음.

해결FU 는 unified register file 에서 읽고 씀. commit 은 data 이동 없이 architectural→physical mapping 만 갱신. PRF 는 committed 와 speculative 값을 모두 보유.

상황·문제destination 마다 free physical register 를 새로 배정하고 source 는 mapping 을 따라 rename (x1→P1 이므로 addi 의 source 도 P1).

원인physical register 수가 유한해 재활용해야 하는데, 언제 P5 를 해제해도 안전한가.

해결RAW 는 mapping 으로 보존, WAR·WAW 는 새 register 배정으로 제거. P5(x6) 는 x6 를 다시 쓰는 다음 명령어가 commit 될 때 해제: 그 앞의 P5 사용자도 모두 commit 됨.

상황·문제p24 rename table·physical regs·free list·ROB(LPRd) 예제는 시간이 없어 다음 강의로. 다음 월요일 휴일이라 수요일 수업, 보강 예정.

branch prediction 이 맞고 exception 이 없다고 가정하고 fetch·issue·execute. 틀리면 복구 필요.

interrupt 시점에 '이전은 모두 commit, 이후는 영향 없음'인 PC 를 특정할 수 없는 상태. 360/91.

dispatch 순서(FIFO)로 명령어·결과를 보관하고 head 부터 in-order commit. CDB tag 로 ROB 번호 사용.

ROB head 가 완료되면 register·memory 갱신. 오예측·exception 이면 newer entry flush.

store 는 head 에서만 memory 갱신(WAW·WAR 제거), load 는 앞선 store 주소와 비교(RAW).

source·result 를 ROB 에, committed 값은 architectural register file 에. rename table <p,tag,value>.

committed·speculative 값을 한 파일에. commit 은 mapping 만 갱신, data 이동 없음.

같은 architectural register 를 쓰는 다음 명령어가 commit 될 때 이전 physical register 를 free list 로.

4.1Tomasulo 에서 분기 해소 전 명령어를 '실행 금지'가 아니라 'dispatch 금지'로 정정한 이유는?

4.2ROB 가 precise exception 을 가능하게 하는 원리는?

4.3예제에서 LD F4 가 완료(Y)됐는데 commit 못 하는 이유는?

4.4memory 를 통한 WAR·WAW 가 자동으로 제거되는 이유는?

4.5ROB 를 RS 로 겸용할 때 장단점은?

4.6unified PRF 에서 P5(x6) 를 free 해도 되는 시점은?