컴퓨팅브릿지일반병렬프로그래밍 김정한
목표 병렬프로그래밍을하기위해필요한사전지식을 전달하고, OpenMP와 MPI의개념및사용법을소개하여간단한병렬프로그램을직접작성할수있게한다.
INDEX 1. 병렬프로그래밍개요 2. OpenMP 사용법 3. MPI 사용법
01. 병렬프로그래밍개요 병렬프로그래밍과관련된개념을정리하고병렬프로그래밍모델, 성능측정, 그리고병렬프로그램의작성과정에대해알아본다.
병렬처리 (1/3) 병렬처리란, 순차적으로진행되는계산영역을 여러개로나누어각각을여러프로세서에서 동시에수행되도록하는것
병렬처리 (2/3) 순차실행 병렬실행 Inputs Outputs
병렬처리 (3/3) 주된목적 : 더욱큰문제를더욱빨리처리하는것 프로그램의 wall-clock time 감소 해결할수있는문제의크기증가 병렬컴퓨팅계산자원 여러개의프로세서 (CPU) 를가지는단일컴퓨터 네트워크로연결된다수의컴퓨터
왜병렬인가? 고성능단일프로세서시스템개발의제한 전송속도의한계 ( 구리선 : 9 cm/nanosec) 소형화의한계 경제적제한 보다빠른네트워크, 분산시스템, 다중프로세서시스템 아키텍처의등장 병렬컴퓨팅환경 상대적으로값싼프로세서를여러개묶어동시에사용함 으로써원하는성능이득기대
프로그램과프로세스 프로세스는보조기억장치에하나의파일로서저장되어있던실행가능한프로그램이로딩되어운영체제 ( 커널 ) 의실행제어상태에놓인것 프로그램 : 보조기억장치에저장 프로세스 : 컴퓨터시스템에의하여실행중인프로그램 태스크 = 프로세스
프로세스 프로그램실행을위한자원할당의단위가되고, 한프로그램에서여러개실행가능 다중프로세스를지원하는단일프로세서시스템 자원할당의낭비, 문맥교환으로인한부하발생 문맥교환 어떤순간한프로세서에서실행중인프로세스는항상하나 현재프로세스상태저장 다른프로세스상태적재 분산메모리병렬프로그래밍모델의작업할당기준
스레드프로세스에서실행의개념만을분리한것 프로세스 = 실행단위 ( 스레드 ) + 실행환경 ( 공유자원 ) 하나의프로세스에여러개존재가능 같은프로세스에속한다른스레드와실행환경을공유 다중스레드를지원하는단일프로세서시스템 다중프로세스보다효율적인자원할당 다중프로세스보다효율적인문맥교환 공유메모리병렬프로그래밍모델의작업할당기준
프로세스와스레드 하나의스레드를갖는 3 개의프로세스 3 개의스레드를갖는하나의프로세스 스레드 프로세스
병렬성유형데이터병렬성 (Data Parallelism) 도메인분해 (Domain Decomposition) 각태스크는서로다른데이터를가지고동일한일련의계산을수행 태스크병렬성 (Task Parallelism) 기능적분해 (Functional Decomposition) 각태스크는같거나또는다른데이터를가지고서로다른계산을수행
데이터병렬성 (1/3) 데이터병렬성 : 도메인분해 Problem Data Set Task 1 Task 2 Task 3 Task 4
데이터병렬성 (2/3) 코드예 ) : 행렬의곱셈 (OpenMP) Serial Code Parallel Code DO K=1,N DO J=1,N DO I=1,N C(I,J) = C(I,J) + (A(I,K)*B(K,J)) END DO END DO END DO!$OMP PARALLEL DO DO K=1,N DO J=1,N DO I=1,N C(I,J) = C(I,J) + A(I,K)*B(K,J) END DO END DO END DO!$OMP END PARALLEL DO
데이터병렬성 (3/3) 데이터분해 ( 프로세서 4 개 :K=1,20 일때 ) Process Iterations ti of K Data Elements Proc0 K = 1:5 Proc1 K = 6:10 Proc2 K = 11:15 Proc3 K = 16:20 A(I,1:5) B(1:5,J) A(I,6:10) B(6:10,J) A(I,11:15) 15) B(11:15,J) A(I,16:20) B(16:20,J)
태스크병렬성 (1/3) 태스크병렬성 : 기능적분해 Problem Instruction Set Task 1 Task 2 Task 3 Task 4
태스크병렬성 (2/3) 코드예 ) : (OpenMP) Serial Code PROGRAM MAIN CALL interpolate() CALL compute_stats() CALL gen_random_params() END Parallel Code PROGRAM MAIN!$OMP PARALLEL!$OMP SECTIONS CALL interpolate()!$omp SECTION CALL compute_stats()!$omp SECTION CALL gen_random_params()!$omp END SECTIONS!$OMP END PARALLEL END
태스크병렬성 (3/3) 태스크분해 (3 개의프로세서에서동시수행 ) Process Code Proc0 Proc1 Proc2 CALL interpolate() CALL compute_stats() CALL gen_random_params() _p
병렬아키텍처 (1/2) Processor Organizations Single Instruction, Single Data Stream (SISD) Single Instruction, Multiple Data Stream (SIMD) Multiple Instruction, Single Data Stream (MISD) Multiple Instruction, Multiple Data Stream (MIMD) Uniprocessor Vector Array Shared memory Distributed memory Processor Processor (tightly coupled) (loosely coupled) Clusters Symmetric multiprocessor (SMP) Non-uniform Memory Access (NUMA)
병렬아키텍처 (2/2) 최근의고성능시스템 : 분산 - 공유메모리지원 소프트웨어적 DSM (Distributed Shared Memory) 구현 공유메모리시스템에서메시지패싱지원 분산메모리시스템에서변수공유지원 하드웨어적 DSM 구현 : 분산 - 공유메모리아키텍처 분산메모리시스템의각노드를공유메모리시스템으로구성 NUMA : 사용자들에게하나의공유메모리아키텍처로보여짐 ex) Superdome(HP), Origin 3000(SGI) SMP 클러스터 : SMP로구성된분산시스템으로보여짐 ex) SP(IBM), Beowulf Clusters
병렬프로그래밍모델 공유메모리병렬프로그래밍모델 공유메모리아키텍처에적합 다중스레드프로그램 OpenMP, Pthreads 메시지패싱병렬프로그래밍모델 분산메모리아키텍처에적합 MPI, PVM 하이브리드병렬프로그래밍모델 분산- 공유메모리아키텍처 OpenMP + MPI
공유메모리병렬프로그래밍모델 Single thread time S1 tim me S1 fork Multi-thread Thread P1 P1 P2 P3 P4 P2 P3 S2 join Shared address space P4 S2 Process Process
메시지패싱병렬프로그래밍모델 Serial Message-passing tim me S1 tim me S1 S1 S1 S1 P1 P1 P2 P3 P4 P2 S2 S2 S2 S2 P3 Process 0 Process 1 Process 2 Process 3 P4 Node 1 Node 2 Node 3 Node 4 S2 Data transmission over the interconnect Process
하이브리드병렬프로그래밍모델 Message-passing time S1 fork Thread time S1 fork Thread P1 P2 P3 P4 S2 S2 join Shared address S2 S2 join Shared address Process 0 Node 1 Process 1 Node 2
DSM 시스템의메시지패싱 tim me S1 S1 S1 S1 P1 P2 P3 P4 Message-passing S2 S2 S2 S2 S2 S2 S2 Process 0 Process 1 Process 2 Process 3 Node 1 Node 2
SPMD와 MPMD (1/4) SPMD(Single Program Multiple Data) 하나의프로그램이여러프로세스에서동시에수행됨 어떤순간프로세스들은같은프로그램내의명령어들을수행하며그명령어들은같을수도다를수도있음 MPMD (Multiple Program Multiple Data) 한 MPMD 응용프로그램은여러개의실행프로그램으로구성 응용프로그램이병렬로실행될때각프로세스는다른프로세스와같거나다른프로그램을실행할수있음
SPMD 와 MPMD (2/4) SPMD a.out Node 1 Node 2 Node 3
SPMD 와 MPMD (3/4) MPMD : Master/Worker (Self-Scheduling) a.out b.out Node 1 Node 2 Node 3
SPMD 와 MPMD (4/4) MPMD : Coupled Analysis a.out b.out c.out Node 1 Node 2 Node 3
성능측정 성능에영향을주는요인들 병렬프로그램작성순서
프로그램실행시간측정 (1/2) Time 사용방법 (bash, ksh) : $time [executable] $ time mpirun np 4 machinefile machines./exmpi.x real 0m3.59s user 0m3.16s sys 0m0.04s real = wall-clock time User = 프로그램자신과호출된라이브러리실행에사용된 CPU 시간 Sys = 프로그램에의해시스템호출에사용된 CPU 시간 user + sys = CPU time
프로그램실행시간측정 (2/2) 사용방법 (csh) : $time [executable] $ time testprog 1.150u 0.020s 0:01.76 66.4% 15+3981k 24+10io 0pf+0w 1 2 3 4 5 6 7 8 1 user CPU time (1.15초) 2 system CPU time (0.02초) 3 real time (0분 1.76 초 ) 4 real time에서 CPU time이차지하는정도 (66.4%) 5 메모리사용 : Shared (15Kbytes) + Unshared (3981Kbytes) 6 입력 (24 블록 ) + 출력 (10 블록 ) 7no page faults 8no swaps
성능측정 병렬화를통해얻어진성능이득의정량적분석 성능측정 성능향상도 효율 Cost
성능향상도 (1/7) 성능향상도 (Speed-up) : S(n) 순차프로그램의실행시간 S(n) = = t s 병렬프로그램의실행시간 (n 개프로세서 ) t p 순차프로그램에대한병렬프로그램의성능이득정도 실행시간 = Wall-clock time 실행시간이 100 초가걸리는순차프로그램을병렬화하여 10 개의프로세서로 50초만에실행되었다면, 100 S(10) = = 2 50
성능향상도 (2/7) 이상 (Ideal) 성능향상도 : Amdahl s Law f : 코드의순차부분 (0 f 1) t p = ft s + (1-f)t s /n 순차부분실행시간 병렬부분실행시간
성능향상도 (3/7) fts Serial section tst ( 1 f )t S Parallelizable sections 1 2 n-1 n 1 2 n processes n-1 n tp ( 1 f ) t S/ n
성능향상도 (4/7) t s S(n) = t = p t s ft s + (1-f)t s /n S(n) = 1 f + (1-f)/n 최대성능향상도 ( n ) S(n) = 1 f 프로세서의개수를증가하면, 순차부분크기의역수에수렴
성능향상도 (5/7) f = 0.2, n = 4 Serial 20 80 Parallel l 20 20 process 1 process 2 process 3 process 4 cannot be parallelized can be parallelized S(4) = = 2.5 1 0.2 + (1-0.2)/4
성능향상도 (6/7) 프로세서개수대성능향상도 24 20 f=0 Speed d-up 16 12 8 f=0.05 f=0.1 4 f=0.2 0 0 4 8 12 16 20 24
성능향상도 (7/7) 순차부분대성능향상도 16 14 Speed d-up 12 10 8 6 4 2 0 n=256 n=16 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
효율효율 (Efficiency) : E(n) t s S(n) E(n) = = [ⅹ100(%)] t p ⅹn n 프로세서개수에따른병렬프로그램의성능효율을나타냄 10개의프로세서로 2배의성능향상 : S(10) = 2 E(10) = 20 % 100개의프로세서로 10배의성능향상 : S(100) = 10 E(100) = 10 %
Cost Cost Cost = 실행시간 ⅹ 프로세서 t s n 개수 S(n) t s E(n) 순차프로그램 : Cost = t s 병렬프로그램 :Cost= t p ⅹn= = 예 ) 10 개의프로세서로 2 배, 100 개의프로세서로 10 배의성능향상 t s t p n S(n) E(n) Cost 100 50 10 2 02 0.2 500 100 10 100 10 0.1 1000
실질적성능향상에고려할사항 실제성능향상도 : 통신부하, 로드밸런싱문제 Serial 20 80 parallel 20 20 process 1 process 2 process 3 process 4 cannot be parallelized can be parallelized communication overhead Load unbalance
성능증가를위한방안들 1. 프로그램에서병렬화가능한부분 (Coverage) 증가 알고리즘개선 2. 작업부하의균등분배 : 로드밸런싱 3. 통신에소비하는시간 ( 통신부하 ) 감소
성능에영향을주는요인들 Coverage : Amdahl s Law 로드밸런싱 동기화 통신부하 세분성 입출력
로드밸런싱 모든프로세스들의작업시간이가능한균등하도록작업을분배하여작업대기시간을최소화하는것 데이터분배방식 (Block, Cyclic, Block-Cyclic) 선택에주의 이기종시스템을연결시킨경우, 매우중요함 동적작업할당을통해얻을수도있음 task0 task1 task2 WORK WAIT task3 time
동기화 병렬태스크의상태나정보등을동일하게설정하기위한조정작업 대표적병렬부하 : 성능에악영향 장벽, 잠금, 세마포어 (semaphore), 동기통신연산등이용 병렬부하 (Parallel Overhead) 병렬태스크의시작, 종료, 조정으로인한부하 시작 : 태스크식별, 프로세서지정, 태스크로드, 데이터로드등 종료 : 결과의취합과전송, 운영체제자원의반납등 조정 : 동기화, 통신등
통신부하 (1/4) 데이터통신에의해발생하는부하 네트워크고유의지연시간과대역폭존재 메시지패싱에서중요 통신부하에영향을주는요인들 동기통신? 비동기통신? 블록킹? 논블록킹? 점대점통신? 집합통신? 데이터전송횟수, 전송하는데이터의크기
통신부하 (2/4) 통신시간 = 지연시간 + 메시지크기 대역폭 지연시간 : 메시지의첫비트가전송되는데걸리는시간 송신지연 + 수신지연 + 전달지연 대역폭 : 단위시간당통신가능한데이터의양 (MB/sec) 메시지크기유효대역폭 = = 통신시간 대역폭 1+ 지연시간 ⅹ 대역폭 / 메시지크기
통신부하 (3/4) Communication Time Commu unication n time 1/slope = Bandwidth Latency message size
통신부하 (4/4) effectiv ve bandw width (M MB/sec) 1000 100 10 1 0.1 0.01 Effective Bandwidth network bandwidth latency = 22 μs bandwidth = 133 MB/sec 1 10 100 1000 10000 100000 1000000 message size(bytes)
세분성 (1/2) 병렬프로그램내의통신시간에대한계산시간의비 Fine-grained 병렬성 통신또는동기화사이의계산작업이상대적으로적음 로드밸런싱에유리 Coarse-grained 병렬성 통신또는동기화사이의계산작업이상대적으로많음 로드밸런싱에불리 일반적으로 Coarse-grained 병렬성이성능면에서유리 계산시간 < 통신또는동기화시간 알고리즘과하드웨어환경에따라다를수있음
세분성 (2/2) tim me tim me Communication Computation Communication Computation (a) Fine-grained (b) Coarse-grained
입출력 일반적으로병렬성을방해함 쓰기 : 동일파일공간을이용할경우겹쳐쓰기문제 읽기 : 다중읽기요청을처리하는파일서버의성능문제 네트워크를경유 (NFS, non-local) 하는입출력의병목현상 입출력을가능하면줄일것 I/O 수행을특정순차영역으로제한해사용 지역적인파일공간에서 I/O 수행 병렬파일시스템의개발 (GPFS, PVFS, PPFS ) 병렬 I/O 프로그래밍인터페이스개발 (MPI-2 : MPI I/O)
확장성 (1/2) 확장된환경에대한성능이득을누릴수있는능력 하드웨어적확장성 알고리즘적확장성 확장성에영향을미치는주요하드웨어적요인 CPU-메모리버스대역폭 네트워크대역폭 메모리용량 프로세서클럭속도
확장성 (2/2) Speedup Number of Workers
의존성과교착 데이터의존성 : 프로그램의실행순서가실행결과에영향을미치는것 DO k = 1, 100 F(k + 2) = F(k +1) + F(k) ENDDO 교착 : 둘이상의프로세스들이서로상대방의이벤트발생을기다리는상태 Process 1 Process 2 X = 4 SOURCE = TASK2 RECEIVE (SOURCE,Y) DEST = TASK2 SEND (DEST,X) Z = X + Y Y = 8 SOURCE = TASK1 RECEIVE (SOURCE,X) DEST = TASK1 SEND (DEST,Y) Z = X + Y
의존성 Serial F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(n) 1 2 3 4 5 6 7 n DO k = 1, 100 F(k + 2) = F(k +1) + F(k) ENDDO F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(n) 1 2 3 5 8 13 21 Parallel F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(n) 1 2 3 5(4) 7 11 18
병렬프로그램작성순서 1 순차코드작성, 분석 ( 프로파일링 ), 최적화 hotspot, 병목지점, 데이터의존성등을확인 데이터병렬성 / 태스크병렬성? 2 병렬코드개발 MPI/OpenMP/? 태스크할당과제어, 통신, 동기화코드추가 3 컴파일, 실행, 디버깅 4 병렬코드최적화 성능측정과분석을통한성능개선
디버깅과성능분석디버깅 코드작성시모듈화접근필요 통신, 동기화, 데이터의존성, 교착등에주의 디버거 : TotalView 성능측정과분석 timer 함수사용 프로파일러 : prof, gprof, pgprof, TAU
병렬프로그램작성예 (1/4) PI 계산알고리즘 1. 정사각형에원을내접시킴 2. 정사각형내에서무작위로점추출 3. 추출된점들중원안에있는점의개수결정 4. PI = 4 ⅹ 원안의점개수 전체점의개수
병렬프로그램작성예 (2/4) 순차코드작성 (Pseudo) tpoints = 10000 in_circle = 0 do j = 1,tpoints x = rand() y = rand() if (x, y) inside circle then in_circle = in_circle + 1 end do PI = 4.0*in_circle/tpoints 거의모든계산이루프에서실행 루프의반복을여러프로세스로나누어동시수행 각프로세스는담당한루프반복만을실행 다른프로세스의계산에대한정보불필요 의존성없음 SPMD 모델사용, 마스터프로세스가최종적으로계산결과를취합해야함
병렬프로그램작성예 (3/4) 병렬코드작성 (Pseudo) tpoints = 10000 in_circle = 0 p = number of process num = tpoints/p find out if I am MASTER or WORKER do j = 1,num x = rand() y = rand() if (x, y) inside circle then in_circle = in_circle + 1 end do if I am MASTER receive from WORKERS their in_circle compute PI (use MASTER and WORKER calculations) else if I am WORKER send to MASTER in_circle end if 기울임글꼴 ( 붉은색 ) 부분이병렬화를위해첨가된부분
병렬프로그램작성예 (4/4) Pi 계산알고리즘 : 적분을통한 Pi 계산 1 4 1 x 0 2 dx dx x tan 2 sec d f ( x 1 ) f ( x 2 ) 4 sec 2 1 tan 4 2 0 2 4 2 1 4 cos 0 2 4 4 d 0 cos d d 1 n... f ( x n ) x 2 (2 0.5) 1 x1 (1 0.5) n 2 1 n 1 x n ( n 0.5) n
Example : PI 계산 (1/4) 순차코드 : Fortran program main implicit none implicit none integer*8,parameter :: num_step = 500000000 integer*8 :: i real(kind=8) :: sum,step,pi,x real(kind=8) :: stime,etime,rtc ( ) step = (1.0d0/dble(num_step)) sum = 0.0d0 write(*,400) stime=rtc()!starting time do i=1,num_step x = (dble(i)-0.5d0)*step sum = sum + 4.d0/(1.d0+x*x)! F(x) enddo ti t ()! di ti etime=rtc()!ending time pi = step * sum write(*,100) pi,dabs(dacos(-1.0d0)-pi) write(*,300) etime-stime write(* 400) write(,400) 100 format(' PI = ', F17.15,' (Error =',E11.5,')') 300 format(' Elapsed Time = ',F8.3,' [sec] ') 400 format('-------------------------------------------') stop end program
Example : PI 계산 (3/4) 순차코드 : C #include <stdio.h> #include <math.h> #include <time.h> int main(){ const long num_step = 500000000; long i; double sum, step, pi, x; time_t st, et; step = (1.0/(double)num_step); sum = 0.0; 0; time(&st); printf( --------------------------------------------\n"); for(i=1;i<=num_step;i++){ x = ((double)i-0.5)*step; sum = sum + 4.0/(1.0 + x*x); } time(&et); pi = step * sum; printf("pi = %.15f (Error = %e)\n", pi, fabs(acos(-1.0)-pi)); printf("elapsed Time = %.3f [sec]\n", difftime(et,st)); printf("-------------------------------------------\n"); ") }