[Compiler] How to Vectorize the code by example

프로그램을 빠르게 실행시키고자 하는 욕망은 컴퓨터를 사용하는 사람이라면 누구나 가지고 있다. 물론 하드웨어 적으로 성능을 극대화시켜서 빠르게 처리할 수도 있겠지만 가장 이상적인 방법은 돈안들이고 처리 속도를 높이는 것이다. 당연히 이렇게 하려면 뭔가 소프트웨어적으로 최적화해줘야 할 것이다. 이때 컴파일러의 역할이 중요하게 작용한다. 물론 요새는 컴파일러 공부하는 사람들도 별로 없겠지만...

 보통 속도를 높여야 할 작업은 사람이 느끼기엔 다르겠지만 보통은 데이터 연산을 처리하는데 필요할 것이고, 그런 데이터는 일반적으로 배열로 들어있다. 그래서 사람들이 생각하기엔 배열에 들어있으니까 한번의 사이클마다 배열의 열 또는 행에 있는 데이터를 한번에 처리하면 어떨까 싶어서 만든 개념이 Parallelization 이라는 것이다. 말그대로 데이터를 병렬적으로 처리할 수 있느냐에 대해 묻는 개념이다. 그런데 한번 생각해보자. 만약 코드내에 루프가 있고, 그 안에 변수가 있다고 가정해보자. 어차피 컴퓨터가 루프내의 변수를 읽으면 그거 자체가 의미를 가지고 있는 것으로 이해하는게 아니라 그 변수가 담긴 메모리에 접근해서 읽는 것이다. 그래서 해당 메모리 주소에 들어있는 값을 읽고 a=b다 라고 이해하는 것이다.

 그런데 문제는 이렇게 읽고 쓰는게 한군데에서 일어나면 어떻게 되냐는 것이다. 만약 a라는 변수에다 무엇을 정의했는데 루프 내에서 그 a 변수에 또 뭔가를 정의하면 당연히 이전에 정의한 값은 사라질 것이다. 당연히 사용자에 따라서는 이전 값을 읽고 싶어했는데 전혀 생뚱맞은 결과를 얻을 수도 있는 것이다. 아마 컴퓨터 구조를 배운 사람이라면 pipeline을 배우면서 hazard라는 걸 배울 것이고, 앞에서 설명한 과정이 그런 hazard 중 하나인 Read After Write (RAW) 라는 것을 알고 있을 것이다. 컴파일러에서도 이런 개념이 중요하다. 더구나 앞에서 언급한 것처럼 행렬에 있는 데이터를 한꺼번에 가지고 와서 처리할때는 이런 문제가 더 크게 작용하게 된다. 그래서 이런 걸 체크하는 작업을 dependence test라고 한다. 그리고 이에 따라서 코드를 최적화하는 작업을 Vectorization이라고 정의한다.

 마침 중간고사를 준비하면서 직접 코드를 vectorize해 볼 수 있는 경우가 있어서 한번 예제를 다시 정리를 해보고자 한다. 문제는 다음과 같이 주어져 있다. 설명은 좀있다가..

자 이제 게임을 시작하지..가 아니고 풀이를 한번 해보겠다.

우선 loop내의 dependence를 측정하기 위해서는 루프의 direction을 일치시켜줘야 한다. 그래서 loop-varient variable을 살펴보면 i, j, k가 있는 것을 볼수 있는데 잘보면 k의 direction이 negative로 되어 있다. 그러니까 memory access를 할때 다른건 순차적으로 찾아가는데 k 혼자 감소하는 방향으로 접근하게 되는 것이다. 그래서 모든 것을 일치 시켜주기 위한 normalization 과정이 필요하다.

normalization과정은 간단하다. 그냥 다른 루프들을 보고 증가인자만 동일하게 해주면 되는 것이다. 따라서 k--이던게 k++로 바뀌게 된다. 물론 증가 인자가 바뀌었으니까 Lower Bound와 Upper Bound도 변화시켜주고 내부적으로 k가 들어간 인자들은 전부 부호를 반대로 해줘야 하겠다.

자 그럼 normalize가 끝났기 때문에 비로소 state간의 dependence test를 할 수 있다. 아마 computer Architecture시간에 hazard를 배운 사람이라면 WAR, RAW, WAW 같은게 있다고 배웠을 것이다. 이걸 확인하는 것이고, compiler에서는 앞에서 언급한 것처럼 dependence test를 수행한다고 한다. 그런데 두가지 케이스로 나눠서 볼 수 있다. 첫번째는 input dependence test, 즉 예를 들어 A = B라는 코드가 있을 때 A -> B로 가는 방향으로 dependence test를 하는 것이고, 다른 하나는 자기 자신에다가 뭔가를 덧쓰는지를 확인하는 것, 간단히 이야기 하면 A->A방향으로 갔을때의 dependence test를 수행하는 것이다. 흔히 이걸 memory에 Write하는 결과물에서 dependence를 측정하는 것이라 하여 output dependence test라고 하기도 한다. 그래서 위의 이미지는 일단 input dependence test를 분류한 결과이고, 이때는 위와 같이 A -> B로 갈때 겹치는 배열이 있으면 그에 따라서 따로 분류한 결과이다. 잘보면 S1과 S2 사이에서는 A배열에 대해서 서로 읽고 쓰는게 진행되고 있으므로 이에 대한 dependence Test를 진행하는 형식이다. 나머지 두가지 케이스도 그렇게 분류하면 input dependence test에서는 총 3가지 경우가 나오게 된다. 

그럼 첫번째로 분류한 s1->s2 on A 케이스를 따져보면 A[j] -> A[j] 에 대한 dependence Test를 진행해야 한다. 그런데 잘 보면 j 값에 따라서 ㅁ