Parallel Programming & MPI 박필성 수원대학교 IT 대학컴퓨터학과

Parallel Programming & MPI 박필성 수원대학교 IT 대학컴퓨터학과

목차 Why Parallel? Parallel Computers Parallel Processing Parallel Programming MPI의기본개념 MPI 표준 MPI 프로그램및실행 Related Topics & Questions

Why Parallel? (1) Why parallel computing? 전통적인 compute-intensive applications 기상예보, 전산유체역학, 화학, 천문학, 다양한공학문제 새로운 data-intensive applications video servers, data mining 미래의 high performance applications VR, 협업환경, CAD Save time and/or money. Solve large problems. Provide concurrency. Use of non-local resources Limits to serial computing http://en.wikipedia.org/wiki/parallel_computer http://www.top500.org/

Why Parallel? (2) Atmosphere, Earth, Environment Physics - applied, nuclear, particle, condensed matter, high pressure, fusion, photonics Bioscience, Biotechnology, Genetics Chemistry, Molecular Sciences Geology, Seismology Mechanical Engineering - from prosthetics to spacecraft Electrical Engineering, Circuit Design, Microelectronics Computer Science, Mathematics

Why Parallel? (3) Databases, data mining Oil exploration Web search engines, web based business services Medical imaging and diagnosis Pharmaceutical design Management of national and multi-national corporations Financial and economic modeling Advanced graphics and virtual reality, particularly in the entertainment industry Networked video and multi-media technologies Collaborative work environments

Why Parallel? (4) Computer 의물리적한계 ( 계속 ) 현재 CPU 의 clock speed 는대략 3GHz - 발열문제 - 반도체소자의문제 1 Tera Hz(1 x 10^12 Hz) 의 computer 는가능한가? 광속 c = 3 x 10^8 m/sec = 3 x 10^11 mm/sec CPU 와 memory 사이의거리를 r 이라고하면 r < c / 10^12 = 0.3 mm!! 1 Tera byte(=10^6 x 10^6 bytes) 의 memory 가지려면 1 byte 는 3A x 3A 이내에저장되어야!! Computer 의성능높아질수록가격은기하급수적으로상승하나의고가시스템보다여러개의저가시스템을사용하여병렬처리하는것이대안

Why Parallel? (5) Computer 의물리적한계 2004 년까지 SW 개선없이도 HW 발전에따라수혜 CPU clock 의증가 : 2000 년대초반까지기하급수적으로증가 CPU 실행시간최적화 : CPU 명령어의순차실행최적화 (pipeline, 분기예측, out-of-order execution 등 ) Cache 크기증가 The free lunch is over: A fundamental turn toward concurrency in SW (Hurb Sutter, 2005) 전력소모및발열문제 : clock 속도의제곱 ( 세제곱?) Clock 속도증가 짧은도선 CPU 의신뢰도하락 2004 년부터 CPU 제조사들은 clock 속도경쟁포기 CPU : single core multi-core GPU : many-core

Parallel Computers (1) Parallel computer 정의 * 다수의 CPU 가다수의프로그램혹은분할된프로그램을동시에처리하는컴퓨터 * 다수의 CPU 를결합하여단일 CPU 성능의한계를극복하기위한컴퓨터구조 http://giyyon.tistory.com/44?srchid=br1http%3a%2f%2fgiyyon.tistory.com%2f44 다양한분류방법이있으나, 메모리공유에따른분류는 * SMP(Symmetric Multi Processing) * MPP(Massively Parallel Processing) * NUMA(Non-Uniform Memory Access) ** Cluster computer (workstation, PC, ) MPI 는이모든구조에서작동

Parallel Computers (2) Cluster computer http://pantheonjk.tistory.com/142?srchid=br1http%3a%2f%2fpantheonjk.tistory.com%2f142 정의개인 PC 나소형 server 등을 network 장비를사용하여다수연결하여구성한일종의병렬처리용 supercomputer 특징 * 저렴한가격 : 상용 supercomputer 의 1/10 * 확장성 * 유연성 2002 년 6 월 Top500 에따른 HPC 시장의 architecture 구성비

Parallel Computers (3) 2011 년 11 월 Top500 에따른 HPC 시장의구성비

Parallel Computers (3) 2011 년 11 월 Top500 에따른 HPC 시장의구성비

Parallel Computers (4) 2011 년 11 월 Top500 에따른 HPC 시장의구성비

Parallel Computers (5) PC Cluster 소형 PC 나 PC 서버를수십대에서수천대까지병렬네트워크로연결해슈퍼컴퓨터에상응하는고성능컴퓨팅 (HPC) 을구현하는기술 최초 NASA CESDIS Beowulf : 16-node Intel DX4 processors http://www.phy.duke.edu/~rgb/brahma/resources/beowulf/

Parallel Processing (1) 병렬처리 (parallel processing) 란? 복수의처리장치를사용하여, 모든처리장치가하나의프로그램상의서로다른태스크를동시에처리함으로써처리의부하를분담하여처리속도를향상시키는방법 여러개의프로그램을동시에병렬처리하는다중처리 ( multiprocessing) 와는다름

Parallel Processing (2) 병렬처리의장단점 장점 : 고속연산가능 단점 - 추가적인 overhead 소요 - 프로그래밍이어려움 - 모든문제에효율적으로적용되는것이아님 병렬처리의예 일상생활 / 회사에서의예 벽에페인트칠하기 병렬처리쉬움 고도의수학문제풀기 병렬처리어려움 / 불가능 / 무의미

Parallel Programming (1) 병렬처리문제 : 1 부터 n 까지의합을구하라. p : 전체 worker 의수각 worker 는 p 와자신이몇번째 worker 인지 ( 자신의 rank ) 알아야. Algorithm 1. master worker 가 n 을입력받는다. 2. master worker 가고르게작업을나누고각자담당할작업범위를 slave worker 들에게알린다. 3. 각자주어진범위의부분합을독립적으로계산한다. 4. slave worker 는각기 master worker 에게자신이계산한부분합을보고한다. 5. master worker 는자신을포함한모든 worker 의부분합을취합하여답을낸다. 2 대신 master worker 는 n 값을 slave worker 들에게 broadcast 하고모든 worker 는각자자신의 rank 에따라자신의작업범위를파악한다.

Parallel Programming (2) 병렬프로그래밍에서고려되어야할사항 고른작업분배가중요 : 모두가동시에작업이끝나야 I/O 문제 : 입출력은하나의 worker 가담당해야 모든 worker 의작업및진도를어떻게 control? 동기화 (synchronization) 의문제 어떻게 worker 간에정보 ( 즉 data) 를주고받을것인가? shared memory vs. distributed memory program 을어떻게작성할것인가? - SPMD(single program multiple data) 모든 worker 가같은프로그램사용 - MPMD(multiple program multiple data) worker 가각기다른프로그램사용 ( 보통은역할에따라소수개의프로그램작성 ) 어떻게각 worker 에게 program 을제공할것인가?

Parallel Programming (3) Shared memory vs. distributed memory Shared memory system - 모든 CPU 는메모리를공유 한 CPU 가다른 CPU 에 data 를전달하려면단순히공유메모리에 write 다른 CPU 가 read programming 이쉽다. - memory contention CPU 개수에한계 Distributed memory system - 모든 CPU 는각자독립된메모리사용 한 CPU 가다른 CPU 에 data 를전달하려면명시적인통신필요 programming 어렵다. - memory contention 없으므로시스템확장용이

Parallel Programming (4) SPMD vs. MPMD [1/2] SPMD(single program multiple data) worker 모두가같은프로그램사용, 단, 각 worker 의 rank 에따라역할을분류 Algorithm master worker의 rank=0을가정 1. If my rank==0, n을입력받고, slave worker들의작업범위를결정하고, 각자에게통보한다. else master worker로부터작업범위를통보받는다.( 그때까지대기 ) 2. 각자독립적으로자신이맡은범위의수를더해부분합을구한다. 3. If my rank==0, 모든 slave worker로부터부분합을전달받아총합을계산한다. else 각자 master worker에게자신의부분합을보고한다. 4. If my rank==0, 총합을출력한다.

Parallel Programming (5) SPMD vs. MPMD [2/2] MPMD(multiple program multiple data) 역할에따라 2 개이상의프로그램사용, Algorithm (master worker) 1. n을입력받고, 각 slave worker의작업범위를결정하고, 각자에게통보한다. 2. 자신이맡은범위의수를더해부분합을구한다. 3. 모든다른 worker로부터부분합을전달받아총합을계산한다. 4. 총합을출력한다. Algorithm (slave worker) 1. master worker로부터자신의작업범위를통보받는다. 2. 각자독립적으로자신이맡은범위의수를더해부분합을구한다. 3. 각자 master worker에게자신의부분합을보고한다.

MPI 의기본개념 (1) Message Passing 지역적으로독립된메모리를가지는 process 들이 data 를공유하기위해 message(data) 를송수신하여통신하는방식 병렬화를위한작업할당, data 분배, 통신의운용등모든것을프로그래머가담당 : 어렵지만효율높다. 다양한 hardware platform 에서구현가능 분산메모리다중 processor system 공유메모리다중 processor system 단일 processor system MPI 란무엇인가? Message Passing Interface de facto standard Message passing 병렬프로그래밍을위해표준화된데이터통신라이브러리 (Message Passing Library) 의표준을정의한것 목적 : 이식성 (portability), 효율성 (efficiency), 기능성 (functionality) * hardware vendor 가자신의 hardware 에최적화된 library 제공가능

MPI 의기본개념 (2) MPI 의역사 1980 년대 1990 년대초까지, 다양한분산메모리병렬컴퓨팅 SW 등장. MPI Forum : 표준마련의필요성에서정부, 학계, 산업체등, 1992 시작 MPI-1 표준마련 (MPI Forum) : 1994 년 http://www.mcs.anl.gov/mpi/index.html MPI-2 발표 : 1997 년 현재 MPI-2.2 : 2009 년 http://www.mpi-forum.org/docs/docs.html MPI 표준에맞추어개발한 MPI Library MPICH, CHIMP, LAM/MPI, OpenMPI,, 기타각 hardware vendor 들의 MPI OpenMPI site http://www.open-mpi.org/

MPI 의기본개념 (3) Process 와 processor MPI 는 process 기준으로작업할당 Processor : process = 1:1 or 1:many Communicator 서로간에통신이허용되는모든 process 들의집합 Process rank 동일한 communicator 내의 process 들을식별하기위한식별자 만일 p 개의 process 가연산에참여한다면 rank 는 0, 1,, p-1

MPI 의기본개념 (4) Message [ = data + envelope ] 어느 process 가보내는가 어디에있는 data 를보내는가 어떤 data 를보내는가 Data 를얼마나보내는가 어느 process 가수신할것인가 어디에저장할것인가 얼마나받을준비를해야하는가 Tag ( 꼬리표 ) Message 의 matching 과구분에이용 순서대로메시지도착을처리할수있음 message buffer 사용 wild card 사용가능 ex. 누군가 message 를보내오면

MPI 의기본개념 (5) 점대점통신 (point to point communication) 두개의 process 사이의통신 하나의송신 process 에하나의수신 process 가대응 집합통신 (collective communication) 동시에여러개의 process 가통신에참여 일대다, 다대일, 다대다대응가능 여러번의점대점통신사용을하나의집합통신으로대체 프로그래밍이쉽고간단하다. 오류의가능성이적다. 최적화되어일반적으로빠르다.

MPI 표준 (1) MPI(Message Passing Interface) http://enc.daum.net/dic100/contents.do?query1=20xx221466 In the definition by Gropp et al 96, MPI "is a message passing applicati on programmer interface, together with protocol and semantic specifica tions for how its features must behave in any implementation", "MPI incl udes point-to-point message passing and collective (global) operation s, all scoped to a user-specified group of processes. MPI is a language-independent communications protocol used to progr am parallel computers. MPI-1 은 127 개의함수로구성 대부분의 MPI implementation 은 Fortran, C, C++ 에서호출가능한 library function 으로구성 보통의 Fortran, C, C++ 프로그램에서다른 process 로통신이필요시적절한함수만호출하면됨 그외 Python, Ocaml, Java 에서도사용하도록노력중

MPI 표준 (2) MPI 프로그램의구조 Include MPI header file - MPI 함수의 prototype 선언 - macro, MPI 관련인수, data type 정의 변수선언 - MPI 함수의 prototype 선언 MPI 환경의초기화 - MPI_Init() - MPI_Comm_rank() - MPI_Comm_size() MPI 통신함수호출하며연산수행 MPI 환경해제 - MPI_Finalize()

MPI 표준 (3) MPI 함수에대하여 MPI 함수의이름과형태 MPI_Xxxxxx(parameter, ); MPI_ 로시작그다음첫글자 X 는대문자 MPI 함수의호출과 return 값 호출예 err = MPI_Init(&argc, &argv); if (err == MPI_SUCCESS) { : } 혹은 MPI_Init(&argc, &argv); Return 값첫예의경우, err 로 return. 호출이성공적이면 MPI_SUCCESS 값가짐

MPI 표준 (4) int MPI_Init(&argc, &argv); MPI 환경초기화 MPI 루틴중가장먼저오직한번반드시호출되어야함 MPI_COMM_WORLD 라는 communicator 가정의됨 호출예 MPI_Init(&argc, &argv); int MPI_Comm_rank(MPI_COMM comm, int *rank); 같은 communicator comm 에속한 process 의 rank 를할당 - p 개의 process 를사용할경우, 0 부터 p-1 의값을할당 호출예 MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

MPI 표준 (5) int MPI_Comm_size(MPI_COMM comm, int *size); Communicator comm 에포함된 process 들의총개수가져오기 호출예 MPI_Comm_size(MPI_COMM_WORLD, &p); int MPI_Finalize( ); 모든 MPI 자료구조정리 모든 process 들이마지막으로한번호출되어야함 Process 를종료시키는것은아님 호출예 MPI_Finalize();

MPI 표준 (6) MPI 메시지 = data + 봉투 (envelope) Data Buffer : 수신 ( 송신 ) data의변수이름 개수 : 수신 ( 송신 ) data의개수 Data type : 수신 ( 송신 ) data의 data 유형 봉투 수신자 ( 송신자 ) : 수신 ( 송신 ) process의 rank Tag( 꼬리표 ) : 송신 ( 수신 ) data를나타내는고유한정수 Communicator : 송신, 수신 process들이포함된 process group MPI data type 기본 type과유도 type(derived type) 유도 type은마음대로만들수있다. 송신과수신 data type은반드시일치해야한다.

MPI 표준 (7) MPI 기본 data type

MPI 표준 (8) 점대점통신 (point to point communication) [1/3] 반드시두개의 process 만참여 communicator 내에서만이루어짐 송신 / 수신 process 의확인을위해 communicator 와 rank 사용 통신의완료 메시지전송에이용된메모리위치에안전하게접근할수있음을의미 Blocking 통신과 non-blocking 통신 Blocking : 통신이완료된후루틴으로부터 return 됨 Non-blocking : 통신이시작되면완료와관계없이 return, 이후완료여부검사 통신완료에요구되는조건에따라통신모드분류

MPI 표준 (9) 점대점통신 (point to point communication) [2/3] 통신모드

MPI 표준 (10) 점대점통신 (point to point communication) [3/3] int MPI_Send(void *message, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) Datatype 형태의자료 message 를 count 개수만큼 dest rank 의 process 에게전송 반환값 : error code ex. MPI_Send(message, strlen(message)+1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); int MPI_Recv(void *message, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status) Source process 로부터 tag 태그를사용해서보내온메시지를받음 Source : process rank 혹은 MPI_ANY_SOURCE 사용 Tag : 전송자가사용한 tag 혹은 MPI_ANY_TAG 사용가능 ex. MPI_Recv(message, 100, MPI_CHAR, source, tag, MPI_COMM_WORLD, &status); 이외많은점대점통신함수가있음

MPI 표준 (11) 집합통신 (Collective communication) [1/3] 한그룹의 process가참여 점대점통신기반 점대점통신을이용한구현보다편리하고성능면에서유리 집합통신루틴 Communicator 내의모든 process 호출 동기화가보장되지않음 Non-blocking 루틴없음 Tag 없음

MPI 표준 (12) 집합통신 (Collective communication) [2/3]

MPI 표준 (13) 집합통신 (Collective communication) [3/3] int MPI_Bcast(void *message, int count, MPI_Datatype datatype, int root, MPI_Comm comm) 전송자와수신자는모두같은명령을사용 root 라는 rank 를가진 process 가송신하며다른모든 process 는수신 Ex. MPI_Bcast(&uplimit,1,MPI_LONG,0,MPI_COMM_WORLD); Int MPI_Reduce(void *operand, void *result, int count, MPI_Datatype datatype, MPI_Op operator, int root, MPI_COMM comm) Operand 에주어진자료에대해 operator 로지정된연산을수행한결과를 result 로반환함 Operator 는 MPI_MAX, MPI_MIN, MPI_SUM, MPI_PROD 등많은종류의연산이가능 Ex. MPI_Reduce(&sum,&gsum,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD); 이외여러집합통신함수가있음

MPI 프로그램및실행 (1) 간단한 MPI 프로그램의예 [1/2] hello, world program (Pacheco) /* "Hello World" Type MPI Test Program */ #include <stdio.h> #include mpi.h int main(int argc, char **argv) { int my_rank; /* rank of process */ int p; /* number of processes */ int source; /* rank of sender */ int dest; /* rank of receiver */ int tag=50; /* tag for messages */ char message[100]; /* storage for the message */ MPI_Status status; /* return status for receive */ MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Comm_size(MPI_COMM_WORLD, &p);

MPI 프로그램및실행 (2) 간단한 MPI 프로그램의예 [2/2] hello, world program (Pacheco, 계속 ) if (my_rank!= 0) { sprintf(message, Greetings from process %d!, my_rank); dest = 0; MPI_Send(message, strlen(message)+1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); } else { /* my_rank == 0 */ for (source = 1; source < p; source++) { MPI_Recv(message, 100, MPI_CHAR, source, tag, MPI_COMM_WORLD, &status); printf( %s\n, message); } } MPI_Finalize(); } /* main */

MPI 프로그램및실행 (3) 프로그램의실행 [1/2] LAM/MPI 에서의 comile & run LAM 환경조성및 process 지정 $ lamboot v lamhosts 병렬 program compile $ hcc o helloworld helloworld.c 병렬로 run 하기 $ mpirun np 4 helloworld LAM 환경해제 $ wipe v lamhosts lamhosts file 이름은임의로줄수있음 - 병렬연산하는데사용되는 host의이름 (IP도 OK) 을나열 - 멀리떨어진 host와도병렬연산가능 ex. psmp 혹은 psmp psmp psmp toshiba 211.221.225.179

MPI 프로그램및실행 (4) 프로그램의실행 [2/2] [pspark@psmp MPI]$ cat lamhosts psmp psmp psmp psmp [pspark@psmp MPI]$ lamboot -v lamhosts LAM 7.1.1/MPI 2 C++/ROMIO - Indiana University n-1<24783> ssi:boot:base:linear: booting n0 (psmp) n-1<24783> ssi:boot:base:linear: finished [pspark@psmp MPI]$ hcc -o helloworld helloworld.c [pspark@psmp MPI]$ mpirun -np 4 helloworld Greetings from process 1! Greetings from process 2! Greetings from process 3! [pspark@psmp MPI]$ wipe -v lamhosts LAM 7.1.1/MPI 2 C++/ROMIO - Indiana University n-1<24800> ssi:boot:base:linear: booting n0 (psmp) n-1<24800> ssi:boot:base:linear: finished [pspark@psmp MPI]$

MPI 프로그램및실행 (5) 1 부터 n 까지더하는프로그램 serial program #include <stdio.h> int main(int argc, char* argv[]) { long int i,last; double sum; printf("this program computes the sum from 1 to a given number.\n"); printf("enter a big number : "); scanf("%ld",&last); sum=0.; for (i=1; i<=last; i++) { sum=sum+i; } printf("\nsum from 1 to %ld is %f\n",last,sum); } parallel program http://pspark.suwon.ac.kr/linux/lectnote/mpisum.c

Related Topics & Questions Related Topics GPU computing GPGPU( 위키백과 ) 한글 http://enc.daum.net/dic100/contents.do?query1=10xx236094 영문 http://enc.daum.net/dic100/contents.do?query1=20x1268939 CUDA 미루웨어 http://www.miruware.com/ 한국 CUDA 사용자그룹 (KCUG) http://cafe.daum.net/kcug OpenCL http://enc.daum.net/dic100/contents.do?query1=10xx281093 OpenMP http://enc.daum.net/dic100/contents.do?query1=20xx381842 Questions?