[system programming] program optimization & parallel programming

본 게시글은
서울대학교 데이터사이언스대학원 성효진 교수님의
데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를
학습을 목적으로 재구성하였습니다

---

 

저번 시간에 이어서

compile optimization에 대해서 계속 해보려고한다

 

 

타일링도 굉장히 중요한 최적화 기법 중에 하나이다

기본적으로 배열을 순차적으로 처음부터 끝까지

nesting을 하는 것이 일반적인데

타일링은 처음부터 끝까지 도는게 아니고

tile이라고 하는 작은 iteration으로 쪼갠다음에

하나하나 차근차근 또 도는 방식이다

loop을 나누는 개념이라고 생각하면 편하다

 

 

 

타일링의 에씨이다

B는 block size인데 타일의 크기이다

이러한 타일링을 하는 가장 큰 이유는 바로

cache locality 때문이다

 

만약 내가 코드를 병렬로 실행한다고 하면

내가 타일링을 했을 때 타일사이즈를 내가 조절함으로써

내 병렬 프로그램의 크기나 병렬성 정도를 조절하기가 쉬워진다

그게 아니라면 너무 작은ㅌ loop를 병렬로 실행시킬수가 있다

 

fusion, tiling, unrolling 이 3개정도가

loop에서 효과를 볼 수있는 최적화 기법이다

 

 

 

loop unswitching에 대해서 알아보자

 

loop안에서 branch가 있는 경우이다

보통 이런 경우는 최적화가 어려워져서 많이 포기한다

따라서 unswitching은 branch를 밖으로 빼내는 것을 말한다

 

condition을 밖에서 처리해도 안전한지

컴파일러가 판단한 다음 그게 된다면

loop 바깥에서 처리하도록 한다

 

 

 

loop unroll에 대한 내용이다

 

loop을 없애거나 혹은 펼치는 것을 말한다

위 예시에서는 1개의 iteration을 4개로 펼쳤다

여기서 4개로 펼쳤으니 4는 unroll factor가 되는데

몇 개의 iteration을 펼칠 것인지를 정하는 것이다

factor가 커지면 그만큼 loop을 적게 도는 것이 될 것이다

 

unroll을 하면 loop의 body가 커지는데

이걸 해주는 이유는 ILP(Instruction Level Parllelism)을

최대로 뽑아주기 위해서이다

loop의 횟수가 주니까 branch가 줄게되고

ILP를 뽑아낼 수가 있는 것이다

 

 

 

loop vectorization에 대해서 알아보자

 

이 친구도 성능에 굉장히 중요한 영향을 미치는 최적화이다

하지만 이 친구를 적용하려면

우선 하드웨어가 벡터연산이 가능하다는 것을 전제로 해야한다

 

우리가 앞에서 배웠던 SIMD parallelism을 적용해주는 것인데

이걸 적용해주려면 우리가 직접 해주거나

아니면 컴파일러가 자동으로 vectorization을 해주게하는

두 가지 방법이 있다

o3로 해서 최적화 레벨을 최대로 주거나

vectorization 옵션을 넣어주면

컴파일러가 vectorization을 해주는 것을 볼 수 있을 것이다

 

이를 위해서 우선 컴파일러는 처음에

loop에 dependency가 있는지 없는지를 확인한다

vectorization을 실행했을 때와 하지않았을 때

이게 얼마나 성능이 더 좋아지는지를 체크할 수 있다

또한 앞에서도 설명했지만

컴파일러는 반드시 이런 최적화를 진행했을 때

코드가 안전하다고 판단해야만 진행시키기 때문에

안전성도 반드시 확인한다

 

 

 

마지막으로 loop parallelization이다

 

이건 컴파일러가 거의 해주지 않는데

컴파일러가 자동으로 구현을 하기에는

너무 복잡하고 어렵기 때문이다

 

따라서 이러한 Loop parallelization을 수행하도록 하려면

사용자가 알고리즘을 정확하게 이해하고

직접 수행을 시켜주는 경우가 대부분이다

 

간혹 컴파일러가 이를 자동으로 처리해주는 경우는

대부분 loop에서만 수행해주고

loop이 아닌 곳에서 컴파일러가 자동으로 판단해서

최적화를 수행하기는 굉장히 어렵다

 

다음 챕터(?)이다

optimization blockers에 대해서 알아보자

 

이 부분은 컴파일러가 최적화를 해줄 것이라고 기대할텐데

못해주는 경우들이 있다

그런 경우가 어떤 경우들인지에 대한 내용이다

 

 

앞에서 봤던 strlen의 예시이다

 

컴파일러가 이러한 strlen을 밖으로 빼줄 수 있을까?

아마 쉽지 않을 것이다

왜냐하면 컴파일러는 최적화가 되었을 때

해당 프로그램이 변하지 않는다는 보장이 있어야 최적화를 진행하는데

함수의 경우, 특히 strlen같은 내장함수의 경우

그런 것들이 어렵다

 

컴파일러는 대부분 함수를 블랙박스로 취급하는데

그래서 함수가 들어오게 되면

최적화를 안하려고 포기하는 경우가 생긴다

이런걸 보통 inline으로 해결하는 경우가 많은데

gcc에서 -o1로 옵티마이저를 해주면

inline을 해주는 것을 볼 수 있다고 한다

 

 

 

위의 노란색 코드를 잘 살펴보자

코드를 잘 살펴보면 이전 iteration의 코드를 저장하고

이 저장한 값들을 다시 불러오고

이러한 과정을 계속해서 반복하고있다

 

그렇다면 이걸 어떻게 고칠 수 있을까

 

 

 

이 부분은 ppt에 오타가 있는데

오른쪽 초록색 박스들에서 22가 아니고 28이 나와야한다

 

아무튼 위의 노란색 코드를

A와 B에 대해서 적용시킬때의 예시를 살펴보자

 

iteration 별로 A를 한 개씩 돌면서 B에 저장하고

두 번째 정하고 세 번쨰로 저장하고 ...

이런 과정을 계속해서 반복하게 된다

 

이러한 방식으로 코드를 동작시키면

매번 update를 할 때마다 program behavior를 고려해야한다

 

 

 

하지만 사실 잘 생각해보면

update를 할 때 B에 값을 계속해서 저장해 줄 필요가 없다

 

 

 

위와 같은 코드를 컴파일러가 최적화시키지 못하는 이유는

memory aliasing 때문이다

memory aliasing은 2개의 메모리 변수가 같은 곳을 가리킬 때 발생하는데

c/c++에서 주로 발생한다

 

이를 피하게 하기 위해서 local variable을 쓰려고 할 때

컴파일러에게 알려줘야하는데

A와 B는 주소가 겹치지 않는 다는 것을 미리 알려줄 수가 있다

그럼 안전하게 컴파일러는 이를 최적화 할 수 있다

 

A와 B가 서로 aliasing을 할 수 있다는 것을 컴파일러는 가정하는데

이 가능성이 조금이라도 있다면 컴파일러는 최적화를 하지 않는다

따라서 코드를 작성할 때 aliasing이 없는 코드를 작성하면

최적화를 더 많이 진행해줄 수 있다

 

 

컴파일러가 최적화를 잘 못하게 되는 요소는 바로

control flow가 복잡할 때이다

 

컴파일러는 최적화를 수행하기 전에

우리의 코드를 시뮬레이션을 하는데

그 시뮬레이션이 완벽하게 정확할 수는 없다

runtime behavior에 대해서 컴파일러가 정확하게 예측을 할 수는 없는 것이다

 

위 예시를 한 번 잘 살펴보자

실제로 상수값으로 할 수 있는 최적화는

constant folding, constant propagation이 있다

그런데 여기서 control flow가 있으면

a의 값이 10이라는 보장이 없이 변할 수가 있게 된다

나눠지지 않는다면 무조건 a는 10이지만

control flow가 존재한다면 10임이 보장이 안된다

따라서 컴파일러는 보수적으로 a에 대한 값이

보장이 안된다고 판단해서 최적화를 실행하지 않는다

 

따라서 코드가 불확실할 수록 최적화가 덜해진다

 

 

control flow paths가 굉장히 divergent해서

예측이 매우 어려워지게 되며

컴파일러가 분석했을 때 결과가 부정확해지게 되고

아무런 최적화도 진행하지 않는다

 

 

 

따라서 결국은 컴파일러에게 최적화를 의존하기 보다는

근본적으로 최적화는 프로그래머가 하는 것이다

 

알고리즘 자체에 대한 최적화는 당연히 프로그래머가 하는 것이지만

그걸 readable하고 maintainable하게 만들어서

컴파일러가 더 잘 이해하고 최적화를 시킬 수 있게 하는 것도

프로그래머의 몫이 되는 것이다

 

함수는 modular하게 만드는 것이 좋지만

compiler friendly하게 만드는 것도 중요하다

 

그러고 성능이 정말정말 중요한 프로그래밍을 하고 있다면

loop nested에서 inner loop을 어떻게 최적화하는지에따라

성능의 차이가 많이 나게 된다

 

 

다음으로 병렬 프로그래밍을 살펴보다

 

 

우리가 지금까지의 내용은

코드를 최적화 할 때 직렬 프로그래밍에서

어떻게하면 코드 자체를 최적화할까에 대한 이슈였다

 

하지만 병렬 프로그래밍도 당연히 중요하기 때문에

아주 간략하게 본 수업에서 설명을 하신다고 하셨다

 

병렬 프로그래밍은 컴파일러가 자동으로 해주는 것이 아닌

프로그래머가 설정해주어야한다

따라서 프로그래머는 병렬 프로그래밍을 작성할 때

어떤 부분이 병렬화 가능한지를 직접 찾아서

크기를 어떤 식으로 나누어서 어떤식으로 매핑할 것인지를 정해야한다

 

 

병렬 프로그래밍의 과정이다

 

decomposition하고 나면 mapping하거나 assignt 해준다

실제로 하드웨어 스레드에 매핑하는 과정은 우리가 하는 것은 아닌다

하지만 그 전에 어떻게 매핑하고 어떻게 나뉠지는

우리가 코드 상에서 정의해야하는 문제이다

 

 

병렬 알고리즘은 이렇게 큰 3개의 주제로 나눌 수 있다

 

 

첫 번째는 주어진 하드웨어의 병렬성을 최대화 하는 것이다

두 번째는 communication을 최소화하는 것

세 번째는 병렬로 실행하는 task간의 balance를 맞추는 것이다

병렬을 실행할 때는 가장 오래 걸리는 task를 기준으로 하기 때문에

그때까지 기다려야한다

 

그런데 이 요소들은 각각 서로간의 Trade off 관계에 있다

 

 따라서 이런 것들이 가장 효율적일 수 있도록 맞춰줘야하는데

하나의 공식이 있는 것이 아니다

우리의 하드웨어와 우리의 상황에 맞도록 잘 설정해주여야한다

 

 

 

task decomposition도 여러가지 방식이 존재하는데

가장 중요한 것은 dependency 여부 파악이다

dependency가 없는 Task를 최대한 파악하고

걔네들끼리 병렬 실행을 하는 것이다

 

 

task decomposition을 사용할 수 있는 예시라고 한다

matrix-vector multiplication인데

뭐 이렇게 병렬화를 할 수 있다고 한다

 

 

 

또 다른 예시이다

 

DB에서 쿼리를 실행한다고 가정해보자

왼쪽의 쿼리에서 데이터를 table에서 찾으려고 한다

 

쿼리를 실행하게 되면 그때 그때 

조건에 만족하는 subset이 되는 테이블들이 만들어지고

또 그안에서 조건을 찾아서 또 subset을 만들고

이런식으로 쿼리가 수행되는데

이걸 순차적으로 할 수도 있지만

만약 이걸 병렬로 수행할 수 있을까?

 

이것도 task decomposition의 문제라고 한다

 

task decomposition에는

data deccomposition이라는 것이 있는데

data를 기준으로 나누는 것이다

 

다양한 data decomposition이 있는데

output data decomposition과

input data decomposition이 있다

 

output data decomposition은 말 그대로

output에 있는 각각의 data들을 decomposition 하는 것이다

matrix-vectorization의 경우

output을 보고서 output 각각의 vector element가

의존성이 없기 때문에 따로따로 계산을 할 수 있는 것이다

 

input data decomposition은

output 데이터를 보는 것이 아니고

입력 데이터를 먼저 보고 나누는 것이다

 

이게 더 general한 방식인데

왜냐면 Ouptut이 항상 독립성이 있다는 보장이 없고

output이 나올 것이라고 항상 보장된 것이 아니기 때문이다

앞의 쿼리 프로세싱의 경우 이러한 input data decomposition을 사용하고

minimum in a list, sorting 같은 것도 이러한 경우인데

최종결과를 아는 것이 아니고

divide and conquer과 같은 방식으로

input data를 기준으로 나눠서 병렬 실행하기 때문이다

 

 

쿼리의 경우 위와 같이 subtask로 바꿀 수 있다

 

한 번 수행하게 되면 중간 테이블들이 나오는데

위 왼쪽의 경우 모델과 연도를 먼저 수행한다

그럼 각각 Civic과 2001 테이블이 만들어지게된다

그 다음 병렬로 white or green에 대해서 테이블을 또 만들고

두 개의 테이블에 대해서 AND를 수행한다

 

아니면 오른쪽과 같은 방식으로 수행할 수도 있는데

이는 dependency가 있는 task이다

 

따라서 각각 이렇게 나누는 방법은 다양하게 있는데

이걸 어떻게 결정하느냐에 따라서 성능에 큰 차이가 생긴다

 

 

앞에서 잠깐 언급을 했는데

병렬 실행을 할 때는 가장 긴 task를 기준으로 결정된다

 

따라서 병렬 실행 path를 봤을 때 가장 긴 것을

critical path라고 부르는데

이게 병렬 실행 시 시간을 결정하기 때문이다

 

 

 

같은 task를 위와 같은 두 가지의 방식으로 병렬할 수 있다

 

왼쪽은 2번만 하면 되는데

오른쪽 방식으로 하면 금방 끝이 날 수도 있지만

매우 긴 path가 존재하고 저걸 다 끝내야 되는 것이다

 

위 두가지의 예시에서 최소한의 실행 시간을 얻으려면

몇 개의 프로세서가 필요할까?

 

A의 경우 처음에 4개를 병렬로 처리해야하기 때문에

4개의 프로세서가 필요하다

하지만 B의 경우는?

우리는 각 task의 길이를 잘 모른다

왜냐하면 B는 dependency를 우리가 만들어버린 셈이기 때문이다

그래서 B도 결국 4개의 프로세서가 필요하게 된다고 한다

(사실 이 부분 설명을 잘 못들었다)

 

 

domain decomposition, functional decomposition과

같은 것들도 있다

 

functional decomposition은 task based라고도 하며

하는 일이 다른 경우 나누는 것을 말한다

흔히 데이터를 나눈다고 하지 않고

task 혹은 function 기반으로 나눈다고한다

 

 

 

그렇다면 우리는 task를 어떻게 decompose를 할까?

이것도 2가지 방식이 있다

 

처음 static한 방식은

static하게 미리 task를 다 나눠놓고 수행하는 것이다

 

두 번째 dynamic하게 바꾸는 경우는

실행을 해놓고 그때 그때 또 뭔가를 바꿔주는 것을 말한다

당연히 훨씬 더 유연하겠지만

추가되는 오버헤드들이 존재한다

 

 

 

 

task decomposition을 할 때

task의 크기가 매우 중요하다

 

task를 크게 만들면 task의 수도 줄고

communication 횟수도 줄지만

너무 커지면 실행시간을 예측하기가 어렵고

load imbalance가 생길 때 예측이 힘들어진다

 

그렇다고 작게 task를 만들면 자주자주 Parallel을 하고

스케줄링을 자주 한다는 뜻인데

load balance는 좋아지지만 communication이 많이 발생한다

그런데 이렇게 communication이 많아지면

사실 병렬을 해서 얻는 의미가 많이 없어진다

 

 

아무튼 그렇기 때문에

task를 나눌 때 task의 크기의 중간 지점을 잘 맞춰줘야한다

 

그리고 병렬을 했을 때 추가되는 overhead들,

communication, idling, 그리고 추가되는 이런 코드들에 대해서도

잘 고려를 해줘야한다

---

 

병렬화에 대한 남은 내용은 다음시간에 계속..-!