[system programming] parallel programming

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

---

저번시간에 이어서 남은 병렬 프로그래밍 부분을

마무리 해보려고 한다

 

병렬 실행은 잘못 수행하면 더 많은 오버헤드가 발생해서

수행 시간이 더 오래 걸릴 수가 있다

이러한 부분은 실제로 연구가 많이 진행되고 있는 부분이다

 

위 ppt에서 T0이 병렬 실행을 해서 생길 수밖에 없는 오버헤드 값인데

load imbalance, communication, excess work가 원인이 된다

 

mapping은 static mapping과 dynamic mapping으로 구분 가능하다

 

task queue에 있는 데이터를 스케줄 하는 시점에

어디에 mapping할지 이런 것들을 동적으로 결정할 수가 있는데

이렇게 되면 유연하긴 하지만

task queue를 또 따로 관리해야하기 때문에

overhead가 당연히 커진다

 

하지만 load imbalance나 결정적인 병렬성은

더 좋아질 수도 있다

 

일반적으로 많이 수행하는 것은 row-wise distribution이다

column-wise로 할 수도 있는데

이건 하드웨어의 특성에 따라 뭘 선택할지가 달라진다

 

 

위는 tiling을 해서 tile 단위로 나누는 방식이다

tile 부분은 sequential하게 실행을 하는 대신에

바깥 loop들은 병렬로 실행이 가능하다

 

 

 

가장 좋은 구조는 타일링된 것의 특정 타일만을

계산하게 만드는 것이라고 한다

 

A에서도 타일에 해당하는 row만 읽고

B에서도 타일에 해당하는 column만 읽게 만들어서

수행하게하는.. 아무튼 그런 구조라고 한다

 

이건 데이터가 있어서 정형적인 데이터로 나누는 경우이다

 

그렇다면 이것은 data가 아닌 task를 기준으로 나누는 경우이다

 

이건 NP-complete 문제이고 풀기가 어렵다

그래서 많은 휴리스틱들이 존재한다

 

binary tree같은게 있다면 leaf는 병렬로 실행하는데

올라갈수록 다른 parent node를

이전에 수행했던 프로세서가 실행하게하는 방식인데

사실 이건 매우 전형적인 방식이고

실제로는 이렇게 깔끔하게 딱 풀리지가 않는다

 

 

이건 옆으로 가면서 매핑을 수행하는 방식이라고 한다

T뒤에 번호가 row의 넘버인데

넘버가 가까울수록 row가 인접해있다

 

가까이에 인접한 row끼리는 같은 프로세서에서 연산을 하면

지역성이 높아져서 성능이 좋아진다

따라서 인접한 row들은 같은 core에 매핑을 하는 것이 좋다

이러한 스케줄링 방식을 affinity라고 하는데

내가 access할 데이터를 가까이에 두는 것을 말하고

affinity scheduling이라고 한다

 

 

 

병렬 프로그래밍에서 결국 중요한 것은

critical path length를 줄이는 것이다

왜냐하면 결국 이게 프로그램의 실행 시간을

좌지우지하기 때문이다

 

load imbalance 문제도 중요한 문제인데

T13을 수행하는 경우 다른 프로세서들은

다 기다리게 되기 때문이다

 

 

 

그래서 task를 이렇게 작게 해주면

load imbalance를 줄일 수가 있다

 

하지만 너무 작아지면 오버헤드가 높아진다

 

 

이건 실행할 시점의 시스템의 상태를 보고

시스템을 스케줄하는 방식이다

이렇게 하면 load imbalance를 굉장히 줄일 수 있다

 

 

이전 시간에 봤던 두 가지 종류의 스케줄 방식이다

 

왼쪽의 경우 처음에 4개를 병렬

그 다음 2개를 병렬 수행

하고 마지막으로 최종 한개를 병렬 수행한다

 

하지만 오른쪽의 경우 병렬성에

dependency가 생겨버린 경우이고

오른쪽은 왼쪽에 비해 load balancing이

덜 잘되어있다

 

 

 

오버헤드를 줄이는 방법에 대한 얘기이다

첫 번째는 최대한 병렬화를 시키는 것

가능하다면 critical path를 줄이는 것인데

첫번째와 세번째는 conflict 된다

 

 

synchoronization을 하는 것 자체도 오버헤드이다

왜냐면 기다리는 시간 자체가 늘어나기 때문이다

이 synchoronization이 높아지면 병렬성이 떨어지기 때문에

최대한 분산된 형태를 사용하는 것이 좋다

 

 

data sharing method에는 2가지가 있는데

첫 번째 message passing model은 프로그래머가 컨트롤 하는 방식이다

 

우리가 익숙한 것은 스레드들이 하는

shared memory model 방식인데

우리가 이전 수업 내용에서 배웠듯이

thread들은 address space를 한개만 갖고있다

따라서 이 스레드들은 실행은 따로따로 하는데 주소공간은 같아서

이걸 따로 동기화해주는 것이 있었다

 

 

communication과 synchronization 방식이다

그냥 위에 이러한 방식들이 있는데

어떤게 있다 정도로 알아만 두라고 하셨다

 

collective의 경우는

broadcast, reduction, scatter and gather이 있는데

scatter은 큰 데이터가 있으면 그걸 파티션해서

일부를 각각의 스레드들에게 나누어주는 것이고

gather는 데이터를 하나로 모아서

하나의 큰 데이터로 다시 합치는 것이다

 

point to point는

producer, consumer, point가 정해져있다

lock이 보통 이런식으로 수행이 되는데

lock을 가지면 이전에 lock을 가졌던 스레드가

다음에 들어온 스레드에게 넘겨주게 된다

그럼 lock이 되었던 lock은 producer가 되어서

그 다음에 lock을 가져가는 consumer thread게 넘겨주게 되는 것이다

 

 

 

병렬성을 갖고 있다고 한다면

전형적으로 이런 구조를 갖고있다고 생각하면 된다

 

물론 현실에서는 훨씬 더 복잡하겠지만

간소화해서 이런식으로 진행된다고 이해하면 편할 것 같다

 

베리어와 베리어 간을 하나의 phase라고 부른다

 

한 종류의 연산이 끝나면

다같이 기다렸다가 다음 연산(phase)으로 넘어가는 방식인데

보통 이렇게 많이 구성이 된다

 

 

베리어가 프로그램 Phase를 만든다

그래서 베리어 싱크로나이제이션이 필요하다고 한다..

 

 

 

베리어와 베리어 사이들에 있는 것들을

아토믹이라고 한다고 한다

 

 

직렬 프로그램을 병렬화하려고 할 때

데이터를 읽고 쓰는 것을 atomic하게 하지 않으면

중간에 간격이 발생하는데 이게 좋지 않다고 한다

따라서 이걸 atomic하게 하나의 덩어리처럼 보이게 해야한다

 

 

 

communication하는 과정에서 overhead를 살펴보자

 

만약 내가 병렬화를 하려고 스레드를 만들었는데

그냥 한 스레드에 전부다 task들을 집어넣을 수가 있다

이러한 경우에는 근데 그냥 직렬 실행 하는 것보다

오버헤드 때문에 더 느려진다

 

 

 

위 상황은 lock이 한 개 밖에 없어서

네 개의 코어에서 다같이 한 개의 lock을 기다려야하는 상황이다

 

그럼 순서대로 lock을 가져갈텐데 네 개가 동시에 락을 가져가려하면

오래 기다릴 수 밖에 없어진다

 

그래서 커뮤니케이션 오버헤드는 기다리는 시간 + 데이터 이동 시간이고

싱크로나이제이션 시간은 데이터를 쓰거나 읽는 시간이 없기 때문에

그냥 기다리는 시간을 말한다

 

 

 

위 ppt에서는 reduction을 수행한다

reduction을 수행하면

reduction time + data communication time 이렇게 걸리는데

중간 결과를 저장해야해서 메모리는 소요를 더 많이 하지만

실행시간은 이게 더 빠르기 때문에

이런 형태로 많이 진행한다고 한다

 

 

 

실제로 communication overhead가 많다

왜냐하면 스레드가 많아져도 메모리나 그런 것들이

같이 빨리지지는 않기 때문에 오버헤드가 많아질 수 밖에 없다

 

따라서 이런 커뮤니케이션 오버헤드를 줄이는 방법이 몇 가지가 있는데

첫 번째는 데이터 재사용이다

우리의 연산 자체가 그걸 계속 재사용할 수 있도록 프로그램을 작성하는 것이고

두 번째는 데이터를 주고 받는 양을 줄이는 것

그 다음은 데이터를 주고받는 횟수를 줄이는 것

마지막은 무조건 기다리는게 아닌

기다리는 것과 연산을 오버랩할 수 있는 알고리즘들을 사용하는 것이다

 

흔히 사용하는 병렬 알고리즘 모델들이다

 

이러한 것들만 사용할 수는 없지만

이것들을 조합해서 사용이 가능하다

 

흔히 말하는게 data parallel model이 있고

task graph model은

dependency 기반으로 나누는 것을 말한다

 

master slave model은

마스터 스레드가 있고 마스터 스레드가 계속

slave 스레드를 만드는 것을 말한다

slave = worker이고

스레드들을 만들고 일을 만들어주고 취합하고

이 것을 계속해서 반복하는 방식이다

마스터가 계속해서 컨트롤을 하는데

task queue도 관리하고 data parallel하게 분배가 가능하다

 

pipeline model은 계속 instruction이 들어오면

다음 스레드에게 흘려보내는 것을 말한다

데이터가 계속 공급이 되는 과정에서

각각의 스레드가 역할이 있고

자기 역할이 끝나면 연산 결과를 다음 스테이지에 해당하는

스레드에게 넘겨준다

이를 위해 중간중간에 큐가 존재하고

굉장히 많이 사용하는 방식이다

특히 데이터 프로세싱을 할 때 특정 순서가 있어서

이걸 지켜야하는데 데이터가 많은 경우에 많이 사용한다

 

hybrid model은 제일 많이 보는 경우이고

쉽게 말해서 다 합쳐진 것을 말한다

 

 

 

병렬화의 성능 측정 방식이다

 

우리가 병렬화를 실행하면 실제로

성능이 얼마나 좋은지 측정할 수 있어야 한다

 

위는 그와 관련한 measure들이다

 

efficiency가 1일때 보통 병렬하면 2배, 3배로 딱딱 늘어나야겠지만

보통 현실적으로 우리의 코드는 efficiency가 1보다 낮다

따라서 이걸 얼마나 1에 가깝게 만드느냐가

병렬화를 할 때 고민을 해야하는 부분이다

 

 

Amdahl's Law라는 것이 있다

f/k * T 이 부분에 의해서 실행시간이 바뀐다고 한다

 

f가 병렬로 실행이 가능한 부분이고

나머지 부분은 병렬이 안돼서 직렬로 해야겠다고

판단한 부분이라고 한다

 

결국 k가 커지면 커질수록

저 공식을 지배하는 것은 1-f의 값이 된다

따라서 1-f를 최소화하는 것이 우리의 목표가 되는데

이렇게 해야 결국 S가 커지기 때문이다

 

 

f에 따른 S를 계산한 것을 그린 그래프이다

 

 

또 f를 키우는 것보다 더 중요한 것이 K를 키우는 것이다

병렬화가 가능한 코어를 다 쓸만큼 일이 많냐는 것인데

만약에 코어가 64개라고 했을 때 일을 64개로 나눌 수 있냐는 것이다

사실 그것보다 작으면 병렬화를 할 필요가 없어지는 것이고

64보다 커야지 64개로 병렬화를 했을 때 의미가 생기는 것이다

따라서 K를 키울 수 있는 알고리즘을 찾아야한다

 

scalability에 대해서 알아보자

 

strong scaling이라고 하는 것은

문제의 크기를 고정하고 p의 개수만 늘리는 것을 말한다

 

weak scaling은 데이터를 같이 늘려주는 것을 말하는데

problem size per processor..일때 어떻게 하냐고?
(사실 이부분 설명을 잘 ㅎ..못들었다)

 

흔히 scalable하다고 말할 때는 efficiency가 constant하게

유지될 때를 말한다

이게 유지가 잘 되면 scalable하다고 한다

 

 

병렬화 기법에 대한 설명이다

 

 

이건 뭐 병렬화를 설계할 때

기억해두면 좋은 말들이라고 한다

 

결국 병렬 프로그래밍을 할 때 가장 중요한 것은

어디를 병렬할 것인지 찾는 것인데

이를 hot spot을 찾는 것이라고 한다

보통 반복문의 경우가 많다고 한다

 

그리고 실제로 우리가 기대하는 것보다

성능이 안나오는 경우에는 병목이 있다는 것인데

그 병목이 어디인지를 찾아야한다

 

아까 말했듯이 dependency도 줄이고..

path길이도 줄이고..

data dependency도 줄이면 좋다

 

 

동기화와 로드 임밸런스의 문제이다

distributed version 이런 연산을 사용하면 좋다고 한다

lock-free 이런것도 있는데 항상 쓸 수 있는 것이 아니라서

그냥 이런게 있다 정도로만 알아도 좋다고 한다

 

coarse-grained과 같은 것들은 피하고

dependency가 많이 걸려있는 job들은

먼저 실행하는 것이 좋다고 한다

 

 

마지막으로 communication에서의 테크닉이다

 

우선 locality를 많이 활용하는 것이 좋고

overlap을 시키라고 한다

 

stale한 데이터를 읽어오는 방식으로

우리 알고리즘을 실행한다면

커뮤니케이션 시간을 줄일 수가 있다고 한다