Static pipeline with out-of-order execution completion(1)

 
 
 
 
5-stage pipeline

Basic 5-stage pipeline

 
 
 
independent한 load, store, ALU instruction을 수행한다.
여기서 instruction이 independent하다는 것은 register나 memory location 등 resource를 서로 공유하지 않는다는 것을 의미한다. 한 stage에서 다음 stage로 instruction이 이동할 때마다 instruction은 recode 되고 다시 recode된 instruction은 매 clock cycle 마다 clock signal에 따라 동작한다. 
 
 
data path의 주요 resource
- instruction memory (cache)
- register file
- 2 read ports
-1 write port
- ALU
- data memory (cache)
 
 
 
일반적으로 data dependency는 register operand와 memory operand에 존재한다.
한 clock에 하나의 instruction을 수행하는 instruction이 fetch되기 이전에 fetch 되었던 instruction들의 결과값이 available하기 때문에 machine에서 data dependency는 어떠한 hazard도 일으키지 않는다. 
하지만 multiple instruction이 동시에 execution 단계에 있다면 data dependency는 data hazard를 일으킨다.
 
 
 
 
Data hazard의 원인
1. data dependency
2. instruction flow of micoarchitecture
3. structure of microarchirecture
 
 
 
 
Data hazard의 type -> memory와 register에서 발생
1. RAW (read after write)

true data dependency를 다룸

following 하는 instruction이 preceding instruction의 result를 필요로 할 때
following instruction이 preceding instruction의 operand를 wait하지 않으면 오래된 값을 read하게 됨

add r2, r5, r3
add r3, r2, r3

첫번째 instruction에서 r2에 write back 되기도 전에 두 번째 instruction에서  r2 값을 read하려할 때

-> forwarding으로 이를 해결할 수 있다.

 

WAR과 WAW는 RAW와는 다르게 여러 thread를 통해 각 instruction이 parallel하게 실행되는 상황에서 발생한다. 

(thread 1개에 instruction 1개가 할당됨)
2. WAR (write after read)
following 하는 instruction이 preceding instruction의 operation에 write 할 때
write가 read보다 먼저 진행되면 preceding instruction은 현재 register 값 대신 나중의 값을 read하게 됨

add r2, r5, r3  ->  1
add r3, r2, r1  ->  2

-첫 번째 instruction이 먼저 실행되고 나서 두 번째 instruction이 실행되는 상황

-두 번째 instruction이 먼저 실행되고 나서 첫 번째 instruction이 실행되는 상황

instruction이 실행되는 순서에 따라 (1->2 or 2->1) r3값이 달라진다.

 

3. WAW (write after write)
following 하는 instruction이 preceding instruction와 동일한 operation에 write 할 때
follwing instruction의 write가 preceding instruction의 write보다 먼저 일어날 경우, operand의 최종 결과 값은 preceding instruction의 write값이 되어 버리므로 오래 된 값이 된다. 

add r2, r5, r3  ->  1
add r2, r1, r3  ->  2

-첫 번째 instruction이 먼저 실행되고 나서 두 번째 instruction이 실행되는 상황

-두 번째 instruction이 먼저 실행되고 나서 첫 번째 instruction이 실행되는 상황

instruction이 실행되는 순서에 따라(1->2 or 2->1) r2의 결과값이 달라진다.

 

RAW) store -> load for the same address

WAR) load -> store for the same address

WAW) store -> store for the same address 

 

 
- 5-stage pipeline에서 memory operand는 hazard를 일으키지 않는다. 
load, store instruction은 MEM stage에서만 in-order 하게 액세스되기 때문에 data dependency를 고려하지 않아도 된다.(only 1 cycle). 5-stage pipeline에서 MEM stage는 sequential한 방식으로 액세스되기 때문에 main memory에 대한 액세스는 atomic하다. 따라서 main memory에서 data dependency는 발생하지 않는다.
 
- 5-stage pipeline에서 ID stage와 WB stage 사이에는 time gap이 존재하기 때문에 register file에 대해서는 data dependency가 존재한다.
 
- 5-stage pipeline에서는 RAW hazard만 고려하면 됨(WAW, WAR는 고려x) -> RAW hazard를 막으려면 data를 forwarding 해야 한다.
- 5-stage pipeline에서 모든 hardware component는 모든 stage에서 sequential하게 사용되기 때문에 2개의 instruction이 동일한 cycle에서 동일한 리소스를 사용하기 때문에 발생하는 structural hazard는 고려할 필요가 없다.
- Control hazard는 Branch, jump, exception으로 인해 발생
 
 
 
Exceptions in 5 stage pipeline
- 파이프라인은 overlap된 instruction execution으로 성능을 향상시키지만 instruction의 flow가 갑자기 interrupt되면 문제가 생기게 된다. 여기서 많은 exception은 precise하게 진행될 필요가 있다.
- exception이 detect되면 excetion handler에 의해 처리되어야 하고 프로세서는 exception이 일어나기 전의 상태를 저장해 두어서 exception을 완료한 다음 원래 상태로 돌아오도록 해야 한다.
- 5-stage pipeline에서 exception은 IF, ID, EXE, MEM stage에서 발생할 수 있다. WB에서는 register file에 write하는 동작만 남아있기 때문에 exception이 발생하지 않는다.
 
 

---

Why out-of-order instruction completion?
 performance improvement

프로세서에서 돌아가는 instruction의 갯수를 증가시키기 위함이다.

즉 ILP를 증가시키기 위함이다.

 

ILP란?

파이프라인 방식을 사용하는 이유 : performance를 향상시키기 위해서이다.

exploiting instruction level parallelism

= increasing instructions running inside a processor

= increase performance of processor by using parallelism

 

TLP란?

increase the number of thread which are running inside of a processor

In multicore processor, we can increase performance by using parallelism

 

 

 

 

 

out-of-order instruction completion
 

out-of-order execution pipeline 아키텍쳐

 
5 stage pipeline architecture에서 모든 instruction은 in-order 방식을 사용해서 pipeline의 stage를 순서대로 진행했다. 
OoO pipeline은 IF, ID, MEM, WB stage를 각각 in-order 방식으로 진행한다.
OoO pipeline은 2가지의 specialize된 pipeline을 실행한다.
1. integer instructions
2. floating point instructions
instruction의 opcode를 기반으로 매 cycle 마다 decoder는 instruction을 integer 혹은 floating point pipeline으로 보낸다.
 
- OoO pipeline의 ID stage에는 integer operand를 처리하기 위한 INT register, floating point operand를 처리하기 위한 FP register가 있다.
- 두 pipeline 모두 IF(in-order) -> ID(in-order) -> EXE (FP datapath의 경우 out-of-order) -> MEM (in-order) -> WB stage (in-order) 를 거친다.

 
 
INT data path = total (4+1 [EXE]) = 5 cycle

- INT unit : INT instruction, branch, load/store instruction 처리
- INT pipeline의 EXE stage에서 integer arithmatic unit structure는 매우 간단하다. 따라서 1 cycle이 걸린다.
 
 
FP data path = total (4+5 [EXE]) = 9 cycle

 
- FP pipeline의 EXE stage에서 floatin point arithmatic unit structure는 매우 복잡하다. 따라서 총 5 cycle이 걸린다.
- FP instruction은 INT instruction 이후에 실행된다.
- 5 stage pipeline architecture와 비교했을 때 OoO architecture는 instruction을 out-of-order 방식으로 실행하며 더 복잡하다. -> out-of-order completion 발생
- out-of-order completion : EXE 단계에서 FP instruction을 reorder함으로써 instruction이 complete되는 순서를 optimize
 
 
Data forwarding path

data forwarding path

 
- store instruction으로 인해 FP/ME -> ID/EX로 가는 path와 ME/WB -> ID/EX로 가는 path가 추가됨

• address part : address 생성으로인해 address를 store -> ME/WB -> ID/EX path
• data part : register에서 data 를 fetch해와서 그 data를 store -> FP/ME -> ID/EX path

- MEM stage에서 FP instruction은 memory에 액세스 하지 않는 별도의 path를 사용하여 memory를 bypassing한다. 
- INT 및 FP instruction은 각각 1개씩만 WB stage에 액세스 할 수 있다.
- WB stage에서 register write port에 대해 1개의 instruction만 clock 당 액세스할 수 있다.
 

structural hazard on the write port of register file -> structural hazard in OoO pipeline

I1(ADD.D)은 C9에 FP register에 write하려 한다. 
I5(L.D)역시 C9에 FP register에 write를 하려 한다.
floating point register file에 write operation을 수행하는 port가 딱 1개 있다면 structural hazard가 발생한다. 
따라서 더 나중에 실행되는 명령어인 I5는 I1보다 priority가 낮으므로 write back이 delay된다.
 
 
 
Hazard detection unit
hazard detection unit은 EXE pipeline에 여전히 있는 이전 instruction과 register dependecy를 가진 경우, 해당 instruction을 ID stage에서 중단해야 한다. 이 때 data hazard (RAW, WAW hazard) 가 발생한다. 
따라서 ID stage에 있는 inst의 의 src reg =  EXE stage에 있는 inst의 dst reg 라면 stall 해야함
 
 
 
Latency vs Initiation interval
 

latency of operation and initiation interval

latency
- 특정 instruction이 result를 생성하고, 그 result를 사용하는 instruction간의 최소 cycle 수
- 만약 functional unit이 linear한 pipeline이면 instruction latency = execution time - 1
 
 
Initiation interval
- 동일한 unit에 instruction이 연속적으로 issue되는 경우 걸리는 cycle 수
 
 
 
latency와 initiation interval은 다른 metric이며 이에 기반해서 data forwarding unit과 hazard detection unit을 design할 수 있다.
 
*hardware는 instruction을 in-order 방식으로 매 cycle 마다 issue하지만 사실 hardware는 compilation time을 고려하며 실행되진 않는다.
따라서 hardware에 기반해 OoO pipeline을 실행하게 되면 performance가 향상되지 않기 때문에 compiler는 instruction reorder이나 loop unrolling 등의 일부 compile optimization technique을 적용해야 한다. 
 
 
 
case1) Integer ALU

add r1 r2 r3
add r4 r1 r5

- r1 register로 인해 data dependency가 발생한다.
하지만 pipeline에 data forwarding path가 있기 때문에 첫 번째 add 명령어 바로 다음 cycle에 두 번째 add 명령어가 실행된다. 따라서 RAW 해저드는 해결되고 data dependency도 해결되어 cycle 낭비가 없기 때문에 integer alu의 latency를 고려할 필요가 없다. -> latency = 0
- 첫 번째 add 명령어가 issue되고 나서 뒤따라 오는 add 명령어가 issue되는 시점 사이 존재하는 cycle 수가 1cycle이다.
-> interval = 1
 
 
case2) Load
- 이전에 issue된 instruction이 load instruction이고 뒤따라 오는 instruction이 data property를 갖고 있다면 1cycle을 stall해야 한다. 이 때 OoO execution의 실행을 최적화 하기 위해 compiler는 두 instruction 사이에 1instruction을 insert한다.
-> latency = 1 
- instruction이 issue되고 나서 바로 다음 cycle에 다음 instruction이 하드웨어적으로 issue된다. -> interval = 1
 
 
case3) FP OP
- 이전에 issue된 instruction이 FP instruction이고 뒤따라 오는 instruction 역시 FP instruction의 경우 compiler optimization technique에 의해 independent한 4개의 instruction이 두 instruction 사이에 실행된다 -> latency = 4
- instruction이 issue되고 나서 바로 다음 cycle에 다음 instruction이 하드웨어적으로 issue된다. -> interval = 1
 
 
 
 
Data hazard in OoO completion

OoO pipeline에서는 FP instruction(위 표에서 MULT.D명령어)로 인한 latency가 4 cycle이므로
RAW hazard로 인한 stall이 5 stage pipeline에서보다 더 빈번하게 발생한다. 
 
 
 
Control hazard in OoO completion
5 stage pipeline에서와 마찬가지로 EXE stage에서 branch instruction으로 인한 hazard는 branch를 taken할 지 not taken할 지로 결정된다. 만약 branch를 taken한다면 EXE stage의 끝에서 IF와 ID stage에 있는 instruction을 flush한다.