Pipeline Hazard

김세영·2021년 5월 29일

computer architecture

Pipeline Reality

여러 가지 명령어들의 실행 시간이 각각 다름
각각의 Stage에서의 실행 시간이 다름
명령어들이 서로 영향을 받음

Hazard

파이프라인의 정상적인 수행을 방해하는 요소들

Structure Hazard
하나의 Resource를 여러 Stage에서 동시에 접근 / 사용
- 부족한 Hardware 구성 요소를 추가하여 해결 가능
Data Hazard
앞의 명령어에서 사용중인 데이터를 뒤의 명령어에서 접근 / 사용
- 파이프라인 지연(Pipeline Stall)
- 전방 전달(추가적인 하드웨어 필요, Forwarding / Bypassing)으로 해결 가능
Control Hazard
branch / jump 명령어에서 생기는 문제점
- 파이프라인 지연(Pipeline Stall)
- 정적/동적 분기 예측(Branch prediction)
- 지연 분기(Delayed Branch, 명령어의 실행 순서를 바꿈)
  로 해결 가능

Waiting으로 모든 Hazard는 해결 가능하지만,
이렇게 되면 Pipeline을 쓰는 의미가 없어짐

Structural Hazard

여러 Pipeline Stage에서 같은 Resource(메모리, 레지스터 등)를 동시에 참조하는 것

Solution 1. 모든 명령어의 Stage 개수를 5개로 맞춤

없는 단계를 만들어 Delay를 주면 그 때 명령어가 아무 작업도 하지 않으므로 비효율적이다

Solution 2. Memory Access 시 L1 Cache의 instruction cache와 data cache를 사용

Solution 3. Register Access는 속도가 매우 빠르므로, 접근 단계를 2단계로 나누어 전반부는 Write, 후반부는 Read로 구성

Data Hazard

Data Dependencies

Pipeline Stage의 데이터 접근 순서에 따라 문제가 생길 수 있음

같은 메모리 혹은 레지스터를 참조하는 명령어 i와 j에서,
명령어 i 이후 j가 실행된다고 가정할 때

RAW(Read After Write), true dependencies
i가 Write하기 이전에 j가 Read하는 경우
WAW(Write After Write), output dependencies
i가 Write하기 이전에 j가 Write하는 경우
WAR(Write After Read), anti dependencies
i가 Read하기 이전에 j가 Write하는 경우

RAR은 데이터가 변경되지 않으므로 문제되지 않음

위와 같이 Stage의 실행 시간을 맞춰주는 경우 문제 해결 가능

WAR, WAW Solution - Renaming

같은 데이터를 두 레지스터로 나누어 관리

---------------------------
a = x + b; // WAR
x = c + 1; // RAW
d = x / 2;
--> 
a = x + b;
x1 = c + 1;
d = x1 / 2; // WAR 해결
---------------------------
x = a + b; // WAW
x = c + 1; // RAW
d = x / 2;
-->
x = a + b;
x1 = c + 1;
d = x1 / 2; // WAW 해결
---------------------------

RAW Solution

add에서 r1에 대한 처리가 끝나지 않았음에도 다른 명령어에서 이를 참조하고 있음

Solution 1 - Delay

Delay가 늘어날수록 성능이 떨어지기 때문에 좋은 방법은 아니다.

Solution 2 - Register file

레지스터 접근을 같은 Cycle에서 처리하여 Delay를 줄임

Solution 3(1) - Forwarding[ALU]

첫 번째 연산에서 ALU의 작동이 끝난 시점에 이미 값을 알고 있으므로, 그 값을 다음 연산에서 활용
하드웨어가 추가로 필요

Solution 3(2) - Forwarding[Load]

Load는 시간이 굉장히 오래 걸리므로, Forwarding으로는 해결할 수 없음
따라서 어쩔 수 없이 Delay(Stall)로 해결
이를 통해 Structural Hazard도 해결

Forwarding Control

1. Load명령이 아닌 경우

위와 같이 경우를 나누어, 실행 단계인 EX hazard / 메모리 접근 단계인 MEM hazard로 구분
위의 경우에서 추가로 구분하여 자세히 처리해야 함
- EX/MEM.RegWrite 혹은 MEM/WB.RegWrite 가 발생
- Destination Register != $zero (0번 레지스터는 변경 불가능)
- EX/MEM.RegWrite일 때 Forwarding Unit은 MUX에 들어가는 신호를 10으로 설정
- MEM/WB.RegWrite일 때 Forwarding Unit은 MUX에 들어가는 신호를 01으로 설정

Double Data Hazard

EX/MEM/WB Solution

add -> sub, sub -> or 이외에 add -> or에서도 Data Hazard가 발생할 수 있음

위의 Forwarding에서, EX/MEM.RegWrite이면서 MEM/WB.RegWrite가 아닌 경우(혹은 반대의 경우)를 추가해주면 해결 가능

Load Solution
적절한 위치에 nop(no operation)을 넣어 처리

위의 경우에 Hazard Detection Unit에서 다음 Pipeline에 nop을 넣고, IF/ID 단계에 받은 명령어를 반복하여 넣어줌으로써 다음 단계에서 동작하도록 처리