한빛출판네트워크

제공 : 한빛 네트워크
저자 : 김대곤

예전에는 MPI 프로그래밍 책에서 Hello World 예제 다음에 나오는 것은 핑퐁(Pingpong)이였습니다. 핑퐁은 두 개의 프로세서를 이용하여 메세지를 주고 받는 프로그램입니다. 하지만 요즘엔 그것도 너무 어렵다고 새로 나온 책[1]의 첫 예제는 MPI_Reduce와 MPI_Bcast를 소개하고 있습니다. 핑퐁이 어려운 이유는 병렬 프로그램에서 생각하기 싫은 Deadlock 발생할 수 있기 때문입니다. Deadlock이란 메세지의 전달 순서로 인해 생긴 프로그램의 실행이 정지한 것 정도로 이해할 수 있습니다. 예를 들어, 두 개의 프로세서 A와 B가 서로에게서 메세지가 전달되기를 기다리는 것이죠.

하여튼 자세한 이야기는 다음으로 미루기로 하고, 두가지 MPI 함수를 소개하기 위한 예제를 시작해 보도록 하겠습니다. 구하는 값은 1 부터 N 까지의 소수의 갯수입니다. 소수(prime number)란 1과 자기 자신을 제외한 어떠한 수로도 나누어 지지 않는 정수를 말합니다. 예를 들어 2, 3 과 5 같은 숫자들입니다. 10은 소수가 아닌데 2 로 나누어 지기 때문입니다. 그럼 257 은 소수일까 아닐까요? 어떻게 알 수 있을까요? 일의 자리가 수가 2로는 나누어지지 않기 때문에 257은 2로 나누어지지 않습니다. 3으로도 나누어지지 않습니다. 왜냐하면 2 + 5 + 7 = 14이고 14는 3으로 나누어지지 않기 때문입니다. 이게 무슨 소리냐고 하실 분이 있을지 모르지만 사실입니다. 각 자리의 수의 합이 3으로 나누어지면 그 수는 3으로 나누어집니다. 그렇지 않으면 본래의 수도 나누어지지 않습니다. 이제 필자에 대한 믿음을 전제하고 그냥 빨리 진행하도록 하겠습니다. 5로도 나누어지지 않습니다. 7로도 나누어지지 않습니다. 11로도 13과 17으로도 나누어 지지 않습니다. 얼마까지 해야 257이 소수라는 확신을 가질 수 있습니까? 답은 ‘13까지 만으로 충분하다’이고 일반적인 룰은 ‘구하는 수의 제곱근까지 소수로만 나누어보면 된다’입니다. 이것을 발견한 사람은 Eratosthene라는 저 먼 옛날 그리스 수학자이다. Sieve of Eratosthene 라는 알고리즘은 그 원리를 이용하고 소수를 구하는 방법입니다.

먼저 크기가 N인 배열을 만들고 전부 소수라고 씁니다. 첫번째 소수인 2를 선택해서 두 칸씩 건너뛰면서 소수가 아니라고 표시합니다. 두 번째 칸 다음부터 소수라고 적혀있는 수를 골라 그 수만큼씩 건너뛰면서 소수가 아니라고 표시합니다. 이 과정을 소수의 제곱이 N보다 작을 때까지 반복하는 것입니다. 그리고 나면 배열에 소수라고 쓰여있는 수는 모두 소수인 것입니다. 아래는 위에서 설명한 알고리즘을 C 언어로 구현한 것입니다.

/*
 * Author : DaeGon Kim
 * Date   : 2008/09/06
 * Desc   : Sequential Sieve of Eratosthenes algorithm
 */


#include 
#include 

int main(int argc, char **argv) {
   // Commandline arg checking
   if ( argc < 2 ) {
      printf("Usage : %s [N]n", argv[0]);
      return 0;
   }
   int N = atoi(argv[1]);
   int i;

   // Check N.
   if ( N <= 4 ) {
      printf("N must be greater than 4.n");
      return 0;
   }

   // memory allocation for arrays
   int *arrays = (int *)malloc(sizeof(int)*(N+1));
   if ( arrays == NULL ) {
      printf("Fail to allocate memory for arrays.n");
      return 0;
   }

   // initialization 
   for ( i=0 ; i <= N ; i++ ) {
      arrays[i] = 1;
   }

   // main algorithm
   int current_prime = 2;

   while ( current_prime * current_prime <= N ) {
      for ( i = 2*current_prime ; i <= N ; i += current_prime ) {
         arrays[i] = 0;
      }
      for ( i=current_prime+1; arrays[i] == 0 ; i++ );
      current_prime = i;
   }
  
   // print primes and total
   printf("Primes up to %dn", N);
   int total = 0;
   for ( i = 2 ; i <= N ; i++ ) {
      if ( arrays[i] == 1 ) {
         printf("%d ", i);
         total++;
      }
   }
   printf("nThe total number of primes is %d.n", total);

   free(arrays);

   return 0;
  
}

코드에는 전혀 한글이 없습니다. 제가 쓰는 대부분의 컴퓨터는 한글 입력이 지원되지 않습니다. 그래서 한글로 된 프로그램은 컴파일이 되지 않아 프로그램에는 한글을 사용하지 않는 버릇이 있기 때문입니다. 양해해주시기 바랍니다. 그리고 제가 영어로 주석을 달았다고 생각이 들진 않거든요.

사실 지금까지는 MPI와 전혀 상관이 없었습니다. 하지만 알고리즘에 대해서 깊이 아는 것이 MPI를 깊이 아는 것보다 훨씬 도움이 많이 됩니다. 사실 제가 보이엔 MPI에는 그렇게 깊은 뜻이 담겨 있지는 않습니다. 영어 알파벳 잘 외운다고 영어 잘하는 것 아니듯 말이죠.

처음에 미리 밝혔듯이 지금은 소수들에 관심이 있는 것이 아니라 소수의 전체수에만 관심이 있습니다. 이러한 문제 설정은 복잡한 MPI 함수를 피하기 위해서 입니다. 앞으로 가면서 이러한 가정이 하나 더 필요할 것입니다. 이제 어떻게 이 알고리즘을 여러 프로세서들을 이용하고 빨리 할 수 있을까 생각해 봅시다.

먼저 p 개의 프로세서가 있다고 가정하고, 배열을 p 개로 나누어봅시다. 그러면 각각의 프로세서들은 N/p 크기의 배열을 가지고 있을 것입니다. 여기서 프로그램을 간단하게 하기 위해서 또 다른 가정을 만들어보도록 하죠. ‘첫번째 프로세서가 가진 배열의 크기가 N의 제곱근보다 크다’입니다. 이 가정은 누가 메세지를 보낼 것인가 하는 복잡한 문제는 항상 첫번째 프로세서가 보내는 것으로 바뀌게 됩니다. 이제 남은 일이라고는 이 설정에 맞추어 프로그램을 변경하는 일만 남았죠.

부연 설명하면, 첫번째 프로세서가 하는 일은 거의 비슷합니다. 즉, 첫번째 소수를 찾아서 그 배수들을 소수가 아니라고 표시하고 그 다음 소수를 찾아서 다른 프로세스들에게 알려주고 다시 그 찾은 소수의 배수들은 소수가 아니라고 표시하는 것이죠. 이 작업을 계속 반복하는 것입니다. 다른 프로세스들은 첫번째 프로세서들에게서 소수를 받아서 그 배수들을 소수가 아니라고 표시합니다.

각각의 프로세서들이 찾은 소수들을 셈한 다음 다시 그 결과들을 합하면 끝이 납니다. 이렇게 해서 만들어진 MPI는 다음과 같습니다.

/*
 * Author : DaeGon Kim
 * Date   : 2008/09/06
 * Desc   : MPI sieve of Eratosthenes algorithm
 */


#include 
#include 
#include 
#include   // for ceil function

#define    MIN(a,b)    ((a)>(b) ? (b) : (a) )
#define    MAX(a,b)    ((a)>(b) ? (a) : (b) )

int main(int argc, char **argv) {

   int rank, size;
   int BLOCK_SIZE;

   MPI_Init(&argc, &argv);

   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
   MPI_Comm_size(MPI_COMM_WORLD, &size);

   // Commandline arg checking
   if ( argc < 2 ) {
      if ( rank == 0 ) printf("Usage : %s [N]n", argv[0]);
      MPI_Finalize();
      return 0;
   }
   int N = atoi(argv[1]);
   int i;

   // Check N.
   if ( N <= 4 ) {
      if ( rank == 0 ) printf("N must be greater than 4.n");
      MPI_Finalize();
      return 0;
   }

   BLOCK_SIZE = ceil((double)(N+1)/(double)size);

   // Checking whether the first processor has all the primes up to sqrt(n).
   if ( BLOCK_SIZE < sqrt(N) ) {
      if ( rank == 0 ) printf("All the primes up to sqrt(N) must be in the first processor.n");
      MPI_Finalize();
      return 0;
   }

   int *arrays = (int *)malloc(sizeof(int)*(BLOCK_SIZE));
   if ( arrays == NULL ) {
      printf("Fail to allocate memory for arrays.n");
      MPI_Abort(MPI_COMM_WORLD, -1);
      return 0;
   }

   int low_value  = rank * BLOCK_SIZE;
   int high_value = MIN((rank+1)*BLOCK_SIZE-1,N);

   for ( i=0 ; i < BLOCK_SIZE ; i++ ) {
      arrays[i] = 1;
   }

   int current_prime = 2;
   int first = 0;

   while ( current_prime * current_prime <= N ) {
      first = 2 * current_prime;
      if ( first < low_value ) { 
         if ( low_value % current_prime == 0 ) {
            first = low_value;
         } else {
            first = low_value + (current_prime - (low_value%current_prime));
         }
      }
      for ( i = first ; i <= high_value ; i += current_prime ) {
         arrays[i-low_value] = 0;
      }
      if ( rank == 0 ) {
         for ( i=current_prime+1; arrays[i] == 0 ; i++ );
         current_prime = i;
      }
      MPI_Bcast(¤t_prime, 1, MPI_INT, 0, MPI_COMM_WORLD);
   }
  
   //printf("Primes up to %dn", N);
   int total = 0;
   for ( i = MAX(2,low_value) ; i <= high_value ; i++ ) {
      if ( arrays[i-low_value] == 1 ) {
         //printf("%d ", i);
         total++;
      }
   }

   int total_count;
   MPI_Reduce(&total, &total_count, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

   if ( rank == 0 ) printf("The total number of primes is %d.n", total_count);

   free(arrays);

   MPI_Finalize();
   return 0;
   
}

첫번째 일반 C 프로그램에서 적지 않는 변화가 있었던 같지만 대부분의 변화는 각 프로세서가 전체 배열의 일부를 가짐으로 생기는 변화입니다. 같이 비교해 가면서 읽어보시기 바랍니다. 필자가 가진 MPI 프로그램이 있었지만 비교를 위해 첫번째 프로그램에서 시작해서 새로이 작성된 프로그램입니다.

실제 새롭게 쓰인 MPI 함수는 세 가지입니다. MPI_Abort, MPI_Bcast, MPI_Reduce 입니다. MPI_Abort는 MPI 환경을 강제로 종료하는 역활을 합니다. MPI_Bcast는 Broadcast를 줄여 쓴 말입니다. 즉, 하나의 프로세서가 모든 프로세서들에게 메세지를 보내는 것입니다. 프로그램에 사용된 아래 문장은 이렇게 해석됩니다. ‘¤t_prim에 저장된 하나의 정수를 프로세서 0 번이 MPI_COMM_WORLD에 있는 모든 프로세서들이 가진 ¤t_prim이 가르치는 공간에 전달한다’.

MPI_Bcast(¤t_prime, 1, MPI_INT, 0, MPI_COMM_WORLD);

두번째로 가정했던 N의 제곱근까지의 모든 소수를 첫번째 프로세서가 가지고 있다는 가정은 이 문장 때문입니다. 그 가정 없이는 어떤 프로세서가 보낼 지 알 수 없기 때문이지요.

마지막으로 MPI_Reduce는 MPI_Bcast와는 반대의 뜻을 가지고 있습니다. 각 프로세서들이 가지고 있는 값을 한 곳으로 모으는 것입니다. 명심하셔야 할 것은 프로세서의 갯수만큼 가지는 것이 아닙니다. 즉, 모아서 하나의 값을 가지는 것입니다. 그래서 프로그램에서 쓰인 아래 문장은 다음과 같이 읽혀집니다. ‘각 프로세서들이 &total이 가르키는 장소에 저장된 하나의 정수를 합하여 첫번째 프로세서가 가진 &total_count이 가르키는 공간으로 보내겠다’는 것입니다.

MPI_Reduce(&total, &total_count, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

지금까지 우리는 MPI가 가진 Collective 함수라고 부르는 것 중에 두 개를 살펴보았습니다. 다음 기사에서는 실제 소수들을 하나의 프로세서에 모아서 출력해 보도록 하겠습니다.

---

[1] Parallel Programming in C with MPI and OpenMP, Michael J. Quinn (Mc Graw Hill, 2003 ISBN 0-07-282256-2).