[Study] Pipeline Hazard

지난 포스트에서 Pipeline이라는 기법을 살펴보았다. 이에 따른 자료는 Open Source Software Learning Center(http://olccenter.or.kr)에 공개되어 있는 민상렬 교수님의 강의를 바탕으로 정리해보고 있다. 

 아무튼 Pipeline을 하는 이유는 instruction을 stage에 나눠서 순차적으로 적용할 수 있게끔 해서 전체적으로 Sequential Execution 보다 처리되는 시간을 줄이고자 하는 것이 목적이었다. 하지만 모든 기술 구현에는 trade-off가 존재하고 Pipeline을 구현하는데 있어서도 operating Speed를 줄이는 장점을 가져올 수 있긴 하지만 이에 따른 문제가 몇가지 발생한다. 이걸 전문 용어로 Hazard(위험) 이라고 하고 이 내용에 관해서 조금 정리해보고자 한다.

 위에서 장황하게 말하긴 했지만 원서에서 언급되어 있는 hazard의 정의는 다음 Instruction이 다음 clock cycle에서 정상적으로 수행되지 못하는 것을 나타낸다. 보통 Instruction과 Cycle간의 비율을 CPI( Cycle Per Instruction)이라고 하고, 이상적인 Pipeline은 바로 한개의 Instruction이 처리되는데 걸리는 Cycle이 1인 구조(CPI=1)를 취한다. 하지만 위와 같이 hazard가 발생해버리면 CPI가 1보다 높아지는 경우가 발생할 수도 있는 것이고, 심각한 경우에는 원치 않는 답까지 얻게 될 수도 있는 것이다. 

 학부 Architecture 수업에서 다루는 Pipeline Hazard는 크게 3가지로 나눌 수 있다. 

 - Structural Hazarden

 - Data Hazard

 - Control Hazard

Structural Hazard는 말그대로 pipeline 구조로 인한 문제이다. 내부 구조를 보면 다음과 같다.

 위의 사진은 MIPS의 내부구조이다. 잘 보면 알겠지만 내부의 형태가 하나의 미세한 도선으로 되어 있다. 위의 구조는 이미 hazard를 해결하기 위한 방안이 적용되어 있긴 하지만 아무튼 도선상에는 0과 1이라는 binary 코드가 전달된다. 그래서 해당 모듈로부터 정보를 얻고 싶으면 이전 모듈이 0과 1로 된 signal을 보내서 그에 대한 결과를 얻는 게 정상적인 동작 수행이다. 그런데 만약 두개의 모듈이 하나의 모듈로 동시에 signal을 보내면 어떻게 할까? 물론 애초의 signal이 어디로부터 온 것인지 안다면 그에 따른 처리는 먼저받은 거 먼저 나중에 받은 건 나중에 하는 식의 논리적인 방식으로 따로 할 수 있겠지만, 일반적으로는 동시에 signal이 들어오게 되면 처리하기 어려워진다. 줄이자면 모듈은 한번에 한가지 기능만 수행할 수 있는데 서로 다른 모듈이 결과를 얻기 위해서 충돌하는 것이다. 소위 하나의 Resource에 대한 Conflict가 발생하는 것이다. 가까운 예로는 메모리 입출력을 들 수 있다.

위의 구조는 4 stage pipeline 구조이다. 모든 Instruction의 수행이 IF-ID-EX-MEM-WB으로 이뤄진다고 가정했을 때 4번째 Cycle에서는 첫번째 Instruction의 Memory Access와 네번째 Instruction의 Instruction Fetch가 동시에 Memory Access를 요구하게 된다. 메모리는 당연히 어디서 해당 signal을 받았는지 알 수 없기 때문에 결론적으로 Resource Conflict 현상이 발생하는 것이다.

 물론 이에 따른 해결책은 아주 근본적인 방법이 Resource를 Duplicate하는 것이다. 설계하는 사람의 입장에 따라서 달라지겠지만 이렇게 중복되는 모듈을 하드웨어를 더 집어넣음으로써 해결할 수도 있는 것이고, 또는 위의 예에서만 보자면 지금 첫번째 Instruction에서 Memory상에서 처리하는 것은 Data이고, 네번째 Instruction에서 처리하는 것은 Instruction 자체를 Fetch하는 것이기 때문에 애초에 Memory를 두개 두어서 Data따로 Instruction 따로 처리할 수도 있게 하는 것이다. 흔히 공개되어 있는 자료에는 이런 해결방법을 다음과 같이 요약하고 있다.

- More Hardware

- Separate ALUs for arithmetic, target address calculation, PC Increamentation

- Dual-ported register file

- Write / Read registers in different phase

- separate the memory for instruction & data ( -> cache)

- improve performance

아무튼 돈을 쓴다면 이런 구조적 문제를 해결할 수 있다. 다 보면 알 수 있다시피 포트를 나누고 ALU를 더 삽입하고 메모리를 삽입하는 것 자체가 구조적 설계가 바탕되어 진행되기 때문에 이에 따른 해결책도 유용하다고 생각하지는 않다. 그래서 간단하게 생각해볼 수 있는 해결책이 바로 저렇게 중복해서 쓰는 부분에서는 다른 Instruction 처리시 쉬어주게끔 고려를 하자는 것이다. 이른바 Stall 이라는 것인데, 기기적으로 이상이 없음에도 일부로 수행을 멈추게 하는 것이다. 당연히 하드웨어적으로는 추가하는 것이 없기 때문에 비용적인 부담은 없겠지만, 아무래도 성능이 전자에 비해서 좋지 않음을 알 수 있다. 

 사실 이 Stall이라는 것은 모든 Hazard에 대해서 적용해서 해결할 수 있다. 그냥 문제만 발생하면 무조건 해당 부분에 대해서 쉬어주면 되기 때문이다. 이부분은 다른 hazard에서도 언급할 것이다.

두번째 Hazard는 Data Hazard이다. 이 문제는 처리속도가 느려지는 것에서 벗어나 아예 사용자가 원하는 답에서 벗어난 것을 출력으로 내놓기 때문에 치명적이다. 물론 그렇다고 다른 hazard도 치명적이지 않은 건 아니지만... 아무튼 Data Hazard는 Data에 대한 Read/Write Sequence가 엇갈리면서 발생하는 문제이다. 간단히 말하자면 두번째 instruction의 결과가 첫번째 instruction에 dependent하기에 발생하는 문제인 것이다. 이에 따른 경우도 3가지를 들 수 있다.

- Read After Write ( RAW )

- Write After Write ( WAW )

- Write After Read ( WAR )

처음보는 사람이라면 왜 Read After Read는 Hazard가 아닌가 궁금해할 수도 있지만 말을 곱씹어보면 문제가 아님을 알 수 있다.단순히 Read만 상황에서는 결과값이 바뀔 염려가 없기 때문이다. 잘 보면 Write 과정이 이런 Data Hazard를 야기하고 있다.

RAW에 대한 예시는 다음과 같다.

 첫번째 Instruction에서는 $2에 저장된 결과를 두번째, 세번째 instruction에서 활용한다. 물론 이전의 Sequential Execution에서는 문제가 없었지만 위와 같이 pipeline을 적용하면서 $2가 저장되기 이전에 그 이후에 수행되어야 할 instruction이 미리 수행되어 버리는 것이다. 그러면 and와 or 의 연산 결과는 $1과 $3이 Sub한 결과가 아닌 이전에 들어있던 쓰레기 값으로 수행될 것이다. 이렇게 값을 Read하기 이전에 그 값이 Write됨으로써 야기되는 문제를 RAW hazard라고 한다. 그럼 이걸 해결할 수 있을까?

 답은 간단하다. 지금 전체적으로 Instruction이 수행되었다고 하는 것은 $2의 값이 Register에 쓰고 난 이후가 되는데 원론적으로 우리가 원하는 결과는 ALU를 거치고 나온 직후의 결과인 것이다. 즉, EXE 이후의 수행은 값을 저장하기 위한 과정인 것이지 값을 구하는 과정이 아닌 것이다. 그러면 EXE 이후의 결과를 바로 두번째 Instruction과 세번째 Instruction에서 활용하게끔 하면, sub한 결과로 밑의 and와 or를 수행할 수 있는 것이다. 일종의 결과가 지나갈 길을 만들자는 뜻에서 Forwarding (또는 bypassing)이라고 하는데 이걸로 hazard를 해결할 수 있다.

사진과 같이 Forwarding Unit을 두고 적절할 때 위와 같이 data를 넘겨주게 되면 적절한 답을 얻을 수 있게 된다. 

아니면 앞에서 언급했던 Stall로도 해결할 수 있다. 강의에서는 Freezing the Pipeline이라는 말로 표현되어 있는데 앞에서 설명한 그대로 첫번째 연산이 끝나기 전까지 두번째와 세번째를 기다리게 하는 것이다. 

보통 내부구조에서 정지되어 있는 형태이기 때문에 pipelined interlock이라는 표현을 하기도 한다. 

또다른 방식으로는 instruction 수행 과정 내에 delayed load를 하나 삽입해서 지연시키는 효과를 가져오기도 한다. 

위와 같은 방식은 하드웨어적으로 개선하기 위한 방안이고, 개발자 또는 컴파일러가 이런 걸 염두하고 프로그래밍하기도 한다. stall을 통해서 하드웨어적으로 처리하는 것을 ASM에서는 nop이라는 명령어로 처리할 수 있다. 이런 해결 방법을 Code Scheduling이라고 한다. 

마지막으로 남은 Hazard는 바로 Control Hazard이다. 

Computer Architecture를 공부하는 사람이라면 아마 instruction을 수행하는데 있어서 Program Counter의 역할이 있다는 것을 알고 있을 것이다. 보통은 4가 더해지면서 다음 instruction을 수행하지만, 이외의 방법을 통해서 instruction이 수행되는 경우가 있는데 바로 Branch나 Jump 같은 소위 건너뛰는 명령어가 발생하는 경우이다. 이런 명령어가 나오면 PC가 가변적으로 변하게 된다. 문제는 해당 instruction이 pipelined execution을 수행하는데 지장을 주는데 있다. 한번 예시를 보겠다.

 이상적인 pipeline 구조라면 앞에서 잠깐 설명한 CPI가 1인 형태를 취할 것이다. 하지만 첫번째 instruction이 Branch 관련 명령어라면 Program counter가 해당 address로 넘어가면서 두번째 instruction은 수행되지 않을 것이다. branch 명령어의 특성상 현재의 address를 저장해둔 상태에서 수행한 후 다시 돌아오기 때문이다. 이때문에 의도하지 않은 stall이 발생하게 되고 결론적으로 pipeline의 제성능을 못 나타내게 된다. 위의 예시에서는  3 cycle의 panalty를 가지게 된 것이다. 참고 자료에 따르면 CPI는 약 45% 정도 증가한 것으로 나와있다. 

 이 hazard 역시 전체적인 처리 속도를 저하시키기에 해결책이 필요한데 대표적인 방법이, 예측을 하자는 것이다.

< branch 조건에 맞지 않을 때>

<Branch 조건에 맞을 때> 

Branch 성립 여부에 상관없이 일단은 두번째 instruction을 수행해놓고 보자는 것이다. 그래서 branch의 성격에 맞게 PC를 바꿔주면 중간에 의도치않게 발생하는 stall을 줄일 수 있을 것이다. 일단 기본적인 전재 자체가 branch가 성립하지 않을거라 가정하고 다음 instruction을 수행한 것이기 때문에 이같은 방식을 Predict-Not-Taken 방식이라고 한다. 반대로 branch가 무조건 성립할거라는 가정하에 target Instruction을 먼저 수행하는 방식을 Predict-Taken 방식이라고 한다. 그런데 잘 보면 알겠지만 Predict Taken 방식은 아무 의미가 없다. Branch라는 것 자체가 Instruction Decode가 이뤄진 뒤에 Target Address가 나오기 때문에 이 방식을 사용해서 줄일 수 있는 stall 자체가 극히 드물다는 것이다. 

 이것 말고도 Delayed Branch라는 해결 방식이 있는데 민상렬 교수님은 이 방식이 꼼수라고 했다. 그말이 뭔가 하니 그냥 branch의 성립조건에 상관없이 무조건 다음 instruction을 수행하게 하자는 것이다. 조금 말하고 보니 이상한데, Branch 자체가 Target으로 넘어가는 것이기에 다시 돌아오기 전까지는 다음 instruction을 수행하는 것이 의미가 없다. 왜 할까 하는 생각이 바로 정답이다. 그냥 할게 없으니까 그냥 수행하게 하는 것이 보기도 좋은 것이다. 그래서 사실 해당 부분이 nop으로 처리되어 있는 것과 비슷한 것이다. 

< Delayed Branch의 적용 >

사실 branch instruction 바로 다음 instruction을 항상 실행하게 해놓은 건 아무 의미가 없는 것이다. 아무튼 이렇게 branch instruction 바로 뒤에서 수행되는 의미없는 instruction이 담긴 걸 Delay Slot 이라고 한다. 내 생각에는 그냥 dummy 라고 보면 좋을 거 같다. 교수님도 강의에선 꼼수라고 표현하신 것도 약간 이해가 될 듯 하다.

아무튼 pipeline 구현시 발생할 수 있는 hazard에 대해서 정리해보았다. 제대로 이해한 건지는 모르겠지만.. 뭐 어떤 hazard가 발생하고 그걸 해결하기 위해서 어떤게 접근할 수 있는 지를 알아보았다. 이제 문제를 알아봤으니까 실제로 구현하기 위해서는 이 모든 것들을 제어할 수 있는 Controller와 어떤 hazard인지를 판별하는 checker가 필요하다는 것을 알 수 있을 듯 하다. 나도 고급 컴퓨터 구조 과제를 수행하면 아주 간단한 6-stage pipelined processor를 Verilog로 구현한 적이 있었는데 그 때 생각보다 너무 안일하게 접근한 것 같다. 조금만 더 깊게 팠더라면 훨씬더 이해가 쉬웠을텐데 하는 아쉬움이 있긴 하다.

Reference 

- Example of Structural Hazard : http://wearcam.org/ece385/lectureB/structuralhazardexample.htm

- Iowa State Univ CA Reference : http://www.cs.iastate.edu/~prabhu/Tutorial/title.html

- Enhancing Performance with Pipeline : http://larc.ee.nthu.edu.tw/~cthuang/courses/ee3450/lectures/06_pipeline.html

- Control Hazard에 대해서 : http://blog.naver.com/PostView.nhn?blogId=leojesus&logNo=80049514256 

- Branch Hazards in pipelined processor (UCSD):  http://cseweb.ucsd.edu/~carter/141/

- Open Source Software learning Center : olccenter.or.kr