본 게시글은
서울대학교 데이터사이언스대학원 성효진 교수님의
데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를
학습을 목적으로 재구성하였습니다
저번시간에 이어서 남은 병렬 프로그래밍 부분을
마무리 해보려고 한다
병렬 실행은 잘못 수행하면 더 많은 오버헤드가 발생해서
수행 시간이 더 오래 걸릴 수가 있다
이러한 부분은 실제로 연구가 많이 진행되고 있는 부분이다
위 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한 데이터를 읽어오는 방식으로
우리 알고리즘을 실행한다면
커뮤니케이션 시간을 줄일 수가 있다고 한다
'강의 > system programming' 카테고리의 다른 글
[system programming] Debugging (3) | 2025.06.02 |
---|---|
[system programming] program optimization & parallel programming (0) | 2025.06.01 |
[system programming] program optimization (compiler와 최적화 기법) (3) | 2025.05.11 |
[system programming] 가상 메모리(virtual memory) 2편 (0) | 2025.05.03 |
[system programming] 가상 메모리(virtual memory) 1편 (1) | 2025.04.30 |