4.8 Control Hazards

🔑Table of Contents

1. Branch Hazards
2. Reducing Branch Delay
3. Data Hazards for Branches
4. Dynamic Branch Prediction(동적 분기 예측)
5. 1-Bit Predictor : Shortcoming (결점, 단점)
6.  2 -bit Predictor
7. Calculation the Branch Target(address)

---

📌 Branch Hazards

브랜치 결과가 MEM단계에서 결정난다면?

Control hazard에서 브랜치 결과를 알기 위해 기다리는 것이 아닌 아닌것으로 가정

아니면 그대로, 맞으면 제대로 명령어를 가져와 수행하기로 함

• 결과 맞으면 그동안 미리 예측해 수행한 명령어는 버려야함
• 제어신호를 0으로 해 비워야

📌 Reducing Branch Delay

예측에 실패하더라도 버려지는 단계를 줄여보자 

• branch 결과를 구하는 것을 ID에서 할 수 있도록 하드웨어를 옮긴다 
  • target address adder (대상 주소를 PC + 4 + offset해주던 ALU,left shift, sign extend)
  • register comparator ( ALU로 빼서 zero인지 봤던)
• 예시 

36: sub $10, $4, $8
40: beq $1, $3, 7
44: and $12, $2, $5
48: or $13, $2, $6
52: add $14, $4, $2
56: slt $15, $6, $7
...
72: lw $4, 50($7)

 

• beq는 다음 stage들도 넘어가도 딱히 할일은 없음 
• 예측이 맞다면 상관없이 다음 명령어 계속 수행
• 틀리고 정말 분기로 이동해야한다면 분기 주소를 PC애 넣어 해당 명령어를 IF할 수 있도록하고 직후 명령어인 IF는 파기한다
• 기존 모델에서 예측으로 실행해둔 여러 명령어를 버리면서 여러 사이클의 버블이 발생하지만 ID stage에서 분기 결과값을 구함으로써 1번의 버블로 줄일 수 있음

📌Data Hazards for Branches

• 만약 branch에서 비교하려는 레지스터가 2,3사이클 전의 rd라면 (WB전) - forwarding을 사용해 해결가능
• 만약 비교하려는 레지스터가 1 사이클 전의 ID/EX.RegisterRd거나 2사이클 전의 EX/MEM.RegisterRt라면 forwarding불가 stall 발생
• 2사이클 전 명령어가 lw면 , beq의 값이 없음 두개 stall발생

📌 Dynamic Branch Prediction(동적 분기 예측)

• 초대형 파이프라인에서 브랜치 패널티의 중요성 
  • stage수가 많으면 나눠서 일을 하니 단일 명령어 처리 속도가 빨라지지만 stall도 여러 사이클 발생가능 (브랜치 패널티 심화됨)
  • 브랜치 결과 확인 지연
    • 초대형 파이프라인에서는 ID단계에서 확인 못하고 EX/MEM 등에서 결정 → 예측 실패시 Flush, stall등 손실이 커짐
• 동적 브랜치 예측을 사용하자
  • 개념 = 분기예측 버퍼를 활용해 브랜치의 과거 결과를 기반으로 분기를 예측 
  • 각 브랜치 명령어의 주소를 인덱스로 사용하고 브랜치 결과를 Taken/Not Taken으로 기록
  • branch를 수행하려면
    • 브랜치 명령어 발생 ( 분기예측 버퍼를 조회해 저장된 결과(Taken/Not Taken)을 기반으로 예측)
    • 명령어 가져오기 (브랜치 대상 주소/다음 명령주소에서 명령어 가져오기)
    • 결과확인 (예측이 맞았는지 확인 → 실패시 잘못된 명령어 모두 제거(flush))
  • 예측 실패 영향
    • 예측이 틀릴 경우 파이프라인 전체를 플러시해야해서 더 많은 사이클 손실 발생
    • 최소화 하려면 2 비트 예측기 사용

📌  1-Bit Predictor : Shortcoming (결점, 단점)

최근 분기의 결과(Taken/Not Taken)을 기반으로 다음 분기 예 

 

• 다중 loop에서 안쪽 loop branch는 예측실패를 두번한다 (처음, 마지막)

• 안쪽 loop종료시 예측 실패
  • 안쪽 loop는 Taken으로 예측되다가 종료시점에서 Not Taken이 되므로 예측 실패
• 안쪽 loop 시작 시 예측 실패 
  • 안쪽 루프 종료 후 바깥쪽 루프로 돌아가면 Not Taken으로 예측된다 그 후 다시 안쪽 루프 실행시에 Taken으로 시작되어야하기에 예측 실 

 

 

📌 2 -bit Predictor

두번의 연속된 예측 실패가 일어나야 예측 기준의 결과를 역전함

11↔10↔01↔00

 

📑문제 다음 괄호안에 들어갈 값은 어떻게 되는지 적어보시오

사이클	2비트 상태	예측	분기결과	2비트 상태
1	00	not taken	taken	01
2	01	not taken	not taken	00
3	00	not taken	taken	01
4	01	not taken	taken	10
5	10	taken	taken	11

 

 

📌 Calculation the Branch Target(address)

• branch 명령어를 위해 기존의 EX에서든 , ID든 대상 주소를 계산 (PC+4  + address)해야함
• predictor을 사용하더라도 여전히 대상 주소는 계산해야한다 
  • 브랜치마다 1사이클 패널티 
• branch target buffer
  • 반복될 branch라면 아예 대상 주소를 기억해두고 재사용하기
  • 대상 주소의 캐시(cache)
  • instruction fetch때 PC에 의해 index됨
    • 만약 예측이 적중하면 대상 주소의 명령어를 즉시 fetch가능 (이미 buffer에 있는 주소면 주소 계산의 오버헤드가 사라진다)