03. Tomasulo's Algorithm and Branch Prediction (Advanced Computer Architectures, SNU CSE)

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

• 목차

Register Renaming §

내용 옮겨짐

• Register Renaming (Arch)

Tomasulo’s Algorithm §

• Tomasulo 의 특징을 간단하게 설명해 보면:
  • Reservation station 을 통해 저런 register renaming 을 지원하고.
  • 이놈을 이용해 Structural hazard 로 인한 stall 도 줄였으며
  • Common Data Bus 로 Data forward 가 가능하게 했다.

Tomasulo Organization §

• Tomasulo 에서는 대충 위와 같은 형상을 띄고 있다.
  • 위 그림에서 FP 가 뭔지는 신경쓰지 말자: 아마 floating point operation 예시여서 그런듯
• Load Buffer: Memory 에서 올라온 데이터 (즉, LOAD operation 의 결과) 들이 담기는 buffer 이다.
• OP Queue: 말 그대로 operation queue.
• Registers: Functional unit 들이 공용으로 사용하는 register 들.
• Store Buffer: Memory 로 내리기 전에 대기하는 (즉, STORE 전에 대기하는) buffer.
• Reservation Station: 각 연산에 대한 operation queue 이자 input value 들의 복사본 임시로 저장하고 있는 장소.
  • “Input value 들의 복사본” 에 집중하자. 이 말은, Reservation Station 에 추가적인 register 가 있어서 register renaming 을 하여 WAR dependence, WAW dependence 를 해결한다고 생각할 수 있다.
  • 따라서 Reservation station 에 있는 이 register 를 Temporary Input Register (TIR) 이라고도 한다.
• Common Data Bus: Components 들을 연결하고 있는 공용 bus.
  • 구체적으로는, 이놈을 통해 전송되는 메세지는 64bit data + 4bit address 로 구성되어 있다.
  • 저 4bit address 는 Source functional unit 에 대한 address 로, 이 메세지를 받은 다른 functional unit 이 이 메세지를 받았을 때 본인이 기다리고 있는 메세지인지 판단하게 해준다.
  • 이 address 를 tag 라고도 부른다.

Reservation Station Components §

• Op: Functional unit 이 실행하고 있는 operation
• $V_j$, $V_k$: Operation 입력값
  • Operation 의 결과물은 Store buffer 의 V 라는 field 에 담기고, $V_j$ 와 $V_k$ 에는 저 공간을 가리키도록 되어 있다.
• $Q_j$, $Q_k$: Scoreboard 에서 처럼, RAW dependence 가 있는 경우 의존하는 functional unit 이 담기는 곳이다.
  • 다만, Scoreboard 와는 다르게 readiness 는 따로 없다. 그냥 여기에 아무것도 적혀있지 않으면 그게 ready 라는 뜻.
• Busy: Functional unit 이 사용중인가에 대한 flag
• Register result status: Scoreboard Architecture 와 동일하다.

CPU cycles §

• Tomasulo 에서는 Scoreboard 와 다르게 3-stage 로 처리한다.
• Issue: 이때에는 Instruction 을 Reservation Station 에 등록하고 Register result status 을 갱신한다.
  • 즉, dependence 를 확인해 $Q_j$, $Q_k$ 를 채우고 필요한 값들을 $V_j$, $V_k$ 에 복사해둔다는 의미이다.
• Execute: 실재로 instruction 을 실행하는데, 만약에 Reservation Station 에 필요한 데이터가 다 있으면 바로 실행하고 만약에 그렇지 않으면 Common Data Bus 를 Polling 하며 필요한 데이터가 전송될때 까지 stall 한다.
• Write result: 실행을 종료한다. 여기서는 Common Data Bus 에 결과를 broadcast 하고 본인의 Reservation Station 을 free 한다.

Example 1 §

• Scoreboard 에서와 마찬가지로, 위와 같은 구조에서 instruction 들을 처리하는 과정에 대해 알아보자.

Cycle 1 §

• 일단 첫번째 LOAD 가 issue 된다. 이에 따라 오른쪽 위의 load buffer 에는 Load1 이 busy 가 되고, 그에 따른 address 가 적힌다.
• 그리고 output register 가 F6 이기 떄문에 Scoreboard 에서 처럼 register result status 의 F6 에 Load1 이 적힌다.

Cycle 2 §

• 이번에는 두번째 LOAD 가 issue 되고, Cycle 1 와 마찬가지로 처리된다.
  • 보다시피 Scoreboard 에서와 다르게, 이때에는 load buffer 덕분에 여러개의 LOAD 가 issue 될 수 있다.
• 근데 이 예제에서 왜 첫번째 LOAD 가 exec comp 되지 않는지는 모르겠다; 아마 LOAD 에 2 cycle 이 걸린다는 설정인듯 하다.

Cycle 3 §

• Cycle 3 에서는 첫번째 LOAD 의 EX 가 완료되고, MULTD 가 issue 된다.
• 이때의 Reservation Station 을 보면
  • 일단 Busy 와 Op 가 채워지고
  • 두번째 LOAD 가 종료되어야 F2 에 접근할 수 있기 때문에 (RAW dependence) $Q_j$ 에 Load2 가 적힌다.
  • 그리고 두번째 피연산자인 F4 는 F4 가 그대로 적히는 것이 아니라 F4 의 값이 Reservation Station 에 적힌다.
    • 이렇게 한다는 것은 F4 register 를 사용하는 것이 아니고 Reservation Station 의 $V_k$ 를 사용하는 것이므로 자동으로 register renaming 이 되는 것이다.

Cycle 4 §

• 우선 첫번째 LOAD 는 write result 까지 끝마치며 종료된다. 이에 따라 load buffer 의 Load1 이 비워진다.
• 그리고 두번째 LOAD 의 EX 이 끝난다.
• MULTD 는 아직 EX 를 시작할 수 없다: 왜냐면 Load2 가 이제서야 끝났기 때문에 아직까지는 RAW dependence 가 해소되지 않았기 때문.
• 마지막으로 SUBD 가 issue 된다. 이때 눈여겨볼 것은 이때의 Reservation Station 의 상태이다.
  • 일단 두번째 피연산자인 F2 는 두번째 LOAD 에 의존하고 있으므로 (RAW) $Q_k$ 에 Load2 가 명시된다.
  • 첫번째 피연산자인 F6 은 첫번째 LOAD 에 의존하고 있는데, 첫번째 LOAD 는 cycle 3 에서 EX 가 끝났기 때문에 이 결과를 Common Data Bus 를 이용해 받아서 Reservation Station 에 복사한다.
    • 이 것이 위 그림에서 M(A1) 이고, 이에 따라 Register result status 에도 바뀐 것을 볼 수 있다.

Cycle 5 §

• Cycle 5 에서는 우선 두번째 LOAD 가 종료되며 Load Buffer 에서 Load2 가 비워진다.
• 그리고 SUBD 와 MULTD 에 대한 EX 가 시작된다.
  • 왜냐면 이 둘은 두번째 LOAD 에 대한 RAW dependence 가 있어서 stall 중이었는데, cycle 5 에서 write result 과정에서 Common Data Bus 로 메세지를 보내 그 즉시 Add1 와 Mult1 이 시작되는 것.
  • 그래서 위의 그림에서도 cycle 4 에서와 유사하게 두번째 LOAD 의 값이 M(A2) 로써 Reservation Station 에 등록되게 되는 것이다.
  • Scoreboard 에서의 예시와 마찬가지로, EX 가 시작되었으므로 그에 대한 남아있는 cycle 수가 Reservation Station 에 적혀있는 것 또한 확인할 수 있다.
• 또한 DIVD 가 issue 된다.
  • 여기서는 F6 은 M(A1) 으로써 Reservation Station 의 $V_k$ 에 복사되고, F0 는 Mult1 에 RAW 가 걸려있기 때문에 $Q_j$ 에 Mult1 이 등록된다.

Cycle 6 §

• Cycle 6 에서는 ADDD 가 issue 된다.
  • 우선 피연산자 F8 은 Add1(SUBD) 에 의존하고 있으므로 (RAW dependence) $Q_j$ 에 Add1 가 등록뢰고, F2 는 이미 종료된 두번째 LOAD 의 값이므로 M(A2) 가 들어간다.
• 근데 여기서 눈여겨볼 것은 Register result status 이다.
  • Cycle 5 까지는 F6 에 M(A1) 이 적혀있었는데, ADDD 가 issue 되면서 Add2 의 결과가 F6 에 적힐 것이므로 Add2 가 등록된다.
  • 하지만 Reservation Station 에서는 Add1 와 Mult2 에 대해 여전히 M(A1) 이 복사된 채로 남아있다. 이 말은 Add2 가 종료되어 F6 에 값을 overwrite 할지라도 Add1 와 Mult2 는 여전히 이전 값을 사용할 수 있다는 말이다.
  • 따라서, 이 Reservation Station 에 값을 복사해 둠으로써 register renaming 을 하여 WAR dependence 가 해소되게 되는 것이다.

Cycle 7, 8 §

• Cycle 7 에서는 ADDD 는 Mult1 에 의존하고 있기 때문에 ($Q_j$) 시작되지 않고,
• Add1 (SUBD) 의 EX 가 끝난다.

• Cycle 8 에서는 Add1 은 write result 까지 실행되며 종료된다.
• 또한 write result 과정에서 Add1 의 결과가 Common Data Bus 를 타고 이놈에 의존하고 있던 functional unit 에게 전달된다.
  • 이 결과를 기다리고 있던 놈은 Add2 이기 때문에, 바로 이놈의 $Q_j$ 가 비워지고 $V_j$ 에 값이 채워진다.
  • 이것은 위 그림에서 M(A1) - M(A2) 라는 의미에서 (M - M) 으로 표시되어 있고, register result status 에서도 그에 맞게 표시되어 있다.
• 이에 따라 Add2 의 EX 가 바로 시작되고, 이놈의 time 에 2cycle 이 남아있음이 보여지고 있다.

Cycle 10, 11 (Skip cycle 9) §

• Cycle 9 는 아무것도 안하기 때문에 생략하고, Cycle 10 에서는 Add2 의 EX 가 종료된다.

• Cycle 11 에서 Add2(ADDD) 는 write result 까지 끝나며 종료된다.
• 그리고 그와 동시에 Add2 의 결과가 Common Data Bus 를 통해 전파되어 보면 Add2 의 결과였던 F6 가 (M - M + M) 로 바뀌어 있음을 알 수 있다.
  • 이것은 Add2 이 (M - M) 에 M(A2) 를 더하는 연산이었기 때문에, (M - M + M) 으로 표시해놓은 것.
  • 물론 이놈에 의존하고 있는 애는 없기 때문에 이번에는 Reservation Station 에 등록되지 않는다.

Cycle 15, 16 (Skip cycle 12 ~ 14) §

• 이때도 마찬가지다; 12 ~ 14 cycle 은 아무것도 안되고 생략하고, cycle 15 에서 Mult1 의 EX 가 끝난다.

• 그래서 다음 cycle (16) 에서는 Mult1 가 write result 까지 끝내며 종료되고, 이놈의 결과가 Common Data Bus 로 전파되어 Reservation Station 에 복사돼 Mult2 의 $V_j$ 가 M * F4 로 바뀐다.
  • 그리고 register result status 의 F0 또한 Mult1 의 결과 M * F4 로 바뀐다.

Cycle 57 (Skip cycle 17 ~ 56) §

• 뭐 이러저러 해서 cycle 57 에 모든 instruction 이 다 끝나게 된다.

Tomasulo vs Scoreboard §

• 그럼 이제 Tomasulo 와 Scoreboard 를 비교해 보자. 위에서 왼쪽이 Scoreboard 이고, 오른쪽이 Tomasulo 이다.
• 보면 Tomasulo 가 좀 더 일찍 끝나는 것을 알 수 있는데, 이건 Tomasulo 의 다음과 같은 특징이 작용했기 때문이다:
  • 일단 Tomasulo example 에서는 좀 더 functional unit 이 더 많았고,
  • Reservation station 으로 인해 사용할 수 있는 register 도 더 많았으며 (그래서 register renaming 도 가능했으며)
  • Common Data Bus 를 이용해 data forwarding 도 가능했기 때문이다.
• 그래서 이 둘의 특징을 비교해 보면 다음과 같이 정리할 수 있다.

• 보면, Tomasulo 에서는
  • Reservation station 을 이용해 Structural hazard 로 인한 issue stall 을 줄일 수 있었고,
  • 여기에의 register 들을 이용해 WAR dependence 및 WAW dependence 로 인한 stall 도 해결했으며
    • 구체적으로는 Reservation Station 의 TIR 로 WAR 이 해소되고 renaming 으로 WAW 이 해소된다.
    • WAW 에 대해서는 뒤의 Example 2 에서 예시가 나오니 뒤에서 확인하자.
  • Common Data Bus 로 functional unit 의 결과를 broadcast 해서 1 cycle 먼저 EX 가 가능하게 만들었고
  • Scoreboard 에서의 central 한 접근이 아닌 functional unit 마다의 reservation station 으로 decentral 한 접근을 했다고 할 수 있다.
    • 즉, RAW dependence detection 을 각 Reservation Station 으로 분배한 것.

Example 2 §

• 이번에는 Tomasulo algorithm 에서, loop 에 대한 예시를 보고 가자.
  • 왼쪽 위의 instruction list 는 loop 을 돌며 실행하게 되는 instruction 을 unroll 해서 보여준 것이고
  • 오른쪽 아래의 instrcution list 는 loop 가 있는 원본의 code 이다.
  • 그리고 왼쪽 아래에 R1 register 의 값이 나와있다.

Cycle 1 §

• Cycle 1 에서는 첫번째 LOAD 가 issue 되고, 이에 따라 load buffer 에 80 (R1) 에 대한 load 가 Load1 로 등록된다.
• 이 예제에서는 이 첫번째 LOAD 가 cache miss 가 나서 8 cycle 이 걸린다고 가정한다. 즉, 이 LOAD 는 cycle 9 나 되어서나 종료될 것이다.

Cycle 2 §

• 그리고 첫번째 MULTD 가 issue 된다.
  • $V_k$ 에는 F2 의 값이 복사되고 (R(F2)),
  • F0 는 Load1 에 의존하기 때문에 $Q_k$ 에는 Load1 가 들어간다.

Cycle 3 §

• 그리고 첫번째 STORE 이 issue 된다.
  • Store buffer 에는 addr 80 (R1) 에 대한 요청이 등록되고, Store 할 값은 Mult1 의 결과라는 것이 명시된다.
• 여기서 저 화살표를 좀 살펴볼 필요가 있다.
  • 이것이 Tomasulo 에서 이런식으로 aliasing 이 되어 register renaming 이 된다는 것을 나타내는 화살표로,
  • Mult1 은 Load1 에 의존하고 있고 Load1 이 끝나자 마자 이 값이 전파되어 Mult1 에서 사용된다는 것과
  • Store1 은 Mult1 에 의존하고 있고 Mult1 이 끝나자 마자 이 값이 전파되어 Store1 에서 사용된다는 의미이다.
• 당연히 첫번째 MULTD 는 EX 되지 않는다; Load1 을 기다리고 있으므로

Cycle 4, 5 §

• Cycle 4 와 5 에서는 loop 을 계속 진행하는 것과 관련된 것이어서 이부분은 빠르게 넘어가자.

• Cycle 4 에서는 R1 에서 8을 빼고
  • 그래서 아래 그림의 cycle 5 에서 R1 이 72 로 감소한 것을 볼 수 있다.

• Cycle 5 에서는 BNEZ 를 통해 다시 loop 이 반복되도록 한다.
  • 즉, 이에 따라 왼쪽 위의 instruction list 에서 iteration 이 1 에서 2로 넘어가게 된다.

Cycle 6 §

• Cycle 6 에서는 loop 한바퀴를 돌아 두번째 LOAD 가 issue 된다.
  • 이에 따라 load buffer 의 Load2 가 채워지게 된다.
• 여기서 주목할 점은 register result status 이다.
  • 보면 F0 이 Load1 에서 Load2 로 변경되어 있는데, 이에 따라 이 예제에서는 Load1 이 메모리에서 가져온 값이 절대로 F0 에 저장되지 않는다는 것을 알 수 있다.
  • 어찌보면 Load1 의 값이 덮어씌워져 Mult1 에서 문제가 생기는 것은 아닌가 생각할 수 있다.
    • 즉, WAR dependence 가 있는 거 아닌가? 라는 의심이 들 수 있다.
    • 하지만 그렇지 않다; 왜냐면 Load1 의 결과가 F0 에 저장되었다가 Mult1 로 가는 것이 아니고 Load1 이 끝나자마자 Common Data Bus 를 통해 Load1 으로 전달되기 때문이다.
    • 즉, 이것은 computation 과 register 가 분리되어 있다고 볼 수 있고, 그에 따라 WAR dependence 이나 WAW dependence 가 해소될 수 있는 것이다.

Cycle 7 §

• Cycle 7 에서는 두번째 MULTD 가 issue 된다.
  • 따라서 reservation station 의 Mult2 에 F2 가 복사되고 (R(F2)),
  • 나머지 피연산자인 F0 은 Load2 에서부터 직접 받으므로 $Q_j$ 가 Load2 로 설정된다.

Cycle 8 §

• Cycle 8 에서는 두번째 STORE 이 issue 된다.
  • 따라서 store buffer 의 Store2 에 이놈이 등록되고,
  • 피연산자는 Mult2 로부터 Common Data Bus 를 이용해 바로 받도록 한다.
• 보면 (노란색으로 칠해놓은 SD 를 무시하면) 첫번째 MULTD 와 두번째 MULTD 는 WAW dependence 관계에 있다.
  • 원래 Scoreboard 의 경우였다면, 이때에는 issue 조차 되지 않았겠지만
  • Tomasulo 의 경우에는 애초에 Mult1 이 F4 에 저장되지 않기 때문에 아무런 문제가 생기지 않는다.

Cycle 9 §

• Cycle 9 에서는 드디어 첫번째 LOAD 의 EX 가 끝난다.
  • 근데 원래대로라면 F0 에 LOAD 가 되었어야 했겠지만, 두번째 LOAD 가 F0 을 점유하고 있기 때문에 여기에는 데이터가 올라가지 않는다.
  • 대신 Cycle 10 에서 write result 할 때 Common Data Bus 를 타고 바로 Mult1 의 $V_j$ 에 꽂히게 된다.
• 뭐 여기서 SUBI 가 실행되어서 Cycle 10 에서 R1 이 줄어들긴 하는데 위에서 말한 대로 이건 loop 을 위한 것이므로 자세한 설명은 생략

Cycle 10 §

• 그래서 위에서 말한 대로 cycle 10 에서는 Mult1 의 $V_j$ 에 바로 첫번째 LOAD 의 값이 올라오며 바로 Mult1 에 대한 EX 가 시작된다.
  • 그래서 Reservation Station 에도 time 이 표시되고 있는 것을 볼 수 있다.
• 그리고 cycle 10 에서는 드디어 두번째 LOAD 의 EX 가 끝난다.

Cycle 11 §

• 그래서 cycle 11 에서는 Load2 가 write result 를 할 때 Common Data Bus 를 통해 Mult2 의 $V_j$ 에 값을 전달하고, 따라서 바로 Mult2 의 EX 가 시작된다.
• 또한 세번째 loop 이 시작되며 64 (Cycle 9 에서 SUBI 를 통해 변경된 R1 값) addr 에 대한 LOAD 가 load buffer 의 Load3 에 올라간다.

Cycle 12 §

• Cycle 12 에서는 다음 MULTD 를 issue 해야 되는데, 여기서 첫번째 stall 이 발생한다.
  • 왜냐면 더 이상 reservation station 에 자리가 없기 때문.
  • 그래서 Mult1 이 끝날때까지 stall 이 발생한다.

Cycle 14, 15 (Skip cycle 13) §

• Cycle 13 은 그냥 stall 되어 있는 거여서 생략하고, cycle 14 에서는 드디어 첫번째 MULTD 의 EX 가 종료된다.

• 그리고 cycle 15 에서는 첫번째 MULTD 에 대해 write result 까지 하며 완료되고, 이 값은 Store1 에게 전파된다.
  • 그래서 store buffer 의 Store1 내용이 Mult1 에서 [80] * R2 로 변경된다.
• 또한 두번째 MULTD 에 대한 EX 도 완료된다.

Cycle 16 §

• Cycle 16 에서는 이제 reservation station 에 자리가 나기 때문에 세번째 MULTD 가 issue 된다.
• 그리고 두번째 MULTD 가 write result 까지 하며 종료되며 이에 따라 그 결과가 Common Data Bus 를 통해 Store2 에 전달된다.
  • 그래서 마찬가지로 store buffer 의 Store2 내용이 Mult2 에서 [72] * R2 로 변경된다.

Tomasulo Limitations §

• 여기까지 보면 Tomasulo 에서는 Common Data Bus 가 엄청 중요하다는 것을 알 수 있다.
• 즉, Tomasulo 에서는 이 CDB 에 contention 이 걸리게 된다.
  • CDB broadcasting 이 빈번하게 발생하며 대역폭을 많이 사용하게 돼 bottleneck 이 되며, CDB 가 비싸기에 CDB 를 여러개 두는 것도 어렵다.
  • 또한 tag comparison 이 필요하기에 구현 복잡도도 올라간다.

Explicit Register Renaming §

• 위의 Tomasulo 는 CDS 로 데이터를 직접 전달해주는 방식이기 때문에, 암묵적으로 register renaming 을 한다고 할 수 있다 (Implicit Register Renaming).
• 이러한 방식 말고 Explicit Register Renaming 을 할 수도 있다.
  • 즉, indirection principle 을 차용해 logical register 와 physical register 를 나누고, logical register 의 개수의 배수가 되는 더 많은 physical register 를 구비한 뒤, 이 둘의 mapping table 을 관리하는 것이다.
• 그래서 CPU 에서는 register 를 더 많이 갖고 있다.
  • 즉, compilier 에서는 4개를 갖고있다고 생각하더라도 CPU 에서는 이것의 배수의 register 를 구비해 놓는다.
  • 그리고 한번 write 가 되면, 다른 physical register 가 사용된다.
  • 예를 들어 logical register 가 4개 있고 logical register $R_1$ 에는 처음에 physical register $P_1$ 이 붙어있다가
  • 여기에 한번 write 가 되면 그 다음부터는 $P_5$ 가 사용된다는 것
  • 근데 WB 은 instruction 실행할 때 항상 사용되니까 issue 할 때마다 이 mapping 이 바뀌게 된다.
• 이러한 logical register 들을 ”name” 이라고 부르고 physical register 들을 ”location” 이라고 부른다.
• 또한 logical register 의 개수는 ISA 에 명시된 register 의 개수와 같다. 즉, 이런식으로 compiler 에게 abstraction 을 제공하는 것.

Mapping Table Example §

• Mapping table 이 logical register 와 physical register 간에 구분이 잘 안돼있어서 좀 보기 힘들긴 한데, 위 그림에서 가운데 table 은 logical register $R_{\ast }$ 에 대한 physical register $P_{\ast }$ 의 mapping 이 시간순대로 (아래로 내려갈수록 시간이 흐른 것) 보여준 것이다.
• 그래서 왼쪽의 logical register code 와 오른쪽의 physical register code 를 비교하면서 보면 된다.
  • 처음 ADD 를 실행하면 $R_1$ 에 write 이 되면서 mapping 이 $P_1$ 에서 $P_5$ 로 바뀐다. 그래서 오른쪽에서는 $P_5$ 로 되어 있는 것.
  • 그리고 두번째 SUB 에서는 ADD 에서 읽은 $R_4$ 가 SUB 에서는 write 한다. 그래서 오른쪽을 보면 ADD 에서는 $P_4$ 로 되어 있던 것이 $P_6$ 으로 바뀐다.

Scoreboard with Explicit Register Renaming Example §

• Scoreboard 에서 이런 Explicit Register Renaming 을 사용하면 어떻게 되는지 살펴보자.

Cycle 1 §

• Cycle 1 에서는 첫번째 LD 가 issue 된다.
  • 위에서 말했다시피, issue time 에 output register 가 rename 된다. 그래서 F6 이 P6 에서 P32 로 rename 된다.

Cycle 2 §

• Cycle 2 에서는 두번째 LD 가 issue 된다.
  • 마찬가지로, 이때 F2 는 P2 에서 P34 로 rename 된다.

Cycle 3 §

• Cycle 3 에서는 MULTD 가 issue 된다.
  • 일단 마찬가지로 F0 이 P0 에서 P36 으로 renaming 된다.
  • 이때 functional unit status 를 자세히 보면, input register F2, F4 에 대해 F4 는 그대로 P4 로 명시되어 있는 반면 F2 는 rename 된 location P34 가 되어 있는 것을 알 수 있다.
  • 그리고 간단히 복습하자면, F2 는 두번째 LD 에 RAW dependence 가 있기 때문에 $Q_j$ 가 Int2 가 되고 $R_j$ 가 NO 가 된다.

Cycle 4 §

• Cycle 4 에서는 SUBD 가 issue 된다.
  • 마찬가지로 이놈의 output register 인 F8 이 P8 에서 P38 으로 renaming 이 되고,
  • Input register 인 F2 는 mapping 된 location 인 P34 가 적히는 것을 알 수 있다.
• 그리고 첫번째 LOAD 가 종료된다.

Cycle 5 §

• Cycle 5 에서는 DIVD 가 issue 된다.
  • 또 마찬가지로, 이놈의 output register 인 F10 은 P10 에서 P40 으로 renaming 되고, input register 인 F0 와 F6 은 renaming 된 register 인 P36 와 P32 를 사용하게 된다.

Cycle 10 (Skip cycle 6 ~ 9) §

• 일단 이전까지는 Add 가 SUBD 에서 사용중이었으므로 ADDD 는 cycle 10 까지 stall 된다.
  • 그래서 cycle 6 ~ 9 는 생략했당.
• 그래서 cycle 10 에서 ADDD 가 issue 된다.
  • 보면 output register 인 F6 은 다시 P32 에서 P42 로 renaming 되고, input register 는 F8 와 F2 에 대해 기존에 renaming 된 register 인 P38 와 P34 를 사용한다.
  • 근데 생각해 보면 이 F6 은 이전에 DIVD 에서 읽고있었던 register 였으므로 DIVD 와 ADDD 간에는 WAR dependence 가 있었던 것을 알 수 있었는데, 이렇게 register renaming 을 통해 이러한 WAR 가 해소된 것을 알 수 있다.
    • 근데 주의할 점은 F6 의 기존 location 이었던 P32 가 DIVD 에서 여전히 사용되고 있다는 것이다.
    • 즉, 추후에 또 mapping 이 바뀌어 DIVD 가 여전히 P32 을 읽고 있는 와중에 P32 가 또 다른 name 에 mapping 되지 않도록 주의해야 한다.
    • 이를 위해 내부적으로 freelist 를 관리하고 있고, 사용을 다 했으면 이 freelist 에 넣어 이러한 문제를 막는다고 한다.

Branch Prediction §

• Branch prediction 이라는 것은 알다시피 branch instruction 이 있으면 다음에 어떤 instruction 을 실행해야 할 지 알 수 없기 때문에, 미리 예측하여 실행하는 것이다.
  • 이러한 관점에서, branch prediction 을 HW-based speculative execution 이라고 하기도 한다.
• 한번에 여러개의 inst 를 issue 하는 superscalar 의 경우에는 한번 misprediction 이 발생하면 다 터지기 때문에 overhead 가 아주 커진다.

• Branch prediction 을 할 때, 그 대상은
  • 일단 방향 (direction): function call 같은 경우에는 single direction 이고, branch 는 binary direction 이기 때문에 1bit 정도면 충분하다.
  • 그리고 위치 (target) 까지 알아야 한다: 어느 주소로 갈 것이냐 (즉, 64bit 가 필요하다).

1-bit Predictor §

• 간단한 predictor 로는 branch 의 PC (address) 를 hash 하여 그놈에 맞는 1bit-history table entry 를 업데이트하는 것이다.
  • 따라서 이렇게 하면 같은 branch 에서는 항상 그 이전의 결과를 따라가게된다.
• 즉, 아래와 같은 방식으로 예측한다는 것이고,
  • 여기서 Branch History Table 을 BHT 라고 부르기도 한다.

• 이를 위해서는 아래와 같은 구조가 필요하며,

• State transition 에 대한 FSM (Finite State Machine) 을 그려보면 다음과 같다.

• 사실 너무 간단해서 별로 설명할게 없는데, 이 구조의 단점은 성능이 구리다는 것이다.
• 아래의 예시를 보자.

• 예시가 좀 불충분하긴 한데, 이 for loop 을 반복해서 실행한다고 해보면
• 1-bit predictor 에서는 이전의 결정을 그대로 따라가기 때문에 i 가 4가 됐을 때 기존처럼 taken 으로 예측하면 실제로는 not taken 이기 때문에 한번 틀리고, 다음에 i 가 0 이 되었을 때 기존처럼 not taken 으로 예측하면 실제로는 taken 이기 때문에 또 한번 틀린다.
• 이런식으로 연속해서 두번 틀리게 되어 60% 라는 낮은 적중률이 나오게 되는 것이다.

2-bit Saturating Up, Down Counter Predictor §

• 위 1-bit predictor 의 문제점은 taken 여부를 바로바로 바꾸기 때문이었다.
• 그렇다면 좀 결정을 차분히 바꾸기 위해 일종의 유예기간을 두자는 것이 이 2-bit Saturating Up, Down Counter Predictor 이다.
• 즉, 여기서는 2bit 를 사용하여, weak-strong 개념을 추가하여 예측하는 방법이다.
  • 만약에 weak taken 에서 한번 더 taken 되면 strong 이 되는 식이다.
  • 즉, second-chance 를 주는 셈이고 strong 상태에서는 두번 연속 반대의 결과가 나와야 taken-not taken 이 바뀌게 된다는 것이다.
• 따라서 아래와 같은 FSM 을 그려볼 수 있다.

• 아니면 이런 식의 방법도 있다:
  • 위의 방법에서는 strong 에서 반대의 strong 으로 가려면 세번의 연속된 동일한 결정이 나와야 하는 반면,
  • 아래의 방법에서는 weak 에서는 strong 으로 옮겨지게 해서 두번만 동일하게 나와도 바뀌는 식이다.

• 이렇게 하면 아래 그림에서 보이는 것 처럼 확률을 높일 수 있다.
  • 즉, 한번 틀리는 것으로는 결정을 바로 바꾸지 않기 때문에 어쩌다 한번 틀리는 경우에 대해 다음번까지 틀리는 것을 방지할 수 있다.

Alias Problem §

• 하지만 위와 같은 hash table 의 접근에서는 항상 문제가 되는 것이 collision 이다.

• 즉, 위처럼 collision 이 발생하는 경우에는 다른놈의 prediction 을 갖다 사용하기 때문에 실패 확률이 높아질 수 있다.

Branch Correlation §

• 실제 code 를 생각해 보면, 각각의 branch 는 독립적이지 않고 연관되어 있는 경우가 많다.
  • 가령 위 그림에서 왼쪽의 code 를 보더라도 경우의 수는 $2^3=8$ 개가 아니고 4개인 것을 알 수 있다.
  • 또한 만약 b1 와 b2 가 taken 이라면 b3 는 당연히 not taken 이라는 것은 누구나 알 수 있다.
• 이런식으로 주변의 branch 를 연관시켜서 prediction 을 하는 branch correlation 이 등장한다.

Correlated Branch Predictor §

• 위 그림에서 왼쪽이 위에서 말한 2-bit saturated counter 이고, 오른쪽이 correlated branch predictor 이다.
• 보면 N-bit global branch history 를 이용한다.
  • 이놈은 N 번의 이전 branch prediction history 를 저장한다.
  • 가령 2-bit 이고, 이전에 taken - not taken 이었으면 10 이런식으로 저장돼 있는 것.
• 그리고 2-bit saturated counter 와 동일하게 branch PC 를 hashing 해서 M-bit 을 만들어 내고, 이 M-bit 을 index 로 해서 배열에 접근하는데
• 어느 배열에 접근할 지가 저 N-bit global branch history 에 의해 결정되는 것이다.
  • 즉, 이렇게 하면 같은 branch 라 할지라도 최근 두번의 prediction 결과에 따라 다른 prediction 을 할 수 있는 것이다.
  • 일종의 prediction context 가 바뀌는 셈.
• 이렇게 N-bit global history 와 M-bit counter 를 사용하는 것을 줄여서 (M, N) scheme 이라고 한다.

Gselect Branch Predictor §

• Gselect Branch Predictor 는 위의 Correlated Branch Predictor 와 아이디어는 동일한데, 여러개의 table 을 사용하는 것이 아닌 하나의 거대한 table 을 사용하는 방법이다.

• 그래서 위 그림에서 보이는 것 처럼 PC 에서 LSB 일부를 뽑아내고 (즉, 이것이 hashing 을 하는 것과 동일한 효과)
• Branch History Register (BHR) 에서 LSB 일부를 뽑아내어 이 두개를 concat 한 값을 index 로 하여 Prediction History Table (PHT) 에 접근한다.

Gshare Branch Predictor §

• 근데 Gselect Branch Predictor 에는 문제가 있다:

• 위 예시에서 보다시피, Gselect 에서는 PC 와 BHR 의 LSB 일부만 뽑아내어 concat 하기 때문에, history 가 충분히 반영되지 않는다는 것이다.
  • 그래서 보면 첫 두 row 에 대해서는 history 가 달라짐에 따라 다른 PHT index (Gselect) 가 나오지만,
  • 그 아래 두 row 에 대해서는 history 가 다른데도 동일한 PHT index (Gselect) 가 나온다.
• 그래서 이런 문제를 해결한 것이 Gshare Branch Predictor 이다.

• 여기서의 핵심은 LSB 를 concat 하는 것이 아니고, address 와 history 전부를 XOR-ing 하는 것이다.
  • 위 예시에서는 address 가 8bit 이니까 상관없지만 실제로는 32/64bit 이니까 아마 LSB 8bit 를 뽑아내겠지
• 그래서 이렇게 하면 history 전체가 반영되기 때문에 아래의 두 row 를 봐도 history 가 달라짐에 따라 PHT index (Gshare) 도 달라지는 것을 볼 수 있다.

Branch Target Buffer §

• 마지막으로 branch target buffer 를 간단히 보면
  • 이놈은 어디로 branch 를 뛸까를 결정하기 위해 PC 와 predicted PC 를 key-value 로 하는 buffer 라고 생각하면 된다.
  • 우선 PC 가 들어오면 이 buffer 를 lookup 해서 여기에 없으면 이 PC 가 branch 가 아니므로 그냥 일반적으로 실행하는 거고
  • 여기에 있으면 여기에 buffering 된 주소를 다음 PC 로 해서 jump 를 뛰는거다
  • 그리고 entry 의 마지막에 branch prediction 결과 (taken, not taken) 이 저장되어 있는 형태라고 한다.