[컴퓨터구조] Pipelining(4): 데이터 해저드 (Data Hazard)

파이프라인을 실행하는 데에는 여러 장애가 존재한다. 앞서 파이프라이닝에 대해 설명하며 언급했다싶이 구조적 해저드, 데이터 해저드, 제어 해저드가 존재한다.

 

[컴퓨터구조] Pipelining(1): 파이프라이닝이란

[컴퓨터구조] Pipelining(1): 파이프라이닝이란

 

여기서는 데이터 해저드에 대해 살펴보도록 하겠다.

 

먼저 종속성이 여러 개 있는 프로그램을 살펴보자. 종속성은 파란색으로 표시했다.

 

마지막에서 네 명령어 모두 첫 번째 명령어의 레지스터 x2의 결과에 종속적이다. 이 종속성을 좀 더 자세히 확인해보자.

위 그림은 다중 클럭 사이클 파이프라인 표현을 통해 명령어들의 실행 과정을 보여준다.

 

x2의 값은 sub 명령어가 레지스터에 결과를 쓰는 클럭 사이클 5에서 변화한다. 

 

먼저 뒤에서 두 개의 명령어, 즉 add와 sw는 문제가 없다. sw가 정상 작동 한다는 것은 자명하다. add처럼 한 클럭 사이클에 같은 레지스터에 대한 읽기와 쓰기가 동시에 일어나는 경우를 살펴보자. 쓰기는 클럭 사이클의 앞부분에서, 읽기는 클럭 사이클의 뒷부분에서 일어나므로 읽기는 새로 써진 값을 읽을 수 있다. 이와 같은 이유로 add도 정상 작동한다.

 

하지만 이 것을 제외한 명령어들, and와 or에서의 x2는 sub 명령어의 결과값이 아님을 볼 수 있다. 즉, 올바른 값을 갖게 되는 명령어는 add와 sw 뿐이다. 파란색으로 표시된 종속성 선이 시간 축에서 거꾸로 갈 때 문제가 발생한다는 것을 관찰할 수 있다. 이와 같은 해저드를 데이터 해저드(data hazard)라고 한다.

 

and와 or 명령어는 언제 데이터를 필요로 할까? 바로 EX 단계의 시작에서 필요로 한다. and의 경우 클럭 사이클 4에서, or의 경우 클럭사이클 5에서 각각 필요하다. 따라서 데이터가 레지스터 파일에서 읽을 수 있게 되기 전이라도 계산되어 나온 데이터를 받을 수 있으면 이 코드들을 지연 없이 실행시킬 수 있다. 이렇게 데이터를 미리 읽어오는 것을 전방전달(forwarding)이라고 한다.

 

forwarding이 어떻게 동작하는지 알아보자.

 

위와 같은 데이터 해저드는 ALU 연산이나 주소를 계산하는 연산에서 발생한다. 즉, 앞선 명령어가 WB 단계에서 쓰기를 하려는 레지스터를 다른 명령어가 EX단계에서 사용하려고 시도할 때 발생한다.

 

이 조건을 좀 더 간단히 표현해보자. 파이프라인 레지스터에 이름을 붙여서 명시적으로 나타낸다.

1a. EX/MEM.RegisterRd = ID/EX.RegisterRs1
1b. EX/MEM.RegisterRd = ID/EX.RegisterRs2

2a. MEM/WB.RegisterRd = ID/EX.RegisterRs1
2b. MEM/WB.RegisterRd = ID/EX.RegisterRs2

 

1a를 자세히 살펴보자. '.' 앞에 있는 부분(EX/MEM)은 파이프라인 레지스터의 이름을 나타내고, 뒷 부분은 그 레지스터의 필드 이름을 나타낸다. 즉, 파이프라인 레지스터 EX/MEM에 있는 레지스터 필드 Rd에 있는 값이 파이프라인 레지스터 ID/EX에 있는 첫 번째 읽기 포트에 실린 레지스터 번호와 같을 때, 1a의 조건을 만족한다.

 

예시를 통해 더 자세히 알아보자.

 

앞의 and 명령어에 해당하는 다중 클럭 사이클 파이프라인 표현을 다시 돌아보자. 사이클 3을 보면, and 명령어의 ID/EX.RegisterRs1에서 지정하는 레지스터 번호의 데이터를 EX/MEM.RegisterRd가 가지고 있음을 확인할 수 있다. 즉, 해저드 조건 1a를 만족한다.

1a. EX/MEM.RegisterRd = ID/EX.RegisterRs1 = x2

 

and 명령어가 EX 단계에 있고, sub 명령어가 MEM 단계에 있기 때문에 발생한다. 

 

하지만 1a~2b의 조건을 만족하더라도 데이터 해저드가 일어나지 않을 수 있다. 어떤 명령어는 레지스터에 쓰기를 하지 않기 때문이다. 이럴 경우 필요가 없을 때에도 forwarding을 수행하게 된다. 따라서 RegWrite 신호가 활성화되어 있는지를 추가적으로 확인한다. 파이프라인 레지스터 EX/MEM의 WB 제어 필드를 조사함으로써 RegWrite 신호가 활성화되어 있는지를 확인할 수 있다.

 

또한, x0는 무조건 값이 0임을 기억하자. 따라서 레지스터 x0으로 가는 값들은 forwarding하지 않는다.

 

위에서 설명한 조건들을 명확히 정리해보자.

1. 1a~2b 중 하나를 만족한다.
2. EX.MEM.RegWrite == 1
3. EX/MEM.RegisterRd ≠ 0 또는 MEM/WB.RegisterRd ≠ 0 

이 3가지를 모두 만족시킬 경우에만 forwarding을 시행한다.

 

---

 

이제 해저드를 "검출" 했으니 어떤 데이터를 forwarding할지를 생각해보자.

 

앞서 살펴본 and 명령어를 예시로 설명해보자. 사이클 3에서 파이프라인 레지스터 EX/MEM이 forwarding 할 데이터를 가지고 있다. 이 데이터를 and 명령어가 필요로하는, 즉 ALU 입력으로 가져올 수 있어야 한다.

 

마찬가지로 or 명령어에서는 사이클 4에서 파이프라인 레지스터 MEM/WB가 forwarding할 데이터를 가지고 있고, 이 데이터를 or 명령어의 ALU 입력으로 가져와야 한다.

 

 

이를 구현하는 파이프라인 레지스터를 확대해 살펴보자. 새롭게 추가된 하드웨어는 파란색으로 표시되어 있다.

 

forwarding multiplexer를 위한 제어값들도 살펴보자. 이런 제어를 통해 multiplexer는 레지스터 파일 값과 forwarding된 값들 중 하나를 선택한다.

Mux control signal	Source
ForwardA = 00	ID/EX	ALU의 첫번째 피연산자가 레지스터 파일에서 온다.
ForwardA = 10	EX/MEM	직전의 ALU 연산 결과가 ALU의 첫번째 피연산자로 forwarding
ForwardA = 01	MEM/WB	데이터 메모리나 전전 ALU 결과가 ALU의 첫번째 피연산자로 forwarding
ForwardB = 00	ID/EX	ALU의 두번째 피연산자가 레지스터 파일에서 온다.
ForwardB = 10	EX/MEM	직전의 ALU 연산 결과가 ALU의 두번째 피연산자로 forwarding
ForwardB = 01	MEM/WB	데이터 메모리나 전전 ALU 결과가 ALU의 두번째 피연산자로 forwarding

 

보다싶이 forwarding 값을 제어하는 multiplexer가 EX 단계에 있기 때문에, forwarding control unit도 EX 단계에 있다. 위 그림에는 forwarding unit과 더불어 해저드를 검출하기 위해 피연산자 레지스터 번호를 전달하기 위한 선들도 추가되어 있다.

 

또한, 이를 위해 rs1과 rs1 필드를 ID/EX에 추가해야 한다.

---

 

이제 해저드를 검출하는 조건과 제어 신호를 한 번에 서술해보자.

< EX 해저드 >

if (EX/MEM.RegWrite)
and (EX/MEM.RegisterRd ≠ 0)
and (EX/MEM.RegisterRd = ID/EX.RegisterRs1) ForwardA = 10 // 첫번째 피연산자로 forwarding


if (EX/MEM.RegWrite)
and (EX/MEM.RegisterRd ≠ 0)
and (EX/MEM.RegisterRd = ID/EX.RegisterRs2) ForwardB = 10 // 두번째 피연산자로 forwarding

 

MEM 해저드에서는 EX 해저드가 함께 발생할 때 또한 고려해야 한다. 이 경우 MEM 단계의 결과값(EX 해저드)이 더 최근의 것이기 때문에 결과값은 MEM 단계(EX 해저드)에서 forwarding된다.

< MEM 해저드 >

if (MEM/WB.RegWrite)
and (MEM/WB.RegisterRd ≠ 0)
and not ((EX/MEM.RegWrite)
        and (EX/MEM.RegisterRd ≠ 0)
        and (EX/MEM.RegisterRd = ID/EX.RegisterRs1)) // EX 해저드가 일어나지 않았을 때
and (MEM/WB.RegisterRd = EX/MEM.RegisterRs1) ForwardA = 01 // 첫번째 피연산자로 forwarding



if (MEM/WB.RegWrite)
and (MEM/WB.RegisterRd ≠ 0)
and not ((EX/MEM.RegWrite)
        and (EX/MEM.RegisterRd ≠ 0)
        and (EX/MEM.RegisterRd = ID/EX.RegisterRs1)) // EX 해저드가 일어나지 않았을 때
and (MEM/WB.RegisterRd = EX/MEM.RegisterRs2) ForwardA = 01 // 두번째 피연산자로 forwarding

 

---

 

지금까지 살펴본 방식은 산술 명령어, 그 중에서도 add, sub, and, or의 R-형식 명령어만을 고려했다. 하지만 적재 명령어와 저장 명령어의 경우에는 부호있는 수치값 또한 고려해야 한다. 이를 위해 ForwardB에 의한 멀티플렉서의 출력과 부호 있는 수치값 중 하나를 선택하는 멀티플렉서가 추가되어야 한다.

---

forwarding도 만능은 아니다. 적재 명령어를 뒤따르는 명령어가 적재 명령어에서 쓰기를 행하는 레지스터를 읽으려고 시도할 때는 forwarding이 해결할 수 없다.

위 그림을 통해 알 수 있듯이 forwarding을 하더라도 여전히 해저드가 남아있는 것을 확인할 수 있다.

 

이런 경우가 발생하면 파이프라인을 지연(stalling)시킴으로서 해결할 수 있다. 이를 위해 해저드 검출 유닛(hazard detection unit)을 추가한다. 이 유닛은 ID 단계에서 동작해, 적재 명령어와 결과값을 사용하는 명령어 사이에 지연(stalling)을 추가할 수 있게 한다.

 

적재 명령어만 검사하면 되므로 조건은 간단하다.

if ( ID/EX.MemRead and // 명령어가 적재 명령어인지 테스트
    (ID/EX.RegisterRd = IF/ID.RegisterRs1 or ID/EX.RegisterRd = IF/ID.RegisterRs2)
   ) stall the pipeline

 

조건이 만족되면 명령어는 1클럭 사이클 지연된다. 1클럭 사이클 이후에는 전방전달로 처리할 수 있어 실행은 계속 진행된다.

 

ID 단계에 있는 명령어가 지연되면 IF 단계에 있는 명령어 역시 지연됨으로서 명령어를 잃지 않게 해야 한다. 이것을 위해서는 PC 레지스터와 IF/ID 파이프라인 레지스터를 변하지 않게 유지한다. EX 단계 이후의 파이프라인을 위해 아무 효과 없는 명령어 nop을 삽입한다. (nop은 EX, MEM, WB 단계의 7개 제어신호에 모두 0을 할당한다. 사실, RegWrite랑 MemWrite만 0으로 만들어도 충분하다.)

 

다음은 hazard detection unit과 forwarding unit이 어떻게 파이프라인에 연결되는지를 보여준다. (분기 회로 생략됨)

---

지금까지 데이터 해저드에 대해 알아보았다.

 

다음 글에서는 제어 해저드에 대해 자세히 살펴보자.