[컴퓨터구조] Pipelining Hazard (파이프라인 해저드)
Hazard : 특정한 이유로 다음 clock cycle에 다음 명령어가 실행되지 않는 상황
3가지의 Hazard 원인
1. Structural Hazard
2. Data Hazard
3. Control Hazard
☞ 모든 Hazard는 waiting으로 해결된다. (stall)
1. Structural Hazard (구조적 해저드) : 자원은 하나인데 여러 명령이 동시에 수행되려고 할 때 발생
예시) memory가 하나인데, 한 명령어는 instruction fetch를 위해서, 다른 명령어는 data fetch를 위해서 memory에 접근할 때 해저드 발생
사진 설명 : instruction1 에서는 data fetch를 위해, instruction4에서는 instruction fetch를 위해 CC5일 때, 한번에 mem에 접근하려고 하고 있다. 이 때, 구조적 해저드가 발생한다.
구조적 해저드 해결책(Solution to structural hazard)
- hardward resource를 추가하면 된다. (예시에 따르면 메모리를 data 용, instruction용 두개를 datapath에 추가하면 된다.)
- 저장장소를 활용한다. (register or cache memory)
2. Data Hazard : 아직 pipeline 명령어가 끝나지 않은 register에 접근하여 명령어를 실행하려고 할 때
사진 설명 : ADD 가 $2 + $3의 결과를 $1에 저장하기 전에, SUB 명령어로 $1 레지스터를 사용해 버린다. 결과 값이 저장되기 전에 레지스터를 읽으려고 하면 데이터 해저드(Data hazard)가 발생한다. ( = 두개의 인접 명령어에 data dependency가 있다.)
데이터 해저드 해결책(Solution to data hazard)
1) Freezing the pipeline ( 앞의 명령어가 데이터를 write할 때 까지, register update 를 중지시킨다.)
사진 설명 : ADD가 $1 레지스터에 데이터를 write할 때까지, SUB는 stall을 넣어 아무것도 하지 않은채 기다린다. write를 하면, ID단계를 실행하여 $1레지스터 값을 읽는다.
사진 설명 : LW가 $1 레지스터에 데이터를 write할 때까지, SUB는 stall을 넣어 아무것도 하지 않은채 기다린다. write를 하면, ID단계를 실행하여 $1레지스터 값을 읽는다.
☞ 둘 다 2 clock 손해
2) 전방 전달 (Forwarding)
- write 하기 전, write 내용이 계산되면 다음 명령어로 미리 받아온다.
사진 설명 : ADD가 $1 레지스터에 데이터를 write 하기 위해 EX 단계에서 write 할 값을 계산한다.
이 때, ADD의 WB까지 기다릴 필요 없이 ADD의 EX단계에서 SUB의 EX 단계로 $1 레지스터 값을 input 값으로 가져오면 된다.
-> stall 필요 없음 ( EX input 결정을 위한 추가 mux 필요, datapath 수정 필요 )
☞ 시간적 이익
사진 설명 : LW가 $1 레지스터에 데이터를 저장하기 위해, MEM 단계에서 write 할 값을 memory에서 가져온다.
이 때, LW의 WB까지 기다릴 필요 없이 ADD의 MEM단계에서 SUB의 EX 단계로 $1 레지스터 값을 input 값으로 가져오면 된다.
-> stall 1번 필요 ( EX input 결정을 위한 추가 mux 필요, datapath 수정 필요 )
☞ 1 clock 손해
3) compiler scheduling ( hw를 수정하지 않고, compiler 와 assembler 만을 이용해서 software 만 수정하는 방법)
예시1) NOP instruction 추가
ADD $1, $2, $3
NOP
NOP
SUB $4, $1, $5
▤ NOP을 통해 ADD가 WB일 때, 동시에 SUB가 ID 단계 일 수 있다. (NOP 2개 이상 필수)
예시2) instruction의 순서 바꾸기
ADD $1, $2, $3
lw $6, 100($7)
AND $8,$8,$10
SUB $4, $1, $5
▤ ADD와 SUB가 사용하지 않는 register을 이용하는 명령어 2개 이상을 중간에 삽입한다. ($1 안쓰는 명령어 2개를 중간에 삽입)
3. Control Hazard : beq 혹은 J 명령어 등 분기 명령어를 통해 명령어를 건너뛰어버리면 PC 값이 변해버리고, 중간에 있는 명령어를 실행하지 않음
- pipeline instruction 실행에 영향
예시 ) pipeline에 의해서 beq다음의 명령어를 실행해야 하는데 갑자기 SUB로 넘어가 버렸다?!
30 ADD $1, $2, $3
34 BEQ $4, $10, 7 ( target address = 34+4+28 = 66)
.
.
.
66 SUB $11, $22, $2
컨트롤 해저드 해결책(Solution to control hazard)
1) stall ( 그냥 기다려 손해봐 ^^)
-문제 해결까지 일시 중지
▩ branch 가 성공한다면, WB이후 새로운 명령어에 들어가야 하기 때문에 3clock 손해 봄
2) optimized branch procession ( 손해 보더라도 조금 덜 손해 보자... 3clock 손해 -> 1 clock 손해)
(1) branch 가 됐는지 안됐는지 빨리 판단하기
(2) branch 할 주소를 빠르게 계산하기
-원래 MEM stage에서 branch prediction을 위한 PC 값이 정해진다.
- NEXT PC 값을 빠르게 결정함으로써 flush instruction 감소
▩ ID단으로 branch execution을 옮기기 (ID단이 최대임, 왜냐하면 ID단이어야 명령어가 branch인것을 해독할 수 있기 때문이다.)
☞ flush instruction 1 clock으로 감소
- 1 clock stall만 하면된다. ( there is only one instruction to flush if the branch is taken )
- branch 주소 계산하는 adder을 EX단 ☞ ID단으로 옮긴다.
- XOR과 OR의 논리게이트를 추가해 RS와 RT가 같은지 검사한다. ( ALU는 EX단에서 옮기지 않는다.)
: 각 bit 끼리 XOR한 32bit를 NOR 하기
- 하드웨어를 앞으로 당겨서 미리 branch address 를 계산하는 방식인거임.
- IF flush control 이 1 이면 : IF/ID register = NOP
-
3) branch prediction (branch 주소 예측 : 1clock도 손해보고 싶지 아놔~~ : hw적 수정임)
▩ static branch prediction
-나는 branch 가 무조건 안될거라고 예측하겠어!
- branch가 안되면 그냥 pipeline 명령어 순서대로 실행
- branch가 안될거라고 예측한게 틀리면 (branch가 되는거라면), 다음 명령어 flush ( 1clock 손해 ) 하고 branch target 명령어를 넣는다.
static branch prediction 종류
- never branch : 안일어날거라고 배팅
- always branch : 일어날거라고 배팅
- predict by op-code : beq 와 bne에 따라 안일어남/ 일어남 결정
▩ Dynamic branch prediction (동적으로 branch 될지 안될지 배팅)
branch history 필요 = 이게 branch가 됐는지 안됐는지 과거이력을 쌓아두고 그것을 바탕으로 배팅함
- 간단한 1 bit prediction scheme
☞ branch 가 일어나면 taken 으로, branch가 안일어나면 not-taken으로 유동적으로 이동
- 수정된 2bit prediction scheme
branch 가 2번 일어나야 taken으로 배팅함. 반대로 2번 실패해야 not-taken 으로 배팅함
4)Delayed branch (sw 고침)
- Branch의 바로 다음 명령어를 branch의 방향에 상관없이 실행하는 것 (always execute next instruction)
- branch 여부는 일찍 알되, hazard가 생기는지에 대한 여부는 신경 안씀
- 2번째 clock에는 새로 계산된 branch 주소가 pc에 들어가기 때문에(ID에서 branch 계산), 하나의 명령어 이후로는 제대로된 주소가 들어온다.
- 그 하나의 명령어는 NOP로 만든다.
- NOP 에 useful 한 명령어를 넣으면 어떨까? (delay slot)
