[Computer Architecture] What is ILP?

다시 컴퓨터구조 책을 펼치고 공부하고 있다. 그런데 공부하면 배우는 내용이 꼭 컴퓨터 구조에 국한된 내용이 아니라는 것을 깨닫곤 한다. 예를 들어 이전 포스트에서 주구장창 다뤘던 hazard문제도 Architecture 관점에서 고려해야 되는 측면도 있으며, 한편으로는 컴파일러 관점에서 고려해줘야 할 점도 있다. 이런저런 생각을 하다가 혼자서 공부해본 내용을 조금 요약해보고자 한다. 

 

 컴퓨터내에서 instruction은 단순히 명령어만을 지칭하는 것이 아니라, 컴퓨터의 성능을 판단하는 지표로 사용된다. 쉽게 말해서 컴퓨터가 정해진 시간에 얼마나 instruction을 처리하냐를 생각하면 좋을 거 같다. 당연히 성능이 좋은 컴퓨터는 단시간에 많은 instruction을 처리할 수 있을 것이다. 이런 개념을 보통 CPI (Clock Per Instruction) 혹은 IPC( Instruction Per Clock) 으로 표현하기도 한다. 

그런데 머리좋은 사람들이 Pipeline이라는 것을 만들어서 단계별로 instruction을 처리할 수 있게끔 했다. 이전 포스트에서도 언급되었지만 Pipeline이라고 하면 각 stage사이에 register를 두고 필요할때 꺼내쓰게 할 수 있음으로써 기존에 순차적으로 처리하는 Sequential 방식에 비해서 처리시간을 줄일 수 있게끔 했다. 당연히 register가 이전 값을 가지고 있으므로 이전 단계는 idle한 상태를 가질 필요없이 지금의 instruction이 요구할 때만 동작하면 되는 것이다. 소위 instruction을 겹치게(overlap) 해주는 방식 전체를 Instruction Level Parallelism (ILP) 라고 한다. (잠깐 여담을 말하자면 compiler 특강 수업을 듣고 있는데 ILP라는 말이 나와서 뭔가 싶었다. 위키에도 나와있지만 ILP는 Instruction Level Parallelism을 말할 수도 있지만 때로는 Integer Linear Programming을 지칭하기도 한다.. 물론 컴파일러 내에서도 증명문제가 논문 근거로 제시되기 때문에 아주 가끔 나온다..)

 아무튼 ILP는 두가지 방법으로 접근할 수 있다. 첫번째는 하드웨어적으로 구현해서 parallelism이 가능한지를 dynamic하게 판단하는 방법이고, 또 다른 방법은 소프트웨어적으로 compiling시 static하게 parallelism을 판단하는 방법이다. 두가지 방법다 시중에 출시되어있는데 첫번째 방법은 pentium이라는 이름으로 나와있고, 후자는 itenium 에 구현되어 있다. 당연한 이야기겠지만 전자로 구현한 방법이 훨씬더 빠르고, 많이 사용된다. 물론 그렇다고 후자가 나쁜 방법인 건 아니지만 이것도 두 방식의 차이라고 볼 수 있겠다.

자 앞에서 컴퓨터의 성능을 판단하는 척도로 CPI를 들었다. 그러면 이렇게 ILP를 적용하고 난 후의 CPI를 구하면 어떻게 될까? 물론 Sequential방식에 비해서 줄어들겠지만 여기에도 고려해야 될 상황이 있고, 그게 이전포스트에서도 계속 언급되었던 hazard문제이다. 일단 ILP내에서의 CPI는 다음과 같다.

Pipeline CPI = ideal pipeline CPI ( 이론상으로 나올 수 있는 performance 의 최대치)

+ structual stalls        

+ Data Hazard Stalls

+ Control Stalls           

당연히 컴퓨터 과학자들의 숙명은 이런 값들을 얼마나 줄일 수 있느냐이고, 이에 따른 여러가지 technique들이 제시되어 있다. 대표적인 내용이 이전포스트에서도 열심히 소개했던 Branch Prediction 과 Speculation, Delayed Branch등이 있고, 소개하지 않은 내용중에서도 SuperScalar 구조내에는 Scoreboarding 방식같은게 이런 Pipeline CPI를 줄일 수 있는 방법이다. 그리고 어떻게 보면 당연하겠지만 대부분의 방법이 ideal CPI 를 줄이는 것보다는 Hazard로 인한 Stall을 방지하는 데 초점이 맞춰있다. (물론 Software Pipelining같은 방법을 잘 찾아보면 ideal CPI를 줄이는 방법에 대해서도 알수 있다..)

 일단 ILP를 적용하면 hazard문제가 있긴 하지만 CPI가 줄어들긴 한다. 그럼 이걸 어디에 적용할 수 있을까? 다르게 말하면 위에서 말한것처럼 hazard가 발생하는 부분은 어디일까? 로 질문할 수 있다. 그리고 일단 보통은 loop iteration시에 이런 관점을 적용할 수 있다. 이걸 Loop-level Parallelism이라고도 한다. 잠깐 예시를 보겠다.

                                                for(i = 1; i <= 1000 ; i++) 
  x[i] = x[i] + y[i];

  

뭔가 이상한 코드다 x[i]가 read가 일어나는 동시에 write가 동시에 진행되고 있다. 하지만 i 시점 내에서는 다른 영역에 접근하는게 아니기 때문에 이걸 구성하는 instruction들이 살짝살짝 overlap할 수 있는 가능성이 보이기는 한다. 이게 Loop-level Parallelism이다. 이걸 Parallelism이라고 인식하는 방법은 앞에서 잠깐 소개했던 여러가지 방법들로 할 수 있다. 그리고 이런 방법말고도 다르게 판단할 수 있는 방법이 바로 vector instruction을 사용하는 것이다. 수학에서 vector는 방향과 크기를 가진 개념이었지만 요기에서는 그냥 1차원 배열로 보면 된다. 즉 다시 풀어말하자면 이런 instruction을 배열에 담아서 보면 Parallelism을 판별할 수 있게 된다는 것이다. 당연히 이걸 처리하기 위해서는 일반적인 processor가 아니라 이걸 처리하기 위한 vector Processor라는 게 존재한다. 간단한 예를 들자면 일반 processor는 위와같이 loop를 한 instruction을 읽어서 처리하는 방식일 것이다. 하지만 vector Processor는 위의 loop를 처리하기 위해서는 4개의 instruction이 필요하다. x와 y를 각각 load하는 instruction, add하는 instruction, 그리고 그걸 다시 x 에 집어넣는 store instruction.. 이렇게 4개의 instruction을 vector에 담아서 처리하는 방식이 되겠다.(물론 요즘 나오는 processor들은 이런 vector Processor가 처리하는 걸 처리할 수 있다.)

뭐 간단히 Instruction Level Parallelism에 대해서 정리해봤다. 아마 책보고 또 공부하다보면 또 올릴게 생길지도 모르겠다.

- reference

Computer Architecture : A Quantitative Approach 4th ed