Pipeline Hazards 2

• Branch Hazards

  • branch 할 때(beq의 경우 EX단계에서 비교함) → 그로인한 new pc value를 업데이트 해서 넘겨줘야함
    • IF단계 이전에 new pc value를 갱신함
    • 그로 인해 생기는 bubble cycle = branch overhead = penalty

  

• branch delay (penalty)를 줄여보자!

  • 레지스터의 값을 비교하는 것을 EX → ID단계로 옮겨보자
  • ID단계로 타겟 address 계산을 옮겨보자
  • slack은 stage마다 stage중 가장 긴 clock period(전체 clock period가 됨) - 개인의 clock period = 즉, 남는시간(낭비되는)

• 그림 2개를 보면 이해가 될 것이다. 남는 시간(slack)에 xor계산을 해줌으로써 ID단계에서 비교 및 계산을 수행할 수 있다!

• Branch 바로 이전에 ALU/Load 명령어가 오는경우(이전까지는Branch→ALU, Load 이런 경우만 해당됐었음)

  • ALU - Branch사이에 bubble이 1개 필요하다
    • ALU : EX단계에서 계산됌 / branch(beq..) : ID단계에서 비교함

  

  • Load - Branch사이에 bubble이 2개 필요하다

    • Load : MEM 단계에서 계산됌 / branch(beq..) : ID단계에서 비교함

    

• Branch Prediction

  • 예측하면 성능향상! (예측이 정확하지 않을떄만 stall로 인한 bubble이 생기는 것은 어쩔 수 없다.)
    • 예측이 틀리다면 취소하고 올바른 branch로 바꿈!
  • 예측 방법

    • 항상 branch가 되지 않은 것(not taken)으로 간주하면 됌!

      • PC + 4로 PC 값을 업데이트
      • 만일 예측이 틀리다면, pipeline에서 예측된 명령어를 취소하고, branch의 실제 타겟에 맞는 PC값으로 업데이트

      

      예시를 보면 쉽게 이해할 수 있다!

      • 예측에 성공한 경우

      

      • 예측에 실패한 경우

      

      • IF/ID → 0으로 만들어서 뒤에 stage들을 실행하지 않도록함**( Flush !)**

      

    • Flush(명령어 취소)는 어떻게 이루어지나?

      • IF/ID flip flop에 IF.Flush를 control signal로 연결함

        • IF.Flush를 통해 IF/ID register을 0x00000013로 만듦
          • ⇒ addi x0, x0, 0 = nop(no-op, no operation)
            • 아무것도 바꾸지 않는 상태를 의미함

      • 언제 이루어지나?

        1. ID에서 현재 명령어가 beq인지 control이 check
        2. 레지스터값이 둘이 같은지 다른지 control이 check
        • beq이고, 둘의 값이 같다면 → Control이 신호를 줘서 IF.Flush를 보내고, PC + imm : branch target을 보냄
          • 밑의 그림에서 빨간색 화살표!

        

    • More-Realistic Branch Prediction

      • Static Branch Prediction : 정적 분기 예측
        • 정의 : 특정 branch 명령어의 동작 패턴을 사전에 정의하고, 이에 따라 결과를 예측한다.
          • perfect하지 않다. (outcome을 중간에 바꾸지 x)
        • 예시
          • Loop(for, while) → Bachward branches : taken
            • n번의 루프 → 1번(마지막루프) not taken, n-1번 taken ⇒ n=100이라면 99% 예측 성공
          • If-else → Forward branches : not taken
          • loop → imm = 음수 / if-else → imm = 양수
      • Dynamic branch prediction : 동적 분기 예측
        • 정의 : 하드웨어가 현재 프로그램의 branch 동작을 모니터링하여 최근 branch결과를 기록하고 이것을 기반으로 outcome를 예측한다.
          • 중간에 outcome이 바뀔수도 있다.
        • Branch Prediction Buffer
          • 이를 통해 최근 명령어 주소가 인덱싱되고, branch 결과를 기록함(taken인지 not taken인지)
          • 새로운 branch를 마주하게 되면
            • table(buffer)를 체크하여 결과를 예측하고, 맞다면 타겟 명령어를 fetch 틀리다면 flush and 예측을 뒤집는다(not t → t / t → not t)

    • Branch Prediction Buffer 자세하게 살펴보자

      • not taken → 0 / taken → 1로 표현 (1 bit 표현, 기본은 0)

      

      • 1 bit predictor

        • 1개의 비트로 not taken / taken을 구분하는 방법
        • 반복문의 맨 처음과 맨 뒤가 무조건 예측 실패임!

        

        • 한계점 : 이중 반복문이 있을 경우 한계점이 드러남

          • i3 = inner loop prediction
          • i4 = outer loop prediction

          i3의 반복문이 1회라 예측결과가 엉망으로 나온다.

        

      • 2-Bit Predictor

        • 00 : Strongly Predict Not Taken (강하게 분기하지 않을 것으로 예측) → not taken 예측
        • 01 : Weakly Predict Not Taken (약하게 분기하지 않을 것으로 예측) → not taken 예측
        • 10 : Weakly Predict Taken (약하게 분기할 것으로 예측) → taken 예측
        • 11 : Strongly Predict Taken (강하게 분기할 것으로 예측) → taken 예측
          • taken 과 not taken의 경계를 2분법이 아닌 중간 단계를 만들어 나눈 느낌
          • 밑의 그림을 참고해서 이해!
            • 00에서 taken이라면 01로 변경 → 또 taken이라면 10으로 변경

        

        • 위의 1bit predictor에서 안 좋은 결과에 대입해보면

        

    • buffer

      • memory 사이즈 > prediction buffer 사이즈

        • 여러 명령어가 하나의 buffer entry에 매핑됨

        

      • 분기 타겟 계산

      • Multiple issue (여태까지 1cycle에 1개의 single 명령어 실행)

      • MIPS with Static Dual Issue 두 명령어 동시 실행

• 요약