35bec628fdd12ea460bcd1bd18d22c3a8e62ea0120a596fbea60f9ef237fd265d3fcce6a






프로그래밍 언어론 듣고 언어 설계해보고

형식언어, 오토마타론 수업 듣고 언어 체계 정의하는 추상기계 배워보고

컴파일러 듣고 렉서 파서 제너레이터 SSA폼중간언어 최적화루틴들 레지스터할당기 어셈블러도 만들어 보고

솔직히 취향 안맞으면 재미는 없다

근데 대학 나왔으면 컴공 3대장 디비 컴파일러 오에스 이 세 개는 다 들어보고 졸업해야되지 않겠냐?

학부생 때 아니면 이런거 언제해보겠냐

니들이 선택한 컴공이다

할꺼면 한 번 제대로 해보자


참고로 짤은 loop unrolling이라는 최적화 패스를 구현한거다

loop unrolling은 걍 존나쉬운 최적화 방법 중 하나다

그냥 루프를 펼쳐놓은거뿐이다

for i = 0 to 10, i+=1를 i+=1, i+=1 ... i+=1 이렇게 바꾼다.

개나소나 할 수 있을 정도의 최적화 아니겠냐?

근데 왜 루프를 펼쳐놓은게 최적화가 되는걸까? 궁금하지 않냐?


컴파일러를 깊게 배우고나면 저런 최적화기법에 대한 이해 및 구현은 기본이고 언제 저런 최적화를 해야 효율이 좋은지까지

논리적으로 통계적으로 딥러닝모델로 파악할 수 있다

간단하게 예를 들어보자


루프를 왜 펼쳐놓는걸까? 왜 펼치면 좋을걸까?

루프를 펼쳐두면 분기 비용을 줄일 수 있는 효과가 있다

분기 비용이 뭘까?

컴퓨터 구조론 시간에 MIPS 아키텍쳐를 배웠으면

이 아키텍쳐를 배울때 시간 낭비를 줄이기 위해서 명령어 파이프라인를 잘게잘게 쪼개어

각 파이프라인 스텝마다 다음번 명령어를 미리 실행한다는 개념이 생각날 것이다

다음번 명령어를 미리 실행했을때 레지스터의 값이 바뀐다던지하는 문제땜에

현재 파이프라인을 날리고 새로 실행해야되는 것이 비용 문제라고 배웠을 것이다


근데 현대 프로세서들은 모두 견고한 분기예측기를 가지고 있다

대충 이번에 분기를 했으면 다음 번에도 분기를 할 확률이 높으니깐 일단 분기를 미리 실행하고

분기가 실패하면 명령어 파이프라인을 날리고 분기끝나는 부분부터 다시 시작한다


그러면 루프를 풀어놓아봤자 분기 예측보다 못하지 않냐?라고 생각할 수 있다

맞다. 루프 언롤링은 간단한 시그마 연산과 같은 경우를 제외하면 대부분의 경우 분기 예측만큼 좋은 성능을 못 낸다고한다.

왜 그럴까?


루프 언롤링의 개념은 사실 C언어와 같은 고급언어영역에서 볼땐 루프를 펼쳐놓은 것이라고 밖에는 설명할 수 없다

어셈블리, 기계어급의 저급언어관점에서 봤을때도 사실 설명이 힘들다

실제로 프로세서의 적재되어 실행되는 과정을 살펴봐야지 제대로된 설명이 가능하다


리눅스 커널의 배리어 함수를 아는가? 이 함수는 컴파일러가 어셈블리 코드의 순서를 지멋대로 바꾸는걸 막는다

왜 이런 함수가 존재할까? 이런 함수가 존재한다는거는 컴파일러가 지멋대로 어셈블리 코드의 순서를 바꾸기 때문이라는걸 알아야한다

왜 지멋대로 순서를 바꿀까? 이건 어셈블리의 실행순서에따라 명령어 파이프라인을 날려벼려 비용이 발생하는 문제를 막기 때문이다

가령 어셈블리코드가 20줄이 있다. 1줄은 4줄과 연관되어 있어서 1줄이 실행되야 4줄이 제대로 실행될 수 있다.

이 어셈블리코드를 돌리는 프로세서의 명령어 파이프라인이 10줄이라고하자. 한 번에 10개의 명령을 동시에 처리하는거다

맨처음 1번줄이 패치된다. 그 다음으로 1번줄은 디코딩되고, 2번줄이 패치된다 쭉쭉 따라가보자

근데 문제가 생긴다. 1줄과 4줄이 연관되어있기때문에 4번줄이 실행되고나서 1번줄이 실행되어야함으로 4번줄의 실행이 끝나면

파이프라인을 날려버려야한다. 즉, 비용이 발생한다.

컴파일러는 이 비용을 최소화하기 위해 기존 1줄과 4줄을 멀리 띄어놓아서 파이프라인이 stall되는것을 막는다


루프 언롤링을 다시 살펴보자. 루프 언롤링은 단순히 루프를 풀어헤친다고하지 않았나?

단순하게 1을 계속 더하는 루프를 살펴보자. for i = 0 to 10, i+=1이다.

이걸 풀어 헤치면 i+=1, i+=1 ... i+=1이 된다. 그렇다면 위에서 말한대로 stall문제때문에 비용이 비쌀까?

그건 아니다. 이정도는 명령어 파이프라인이 stall하진 않는다. 그냥 풀어헤치던 말던 좆대로해도 큰차이는 없다


그렇다면 다른 루프는 어떨까? 가령 a=[1,2,3,4,5,6,7],x=0,foreach e in a, x+= e이 있다고 해보자

위 루프와 다른 점은 배열이 들어갔다는 점이다. 이걸 풀면 x += a[0], x+=a[1], ... x+=a[6]이 될 것이다.

이건 어떨까? 이것도 사실 stall 문제는 없다. 명령어간 의존성이 그다지 크지 않기 때문이다

다만, 이 코드는 루프 언롤링했을때 대부분의 아키텍쳐에서 더 빠르게 실행될 여지가 있다

캐시라인, 캐시히트의 개념을 알고 있다면 이해가 쉬울 것이다.


루프를 풀기전 코드는 a의 iteration에 사용되는 코드와, a를 참조하는 코드 두 가지를 주목할 필요가있다

a의 iteration하는 코드와 a를 참조하는 코드 두 가지가 동시에 같은 횟수만큼 실행되기 때문에 작업이 균등하게 배분되지 않는 다는 문제가 있다

루프를 풀어헤친코드는 a를 iteration하는 코드가 없기 때문에 a를 참조하는 코드 부분만 집중할 수 있다.

이는 단순한 예제지만 조금만 확장해서 생각하면 루프 언롤링이 캐시히트율에 미치는 영향이 커지는 것을 알 수 있을 것이다.

그렇다고 무작정 풀어헤치면 안된다. 캐시라인이 캐시히트율에 영향을 미치기 때문이다.

또, 캐시라인, 캐시히트율을 고려하지 않아도 루프 본문의 크기가 크다면 명령어 바이트를

캐싱해놓는 부분도 캐시 미스가 발생하는 확률이 커지기 때문에 그러면 안된다


그러면 stall문제는 언제 발생한다는 것인가?

간단한 예를 또 들어보자. a=new int[100], a[0] = 1, for int i = 1 to 99, a[i] = a[i-1] + 1

이걸 풀어놓으면 a[1]=a[0]+1, a[2]=a[1]+1 ... a[99]=a[98]+1이 된다.

이 명령들이 명령어 파이프라인에 들어간다면 한 스텝 건너 stall이 발생한다. 왜냐하면 a[2]를 계산하는데에 a[1]의 값이 필요하고,

a[3]를 계산하는데 a[2]의 계산이 필요하고 이런식으로 연속된 체인 형식으로 참조가 발생하기 때문이다.

그러면 다음 코드를 보자. a=new int[100], b=new int[100], for int i = 1 to 99, a[i]=a[i-1]+1, b[i]=b[i-1]+1

이걸 풀어 놓으면 a[1]=a[0]+1,b[1]=b[0]+1 그다음 a[2]=a[1]+1,b[2]=b[1]+1 ... 이된다.

위 예랑 다른 점은 a에 대한 참조 바로 다음스텝에 일어나지 않는 점에 있다

즉 이전 예제는 한 스텝 건너 stall이 발생한다면 이 예제는 두 스텝 건너 stall이 발생한다. 대충 두 배 정도 성능이 좋아진것 같지 않나?

배열을 또 추가하거나 stall이 발생하지 않는 다른 연산부분으로 코드를 채워둔다면 루프 언롤링은 좋은 성능을 보일 것이다


컴파일러에 수 많은 최적화 기법 중에 딱 한 가지만 가져온 것이다.

더 많은 것을 배우고 익혀 볼 것을 생각하니 벌써부터 재밌지않나?

컴파일러 수업을 듣고 더 많은 최적화 기법들을 알아보자.