9. 파이프라인 (Pipelining)

명령어의 수행은 Instruction Fetch부터 Write Back까지 크게 5단계에 걸쳐 수행된다.
파이프라이닝은 이러한 5단계를 동시에 수행하도록 하여 속도를 향상시키는 방법이다.

	1	2	3	4
명령어 A	Instruction Fetch	Operand Fetch	Execute	Write Back
명령어 B		Instruction Fetch	Operand Fetch	Execute
명령어 C			Instruction Fetch	Operand Fetch

$n$개의 과정을 파이프라이닝 할 경우, 각 과정을 순차적으로 실행하는 거에 비해 $n$배에 수렴하는 속도 향상을 갖는다.

MIPS의 파이프라인

MIPS에서는 명령어 실행을 아래 단계로 구분하여 파이프라인을 만든다.

1. IF: Instruction Fetch from memory
2. ID: Instruction Decode & Register Read
3. EX: Execute Operation or Calculate Address
4. MEM: Access memory operand
5. WB: Write Result back to register

이때, 각 단계에 소요되는 시간이 다를 수 있는데, 이 경우 파이프라인의 기준은 가장 소요시간이 긴 단계에 맞춰진다.
그렇기에 각 단계에 소요되는 시간은 비슷할 수록 성능향상의 폭이 커진다.

MIPS for Pipelining

MIPS ISA는 사실상 파이프라인을 위해 만들어졌다.

모든 명령어가 32bits인 특징은 Fetch 및 Decode를 One Cycle에 처리하기 용이하게 해준다. 기본 명령어 포맷의 종류가 적은 점도 Decode와 Register Read를 빠르게 처리하게 해준다.

Load/Store 명령어가 3단계에서 주소를 계산하고 4단계에서 메모리에 접근함으로써 한 사이클 안에 메모리 접근도 가능하다.

Hazard

파이프라인에서, Next Cycle의 다음 명령어가 시작되어야 하는 것을, 모종의 이유로 방해받는 상황을 해저드라고 한다.

• Structure Hazard: Required Resource가 어떤 이유로 Busy한 경우
• Data Hazard: 이전 명령어의 Data read/write가 끝나지 않아 대기하는 경우
• Control Hazard: Control이 이전 명령어의 결과에 의존적인 경우

Structure Hazard

Resource Conflict로 인해 발생한다. Load/Store 과정에서 Data Access가 발생하는데, 이 과정이 다른 사이클의 Instruction Fetch에서 진행하는 메모리 접근과 충돌하면 발생한다.

이로인해 파이프라인이 한 사이클을 쉬어가는 Stall이 발생하고, 파이프라인에 버블이 생긴다.

따라서, 파이프라인 데이터패스는 Instruction/Data Memory혹은 Cache를 분리할 필요가 있다.

Data Hazard

Data Hazard는 대표적인 의존성 문제이다. 이전 명령어가 작업 중인 Data에 다음 명령어가 영향을 받는 경우로, 역시 파이프라인 버블을 야기할 수 있다.

add $s0, $t0, $t1
sub $t2, $s0, $t3

위 코드에서, sub 명령어가 수행되려면 앞서 add 명령어가 완료되어 s0 레지스터에 결과가 저장되어야 한다.
결국, add 명령어가 끝날 때까지 sub 명령어는 Execute를 하지 못하고 대기해야 한다.

Fowarding, Bypassing

Data Hazard를 해결하는 방법으로, 이전 명령어의 Execute가 끝나면 결과를 바로 다음 명령어로 넘겨준다. (레지스터를 거치지 않고)

Datapath 내에 Extra Connection이 필요하다.

Data Hazard를 피하는 코드 스케쥴링

Data Hazard가 발생할 수 있는 명령어의 실행순서를 일부 바꾸어 해저드를 피할 수도 있다. 예를들어 A=B+E; C=B+F;를 실행할 때 원래 코드는 다음과 같다.

lw $t1, 0($t0)
lw $t2, 4($t0)
add $t3, $t1, $t2 # t2가 다 불러와지지 않아 stall 발생
sw $t3, 12($t0)
lw $t4, 8($t0)
add $t5, $t1, $t4 # t4가 다 불러와지지 않아 stall
sw $t5, 16($t0)

위 코드에서, stall이 발생하지 않도록 다음과 같이 명령어 순서를 수정해 줄 수 있다.

lw $t1, 0($t0)
lw $t2, 4($t0)
lw $t4, 8($t0) # t2가 로드되는 동안 t4도 미리 로드해 놓기
add $t3, $t1, $t2 # t2 로드되어 정상 실행
sw $t3, 12($t0)
add $t5, $t1, $t4 # t4 미리 로드되어 정상 실행
sw $t5, 16($t0)

Forwarding만으로는 항상 stall을 막지 못하기 때문에, lw 명령어의 위치 수정을 적절히 병행할 수 있다.

Control Hazard

컨트롤 해저드는 branch 명령어에 의해 발생된다. branch 이후 명령어는 branch 결과에 따라 달라지기에, 이전 명령어에 항상 의존성을 갖는다. 그렇기에 branch 명령의 execute 단계 이전까지 다음 명령어의 Instruction Fetch 조차 실행되지 못하는 문제가 생긴다.

그렇기에 branch 명령어에 한해서 파이프라인 실행 속도보다도 최대한 빨리 ALU 연산이 실행되도록 하는 편이지만, 긴 파이프라인에서는 이렇게 지연되는 사이클조차 치명적이므로 Branch Prediction 방법을 사용한다.

Branch Prediction

Branch 결과를 미리 가정하여 연산을 수행하고, Prediction 결과가 틀렸을 경우 다시 연산을 시작한다. 가정이 옳다면 stall없이 파이프라인을 운영할 수 있다.

• Static BP: 일반적인 브랜치에 기반한 예측을 한다. 예를들어, While문이나 If 문의 경우, 내부의 코드를 실행할 확률이 높다.
• Dynamic BP: 하드웨어가 실제로 해당 브랜치의 행동을 측정하여, 확률이 높은쪽으로 예측한다.

파이프라인 레지스터

파이프라인의 각 Step 사이에는 파이프라인 레지스터가 있어, 이전 Step의 결과를 저장했다가 다음 Step으로 넘겨준다.
파이프라인 레지스터는 이전 Step의 결과 뿐 아니라, 명령어 별로 필요한 Control 신호도 저장하고 있다가 적절히 넘겨준다.

Forwarding 감지하기

Forwarding이 필요한 시점은 파이프라인 레지스터를 통해 감지할 수 있다.

• EX/MEM. Destination의 주소가 ID/EX. RS 또는 ID/EX. RT 와 같을 때
• MEM/WB. Destination의 주소가 ID/EX. RS 또는 ID/EX. RT와 같을 때

Forwarding이 필요하다.

Double Data Hazard

# rs, rt, rd
add $1, $1, $2
add $1, $1, $3 # rt에서 위 명령어의 rs를 포워딩
add $1, $1, $4 # rt에서 위 명령어의 rs를 포워딩 해야함 (첫 명령어의 rs를 포워딩하면 안됨)

위 코드와 같이 해저드가 중첩되어 발생될 경우 해결법을 생각해보자.

2번째 add에선 자연스럽게 ID/EX. RT가 EX/MEM. RD와 같으므로 Forwarding이 잘 될 것이다.

문제는 3번째 add인데, ID/EX. RT와 EX/MEM. RD, MEM/WB. RD가 같다.
이 경우, 가져와야 하는 것은 EX/MEM의 RD 값이다. Forwarding Unit에서 EX hazard가 발생하지 않았을 때만 MEM hazard를 허용하여 해결할 수 있다.

파이프라인 Stall

스톨은 파이프라인이 한 사이클 쉬어가는 것을 말한다.

ID/EX 레지스터의 Control 신호를 0으로 하여 EX, MEM, WB 부분은 쉰다. 명령어가 실행되지 않았으므로 PC와 IF/ID 레지스터는 업데이트 하면 안된다.

이를 통해 stall 이후 대기중이던 명령어가 순서대로 다시 실행된다.

Branch Prediction이 잘못되었을 때

특정 스테이지에서 Branch 연산이 완료되었고, 그 결과가 Prediction과 다르면 Prediction을 기반으로 진행한 사이클들의 Control 신호에 0을 줘서 다 날리고 Branch를 수행하면 된다.

가능한 적은 사이클을 손해보기 위해 Branch 결과는 최대한 Early Stage에서 나오는 것이 좋은데, 하드웨어 수정을 통해 ID Stage에서 나오게 할 수 있다.