[Computer Architecture] 해저드

+ 한국항공대학교 길현영 교수님의 컴퓨터구조론 과목 내용을 정리한 글입니다.

해저드

선행 명령어와 후행 명령어의 중첩/실행이 원활하게 이루어지기 어려운 경우가 존재한다.
=> m단계 파이프라이닝에 대한 이론적 (거의) m배 성능 향상은 실제로는 불가능하다.
 
= 다음 명령어가 다음 클럭 사이클에 실행될 수 없는 상황
= 명령어나 데이터가 준비되지 않아서 파이프라인을 멈춰야 하거나 새로운 명령어를 파이프라인에 투입할 경우 잘못된 결과가 초래되는 모든 상황이나 조건
 
해결 방법?
=> 해저드 원인이 사라질 때까지 파이프라인에 명령어 투입을 멈춰야 한다.
- 파이프라인 중지 (Pipeline Stall) or 파이프라인 버블 (Pipeline Bubble)

---

구조적 해저드

= 파이프라인에서 실행 중인 2개 이상의 명령어가 동일한 HW 자원을 동시에 요구하기 때문에 파이프라인을 멈춰야 하는 상황/조건 (HW 자원 충돌)
 
최악의 경우, m단계 파이프라이닝에서 m개의 명령어가 동시에 동일한 자원을 필요로 할 수 있다.
 
< 명령어와 데이터가 하나의 메모리에 존재하고 포트도 하나일 경우 >

Load 명령이 메모리에서 데이터 읽기를 수행하는 것과 Fetch 명령이 메모리에서 명령어를 인출하는 것 사이에서 메모리 자원 충돌이 발생한다.

 

해결 방법

=> HW 추가(분할), 예약표, 입출력 포트 다중화 등

 

1. IF 단계의 PC 값 증가

=> 간단한 adder를 추가하여 해결한다.

 

2. IF - MEM 단계의 메모리 접근 충돌

=> 명령어 메모리와 데이터 메모리로 나누거나, 별도의 Cache 메모리를 두어 해결한다.

 

3. ID - WB 단계의 레지스터 접근 충돌

=> 시분할 R/W 접근 or 멀티포트 레지스터를 사용하여 해결한다.

 

4. 자원 충돌 가능성이 있는 단계

=> 파이프라인 재구성 (파이프라인 추가) or 예약표 방식을 사용하여 해결한다.

 

5. 기다려야만 하는 경우

=> 해당 클럭 사이클동안 NOP(Bubble) 명령어를 수행하여 해결한다.

NOP: 아무 일도 하지 않는 명령어

---

데이터 해저드

= 연산할 피연산자 데이터가 준비되지 않아 파이프라인을 멈춰야하는 상황/조건
 
주로 선행 명령어와 후행 명령어가 사용하는 데이터간 종속성(dependency) 문제로 발생한다.
 

r1이 갱신되지 않은 사이클에서 r1을 사용한다. (Clock Cycle 6부터 r1은 갱신된 값이다.)

 

데이터 간 관계

+ 1은 선행 명령어, 2는 후행 명령어이다.
+ 순차 수행 결과와 파이프라이닝 결과가 같아야한다.
 
1. RAR (Read2 After Read1)
=> 데이터를 읽은 후 다시 읽는 경우
(읽기만 하는 경우, 문제가 발생하지 않는다.)
 
2. RAW (Read2 After Write1)
=> 선행 명령어가 데이터를 쓰기(수정) 전에 후행 명령어가 데이터를 읽는 경우
(가장 많이 발생한다.)
 
상황 1. 계산 후 읽기
(가정: 5개 레지스터 r1 ~ r5의 초기 값은 각각 1 ~ 5이다.)

I1 = add r1 r2 r3 (레지스터 쓰기 단계에서 덧셈한 결과로 갱신)

I2 = add r4 r1 r5 (레지스터 읽기 단계에서 덧셈의 피연산자로 사용)
=> I2에서 피연산자로 사용할 때, r1값이 갱신한 값 5가 아니라 원래 값 1이다.
 
상황 2. 적재 후 읽기
(가정: 5개 레지스터 r1 ~ r5의 초기 값은 각각 1 ~ 5이다. 메모리 12번지 값은 120이다.)
I1 = load r1 M[10] (r2) // r1 <- M[12]
I2 = add r3 r1 r4 
=> I2에서 r1을 요구할 때, I1은 아직 M[12]에 접근하지 못했기 때문에, I2는 r1의 원래 값 1을 사용한다.
 
3. WAR (Write2 After Read1) & WAW (Write2 After Write1)
=> 선행 명령어가 데이터를 읽거나 쓰기전에 후행 명령어가 먼저 데이터를 갱신하는 경우
(단일 파이프라인이 아닌 SuperScalar처럼 여러 기능의 유닛이 동시에 수행하는 경우 발생한다.)
단일 파이프라인: 한 사이클에 하나씩 명령어를 가져오는 파이프라인

SuperScalar 파이프라인 방식

ex) A = f(B, C); B = g(D, E); (f연산이 g연산보다 시간이 오래걸리는 복잡한 연산일 경우)
- f연산: IF -> ID -> EX1 -> EX2 -> EX3 -> M -> WB
- g연산: IF -> ID -> EX -> M -> WB

해결 방법

=> 포워딩(forwarding), 코드 재배치
 
1. 포워딩
=> ALU 출력으로부터 직접 데이터를 받아 바로 ALU 입력으로 재전송한다. (바로 다음 명령어에서 사용할 수 있도록)

포워딩 방식

 
2. 코드 재배치
=> 컴파일러에서 프로그램 내의 명령어 의존성을 분석하여 재배치한다.

컴파일러의 코드 재배치

---

명령어 해저드 (분기 해저드 or 제어 해저드)

= 실행할 명령어가 결정/준비되지 않아서 멈춰야하는 상황/조건
- 발생 패널티(성능 저하)가 매우 크다.
 
주로 분기 명령으로 발생한다.
- 분기 명령에서 분기가 결정되는 시점(EX - M)에 이미 파이프라인에는 후속 명령들이 채워진다.

분기별 PC 갱신 시기

 
ex) 조건 분기 명령어
I1: if (a == b) goto EQUAL
I2: a = 0
I3: b = 2
I4: EQUAL: y = x + a × 2
I5: z = x + y
 
1) 분기 조건 불만족
=> 상관없다.

 
2) 분기 조건 만족
=> 다음 명령어가 I2, I3가 아닌 I4임이 결정되었으므로 미리 했던 과정을 되돌려야한다.
 

 

명령어 해저드의 영향

< 가정 >
1. 5-단계 파이프라인을 사용하는 picoMIPS 아키텍쳐이다.
2. 명령어 해저드가 없는 경우 CPI = 1이다.
3. 명령어의 17%가 분기 명령어이며, 분기 패널티는 3 사이클이다.
 
< 명령어 해저드가 있는 경우 >
평균 CPI: 1 + 0.17 × 3 = 1.51
성능: 1 ÷ 1.51 = 0.66
 
< 3개 명령어 동시 수행이 가능한 SuperScalar의 경우 >
해저드가 없을 때 평균 CPI: 1 ÷ 3 = 0.33
해저드가 있을 때 평균 CPI: 0.33 + 0.17 × 3 = 0.84
=> 성능: 0.33 ÷ 0.84 = 0.38
 
무조건 분기 명령의 패널티를 없애기 위해 명령어 인출단계에 HW를 추가하기도 한다.
- 디코더는 IF 단계에서 무조건 분기 명령어를 식별한다.
- 평균 CPI는 낮아질 수 있으나, HW 추가로 인한 부하가 발생하여 클럭 속도가 느려질 수 있다.
 

해결 방법

=> 명령어의 분기 예측, 지연 분기
 
1. 정적 명령어 분기 예측
=> 분기가 실패할 것으로 예측 (성공 시 정지 후 분기) vs 분기가 성공할 것으로 예측 (패널티가 항상 1)
 
+ 분기 주소는 ID 단계에서 미리 계산한다.
 
2. 동적 명령어 분기 예측
=> 과거 이력에 따라 분기 예측을 결정한다.
 
3. 지연 분기
=> 분기 명령어 주변의 명령어 순서를 바꿔서 실행한다.
(분기 결과가 나오기 전까지 다른 일을 먼저하도록)

---

해저드 해결 방법

< 가장 기본적인 해결 방법 (Naive Solution) >
1. 정적 해결 방법
=> HW를 추가(분할)하거나, 코드를 재배치한다. (잠재적 해저드 분석 후 원인 제거)
+ HW 추가 -> 개발 비용 증가
 
2. 동적 해결 방법
=> 해저드 발생 시, 원인이 제거될 때까지 다음 명령어의 수행을 연기한다.
- 다음 명령어 수행을 임시로 중단 (pipeline interlock) 하거나, 아무 동작을 하지 않는 Nop 명령으로 파이프라인을 채운다.
+ Nop 명령어 추가 -> 성능 저하
 
정적(Static) - at compile time: 프로그램이 수행되기 전, 주로 컴파일 단계를 의미한다. (소스 코드 기반)
동적(Dynamic) - at run time: 프로그램이 실제로 수행되는 과정을 의미한다.

---

파이프라이닝의 인터럽트 발생 처리 (참고)

= 또 다른 형태의 제어 해저드
 
ex) add 명령의 EX 단계에서 overflow가 발생한 경우
add $1 $2 $1
 
1. $1 레지스터에 overflow값이 쓰여지는 것을 막는다.
2. 이전 명령어들은 실행을 완전히 끝낸다.
3. 파이프라인에 들어온 add와 후속 명령어들을 버리고, 제어를 핸들러(ISR)에게 넘긴다.
4.핸들러가 실행된 후, 원래 명령어를 다시 적재해서 실행한다. (PC 조정)
 
다중 인터럽트: ISR을 수행하는 동안 다른 인터럽트가 발생
=> 우선 순위로 결정한다.