Data Hazard in ALU

• 종속성을 갖는 프로그램 코드
  sub $2, $1, $3
  and $12, $2, $5
  or $13, $6, $2
  add $14, $2, $2
  sw $15, 100($2)

• 첫 번째 $2의 결과에 밑에 4개의 코드가 모두 종속적이다
• We can resolve hazards with forwarding

Dependency & Forwarding

(내용이 많이 복잡해서 교재 보면서 정리한다)

• 우선, 위 그림의 파란색 선은 종속성(dependency)를 나타낸다
  각 명령어마다 $2를 사용하는 단계를 표시해두었다.
• 교수님께서 수정해주셨지만,
  일단 교재에서는 읽기는 clock cycle의 앞부분,
  쓰기는 clock cycle의 뒷부분에서 일어난다고 가정한다
• 따라서 위 코드에서 add와 sw에서는 올바른 $2의 값을 사용할 수 있다.
  결국, dependency 선이 시간 축에서 뒤로 갈 때 문제가 발생한다
  
  

• A Pipeline Processor[2]에서, 잠깐 보았듯이,
  $2의 계산은 EX 단계의 끝에서 만들어진다.
  즉, CC3의 끝에서 $2는 완성이다.
• and와 or이 $2의 값을 필요로 하는 부분은 CC4와 CC5이다.
  따라서,
  데이터가 register file에서 읽을 수 있게 되기 전이라도,
  데이터가 가용되자마자 이를 필요로 하는 유닛으로 forwarding(전방전달)하기만 하면
  이 코드들을 delay 없이 실행할 수 있다
  
  

• 교재에서는 단순화를 위해 EX단계의 연산으로 forwarding하는 문제만 생각한다.
  ALU연산 또는 실제 주소 계산을 위한 ALU의 입력으로 그 값이 필요하다.
• Data hazard의 조건
  • 1a. EX/MEM.RegisterRd = ID/EX.RegisterRs
  • 1b. EX/MEM.RegisterRd = ID/EX.RegisterRt
  • 2a. MEM/WB.RegisterRd = ID/EX.RegisterRs
  • 2b. MEM/WB.RegisterRd = ID/EX.RegisterRt
• 위 코드들에 대입하면,
  sub-and는 1a,
  sub-or는 2b이다.
  
  

• 그런데, 어떤 명령어들은 register에 쓰기를 하지 않는다. (?? 음...)
  즉, 필요가 없는데도 forwarding하는 경우가 있다.
• 이를 확인하는 방법은,
  먼저 RegWrite 신호가 활성화되어 있는지 확인한다.
  EX/MEM.Regster의 WB제어 필드를 확인하면 RegWrite 신호가 인가되었는지 확인할 수 있다
  • EX/MEM.RegWrite
  • MEM/WB.RegWrite
• 다음은,
  목적지가 $0인지 확인한다.
  $0는 항상 0을 갖기 때문에 그 값을 변경할 수 없다.
  결국, 목적지가 $0라면 결과값을 굳이 forwarding할 필요가 없다.
  • EX/MEM.RegisterRd ≠ 0
  • MEM/WB.RegisterRd ≠ 0
    
    

• 이제, 올바른 데이터를 forwarding해야 한다
  모든 pipeline register에서 ALU 입력을 가져와서
  ALU 입력에 멀티플렉서를 추가하고 적절한 제어를 붙이면
  적절한 데이터를 forwarding할 수 있다.
  
• 이러한 forwarding제어는 EX단계에서 이루어진다.
  따라서 forwarding 여부를 결정할 수 있게 피연산자 레지스터 번호를
  ID 단계에서부터 pipeline register를 거쳐 전달해 주어야 한다.
• rt(20:16)은 이미 ID/EX에 저장되어 있고,
  이전까지는 rs(25:21)이 필요가 없었는데, 이제부터는 ID/EX에 추가해 주어야 한다.
• 위 그림의 ForwardA와 ForwardB값에 따라
  forwarding의 종류가 달라진다

• MUX Control	Source	Explanation
  ForwardA == 00	ID/EX	first ALU operand comes from register file
  ForwardA == 10	EX/MEM	first ALU operand is forwarded from the prior ALU result
  ForwardA == 01	MEM/WB	first ALU operand is forwarded from data memory or an earlier ALU result
  ForwardB == 00	ID/EX	second ALU operand comes from register file
  ForwardB == 10	EX/MEM	second ALU operand is forwarded from the prior ALU result
  ForwardB == 01	MEM/WB	second ALU operand is forwarded from data memory or an earlier ALU result

  
  

• 이제 EX hazard와 MEM hazard의 조건과 control signal을 정리한다

// EX HAZARD
if ( (EX/MEM.RegWrite) && (EX/MEM.RegisterRd ≠ 0) && (EX/MEM.RegisterRd = ID/EX.RegisterRs) )
	ForwardA = 10

if ( (EX/MEM.RegWrite) && (EX/MEM.RegisterRd ≠ 0) && (EX/MEM.RegisterRd = ID/EX.RegisterRt) )
	ForwardB = 10

// MEM HAZARD
if ( (MEM/WB.RegWrite) && (MEM/WB.RegisterRd ≠ 0) && (MEM/WB.RegisterRd = ID/EX.RegisterRs) )
	ForwardA = 01
if ( (MEM/WB.RegWrite) && (MEM/WB.RegisterRd ≠ 0) && (MEM/WB.RegisterRd = ID/EX.RegisterRt) )
	ForwardB= 01

• 한 가지 문제는 모든 명령어 코드가 같은 레지스터를 읽고 쓰려고 할 수도 있다
  Double Data Hazard
• add $1, $1, $2
  add $1, $1, $3
  add $1, $1, $4
• 이 경우, 두 Hazard가 모두 일어난다.
  우리는 더 최근의 값을 사용해야 하기 때문에,
  MEM 단계로부터 forwarding을 받아야 한다.
  즉, EX Hazard로 판단한다.
• 그래서 MEM HAZARD에 대한 조건을 추가한다

// MEM HAZARD
if (MEM/WB.RegWrite) && (MEM/WB.RegisterRd ≠ 0) && (MEM/WB.RegisterRd = ID/EX.RegisterRs) )
	&& not ( (EX/MEM.RegWrite) && (EX/MEM.RegisterRd ≠ 0) && (EX/MEM.RegisterRd = ID/EX.RegisterRs) )
	ForwardA = 01
if (MEM/WB.RegWrite) && (MEM/WB.RegisterRd ≠ 0) && (MEM/WB.RegisterRd = ID/EX.RegisterRt) )
	&& not ( (EX/MEM.RegWrite) && (EX/MEM.RegisterRd ≠ 0) && (EX/MEM.RegisterRd = ID/EX.RegisterRt) )
	ForwardB= 01

Datapath with Forwarding

Delay with Data Hazard (Load-use)

(여기도 교재 참고해서 차근차근 정리한다)

• lw 명령어를 뒤따르는 명령어가
  lw에서 쓰기를 행하는 register를 읽으려고 시도할 때,
  forwarding으로 해결이 안된다.
  즉, 누군가가 pipeline을 지연시켜야 한다.
  
  
  

• 따라서 forwarding unit뿐만 아니라
  hazard detecting unit도 필요하다.
  이 유닛은 ID 단계에서 동작하여,
  lw 명령어와 결과 값 사용 사이에 delay를 추가할 수 있도록 한다
• 다음과 같은 조건을 갖는다

  if (	ID/EX.MemRead 	// 명령어가 lw인지 확인한다. (lw : 데이터 메모리를 읽는 유일한 instruction
          && ( (ID/EX.RegisterRt == IF/ID.RegisterRs)
              or (ID/EX.RegisterRt == IF/ID.RegisterRt) ) ) // EX단계의 lw의 목적지 register가 ID단계의 명령어의 근원지 register인지 확인
      stall the pipeline

• 위 조건을 만족하면 명령어는 1 clock cycle 지연된다
  
  

• ID 단계에 있는 명령어가 지연되면, IF 단계 명령어도 지연된다.
  이처럼 두 명령어의 진행을 막기 위해서,
  PC register와 IF/ID pipeline register를 변하지 않게 한다
• PC register가 그대로 유지되면
  IF단계에서는 똑같은 명령어를 계속 읽는다.
  IF/ID pipeline register가 그대로 유지되면
  ID단계에서는 같은 명령어 필드를 이용해서 rs, rt register를 계속 읽는다.
• EX단계부터는, 아무런 효과 없는 nop을 실행한다.
• ID/EX register에 들어가는 control 값들을 모두 0으로 설정한다.
  
  

• 
• 

---

Branch Hazard

(ppt 내용 기반으로 정리한다)

• 분기를 할 것인가에 대한 결정은 MEM 단계에서 이루어진다.
  
• branch가 결정되었으면, hazard를 해결하기 위한 방법은 두 가지이다
  
  

• branch가 일어나지 않는다고 가정한다
  branch가 일어나지 않는다고 예측하거, 명령어들을 순서대로 계속 실행한다
• 만약 branch가 일어났다면, fetch와 decode되었던 명령어들은 모두 버리고, branch target에서 실행을 계속한다
• 결국, 고려해야 할 것은 명령어들을 버리는 비용이다. 이게 거의 없다면, 이 방법은 hazard의 대가를 절반으로 줄인다.
• 명령어를 버리는 방법은, load-use에서 한 것 처럼,
  원래 control 값을 0으로 바꾸는 것이다.
  MEM단계에 도달했을 때, IF, ID, EX 단계에 있는 3개의 명령어를 바꿔주어야 한다.
• 이를 flush(쓸어낸다)라고 한다.
  
  

• branch에 따른 지연을 줄인다
  이전까지는 branch했을 경우 target address가 MEM단계에서 결정된다고 했다.
  이제부턴 이걸 앞으로 좀 당긴다
• branch target address를 계산하는 것과
  branch 여부를 판단하는 것, 이 두 가지 일이 더 일찍 일어나게 한다.
  • branch target address
    • IF/ID register에는 이미 PC값과 offset이 저장되어 있다.
    • 따라서 branch adder를 EX단계에서 ID 단계로 옮겨준다.
  • branch 여부
    • (교재에 보면 많은 어려움이 있다)
    • 어쨌든 ID 단계로 옮긴다.

---

Data Hazard for Branch

case 1 : comparison register is destination of
2nd or 3rd preceding ALU insturction

• Can resolve using forwarding

---

case 2 : comparison register is destination of
preceding ALU instruction or
2nd preceding load instruction

• Need 1 stall cycle

---

case 3 : comparison register is destination of
immediately preceding load instruction

• Need 2 stall cycles