[컴퓨터 구조] 20. Pipeline MIPS (4) - 회로 개선 (Data Hazard)

Data Hazard

 

우선 Forwarding 이 적용되지 않은 상황에서 그냥 pipeline MIPS 회로에 그대로 위와 같은 과정으로 명령어를 실행한다고 해보자.

그럼 클럭 사이클 (CC) 이 지나갈 때 회로의 흐름이 위와 같이 나타난다.

그런데 첫번째 명령어인 sub의 결과로 $2 레지스터에 값이 쓰이는데, 그 다음 명령어는 곧바로 $2 레지스터의 값을 이용해 연산을 한다.

즉, 데이터 의존성이 존재하는 것이다.

 

먼저 명령어의 흐름을 가로축으로 보았을 때, sub 명령어에 기존에는 10이라는 값이 있었고, sub 연산 결과 -20이 저장된다고 하자.

그러면 WB 단계 전까지 Reg 에는 10 이 저장되어 있다가, Write Back 이 되는 전반부 쓰기 동작 이후에는 -20이 저장될 것이다.

 

이번엔 명령어의 흐름을 세로축으로 보았을 때, 처음에는 sub 명령어가 2번 레지스터를 업데이트 했는데, 나머지 4개 명령어는 모두 2번 레지스터를 어딘가에 피연산자로 쓰고 있다는 것을 알 수 있다.

그래서 2번 레지스터에 대한 의존성이 존재한다.

 

이제 이 디펜던시 중에 어떤 것이 해저드이고 어떤것이 해저드가 아닌지 살펴보자.

 

1. and 명령어와의 디펜던시

이때 and 명령어를 읽는 시점에서는 아직 sub 명령어의 WB 스테이지가 실행되기 이전이다.

따라서 2번 레지스터의 값이 업데이트 되기 이전에 접근하여 값을 읽게 되므로 데이터 해저드가 발생한다.

 

2. or 명령어와의 디펜던시

이때도 or 명령어를 읽는 시점에서는 아직 sub 명령어의 WB 스테이지가 실행되기 이전이다.

따라서 아직 2번 레지스터의 값이 업데이트되지 않았기 때문에, 업데이트 되기 이전 값에 접근하게 되어 데이터 해저드가 존재한다.

 

3. add 명령어와의 디펜던시

이때는 레지스터의 값을 쓰는 타이밍과 읽는 타이밍이 모두 CC 5로 동일하다.

위태위태해 보일지 모르지만, 값을 쓰는 타이밍은 Reg에 접근하는 전반부이고, 값을 읽는 타이밍은 Reg에 접근하는 후반부이다. 따라서 이때도 해저드가 없다고 볼 수 있다.

 

4. sw 명령어와의 디펜던시

sub 명령어에 의해 2번 레지스터의 값이 -20으로 업데이트 되는 타이밍은 sub 명령어의 5번째 스테이지 전반부에 끝난다.

이때 sw명령어가 2번 레지스터를 읽는 타이밍은 업데이트 된 다음 클럭 사이클 (CC 6) 이다.

따라서 이때는 업데이트된 2번 레지스터의 값을 읽어들이므로 해저드가 없다.

 

---

 

이때 데이터 해저드를 소프트웨어적으로 (프로그램 내에서) 해결하려면 nop를 넣어서 해결할 수 있다.

(코드 스케줄링)

이때 nop를 넣을 때는 and 명령어와 sub 명령어 사이에 nop를 2번 넣어주면 된다.

그러면 and, or 명령어 모두 업데이트된 2번 레지스터 값을 읽게 될 것이다.

 

참고로 MIPS에서 nop 명령어는 32bit 명령어의 bit를 모두 0으로 채우면 된다.

nop는 슈도 명령어이므로, 이를 기존 명령어대로 해석하면 sll 을 0번 레지스터에 대해 수행하는 효과가 되어서 아무런 일도 일어나지 않는다. (0번 레지스터를 왼쪽으로 0번 밀은 값을 0번 레지스터에 쓴다.)

 

그런데 이렇게 하면 의미없이 쉬어야하는 nop가 많이 삽입되면서 프로그램의 전체적인 성능이 느려질 것이다.

또 이런 코드 스케줄링 방법으로 항상 해결할 수 있는 것도 아니다.

따라서 프로그램의 성능이 줄어들지 않을 다른 방법을 찾아야 한다.

 

Forwarding (Bypassing)

데이터 해저드를 하드웨어적으로 해결하는 방법은 forwarding (bypassing) 이다.

간단히 복기해보면, -20 이라는 값으로 실제 업데이트 되는 것은 CC 5 이지만, -20 이라는 값을 실제로 얻는 시점은 CC 3 에서도 이미 얻은 상황이다. 따라서 이때 얻은 값을 곧바로 다음 사이클에 넘겨주어서 쓸 수 있도록 하는 것이 포워딩이다.

 

그런데 정상적인 상황에서도 포워딩을 하면 안되므로, 포워딩을 해야하는지 해야하지 말아야하는지를 판단할 수 있어야 한다.

 

 

포워딩을 하는 상황을 그림으로 나타내면 위와 같다.

그런데 이 그림 우측에서 봤을 때, 4가지 조건 중에 포워딩이 필요한 조건은 무엇일까?

 

EX/MEM 파이프라인 레지스터에 백업된 reigster rd 의 값(레지스터 번호)이 ID/EX 레지스터의 register rs 의 값(번호)와 같다면 포워딩이 필요하다는 것은 확실하게 알 수 있다.

 

우선 sub와 and 사이의 관계를 보면 4가지 선택지 중 1a 선택지가 포워딩 조건에 해당한다.

그래서 이렇게 이전 rd 레지스터 번호와 이번의 rs 레지스터의 번호가 같다면 데이터 해저드를 감지하고 포워딩한 값을 가져와서 대신 쓰면 된다.

 

and 명령어는 절대적인 시간으로 볼 때 CC 4 에서 실행하고 있고, 이 시점에서 포워딩된 값을 받아서 연산해야 한다.

이때 포워딩된 값은 ID/EX 파이프라인 레지스터에 저장되어 있을 것이고, 이 값을 그대로 가져와서 사용하면 된다.

그리고 데이터 해저드를 감지하려면 ED/EX 파이프라인 레지스터에는 포워딩된 값 뿐만 아니라, rd 필드에 있는 레지스터 번호도 같이 저장되어 있어야 한다.

 

데이터 해저드를 감지한다는 것은 ID/EX 파이프라인 레지스터에 저장된 rs 필드의 레지스터 번호와 EX/MEM 파이프라인 레지스터에 저장된 이전 명령어의 rd 필드 레지스터 번호가 같다는 것을 감지한다는 것과 같다.

 

만약 rt 필드에서 겹친다면 그때는 1b에 해당하여 데이터해저드를 감지한다.

공통적으로 1a, 1b 는 모두 자신보다 앞선 명령어와의 관계를 보는 것이다.

나의 정보는 ID/EX 에서 오고, 바로 앞선 명령어의 정보는 EX/MEM 에서 온다.

---

 

or 명령어의 경우, 두번째 rt 필드의 값을 보고 있고, 명령어 사이의 간격이 2칸이므로 이때는 데이터 해저드를 감지하는 조건이 MEM/WB 단계에서 저장된 register rd 의 값과 ID/EX 단계에서 저장된 rt 의 값이 같은지 비교하는 2b 에 해당할 것이다.

 

그리고 지금은 비록 rs 필드에 있는 6번 레지스터가 이전 명령어와 겹치지 않긴하지만, 겹칠 수도 있기 때문에 1a, 1b 조건도 당연하게 체크를 해야한다.

 

---

 

이 내용을 토대로 데이터 해저드를 감지하고 포워딩하는 유닛을 아래와 같이 구성할 수 있다.

 

우선 포워딩은 연산을 하는 EX 단계에서 ID/EX 값과 비교해야 하기 때문에, 포워딩 유닛은 Ex 단계에 위치해야 한다.

 

and 명령어에서 해저드를 감지할 때는 EX/MEM 파이프라인 레지스터에 있는 rd 값을 이용하여 감지하였다.

이렇게 바로 직전의 명령어와의 관계에서 감지한 데이터 해저드를 'EX 해저드'라고 한다.

그리고 그 앞앞에 있는 명령어와의 관계에서 감지한 데이터 해저드를 'MEM 해저드'라고 한다.

 

먼저 EX 해저드는 발생 조건이 아래와 같다.

 

1. 앞선 명령어가 레지스터에 값을 쓰는 명령어였다. == EX/MEM 레지스터 안에 RegWrite 필드 값이 1인지 확인한다.

(그런데 지금 시점에서 저장된 RegWrite 는 현재 명령어의 컨트롤 신호 아닌가..? 라고 생각했었는데, 생각해보니 현재 명령어의 컨트롤 신호가 EX/MEM 단계에 실제로 저장되려면 1사이클이 더 지나야 한다. )

 

2. 데이터를 쓴 레지스터의 번호가 0번이 아니었다.

그런데 Write Back 하는 경우 중 유일하게 해저드가 아닌 경우가 있다.

바로 0번 레지스터에 쓰는 경우이다.

이때는 실제로 쓰기가 일어나지 않기 때문에 해저드가 아니다!

(근데 실제로 0번 레지스터에 쓰기가 안된다면 어차피 0번 레지스터의 값을 읽어올 때 의존성과 관련 없이 0으로 읽어오지 않나? 굳이 이걸 체크하는 이유가 있을까)

예를 들면 nop는 0번 레지스터에 쓰기를 하는 명령어이다.

 

3. 앞선 명령어의 rd 필드 (EX/MEM 의 rd) 번호 값과 현재 명령어 (ID/EX) 의 rs 또는 rt 값이 같았다.

 

이 3가지 조건이 모두 해당한다면 EX hazard가 발생했으므로 포워드 A를 10으로 한다.

포워드 A는 ALU에 들어오는 값들을 선택하는 mux의 셀렉트 신호로서 아래 3가지 값 중 하나를 가져온다.

 

1. 기존 대로 ID/EX 로부터 가져온 값을 쓴다.

2. 직전 명령어의 ALU 연산결과로 가져온 값을 쓴다.

3. 직직전 명령어의 연산 결과로서 ALU 결과를 파이프라인 레지스터를 2번 거쳐서 나오는 값을 쓴다.

 

그러면 mux로 들어오는 값 중 0, 1, 2 중 2번째 값을 선택하게 되므로 이전 명령어의 ALU의 결과에서 바로 가져온 연산 결과를 ALU의 rs 에 해당하는 소스로 들어온다.

 

포워드B를 10으로 하는 경우는 RT 를 비교하는 것으로 동일하게 생각하면 된다.

이때 난 처음에 RT 의 경우, 명령어 타입이 I 면 rt 필드가 write destination 으로 쓰이니까 오작동을 유발할 수도 있을 것 같아서 명령어 타입도 체크해야하지 않을까 생각했는데, 지금처럼 회로를 구성한다면 굳이 타입을 체크할 필요가 없다.

 

만약 I 타입이었다면 애초에 ALU의 두번째 src로 immediate 값이 들어가므로 RT 값이 들어갈 일이 없고, RT의 값이 들어가지 않으면 문제는 없다. 어차피 register destination 의 값은 바뀔 일이 없다.

 

---

 

MEM 해저드의 경우도 동일하다.

다만 이때는 비교하는 것이 MEM/WB 파이프라인 레지스터에 저장된 rd 값이고, 해저드가 발견되었을 때 보내는 셀렉트 신호가 01이 되어 mux의 가운데 값이 들어갈 뿐이다.

 

그리고 회로도를 보면 아래쪽에 mux가 하나 더 있다.

 

이 mux 는 RT, RD를 입력으로 받은 뒤, 하나를 골라서 EX/MEM 파이프라인 레지스터에 저장하고 있다.

이는 I 포맷일 대는 RT 가 쓰는 레지스터가 되고, R포맷 일때는 RD가 쓰는 레지스터가 되기 떄문에 적절한 5bit 레지스터 '번호'를 선택해서 저장하기 위함이다. (레지스터의 값을 저장하는 것이 아님!)

그리고 저장할 때는 그냥 RegisterRd 라는 이름으로 저장했다. (경우에 따라 rt를 저장할 수도 있지만 이름만 rd로 지은 것)

 

예시를 보면

 

위 코드는 데이터 해저드가 존재한다.

1번 레지스터가 계속 destination 이면서 동시에 source 이기 때문이다.

그런데 3번째 레지스터를 보면 지금 EX 해저드와 MEM 해저드가 동시에 존재한다.

그런데 과연 EX 해저드와 MEM 해저드가 동시에 존재할 수 있을까?

동시에 존재할 수 없다.

이런 경우에는 EX 해저드만 존재해야 한다.

 

따라서 MEM 해저드를 처리할 때는 위와 같은 조건을 추가해야 한다.

 

기존 조건에서 EX 해저드가 아니라는 조건이 추가되어야 MEM 해저드로 받아들인다.

따라서 포워딩을 고려한 최종 회로도는 아래와 같이 된다.

 

---

Load-Use case

하지만 아직 데이터 해저드는 온전히 해결하지 못했다.

Load Use case가 남아있기 때문이다.

 

 

위 그림이 load-use 케이스에 대한 그림이다.

이 케이스는 하드웨어적으로는 해결할 수 없다.

이 케이스를 알아차리는 타이밍이 기존 데이터 해저드 사례와 다르게 1스테이지 느린 Memory Stage 에서 알아차리기 때문이다.

이때는 어쩔 수 없이 stall을 해야 한다.

따라서 기존 회로대로 쓴다면 소프트웨어적으로 nop를 한번 집어 넣어야만 한다.

 

이제 기존 회로도에 stall 을 가해주는 회로를 만들어서 추가해보자.

우선 stall 을 가하기 이전에 load-use 케이스를 감지하는 기능을 먼저 생각해보자.

 

load-use 케이스는 ID 스테이지에서 감지한다.

ID 단계에서 먼저 앞선 명령어가 load 명령어인지 감지한다.

이 부분은 이전 클락에서 ID 단계에서 파악했던 내용을 토대로 확인할 수 있다.

왜냐하면 만약 load 명령어였다면 컨트롤 신호중 MemRead 신호가 1이었을 것이기 때문이다.

 

다음으로 파악할 것은, 이전 명령어의 RT 필드의 레지스터 번호 값이 지금 현재 명령어의 RS 또는 RT 필드와 같은지 비교하는 것이다.

 

따라서 아래와 같은 코드와 같이 load use 케이스를 확인할 수 있다.

 

이때 이전 명령어의 RT 필드 레지스터 번호는 ID/EX 파이프라인 레지스터에서 가져와야 한다.

IF/ID 레지스터에는 현재 명령어의 정보가 들어있기 때문이다.

(EX/MEM 이나 MEM/WB 에는 전전, 전전전 명령어에 대한 정보가 들어있을테니 가져오면 안된다.)

 

이를 회로도로는 아래와 같이 나타낼 수 있다.

 

이제 디텍팅을 했을 때, 어떻게 stall 할 수 있을지 생각해보자.

stall 은 파이프라인을 stall 하는 작업이다.

 

우선 해저드 디텍션 유닛이 프로그램 카운터의 write 신호를 disable 한다.

그리고 IF/ID 파이프라인 레지스터의 각 write 신호도 disable 한다.

프로그램 카운터도 본질적으로는 flip-flop 이고, 파이프라인 레지스터들도 flip-flop 이기 때문에 각각의 flip-flop에 write enable 신호가 있다면, 이 신호들을 모두 disable 시켜서 쓰기 작업을 못하게 1사이클을 막는다.

그리고 그 동안은 나머지 파이프라인은 게속 돌린다.

 

위 회로도에서 상단을 보면, 해저드 디텍션 유닛이 PC Write, IF/ID Write 신호를 꺼서 보내주는 것을 알 수 있다.

PC 도 업데이트 하지 않고, IF/ID도 업데이트 하지 않는다.

 

하지만 이렇게 하면 전에 이미 가져와서 Decode한 명령어를 실행할 수 있다.

따라서 ID/EX 파이프라인 레지스터에는 모든 컨트롤 신호를 0으로 만들어서 들여보내, decode 이후 단계를 버블화한다.

모든 컨트롤 신호가 0이라는 뜻은 nop와 같은 효과를 갖게 된다.

 

그러면 스톨되는 클락 사이클이 지나면 그제서야 pc 값이 업데이트 되면서 그 다음 명령어를 Fetch하면서 IF/ID 레지스터에 들여보내고, IF/ID 레지스터에 기존에 있던 값은 이미 컨트롤 신호를 다 0으로 써버렸기 때문에 된다.

그리고 ID/EX 에 모든 컨트롤 신호가 0으로 들어갔던 데이터들이 다음 사이클부터 다음 회로도로 들어가면 기존 회로에 아무 값을 쓰지 않기 때문에 무시된 채로 지나가게 된다.

 

그림으로는 위와 같다.

lw 이후에는 기존에 fetch 했던 and 명령어의 실행을 막고, pc값의 업데이트를 막아서 다음 클락 사이클에도 and가 fetch 되도록한다. (근데 이미 업데이트가 되지 않았을까..? IF 단계에서 업데이트하는데, 이걸 detect 하는건 ID 단계니까..

→ IF 단계에서 업데이트 하는게 아니라 IF 단계에서는 PC+4를 mux로 들여보내고만 있다. 실제 select 신호가 mux에 들어가는 건 MEM 단계 (pc src 컨트롤 신호가 결정되는 것이 mem 단계니까) 이고, 이렇게 결정된 다음 PC 값이 실제로 쓰여서 업데이트 되는 시점은 그 다음 클락사이클일 것이라고 생각하면 이해가 되었다.)

그리고 lw 라는 것을 ID 단계에서 detect 했다면 기존에 fetch 해온 and 명령어를 버블화 시켜서 (모든 컨트롤 신호를 0으로 만들어서) nop로 만든다.