[컴퓨터구조] Data Hazards

아래 사진과 같은 Pipelined Processor에서 일어날 수 있는 Data Hazard, 그리고 그에 대한 해결법에 대해 알아보자.

Pipeline은 총 5 Stage로, IF, ID, EX, MEM, WB stage가 있다고 가정한다.

또한 각 Stage들 사이에서 실행 중인 instruction의 중간 정보들을 저장하는 레지스터 4개를 각각 if2id, id2ex, ex2mem, mem2wb라고 부르자.

(사진: Patterson 교재)

Data Hazard

만약 프로그램이 앞선 inst에서 rd(destination register)에 값을 쓴 직후 다음 inst에서 그 값을 rs(source register)로 읽어들인다면, 앞 inst의 write back stage가 수행되기도 전에 뒤 inst에서 값을 가져오는 것이므로, stale value를 가져오는 격이 된다. 결과적으로 프로그램이 올바르게 실행되지 않을 수 있다. 이러한 오류의 발생 위험을 Data Hazard, 그 중에서도 RAW(Read-after-write) hazard라고 부른다.)

Scoreboard

Data Hazard에 대처하는 가장 단순한 방법은, pipeline에서 앞서 실행되고 있는 inst들의 rd를 리스트에 모두 기록해 두고, 다음 inst의 rs가 그 리스트에 있다면 그 inst를 pipeline에 진입시키지 않는 것이다.

이러한 리스트를 구현하는 하드웨어 자료 구조를 scoreboard라고 부른다. scoreboard 모듈에는 크게 세 가지 기능이 있어야 한다.

(1) insert: 새로운 inst의 rd를 리스트에 추가

(2) search: rs가 scoreboard 내에 존재하는지 검색하고 존재 여부를 신호로 출력

(3) remove: write back 시점에 맞춰, scoreboard 내 추가된 지 가장 오래된 rd를 제거

여기서, search는 새로운 inst의 rs1과 rs2에 대해서 동시에 수행해야 하므로 하드웨어적으로는 search1과 search2로 두 개의 port가 있어야 한다.

scoreboard 모듈을 활용하여 data hazard를 해결하는 방법은 다음과 같다. search1과 search2의 출력 신호 중 하나라도 켜진다면 pipeline을 멈추고, 앞선 inst가 충분히 처리되어 두 출력이 모두 꺼졌을 때 다음 inst를 pipeline에 진입시킨다.

Forwarding

Scoreboard를 이용한 Data hazard 해결은 확실하긴 하지만, rd와 rs가 겹치는 것이 있기만 하면 무조건 pipeline을 멈추기 때문에 시간 낭비가 크다. 그래서 Data Hazard는 주로 Forwarding이라는 방법을 통해 해결한다. pipeline을 멈추는 대신, 아직 rd에 쓰이지 않은 앞 inst의 연산 결괏값을 다음 inst에 직접 전달해주는 것이다. 아래 사진의 빨간 선이 forwarding을 통한 데이터 전달 경로에 해당한다.

하드웨어가 Forwarding을 수행하기 위해서는 Data Hazard를 감지하고 필요한 상황에만 forwarding을 해주는 로직이 필요하다.

어떤 조건이 만족될 때 data hazard가 발생했다고 판단할 수 있을까?

(1) 먼저 당연하게도, 앞선 inst가 레지스터 파일의 값을 업데이트하는 놈인지 확인해야 한다. (이 과정은 ex2mem과 mem2wb의 control signal을 확인함으로써 이루어진다)

(2) 여기서 앞선 inst의 rd가 x0인 경우는 제외해야 한다. (RISC-V에서 x0은 hard-wired zero이므로, 값이 실제로 업데이트되는 경우가 아니다)

(3) 이때 id2ex의 rs1 주소 혹은 rs2 주소가 ex2mem의 rd 주소와 일치한다면, data hazard가 발생한 것이다. 이 경우엔 ex2mem의 rd 값을 id2ex에 있는 inst로 forwarding해 준다. 또, id2ex의 rs1 주소 혹은 rs2 주소가 mem2wb의 rd 주소와 일치한다면, data hazard가 발생한 것이다. 이 경우엔 mem2wb의 rd 값을 id2ex에 있는 inst로 forwarding해 준다

그런데, 여기서 id2ex의 rs1 주소 혹은 rs2 주소가 ex2mem의 rd 주소와도 일치하고, mem2wb의 rd 주소와도 일치한다면 어떻게 해야 될까? (이 경우를 double hazard라 한다) 당연하지만 더 '최신의' 값을 forwarding해줘야 할 것이다. 그래서 이러한 경우에는 ex2mem의 rd 값을 forwarding해 준다.

이상으로 앞 inst에서 레지스터 파일에 값을 쓰고, 뒤 inst에서 레지스터 파일의 같은 위치에서 값을 읽어오는 경우 발생하는 data hazard의 해결법을 알아봤다. 하지만, 이와 같은 방식으로 해결이 불가능한 data hazard가 있다. 앞 inst가 load inst라서, 메모리로부터 값을 읽어와 레지스터 파일에 값을 쓰는 경우이다. 이런 경우를 Load-use hazard라고 한다.

이 경우가 문제인 이유는, ALU 연산 결과는 EX stage에서 바로 나오지만 메모리 load의 결과는 그보다 한 cycle 뒤에 해당하는 MEM stage가 돼서야 알 수 있기 때문이다. 그래서 이 경우에 즉각적인 Forwarding은 불가능하고, pipeline이 1 cycle동안 멈춰야 한다.

Load-Use hazard는 다음과 같은 로직으로 감지할 수 있다.

(1) 앞선 inst가 메모리로부터 값을 읽어오는 inst인지 확인한다. (id2ex의 control signal을 확인한다.)

(2) if2id의 rs1 주소 혹은 rs2 주소가 id2ex의 rd 주소와 일치한다면, Load-use hazard가 발생한 것이다. pipeline을 1cycle동안 지연시키고, 앞 inst의 MEM stage 결과가 나오면 forward해준다.

Stalling the pipeline

pipeline을 지연(stall)시키는 작업은 하드웨어 수준에서 어떻게 수행할까?

먼저 id2ex 레지스터에 있는 control signal을 조작해, 해당 레지스터 속 inst 정보가 다음 stage에 도달해도 아무런 operation이 수행되지 않도록 한다. 사실상 no operation에 해당하는 inst를 하나 끼워넣는 것이다. (bubble을 만든다고도 한다.) 그리고 pipeline이 stall 중인 동안에는 if2id 레지스터와 PC 값이 변하지 않도록 해당 레지스터 모듈에 control signal을 주면, clock cycle이 흘러도 id2ex보다 앞쪽에 있는 레지스터들의 값은 바뀌지 않게 된다.

pipeline이 stall되면, 그 시간만큼 instruction을 수행하지 못한다는 말이기 때문에 하드웨어의 성능에 악영향을 준다. 그러나 data hazard가 발생했을 때 프로세서가 올바른 실행 결과를 내기 위해선 stall이 필요하다.

stall의 발생 빈도를 줄이기 위해, 컴파일러 차원에서 instruction의 순서를 조율하여 Load-use hazard가 최대한 발생하지 않도록 하기도 한다.

References

1. D. Patterson, J. Hennessy (2021). Computer Organization and Design: RISC-V edition (2nd ed). Morgan Kaufmann.
2. Lecture Notes from SNU CSE (김지홍 교수님 강의노트)