Hazards

저번 포스트까지 pipelining에 대해 알아봤습니다. 파이프라이닝이 정말 강력한 도구임은 분명하지만, 이 또한 문제가 발생할 수 있습니다.

기본적으로 파이프라이닝은 최초로 하나의 명령어가 완료된 이후 CPI가 1이 되는 것을 목표로 합니다. 즉, 한 clock cycle에 하나의 명령어를 마치는 것입니다. 하지만 특정한 조건들 하에 CPI가 1이 되지 않는 경우가 발생합니다.

이 문제들을 Hazards라고 하며, 총 3가지가 있습니다.

1. Structural hazards

2. Data hazards

3. Control hazards

아래에서 하나하나 자세히 설명하겠습니다.

Stall Cycle

그 전에 간단하게 짚고 넘어가야하는 개념이 있습니다. Stall cycle 이라는 것인데 이것은 hazard가 발생했을 때, 명령어를 실행하지 않고 쉬는 사이클(대기시간)을 만들어 줌으로써 다음 명령어를 실행할 수 있게 하는 것입니다.

물론 이것도 hazard를 해결할 수 있는 방법 중 하나이지만, 성능 저하를 일으키기에 stall cycle을 만들지 않고 해결하는 방법들을 아래에서 소개합니다.

Structural Hazards

Structural hazards 는 서로 다른 stage들이 동시에 같은 resource를 필요로할 때 발생합니다.

예를 들면 IF와 MEM의 경우 둘 다 Memory를 Acess 해야합니다. 처음 3번까지는 문제가 없겠지만, 4번째부터는 계속해서 IF와 MEM이 동시에 실행됩니다. 이 때 2개의 stage 모두 memory를 사용해야하므로 structural hazards가 발생하는 것입니다.

이걸 해결하는 방법은 2가지가 있습니다.

1. Instruction memory와 Data memory로 나누기

2. multi port로 설정하여 read/write를 동시에 할 수 있게 하기

두 개의 해결 방법 모두 단순히 resource를 늘림으로써 해결할 수 있는 문제이기 때문에 현대에는 structural hazards는 큰 문제가 되지 않습니다.

Data Hazards

Data hazards는 이전 명령어에서 data를 받아와서 현재 명령어를 실행해야하는데, 이전 명령어가 아직 끝나지 않아서 data를 받아오지 못하는 경우에 발생합니다.

위의 예시에서 sub 명령어는 add 명령어의 결과 값이 필요한데, sub의 EX stage가 실행될 때 아직 레지스터에 write 된 상태가 아닌 것입니다.

이를 해결하기 위해서 당연히 아래 그림처럼 stall cycle을 넣어도 됩니다. 하지만 CPI가 4로 증가하였기에 바람직하지 않습니다.

Forwarding(Bypassing)

그렇다면 해결 방법엔 뭐가 있을까요? 생각보다는 간단합니다. add 명령어가 실행되고 최초로 값이 결정되는 것은 EX stage입니다. 그럼 EX stage의 결과값을 sub의 input으로 넣으면 해결이 될 것 입니다.

물론 어떻게 output을 input에 넣는지는 컴퓨터공학의 범주에서 설명할 부분은 아닙니다. 그냥 전선 연결하면 되겠죠.

이 방식이 바로 forwarding 입니다.

하지만 방금 소개한 것은 결과값이 EX stage에서 바로 나오는 경우에 국한됩니다. 반드시 메모리에서 읽어야하는 Load 같은 경우에는 MEM에서 바로 EX의 input으로 간다고 해도 1개의 stall이 발생합니다.

그냥 add처럼 하면 안되냐는 질문은 받지 않겠습니다. 이 기법의 이름이 Forwarding 인 것에는 다 이유가 있습니다. MEM의 output을 stall 없이 EX의 input으로 하면 그건 Backwarding이고... sub 입장에선 미래를 예측하는 꼴이 되는겁니다.

그럼 어떻게 해결하는지는 아래에 보여드리겠습니다.

stall cycle 자리에서 할 수 있는 일을 하면 됩니다. 물론 위의 예시들처럼 명령어를 단 2개만 실행한다면 아무런 의미가 없겠지만, 사실 2개만 실행할 정도면 stall 하나쯤 들어가도 체감도 안 될겁니다.

Data Hazards Type

Data Hazards에는 4가지 Type이 있습니다. 결론만 말하자면 쓰거나 읽기 위해서는 그 대상이 반드시 업데이트 돼 있어야 한다 는 것 입니다.

기본적으로 먼저 실행되는 명령어를 I, 뒤에 실행되는 명령어를 J로 두고 시작하겠습니다.

1. RAW (Read After Write)

이 경우는 데이터 종속성을 위반한 경우입니다. (True Dependency)

J가 데이터를 읽으려고 할 때, I가 데이터를 아직 쓰지 않은 상태입니다. 즉 J가 I의 결과를 읽어야 하지만, I가 아직 데이터를 쓰지 않은 상태입니다.

아까 위에서 봤던 것이 이 경우입니다.

2. WAW (Write After Write)

이 경우는 출력 종속성을 위반한 경우입니다. (Output Dependency)

J가 데이터를 쓸려고 할 때, I가 아직 데이터를 쓰는 작업을 완료하지 않았습니다. 즉 쓰기 작업이 순서대로 실행되지 않아 J의 쓰기가 I의 쓰기보다 먼저 완료될 수 있습니다.

이는 명령어가 동시 실행되어 같은 레지스터를 사용할 때 발생하며, 순차적으로 실행할 때는 문제가 되지 않습니다.

3. WAR (Write After Read)

이 경우는 입력 종속성을 위반한 경우입니다. (Anti-dependency)

J가 데이터를 쓰려고 할 때, I가 해당 데이터를 읽으려고 하는 상황입니다. 즉 J가 데이터를 덮어 쓰게 되면 I는 잘못된 값을 읽게 됩니다.

이 또한 명령어가 동시 실행되어 같은 레지스터를 사용할 때 발생하며, 순차적으로 실행할 때는 문제가 되지 않습니다.

4. RAR (Read After Read)

이 경우는 두 명령어가 같은 데이터를 읽는 경우이므로 hazard가 발생하지 않습니다.

Control Hazards

Control hazards는 branch나 jump 명령어를 실행할 때 발생합니다. 이 명령어들 특성상 조건이 일치하는지 확인하고 맞다면 PC+offset를, 아니면 PC+4를 실행하는 구조입니다. 그 말인 즉슨 값이 결정될 때 까지는 어디로 갈 지 모른다는 것입니다.

여기서 PC+offset을 실행하는 경우를 taken PC+4(다음 명령어 순차 실행)인 경우를 untaken 이라고 명시합니다.

stall cycle만을 넣어서 해결한다고 가정하면 총 3개의 cycle을 넣어야 합니다. PC 값을 몰라서 발생하는 것이므로 알 수 있는 방향으로 해결하면 됩니다.

첫번째로 일단 위에서 알게 된 Forwarding으로 하나를 줄일 수 있습니다. MEM의 output을 IF의 input으로 넣는 것이죠.

두번째 cycle을 없애는 방법은 하드웨어적인 측면입니다. ID stage에서 ALU를 넣어 미리 비교를 하고 IF의 input으로 주는 것입니다.

마지막 cycle은 data hazards에서 배웠듯이 stall 자리에 할 수 있는 명령어를 넣으면 됩니다.

이런 식으로 해결을 할 수'도' 있지만 너무 복잡합니다.

Prediction

그래서 사용하는 것이 prediction 입니다. 말 그대로 다음에 올 명령어를 예측하여 실행하는 것입니다. 단순한 방법으로는 일단 다음이 untaken이라고 예상하고 맞으면 그대로 진행하며 아니면 branch target으로 가면 됩니다. 예상이 틀렸다면 stall이 하나 생기는 것입니다.

근데 중요한 건 이것도 별로 마음엔 안 듭니다. 극단적으로 branch만 1억번 있다면 너무 비효율적인 방법이니까요.

그래서 명령어들의 경향을 보아 taken이었다면 taken, untaken이었다면 untaken일 것이러는 정보를 Branch Target Buffer(BTB) 라는 곳에 저장하여 사용합니다.

예를 들어 반복문을 100번 돈다고 가정해보면 최초에는 untaken이겠지만, taken이 반복됨으로써 계속해서 taken으로 branch 명령어를 실행하는 것이 이득입니다.