Lec 11 · branch prediction 마무리 (trace cache·predication), exception 과 interrupt

1.1앞부분(~34분)은 Lecture 10 branch prediction 마무리: predictor state 갱신 시점, trace cache, x86 decoding, predication, SW hint.

1.234분부터 Lecture 11: 예기치 않은 event 처리 — polling vs interrupt, interrupt 종류(synchronous/asynchronous/system call)와 source.

1.3OS 의 virtualization·protection 을 위한 privilege level 과, pipeline 에서의 precise interrupt·flush.

1.4RISC-V CSR(SSTATUS/SEPC/SCAUSE), direct/vectored handler, ERET 복귀, MIPS handler 예까지 진행하고 nesting interrupt 도입에서 끝남 (slide 25~28 미진행).

상황·문제pipeline 안에 branch 가 여러 개 있으면 앞 branch 의 결과가 나오기 전에 뒤 branch 를 예측해야 한다.

원인PHT(pattern history table) 는 바로 갱신해도 뒤 예측이 같은 방향이라 이득이 없다. branch history(최근 5개 결과 등)는 바로 반영해야 뒤 예측이 달라진다.

해결PHT 는 실제 outcome 이 나온 뒤 갱신. history 는 예측 직후 추측 갱신하고, 틀리면 이전 state 로 복구(추가 storage·복구 mechanism 필요).

상황·문제fetch 하는 모든 instruction 에 대해 예측한 next PC 를 pipeline 따라 들고 가야 한다.

원인실제 outcome(branch resolution) 은 나중 stage 에서야 알 수 있다.

해결맞으면 BHT 등 갱신. 틀리면 BHT·BTB 갱신 + wrong path 의 younger instruction flush + 올바른 target 에서 재시작.

상황·문제static instruction count 가 큰 basic block(E) 보다 실제로 많이 실행되는 경로(D→F→G)가 더 중요하다.

원인일반 I-cache 는 static 배치대로 저장해 안 쓰는 경로 instruction 까지 fetch·보관한다.

해결자주 실행되는 basic block 연속(trace)을 하나의 단위로 저장. PC 와 branch 예측 결과로 trace 를 찾는다. 단 여러 경로를 담으면 중복으로 공간 낭비.

상황·문제x86 은 CISC 라 instruction 이 가변 길이(1 byte~10여 byte)이고 decode 가 어렵다.

원인현재 instruction 을 decode 해야 다음 instruction 시작 위치를 알 수 있다.

해결(1) ILD 로 길이를 판정해 경계를 찾고 (2) dynamic translation 으로 micro-op 변환. Pentium 4 는 micro-op 을 trace cache 에 보관.

상황·문제branch 예측이 틀리면 wrong path instruction 을 flush 해야 한다.

원인control flow 가 branch outcome 에 의존하기 때문.

해결양쪽 basic block 을 모두 pipeline 에 넣고 predicate 가 false 인 instruction 은 no-op 처리. 대신 필요 없는 instruction 도 자원을 소모한다.

상황·문제hardware 만으로 예측하지 않고 software 가 도울 수 있다.

원인program 을 아는 쪽(프로그래머·compiler)이 branch 경향을 알려줄 수 있다.

해결branch 마다 taken/not-taken hint 를 인코딩(C 에서 GCC 로 unlikely 표시). Itanium 의 brp instruction 으로 BTB 상태를 미리 설정, TAR hit 는 다른 예측을 override.

상황·문제instruction 실패(invalid instruction), I/O 입력(keyboard), time-shared 시스템의 quantum 만료 같은 event 를 처리해야 한다.

원인polling 은 toaster 같은 단순 embedded 시스템엔 괜찮지만, I/O device 가 수백 개면 대부분 event 가 없는데도 확인하느라 overhead 가 크다.

해결interrupt: 평소엔 정상 실행, event 가 나면 알림을 받아 exception handler 로 제어 이동 후 중단된 instruction 에서 재시작. 원래 program 에 투명해야 한다.

상황·문제interrupt 는 원인에 따라 처리 긴급도가 다르다.

원인특정 instruction 에 묶인 것(synchronous)과 외부 event(asynchronous), 의도적 trap 이 있다.

해결synchronous(exception): illegal opcode/operand, page fault 등, forward progress 불가라 즉시 처리. asynchronous(interrupt): I/O·timer, 약간 지연 가능하나 무한정 미룰 수 없음. system call: printf 안의 trap 처럼 OS 경유 I/O 요청.

상황·문제browser, PowerPoint, Zoom 등 여러 process 가 time-share 하지만 각자 전용 machine 처럼 동작한다.

원인process 가 다른 process 의 state·device 를 직접 조작하면 서로를 망칠 수 있다.

해결OS 가 device handler·thread scheduler 를 관리하고 별도 privileged(protected, kernel) mode 를 둔다. interrupt 때만 user → privileged 로 전환, 처리 후 user 로 복귀.

상황·문제code 의미론은 instruction 을 하나씩 원자적으로 실행하지만 pipeline 에선 실행이 겹친다.

원인exception 시점에 앞뒤 instruction 이 부분적으로 실행된 상태로 pipeline 에 있다.

해결precise: older 는 완료, younger 는 실행 안 된 것처럼 보이게 → OS 쉬움, HW 복잡. imprecise: HW 단순, OS 가 younger 의 부분 효과를 고려해야 함.

상황·문제t5 에 I3 가 EX 에서 exception 을 낸다.

원인I3 는 계속 실행될 수 없고 뒤 instruction 도 이어갈 수 없다.

해결I3·I4·I5 를 bubble 로 flush 하고 t6 부터 handler(Ih) 를 fetch. asynchronous interrupt 는 이미 pipeline 에 있는 instruction 을 마치고 handler 를 시작해도 된다.

상황·문제pipeline stage 마다 생길 수 있는 exception 이 다르다.

원인각 stage 가 접근하는 자원(I-mem, decoder, ALU, D-mem)이 다르다.

해결IF: instruction memory address/protection fault. ID: illegal opcode, 미구현 instruction SW emulation, system call. EX: divide-by-zero, overflow(MIPS 만). MEM: data memory protection fault. WB: 멈출 수 없음.

상황·문제interrupt 처리에 필요한 state 를 user 가 건드리지 못하게 보관해야 한다.

원인PC 는 handler 가 곧 덮어쓰고, x1 은 user 의 return address 라 쓸 수 없다.

해결privileged CSR(CSRRW 로 접근): SSTATUS(interrupt enable, privilege mode), SEPC(중단된 instruction 주소), SCAUSE(MSB=interrupt bit, 나머지=exception code). HW 는 SW 가 저장 못 하는 것만 자동 저장.

상황·문제원인(I/O, invalid instruction, data memory 접근 등)에 따라 다른 처리를 해야 한다.

원인어느 handler 로 갈지 결정하는 방식이 필요하다.

해결option 1(direct): 항상 STVEC 주소로 가서 초기 handler 가 cause 를 보고 분기 (RISC-V, MIPS). option 2(vectored): cause 별 주소로 바로 점프, 공간 제한 때문에 길면 real handler 로 점프 (x86, Arm, RISC-V).

상황·문제interrupt 종류별로 handler 가 하는 일이 다르고, 끝나면 원래 위치로 돌아가야 한다.

원인external interrupt 는 device 서비스, exception 은 수정·signal·kill 중 선택, system call 은 OS 기능 수행.

해결ERET 로 CPU state 복원(PC←SEPC), privilege 를 user 로 복원, 중단 주소로 jump 를 원자적으로 수행.

상황·문제handler 실행 중 새 interrupt 가 오면 어떻게 할지 정해야 한다.

원인interrupt 를 재활성화하지 않으면 그동안의 interrupt 는 무시된다.

해결아주 짧은 handler 는 r26·r27 만 쓰고 재활성화 안 함. 조금 길면 stack 에 r8·r9 저장 후 사용. 중요한 interrupt 를 놓치지 않으려면 재활성화(nested) — 다음 강의로 이어짐.

static 은 실행 파일 속 instruction 수, dynamic 은 실제 실행된 수. 10개짜리 loop 을 10번 돌면 dynamic 100.

자주 실행되는 basic block 연속을 한 line 으로 저장. PC + branch 예측으로 접근.

x86 instruction 을 RISC 형태로 바꾼 내부 연산. 대부분 1:1, 복잡하면 4개 이상.

양쪽 경로를 모두 실행하되 predicate false 인 instruction 은 no-op. flush 가 없지만 resource 낭비.

polling 은 주기적 확인(단순 embedded 에 적합), interrupt 는 event 시 알림(device 많을 때 효율적).

synchronous(exception)는 특정 instruction 에 묶여 즉시 처리. asynchronous(interrupt)는 외부 event, 약간 지연 가능.

exception 발생만이 목적인 instruction. I/O 는 OS 만 접근 가능해 printf 도 이를 거친다.

kernel/protected mode. interrupt 때만 진입하며 user code 는 여기서 실행되지 않는다.

older 는 완료, younger 는 미실행처럼 보이게 함. HW 복잡·SW 단순 (imprecise 는 반대).

interrupt enable/privilege, 중단 instruction 주소, 원인(MSB interrupt bit + exception code). CSRRW 로 접근.

direct: 모든 trap 이 STVEC 한 주소로. vectored: cause 별 주소로 바로 이동.

state·privilege 복원과 SEPC 로의 jump 를 원자적으로. 강의는 ERET, RISC-V spec 의 S-mode 명령은 SRET.

4.1branch history 는 예측 직후 갱신하고 PHT 는 outcome 후에 갱신해도 되는 이유는?

4.2loop 안 10 instruction 을 10번 반복하면 static/dynamic count 는?

4.3predicated execution 의 단점은?

4.4synchronous 와 asynchronous interrupt 의 처리 시점 차이는?

4.5interrupt 주소를 PC 나 x1 에 둘 수 없는 이유는?

4.6precise interrupt 를 지원하면 HW 와 SW 중 누가 복잡해지나?