References
- An Introduction to Parallel Programming
Contents
- PI 값 구하기
- Critical Section (크리티컬 섹션)
- Busy waiting
- Mutex (뮤텍스)
행렬-벡터 연산 코드는 꽤 쉽게 작성했습니다. 이는 공유 메모리 위치를 쉽게 액세스할 수 있기 때문입니다. 초기화 이후에, y를 제외한 모든 변수들은 각 스레드에서 쉽게 접근할 수 있습니다. 즉, y를 제외한 모든 공유 변수들은 main 스레드에서 초기화된 이후에 변경될 수 없다는 것을 의미합니다. 게다가 y에 대해서 무언가 변경을 하려고 하더라도 오직 하나의 스레드만이 개별 컴포넌트를 변경할 수 있습니다. 따라서 두 스레드(혹은 그 이상)가 하나의 컴포넌트를 변경하지 않습니다. 잘 아시겠지만, 여러 스레드가 하나의 변수에 접근하여 값을 변경하려고 하면 문제가 발생할 것입니다.
\(\pi\) 값을 구하는 예제를 통해서 살펴보도록 하겠습니다. 사용할 수 있는 공식은 많은데, 그 중에 다음의 간단한 공식을 사용하도록 하겠습니다.
\[\pi = 4(1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots + (-1)^n \frac{1}{2n+1} + \cdots)\]
위 수식을 시리얼 코드로 작성하면 다음과 같이 작성할 수 있습니다.
위의 코드를 병렬화해보도록 하겠습니다.
행렬-벡터 연산과 유사하게 for 루프를 각 스레드로 분할하고, 이번에는 공유 변수 sum을 만들어 줍니다. 연산을 간단하게 하기 위해서 스레드의 수 t는 n으로 나누어진다고 가정하면, 스레드 0에서 루프 변수 i는 0부터 \(\frac{n}{t} -1\)까지의 범위를 갖게 됩니다. 스레드 1은 \(\frac{n}{t}\)에서 \(\2frac{n}{t} - 1\)의 범위를 가지게 됩니다. 일반화하여 스레드 q의 루프는 다음의 범위 갖게 됩니다.
\[q\frac{n}{t}, q\frac{n}{t}+1, q\frac{n}{t}+2, \cdots, (q+1)\frac{n}{t}-1\]
그리고 각 스레드의 첫 항의 부호는 \(q\frac{n}{t}\)가 짝수라면 (+)가 되고 홀수라면 (-)가 됩니다.
위 내용을 조합하여 \(\pi\)값을 구하는 스레드 함수를 작성하면 다음과 같이 작성할 수 있습니다.
double sum;
void* Thread_sum(void* rank)
{
long my_rank = (long)rank;
long long my_n = n / thread_count;
long long my_first_i = my_n * my_rank;
long long my_last_i = my_first_i + my_n;
double factor;
if (my_first_i % 2 == 0)
factor = 1.0;
else
factor = -1.0;
for (long long i = my_first_i; i < my_last_i; i++, factor = -factor)
sum += factor/(2*i + 1);
return NULL;
}전체 코드는 아래 링크에서 확인바랍니다 !
https://github.com/junstar92/parallel_programming_study/blob/master/pthread/02_pth_pi.c
GitHub - junstar92/parallel_programming_study
Contribute to junstar92/parallel_programming_study development by creating an account on GitHub.
github.com
위 코드를 사용하여 작은 수의 스레드와 상대적으로 작은 n 값으로 실행하면, 결과가 시리얼로 계산한 값과 거의 동일하다는 것을 알 수 있습니다. 하지만 n이 커지면 \(\pi\) 값에서 조금씩 벗어나는 것을 확인할 수 있습니다.
싱글 스레드에서 n이 증가하면 \(\pi\)값이 점점 더 정확해집니다.
하지만 2개의 스레드에서 n을 10배씩 했을 때, 그 값은 점점 더 나빠지는 것을 확인할 수 있습니다.
이 문제의 원인은 명확하게 '여러 스레드가 하나의 공유 변수를 업데이트하면 문제가 발생한다'라는 것을 보여주고 있습니다.
두 개의 값에 대한 덧셈은 일반적으로 하나의 기계어만으로 완성되지 않습니다. 예를 들어, y의 메모리에 있는 값과 x의 메모리에 있는 값을 하나의 C 문장으로 덧셈한다면,
x = x + y;로 작성할 수 있습니다.
하지만, 이를 기계어로 번역하면 좀 더 복잡합니다. x와 y에 저장되는 현재 값은 일반적으로 산술 연산을 수행하는 회로가 없는 컴퓨터의 메인 메모리에 저장됩니다. 그러므로 덧셈을 수행하기 전에 x와 y에 저장된 값을 메인 메모리에서 CPU의 레지스터로 먼저 이동되고, 값이 레지스터로 이동되고 나면 그때서야 덧셈이 수행됩니다. 덧셈이 완료되고 나면, 그 결과는 다시 레지스터에서 메모리로 이동합니다.
두 개의 스레드에서 private 변수 y에 저장된 값을 더해서 메인 스레드 0에서 초기화된 공유 변수 x에 저장한다고 가정해봅시다. 각 스레드는 다음과 같은 코드를 실행하게 됩니다.
y = Compute(my_rank);
x = x + y;스레드 0은 y = 1을 연산하고, 스레드 1은 y = 2를 연산한다고 가정한다면, 올바른 결과는 x = 3이 되어야 합니다. 하지만, 기계어로 표현하면 하나의 문장이 아니기 때문에 다음과 같은 시나리오가 가능합니다.
스레드 0이 그 결과를 x에 저장하기 전에 스레드 1이 메모리에서 x의 값을 복사하여 레지스터로 전달할 수 있습니다. 그렇게 되면 스레드 0에서 수행된 연산은 스레드 1에 의해서 덮어쓰게 됩니다. 문제는 반대로도 일어날 수 있습니다. 스레드 1이 스레드 0보다 먼저 실행되면 결과는 스레드 0에 의해서 덮어쓰이게 됩니다. 어떤 스레드라도 메모리로부터 x를 읽기 전에 결과를 저장하지 않는다면 이러한 상황은 언제든지 발생할 수 있습니다.
이 예제는 공유 메모리 프로그래밍의 근본적인 문제를 보여주고 있습니다. 이 문제는 다중 스레드가 공유 리소스를 업데이트하려고 할 때 발생하며, 이 경우에 공유 변수에는 어떤 결과가 저장될 지 예측할 수 없습니다. 다중 스레드가 공유 변수나 공유 파일과 같은 공유 리소스에 액세스하려고 할 때, 적어도 액세스 중의 하나는 업데이트하고, 나머지 액세스는 에러를 발생하게 되는데 이런 상태를 race condition(레이스 컨디션)이라고 합니다.
따라서, 위 예제에서 올바른 결과를 얻기 위해서는 스레드 중의 하나가 x = x + y를 수행할 때, 다른 스레드들은 이 문장을 실행하지 않도록 보장해야 합니다. 즉, x = x + y 코드는 하나의 스레드만 접근할 수 있고, x = x + y 코드처럼 한 번에 하나의 스레드에 의해서만 업데이트될 수 있는 코드의 블록을 critical section(크리티컬 섹션)이라고 합니다.
Busy waiting
위의 코드를 정상적으로 실행하기 위해서는 스레드 0이 x = x + y를 실행하려고 할 때, 스레드 1은 이 문장을 아직 시작하지 않았다는 것을 보장해야 합니다. 따라서, 스레드 0이 이 문장을 실행하면 스레드 0이 실행이 끝날 때까지 스레드 1에게 아직 실행하지 말라는 정보를 전달하고, 스레드 0이 문장의 실행을 끝마친 후에 스레드 1에게 x = x + y를 실행해도 된다는 정보를 주어 안전하게 실행하도록 해야합니다.
간단한 방법은 flag 변수를 사용하는 것입니다. flag 변수는 메인 스레드에서 0으로 초기화되는 공유 int형 변수이며 위의 예제의 Thread_sum 함수를 아래처럼 변경합니다.
void* Thread_sum(void* rank)
{
long my_rank = (long)rank;
long long my_n = n / thread_count;
long long my_first_i = my_n * my_rank;
long long my_last_i = my_first_i + my_n;
double factor;
if (my_first_i % 2 == 0)
factor = 1.0;
else
factor = -1.0;
for (long long i = my_first_i; i < my_last_i; i++, factor = -factor) {
while (flag != my_rank);
sum += factor/(2*i + 1);
flag = (flag + 1) % thread_count;
}
return NULL;
}line 15, 17이 추가되었습니다. 스레드 1이 스레드 0보다 먼저 for문에 도달하여 line 16을 수행하려고 시도할 때 어떻게 될까요? line 15의 while 문에 의해서 무한정 대기가 걸리게 됩니다. flag의 초기값은 0이고, 스레드 1의 my_rank의 값은 1이기 때문에 while문으로 인해 무한 루프가 걸리게 되어 크리티컬 섹션에 진입하지 못하게 됩니다. 스레드 0의 경우에는 flag의 초기값이 0이고, 스레드 0의 my_rank도 0이기 때문에 while문을 벗어나 크리티컬 섹션에 진입하여 for문을 수행합니다. 수행 후에는 flag값을 1 증가시키고 다음 for 루프에서는 while문에 걸려 무한 루프가 시작됩니다. 스레드 0이 수행하고 나서야 flag의 값은 1이 되었기 때문에 스레드 1에서는 이제 while문을 벗어날 수 있고 크리티컬 섹션에 진입하여 스레드 1이 for문을 수행합니다.
이 while 루프는 busy-waiting의 예입니다. 스레드가 반복적으로 조건을 테스트하여 조건이 될 때 크리티컬 섹션으로 진입하여 코드를 수행하고, 조건을 만족하지 못한다면 조건을 만족할 때까지 무한 루프에 빠지게 됩니다.
컴파일러는 프로그램이 멀티 스레드로 되어 있다는 것을 인식하지 못하고, flag과 x가 다른 스레드에서 업데이트되는 것을 알지 못합니다. 그 결과 컴파일러는 busy waiting을 방해하는 최적화를 진행할 수 있습니다.
아래 코드는 컴파일러 최적화로
y = Compute(my_rank); while (flag != my_rank); x = x + y; flag++;다음과 같은 코드로
y = Compute(my_rank); x = x + y; while (flag != my_rank); flag++;변경될 수 있습니다. 이렇게 되면 우리의 busy-waiting 루프를 거스르게 되는 것이므로, busy-waiting을 사용할 때에는 컴파일러 최적화 옵션을 끄는 것이 좋습니다. 하지만 옵션을 끄면 전체적인 성능이 저하되므로 추천하는 방법은 아닙니다.
다른 방법으로 C에서 제공하는 키워드인 volatile을 사용하면 되는데,int volatile flag; int volatile x;로 두 변수를 정의합니다. 이렇게 되면 컴파일러는 x와 flag가 공유 변수로 인식하여 다른 스레드에서도 업데이트될 수 있다는 것을 알게 되고, 해당 변수가 존재하는 문장은 최적화를 진행하지 않고 코드를 재배치하지 않습니다.
전체 코드는 아래 링크에 있습니다.
https://github.com/junstar92/parallel_programming_study/blob/master/pthread/03_pth_pi_busy1.c
GitHub - junstar92/parallel_programming_study
Contribute to junstar92/parallel_programming_study development by creating an account on GitHub.
github.com
하지만 실행 결과를 보면 알겠지만, 싱글 스레드보다 성능이 더 안 좋게 나옵니다. busy-waiting이 크리티컬 섹션을 보호하지만, while 문에 의해서 낭비되는 리소스가 너무 많기 때문입니다. 각 스레드에서 한 번의 for문을 돌 때마다 while문을 마주하면서 조건을 테스트하는데 보내는 시간이 너무 많기 때문에 성능이 매우 저하되어서 나옵니다.
이처럼 busy-waiting은 크리티컬 섹션에 대한 액세스를 제어하는 최적의 솔루션은 아닙니다. 스레드 1은 스레드 0이 flag의 값을 1 증가시킬 때까지 while문의 조건을 계속해서 테스트합니다. 만약 스레드 0이 지연되면 스레드 1은 단순히 테스트만을 반복하여 계속해서 CPU 사이클을 소비하게 됩니다. 이러한 상황은 성능 관점에서 매우 비효율적입니다. 또 다른 문제로 컴파일러 최적화를 끄는 것 역시 성능을 저하시킵니다. 어쩔 수 없이 busy-waiting을 사용한다면, 좀 더 효율적으로 동작하기 위해서 적절하게 코드를 아래처럼 수정할 수 있습니다.
void* Thread_sum(void* rank)
{
long my_rank = (long)rank;
long long my_n = n / thread_count;
long long my_first_i = my_n * my_rank;
long long my_last_i = my_first_i + my_n;
double factor, my_sum = 0.0;
if (my_first_i % 2 == 0)
factor = 1.0;
else
factor = -1.0;
for (long long i = my_first_i; i < my_last_i; i++, factor = -factor) {
my_sum += factor/(2*i + 1);
}
while (flag != my_rank);
sum += my_sum;
flag = (flag + 1) % thread_count;
return NULL;
}위 코드에서 line 19가 크리티컬 섹션입니다. 마찬가지로 busy-waiting을 사용하여 while 루프를 사용하지만 for루프 이후에 ciritical section을 만들어서 각 스레드가 함수를 수행하면서 단 한번만 크리티컬 섹션에 진입하도록 했습니다. 이처럼 크리티컬 섹션에 진입하는 횟수를 최대한 줄이면, 조금 더 성능을 향상시킬 수 있습니다.
첫 번째 버전이 0.667초가 나온 것에 비해 0.006초로 매우 큰 성능의 향상을 보여주고 있습니다.
아래는 n이 \(10^8\)일 때의 결과입니다.
전체 코드는 아래에서 확인 가능합니다.
https://github.com/junstar92/parallel_programming_study/blob/master/pthread/04_pth_pi_busy2.c
GitHub - junstar92/parallel_programming_study
Contribute to junstar92/parallel_programming_study development by creating an account on GitHub.
github.com
Mutex 뮤텍스
busy-waiting을 사용하는 스레드는 CPU를 계속해서 사용하기 때문에 일반적으로 ciritical section에 대한 액세스를 제한하는데 사용하기에 적절하지는 않습니다. 더 좋은 방법이 있는데, 하나는 뮤텍스(mutex)이고, 다른 하나는 세마포어(semaphore)입니다. 뮤텍스는 상호 배제(mutual exclusion)의 축약어입니다.
뮤텍스는 특별한 타입의 변수인데, 특별한 함수들과 함께 사용되어서 한 번에 하나의 스레드가 크리티컬 섹션에 진입하도록 제한하는데 사용됩니다. 따라서, 하나의 스레드가 크리티컬 섹션을 수행할 때 다른 스레드를 배제(exludes)하도록 보장해줍니다. (크리티컬 섹션에 대해 상호 배제를 보장)
Pthreads 표준은 뮤텍스를 위해 특별한 타입인 pthread_mutex_t를 포함하고 있습니다.
이 pthread_mutex_t 타입의 변수는 사용하기 전에 시스템에 의해 초기화되어야 하는데, 이 작업은 pthread_mutex_init 함수를 통해 이루어집니다.
int pthread_mutex_init(
pthread_mutex_t* mutex_p /* out */,
const pthread_mutexattr_t* attr_p /* in */);여기서 두 번째 인수는 사용하지 않기 때문에 무시하고 NULL을 전달합니다.
그리고 Pthreads를 사용하는 프로그램에서 뮤텍스의 사용을 끝낼 때에는 pthread_mutex_destroy를 호출해야 합니다.
int pthread_mutex_destroy(
pthread_mutex_p* mutex_p /* in/out */);
뮤텍스를 사용하여 크리티컬 섹션에 진입하거나 빠져나올 때에는 다음의 함수를 호출합니다.
int pthread_mutex_lock(pthread_mutex_t* mutex_p /* in/out */);
int pthread_mutex_unlock(pthread_mutex_t* mutex_p /* in/out */);pthread_mutex_lock 함수 호출은 다른 스레드가 크리티컬 섹션에 없을 때까지 스레드를 대기하도록 합니다. 그리고 크리티컬 섹션에 진입하면 뮤텍스를 lock하고 작업을 수행한 후에 크리티컬을 빠져나오면서 pthread_mutex_unlock 함수를 호출하여 크리티컬 섹션의 코드 실행을 완료했다고 시스템에게 알려줍니다.
뮤텍스를 사용하여 Thread_sum 함수를 작성하면 다음과 같이 작성할 수 있습니다.
void* Thread_sum(void* rank)
{
long my_rank = (long)rank;
long long my_n = n / thread_count;
long long my_first_i = my_n * my_rank;
long long my_last_i = my_first_i + my_n;
double my_sum = 0.0;
double factor;
if (my_first_i % 2 == 0)
factor = 1.0;
else
factor = -1.0;
for (long long i = my_first_i; i < my_last_i; i++, factor = -factor)
my_sum += factor/(2*i + 1);
pthread_mutex_lock(&mutex);
sum += my_sum;
pthread_mutex_unlock(&mutex);
return NULL;
}busy waiting에서 while문은 pthread_mutex_lock로 flag를 증가시키는 코드는 pthread_mutex_unlock로 대체되었습니다.
뮤텍스는 main 스레드에서 초기화 및 소멸되는데, main문에서 pthread_mutex_init과 pthread_mutex_destroy 함수가 호출되면서 뮤텍스가 초기화 및 소멸됩니다.
pthread_mutex_t mutex;
int main(int argc, char* argv[])
{
pthread_t* thread_handles;
Get_args(argc, argv);
thread_handles = (pthread_t*)malloc(thread_count * sizeof(pthread_t));
pthread_mutex_init(&mutex, NULL);
sum = 0.0;
double start, finish;
GET_TIME(start);
for (long thread = 0; thread < thread_count; thread++)
pthread_create(&thread_handles[thread], NULL, Thread_sum, (void*)thread);
for (long thread = 0; thread < thread_count; thread++)
pthread_join(thread_handles[thread], NULL);
sum *= 4.0;
GET_TIME(finish);
printf("With n = %lld terms,\n", n);
printf(" Multi-threaded estimate of pi = %.15f\n", sum);
printf(" Elapsed time = %f seconds\n\n", finish - start);
GET_TIME(start);
sum = Serial_pi(n);
GET_TIME(finish);
printf(" Single-threaded estimate of pi = %.15f\n", sum);
printf(" Elapsed time = %f seconds\n\n", finish - start);
printf(" Math library estimate of pi = %.15f\n", 4.0*atan(1.0));
pthread_mutex_destroy(&mutex);
free(thread_handles);
return 0;
}전체 코드는 아래 링크에서 확인 바랍니다 !
https://github.com/junstar92/parallel_programming_study/blob/master/pthread/05_pth_pi_mutex.c
GitHub - junstar92/parallel_programming_study
Contribute to junstar92/parallel_programming_study development by creating an account on GitHub.
github.com
thread = 8, n = \(10^8\)로 실행해보겠습니다.
두 번째 버전의 busy-waiting과 유사하지만 조금 더 성능이 좋게 나오긴 했습니다.
다음 표는 6개의 코어를 사용하는 시스템에서 스레드 개수 별 n = \(10^8\)일 때의 프로그램 실행 시간(단위 sec)입니다.
| 스레드 | Busy-Waiting(Ver2) | Mutex |
| 1 | 0.238 | 0.241 |
| 2 | 0.114 | 0.121 |
| 4 | 0.074 | 0.058 |
| 8 | 0.047 | 0.045 |
| 16 | 0.047 | 0.038 |
| 32 | 0.11 | 0.031 |
| 64 | 0.49 | 0.033 |
busy waiting에서는 스레드가 증가할수록 성능이 좋아지다가 어느 순간부터 급격하게 다시 나빠지는 것을 볼 수 있습니다. 뮤텍스 또한 스레드가 증가할수록 성능이 좋아지다가 어느 순간부터 성능 향상이 더디게 되지만, busy-waiting처럼 급격히 성능이 나빠지지는 않는 것을 확인할 수 있습니다.
크리티컬 섹션의 액세스를 제한하는 또 다른 방법 중의 하나인 세마포어는 다음 포스팅에서 다루어보도록 하겠습니다 !
'프로그래밍 > 병렬프로그래밍' 카테고리의 다른 글
| [pthread] 배리어(Barrier)와 조건 변수(Condition Variable) (0) | 2021.11.19 |
|---|---|
| [pthread] Thread 동기화 (0) | 2021.11.18 |
| [pthread] 행렬 - 벡터 곱 연산 (+ 캐시 일관성, 거짓 공유) (0) | 2021.11.16 |
| [pthread] Hello, Pthreads (0) | 2021.11.15 |
| [MPI] Odd-even transposition sort (MPI Safety) (0) | 2021.11.13 |
댓글