10. 병렬프로그래밍: 병렬화가 잘되는 경우 (Embarrassingly Parallel Computations)

* Embarrassingly Parallel Computations 란?

완전히 독립적인 여러부분으로 나눌 수 있고, 프로세스 각각 계산이 가능한 병렬 프로그램을 말한다. 프로세스 간에 통신이 거의 필요없고, 각 프로세스는 다른 프로세스와 관계없이 실행될 수 있다. 모든 프로세스(Workers)가 같이 일을 시작하는 형태의 프로그램을 가진다.

 

1. 함수 적분 프로그램

사다리꼴 공식을 사용한 정적분 공식: h[f(x0)/2 + f(x1) + f(x2) + ... + f(xn)/2]

적분: 사다리꼴 공식

#include <stdio.h>
#include <mpi.h>

double f (double x) //적분할 함수
void Get_data(int,int,double *, diuble *, int *); //데이터 입력

intmain(void){
int my_rank,size;
int n,local_n,i; //사다리꼴, 개별사다리꼴
double a,b,h,local_a,local_b; //양끝,밑변
double local_int, total_int; //면적
double x; //f(x)의 x값

MPI_Init(NULL,NULL);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
MPI_Comm_size(MPI_COMM_WORLD,&size);
Get_data(my_rank,size,&a,&b,&n);

h=(b-a)/n //사다리꼴 밑변
local_n=n/size; //각노드가 맡은 사다리꼴개수
local_a=a+my_rank*local_n*h;
local_b=local_a+local_n*h;
local_int=(f(local_a)+f(local_b)/2.0;
x=local_a;
for(i=1;i<=local_n-2;i++){
x+=h;
local_int+=f(x);
}
local_int *=h
MPI_Reduce(&local_int,&total_int,1,MPI_DOUBLE,MPI_SUM,0,MPU_COMM_WORLD);

if(my_rank==0){
printf("넓이=%d",total_int);
}
MPI_Finalize();
}

double f(double x){
return x*x+2.0;
}

void Get_data(int my_rank,int size, double *a, double *b, int *n){
if(my_rank==0){
printf("enter a,b,n:");
scanf("lf %lf %d",a,b,n);
}
MPI_Bcast(a,1,MPI_DOUBLE,0,MPI_COMM_WORLD);
MPI_Bcast(b,1,MPI_DOUBLE,0,MPI_COMM_WORLD);
MPI_Bcast(n,1,MPI_INT,0,MPI_COMM_WORLD);
}

 

2. Mandelbrot Set Problem

망델브로 집합은 다음 점화식으로 정의된 수열이 발산하지 않는 성질을 갖도록 하는 복소수 c의 집합으로 정의된다. 해당 평면에 속한 모든 복소수 c에 대해 색을 계산하고 출력하는 것이다. c의 color는 색상표에서 n값을 갖는 색이다.

Mandelbrot Set Problem

이 문제를 푸는데 같은 지역을 정해진 숫자로 균등하게 나누어 계산한다면 복소수 1개의 색상을 계산하는데 드는 시간이 각각 다르기 때문에 루프 실행횟수가 달라질 것이다. 따라서 dynamic task assignment를 이용해야한다.

*Dynamic Task Assignment란?

Master가 work pool을 가지고 있고 worker에게 일을 할당하는 것이다. task를 1행씩 만들어서 프로세스에게 주고, 먼저 끝나면 또 task를 할당하는 것이다. 

if(my_rank==0){

for(i=0;i<10;i++)
for(j=0;j<10;j++){
MPI_Recv(요청: x,y,color을 받는다);
MPI_Send(할당: task,(x,y,color)를 k에게 보낸다);
if(x!=-1) screen[x][y]=color;
}

for(i=0;i<numproc;i++){
MPI_Recv(프로세스k의 요청을 받는다.);
screen[x][y]=color;
MPI_Send(종료: (-1,-1));
}
screen을 화면에 출력;

}

else{
while(1){
MPI_Send(요청과 계산결과를 함께 보낸다);
MPI_Recv(좌표를 받는다);
if(x!=-1) 색 계산함수 실행
else break;
}
}