아래는 입문자를 위한 병렬 프로그래밍 (An Introduction to Parallel Programming) 1장 연습문제를 풀이하였습니다. 해당 책의 솔류선은 구글링하면 책의 저자가 쓴 솔류선이 나오긴 하지만, 개인적으로 공부 목적을 위해 아래처럼 정리를 하였습니다. 오타나 에러가 있을 수 있으니 참고하시길 바랍니다
1. 글로벌 합계 예제에서 my_first_i와 my_last_i를 계산하는 함수에 대한 공식을 만들어 보자. 각 코어는 루프에서 같은 양의 항목에 대한 계산을 할당 받아야 한다는 것을 기억하자. (힌트) n이 p로 나뉠 수 있는 경우를 고려하자.
가정 1: 병렬 프로그래밍에 사용할 프로세서의 갯수: p
가정 2: 각 프로세서의 호출은 my_rank를 통해서 한다.
- my_rank: 0,1,2,...p-1
- 1번 프로세서: 0
- 2번 프로세서: 1
- p번 프로세서: p-1
문제에서 요구하는 것은 n개의 1차원 숫자 배열*이 존재할 때, 병렬 프로그래밍을 이용하여, 각 코어들이 최대한 같은 길이의 배열을 할당받도록 하는 것이다. 이때, 사용하는 프로세서의 갯수는 p 개이므로, 다음과 같은 관계식을 쓸 수 있다:
(1) n = m*p + x
(2) m = n quotient p
(3) l = n mod p.
이때, l 개의 숫자 배열들을 각각 l개의 프로세서에 하나씩 추가적으로 할당한다. 따라서, 각 프로세서들이 계산을 해야할 배열의 크기는 아래와 같다.
(1) 0번 프로세서: m + 1 개 배열, 배열 index: 0~ m
(2) 1번 프로세서: m + 1 개 배열, 배열 index: m+1 ~ 2m + 1
...
(l-1) l-1 번 프로세서: m + 1개 배열, 배열 index: (m+1)(l-1) ~ l (m+1) - 1
(l) l 번 프로세서: m 개의 열, 배열 index: (m+1)l ~ m (l+1) + l-1
(l+1) l+1 번 프로세서: m 개의 열, 배열 index: m (l+1) + l ~ m (l+2) + l-1
...
(p-1) p-1번 프로세서: m개의 배열: m (l+p-1) + l ~ m (l+p) +l
따라서, 이를 코드로 작성하면 아래와 같다.
quotient = n/p;
remainder = n%p;
if (my_rank < remainder ) {
n_array = quotient + 1;
my_first_i = my_rank * n_array;
}
else{
n_array = quotient;
my_first_i = my_rank * n_array + remainder;
}
my_last_i = my_first_i + n_array;
문제 1.3
그림 1.1에 있는 것처럼 트리 구조 글로벌 합계를 위한 의사 코드를 작성해보자. 코어의 수는 2의 제곱(1,2,4,8...)이 된다. (힌트) 코어가 자신의 합계를 전송하는지 아니면 합계를 전송받아 덧셈하는지를 결정하기 위해 변수 divisor를 사용하자. divisor는 2로 시작하며 반복될 때마다 두 배씩 증가한다. 또한 core_difference 변수를 사용하여 어떤 코어가 현재 코어와 파트너로 작업을 하는지를 결정한다. 이 변수는 1을 갖고 시작하며 마찬가지로 반복될 때마다 두 배로 증가한다. 예를들면, 첫번째 반복 0% divisor =0 이고 1%divisor =1인 경우에 1이 전송할 때 0은 수신 받아 덧셈을 하게 된다. 또한 첫 번째 반복은 0 + core_difference = 1이고 1- core_difference = 0인 경우에 0과 1은 첫 번째 반복에서 한 쌍으로 간주된다.
댓글