04. Speculation, Interrupts, In-Order Completion (Advanced Computer Architectures, SNU CSE)

서울대학교 컴퓨터공학부 유승주 교수님의 "고급 컴퓨터 구조" 강의를 필기한 내용입니다.

• 목차

Process State §

• Interrupt 와 Branch prediction 간에는 유사점이 있다.
  • 우선 알다시피 모든 intruction 의 실행 이후에는 interrupt checking 을 하고 interrupt 가 있으면 interrupt service routine 을 실행한다.
  • 이것을 위해서는 interrupt service routine 을 실행하기 전에 state 를 저장해 놓았다가 실행 후에 다시 이 state 를 불러와서 이어가야 할 필요가 있다.
  • 근데 branch misprediction 시에도 이러한 기능이 필요하다: branch prediction 이라는 것은 기본적으로 speculative execution 이기 때문에, 만약에 misprediction 시에는 원래의 자리로 돌아와 다른 instruction 을 실행해 주어야 하기 때문.
  • 즉, 이 둘 다 상태를 “기억” 해놓았다가, 원래의 위치로 “돌아와야” 할 필요가 있는 것이다.
• 그런데 이렇게 “기억” 하는 것은 쉽지가 않다.
  • 왜냐면 어떤 instruction 을 실행하는 것 중간에 끊겼고, 다시 돌아왔을 때 정확하게 그 시점부터 다시 시작하기 위해서는 각 functional unit 이 그 시점에 뭘 하고있었는지를 전부 다 저장해 놓아야 하기 때문.
  • 또한, 그렇다고 해서 너무 대충 기억해 버리면, 이미 완료한 instruction 을 다시 실행해야 할 수도 있다.
• 때문에, 간단하지만 정확한 precise process state definition 이 필요하다.

In-order Completion §

• 간단하지만 정확한 process state 를 추적하기 위한 방법은
  • 일단 process state 를 memory state 로 규정하고
    • 여기서 memory 라는 것은 main memory 뿐 아니라, register file 도 포함이다.
  • In-order 로 memory state 를 변경하는 것이다.
  • 이렇게 하면 process state 가 모두 memory state 에 있기 때문에, 이것들만 다시 복구해서 실행하면 되는 것이다.
  • 만약에 Out-of-order execution 을 하게 되면, 어떤 순서로 실행을 했는지 또한 어딘가에 저장해놔야 하기 때문에 더욱 복잡해진다.
• In-order 를 “instruction 순서 그대로” 로 정의하고 out-of-order 를 “Instruction 순서와는 다르게” 라고 정의할 때
  • 일단 issue 는 in-order 로 하고, 실행하는 것은 out-of-order 로 하되, 종료하며 memory state 를 변경하는 것은 다시 in-order 로 하겠다는 말이다.
• In-order 로 memory state 를 변경한다는 말은
  • Instruction 이 종료된 뒤에 memory state 를 변경하는 것을 이 instruction 이 더 이상 speculative 하지 않을 때 수행하겠다는 것이다.
  • 즉, branch prediction 을 하여 speculative 가 되거나, 아니면 이전 instruction 보다 먼저 끝나서 speculative 가 되었을 경우에는, memory state 를 변경하지 않고 어딘가에 저장해 놓았다가 더이상 speculative 하지 않게 되면 이 저장해 놓은 애들을 memory state 에 반영한다는 것.
  • 따라서 이런 것을 In-order Completion 혹은 In-order Commit 라고 한다.
  • Commit 대신 Retire 이란 말을 사용하기도 한다. 즉, 이 용어는 instruction 의 실행을 완료한 뒤 in-order 로 process state 까지 바꾸어 완전히 종료되는 것을 말하는 것.

Reorder Buffer (ROB) §

• 그래서 임시로 값들을 저장하기 위한 추가적인 register 들이 필요하다.
• 이때 임시로 사용하는 Input register 들은 Reservation Station 에 이미 있기 때문에 임시로 사용할 Output register 들만 있으면 된다.
• 임시로 사용할 Output register 들은 새로운 component 인 Reorder Buffer (ROB) 에 구비된다.

Tomasulo with ROB Example §

약자 정리

• EX: Execution
• ROB: Reorder Buffer
• RS: Reservation Station

• 그래서 위와 같이 ROB 까지 전부 있는 상황에서 Tomasulo 가 어떻게 굴러가는지 확인해 보자.
• 기존에는 Issue, Execute, Write 세 stage 가 있었다면, 여기에는 Commit 이라는 stage 하나가 더 추가되게 된다.
  • Commit stage 에서는 write stage 이후 in-order 가 되면 register 에 쓰거나 아니면 (STORE 의 경우) memory 에 쓴다.

Cycle 1 §

• 우선, 첫번째 LD 가 issue 된다.
  • 여기서 중요한 점은 ROB 에 우선 등록을 한 뒤에 instruction 을 한다는 것이다.
  • 즉, ROB 에 등록을 하여 ROB 에 valid entry 가 있을 때에만 이놈을 issue 한다.
  • 따라서 만약에 ROB 가 꽉 차서 더 이상 자리가 없을 때에도 stall 이 발생하게 된다.
• 그리고 아래에 register result state 를 보면, output register 인 F6 에 ROB 의 index 인 1 이 등록되는 것을 확인할 수 있다.

Cycle 2 §

• Cycle 2 에서는 첫번째 LD 는 EX1 이 되고, 두번째 LD 가 issue 된다.
  • 여기에서도 cycle 1 와 동일하게 ROB, Register result status, Load buffer 가 다 채워지는 것을 볼 수 있다.
• 그리고 여기서 눈여겨볼 것은 저 head 와 tail 이다.
  • 즉, 이 ROB 는 ring buffer 의 형태로 작동하고, 따라서 head 는 commit 되지 않은 가장 오래된 entry 를, tail 은 commit 되지 않은 가장 최신의 entry 를 추적하게 된다.
    • 따라서 entry 1 이 head 가 되고, entry 2 가 tail 이 되는 것.

Cycle 3 §

• Cycle 3 에서는 첫번째 LD 는 EX 가 끝나고 write stage 가 되고, 두번째 LD 는 EX1 에 진입한다.
• 또한 MULTD 가 issue 된다.
  • 여기서 RS 를 확인해 보면 사실 기존의 Tomasulo 랑 다를 것은 없는데 여기에 적히는 내용들이 좀 달라진다.
    • 보면 일단 $V_k$ 는 그대로 register F4 를 복사해와서 Regs[F4] 가 되지만
    • $Q_j$ 는 F2 를 기다리고 있기 때문에 ROB 의 entry 2 번이 명시 되어 ROB 에 값이 적힐 때 까지 대기하게 되고
    • Dest 는 ROB 의 entry 3 번이 적혀서 이 instruction 의 write stage 에서 ROB entry 3 에 결과가 적힌다는 것을 명시하고 있다.

Cycle 4 §

• Cycle 4에서는 첫번째 LD 가 commit 된다.
  • 그래서 이 시점에 (그림에는 표현이 되어있지 않지만) ROB 1 의 결과 (Mem[load1]) 가 register F6 에 적히게 되고,
  • Head pointer 또한 ROB 2 로 움직이게 된다.
• 그리고 두번째 LD 가 write stage 에 진입한다.
• 그래서 ROB 2 를 대기하고 있던 MULTD 에 대해, $V_j$ 에 ROB 2 의 결과 (Mem[45 + Regs[R3]]) 가 복사되며 $Q_j$ 가 사라지게 된다.
  • 따라서 이에 따라 MULTD 가 EX1 에 진입한다.
• 또한 SUBD 가 ROB 4 에 채워지며 issue 된다.

Cycle 5 §

• Cycle 6 에서는 두번째 LD 가 commit 되어, ROB 의 head pointer 가 움직인다.
• 또한 MULTD 와 SUBD 의 EX stage 가 하나씩 추가되고 (각각 EX2, EX1)
  • 당연히 얘네들은 아직 EX 중이기 때문에 head pointer 가 움직이지 않는다.
• DIVD 가 ROB 에 추가되고 issue 된다.
  • 그래서 $V_k$ 인 F6 은 이미 첫번째 LD 로 인해 commit 되었으므로 해당 값을 복사해오고 (Regs[F6])
  • F0 은 MULTD 에 의존하기 때문에 $Q_j$ 에 MULTD 의 ROB entry 인 3 이 들어가게 된다.

Cycle 6 §

• Cycle 6 에서는 ADDD 가 ROB 6 에 등록되며 issue 된다.
  • 따라서 RS 에는, 이놈이 F8 에 의존하고 있기 때문에 F8 에 대한 ROB entry 인 4 가 $Q_j$ 에 등록되게 된다.
• 그리고 MULTD 와 SUBD 는 여전히 EX 중이고 (각각 EX3, EX2)
• DIVD 는 $Q_j$ 가 해소되지 않았기 때문에 여전히 issue 상태에서 stall 되어 있다.

Cycle 7 §

• Cycle 7 에서는 SUBD 가 write stage 에 진입하며, 이놈을 기다리고 있던 ADDD 의 RS 에 $V_j$ 로써 ROB 4 가 등록되고, $Q_j$ 는 사라진다.
  • 그리고 그와 동시에 ADDD 는 EX1 에 진입한다.

Cycle 8 §

• Cycle 8 에서는 MULTD 가 계속 실행되고 있어서 바뀌는 것은 없는데,
• 여기서 눈여겨볼 것은 SUBD 가 write stage 에서 멈춰있는 것이다.
  • 즉, 아직 이전 instruction 인 MULTD 가 아직 commit 되지 않았기 때문에, SUBD 도 commit 하지 못하고 write 상태에 머물러 있는 것이다.

Cycle 9 §

• Cycle 9 에서는 ADDD 가 write stage 에 진입한다.
• 이것 말고는 따로 볼건 없음

Cycle 13 (Skip cycle 10 ~ 12) §

• Cycle 10 ~ 12 까지는 계속 MULTD 가 돌고 있기 때문에 생략하고 cycle 13 을 보면
• 이때 드디어 MULTD 가 write stage 로 가며 이놈을 대기하고있던 DIVD 에 결과값 (#2xRegs[F4]) 이 전파된다.

Cycle 14, 15 §

• 두 LD 가 모두 commit 이기 때문에 cycle 14 에서는 MULTD 가 commit 을 하고

• 이에 따라 write stage 에서 대기하고 있던 SUBD 가 연달아 commit 된다.
  • 그리고 head pointer 도 움직이는 것을 볼 수 있다.

Example Summary §

• 그래서 결과적으로 위와 같이 되는 것을 볼 수 있다: Issue 와 Commit 은 in-order 로 수행되고, EX 와 WB 은 out-of-order 로 수행된다.

Handling Branch Misprediction w/ ROB §

• ROB 를 이용하면 Branch misprediction 시에 날리는 것도 아주 간단하다. 그냥 branch 이후의 모든 ROB entry 들을 날려버리면 된다.
  • Branch 가 EX 중이라면, 그 뒤에 있는 애들은 모두 EX 가 끝났다 할지라도 전부 uncommit 상태이기 때문에 branch 의 EX 가 끝나고 WB 이 되면 branch 이후 어디로 가야할지가 결정된다.
  • 따라서 이 시점에 만약 prediction 이 틀렸다면, branch 이후에 있는 ROB 를 전부 날려주기만 하면 얘네들은 commit 되지 않았기 때문에 memory 나 register file 은 건들 필요 없이 전부 rollback 이 된다.
  • 그리고 나서 ROB tail 도 branch 로 땡겨지게 된다.
• 위 예제로 설명을 하면,
  • ROB 5 에 branch 가 있다면, 이놈이 WB 이기 때문에 이미 branch probing 이 종료되었고 따라서 prediction 이 맞았는지 아닌지 알 수 있다.
  • 만약에 아니라면, ROB 6 ~ 10 를 다 날려주면 되는 것.
  • 그리고 다음 cycle 에 5번에 ROB head 와 tail 이 모두 위치하게 된다.
    • 위 그림에 있는 저 ROB head 는 다음 cycle 에 저렇게 될거다 라고 생각하면 될듯.

ROB + Tomasulo Limitations §

• 이 방법이 장점만 있는 것은 아니다.
  • 일단 Reg -> RS -> ROB -> Reg 의 data copy 가 일어나기 때문에 비효율적이고
  • ROB 가 Common Data Bus 에 붙기 때문에 CDB 에 걸리는 부하가 더 심해진다.

Superscalar (Multi-issue Processor) §

• Superscalar 에서는 Fetch / Decode 가 여러개 있어서 한 cycle 에서 여러개의 instruction 을 issue 할 수 있는 processor 를 말한다.

W/ or w/o Speculation §

• Superscalar 와 branch prediction 는 연관성이 없다: Superscalar 를 하면서 branch prediction 을 안할 수도 있다.
• 근데 당연히 branch prediction 을 하는 것이 더 성능이 좋다. 아래의 예시를 보자.

• 2 개씩 issue 한다고 했을 때, branch prediction 를 하지 않는다면 5번째줄의 BNE 때문에 이후의 LD, DADDIU 등이 쭉 밀리게 된다.
  • 그래서 얘네들의 EX 가 cycle 8, 9 등의 시간에 시작된다.

• 하지만 branch prediction 을 하는 위의 예제를 보면, EX 가 훨씬 더 일찍 시작되어 전반적으로 일찍 끝나는 것을 알 수 있다.

How Much Speculation? §

• 근데 당연하게도 Superscalar 에서 branch prediction 이 항상 좋은 것은 아니다.
  • 한번에 여러 instruction 들을 issue 하기 때문에, branch misprediction 시에 당연히 날라가는 instruction 의 수도 많아지고,
    • 단순히 날라가는 instruction 의 수 뿐 아니라 Cache 나 TLB 도 날려야 할 수 있기 때문에 이로 인한 penalty 가 아주 커질 수 있다.
  • Branch prediction 을 해서 쭉 진행하던 중에 또 다른 branch 를 만났을 경우에 어떻게 해야 하는지도 난감하다.
    • 만일 계속 prediction 을 해서 진행하다 보면, 어떤 것은 recovery 하고 어떤 것은 recovery 하지 말아야 하는 지 결정해야 되는 등의 구현 복잡도가 커진다.
• 반대로 branch prediction 을 했을 때의 좋은점은 당연히 성능이다.
  • 이것은 memory access 가 있는 경우에 더 효과가 커진다.
  • 왜냐면 branch prediction 을 해서 이후의 memory access 를 먼저 실행하게 되면, latency hiding 이 되기 때문에 memory access time 이 줄어드는 효과를 가져온다.
  • 또한 요즘의 CPU 들은 당연히 cache 를 사용하여 speculative memory access 를 하기 때문에 branch prediction 으로 인한 speculative execution 과 cache 를 이용한 speculative memory access 가 만나면 효과가 상당히 커진다.
• 따라서 이 둘 사이의 balance 를 맞춰서 얼마나 speculative 할지 결정하는 것이 중요하다.
  • 그래서 cache, TLB 까지 고려해서 misprediction penalty 가 얼마나 될 지를 가늠하고, speculative amount 를 정한다고 한다.
  • 그리고 이 크기는 ROB 의 크기로서 구체화된다: 이놈이 다 차면 더 이상 speculative execution 을 하지 못하기 때문
  • 그래서 branch 를 만날 때 마다 branch prediction 을 하고 저 “얼마나 speculate 할까” 에 따라서 해당 만큼의 instruction 들을 memory 에서 읽어온다고 한다.
  • 뭐 구체적으로 어떻게 하는지는 안배움
• 참고로 instruction fetch / decode logic 을 Frontend 라고 한다.
  • 이부분이 복잡하기 때문에 보통 이부분에서 performance 가 많이 결정된다고 한다.

Forward Store to Load Buffer §

• Load buffer 와 Store buffer 도 Common Data Bus 로 연결되어 있어서 만약에 Store 하려는 놈의 memory 주소와 Load 하는 놈의 주소가 같다면, Store 하는 값을 Load buffer 로 보내버린다.
• 즉, 원래는 Store 를 한 후, 다시 Load 를 통해 memory 에서 갖고와야 하는데 이건 너무 latency 가 크기 때문에 Store 하려는 것을 Load buffer 에 바로 찔러서 Load 시에는 memory access 를 하지 않아도 되게 하는 것.

Load / Store Disambiguation §

• Memory access instruction 에 대해서도 speculative 하게 하기도 한다.
  • 가령 두 memory access instruction 에 대해, 이 둘의 memory address 가 다르다면 이 둘을 out-of-order execution 을 하거나
  • 아니면 혹시 접근하는 주소가 나중에 결정된다면, 미리 이 주소도 예측해서 접근하는 방법을 사용하기도 한다.
• 이렇게 해서 memory request 에 대한 utilization 을 최대한 끌어올리는 것이다.

Very Long Instruction Word (VLIW) §

• VLIW 은 여러 instruction 들을 하나의 instruction 으로 묶어서 사용하는 것인데,
• 어떤 애들을 어떻게 묶을건지는 모두 compiler 가 결정한다.
• 하지만 요즘은 거의 사용되지 않는다.

• 위 예시를 보면 5개의 연산을 묶는다고 쳐도, 이상적으로는 5배의 성능 향상이 있어야 하겠지만, memory access 등 때문에 실제로는 그다지 parallel 하게 실행되지 않는다고 한다.
  • 뭐 5개를 묶어도 기껏해야 2-3 배라고 한다.

Limitations to ILP §

• ILP 가 이상적으로 작동하려면 다음처럼 되어야 한다:
  • Register Renaming: 가용한 register 가 무한대
  • Branch Prediction: 항상 prediction 이 맞음
  • Jump Prediction: 항상 어디로 jump 할지 사전에 알고 있음
  • Memory Access: 미리 알려진 메모리 주소에 대해, 독립적으로 접근
• 근데 당연히 이렇게 될 리가 없다: 아래의 실험을 보자.

• 보면 빨간색이 이런 모든 자원이 무한대라고 했을 경우에의 성능이고, 그 뒤로 초록색, 파란색 등이 window size (가령 ROB 의 크기) 를 제한했을 때의 성능이다.
  • 따라서 이상적인 상황들과는 다르게 이러한 제약들에 따라 성능이 크게 저하되는 것을 알 수 있다.
• 그럼 이 window size 를 더 늘리면 되지 않냐 라고 생각할 수 있는데, 이게 그리 쉬운 일이 아니다.
  • 가령 cycle 당 issue 할 수 있는 instruction 의 수를 3-6 에서 6-12 로 두배 늘리면 다음과 같은 부하가 발생한다:
    • Cycle 당 memory access instruction 3-4 개를 처리해야 하고
    • Cycle 당 2-3 개의 branch 를 처리해야 하며
    • Cycle 당 12-24 개의 instruction 을 fetch 해와야 하고
    • Cycle 당 20개가 넘는 register 들에 대해 renaming 을 컨트롤해야 한다고 한다.
  • 물론 이런 부하들을 모두 처리하도록 구현할 수는 있다: 근데 문제는 이렇게 하면 power consumption 이 너무 많아져 발열문제가 생기고 발열을 낮추기 위해서는 어쩔 수 없이 clock freq 를 낮추며 성능을 희생해야 한다.
• 이러한 것들이 ILP 에 관한 성능 개선은 이제 점점 멈추고 GPU 와 같은 별도의 Accelerator 가 각광을 받는 배경이 된다.