상위 질문
타임라인
채팅
관점
배리어 (컴퓨터 과학)
위키백과, 무료 백과사전
Remove ads
병렬 컴퓨팅에서 배리어(barrier)는 동기화 방법의 일종이다.[1] 소스 코드의 스레드 또는 프로세스 그룹에 대한 배리어는 모든 스레드/프로세스가 이 지점에서 멈춰야 하며, 다른 모든 스레드/프로세스가 이 배리어에 도달할 때까지 진행할 수 없음을 의미한다.[2]
많은 집단 루틴과 지시문 기반 병렬 언어는 암시적 배리어를 부과한다. 예를 들어, OpenMP가 포함된 포트란의 병렬 do 루프는 마지막 반복이 완료될 때까지 어떤 스레드에서도 계속할 수 없다. 이는 프로그램이 루프 완료 직후의 결과에 의존하는 경우에 대비하기 위함이다. 메시지 전달에서, (리덕션 또는 스캐터와 같은) 모든 전역 통신은 배리어를 암시할 수 있다.
병행 컴퓨팅에서 배리어는 상승 또는 하강 상태일 수 있다. '래치'라는 용어는 때때로 상승 상태로 시작하여 하강 상태가 되면 다시 상승할 수 없는 배리어를 지칭하는 데 사용된다. '카운트다운 래치'라는 용어는 미리 정해진 수의 스레드/프로세스가 도착하면 자동으로 하강하는 래치를 지칭하는 데 사용되기도 한다.
Remove ads
구현
요약
관점
스레드 배리어로 알려진 스레드에 대한 예시를 살펴보자. 스레드 배리어는 배리어에 진입한 총 스레드 수를 추적하는 변수를 필요로 한다.[3] 충분한 스레드가 배리어에 진입하면 배리어가 해제된다. 뮤텍스와 같은 동기화 기본요소 또한 스레드 배리어를 구현할 때 필요하다.
이 스레드 배리어 방법은 "중앙 배리어" 앞에서 대기해야 하는 스레드들이 예상된 수의 스레드가 배리어에 도달할 때까지 배리어가 해제되지 않는다는 점에서 중앙 집중식 배리어라고도 불린다.
다음은 POSIX 스레드를 사용하여 스레드 배리어를 구현한 C 코드이며, 이 절차를 보여준다:[1]
#include <stdio.h>
#include <pthread.h>
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // pthread barrier attribute
typedef struct _thread_barrier
{
int thread_barrier_number;
pthread_mutex_t lock;
int total_thread;
} thread_barrier;
thread_barrier barrier;
void thread_barrier_init(thread_barrier *barrier, pthread_mutexattr_t *mutex_attr, int thread_barrier_number){
pthread_mutex_init(&(barrier->lock), mutex_attr);
barrier->thread_barrier_number = thread_barrier_number;
barrier->total_thread = 0;// Init total thread to be 0
}
void thread_barrier_wait(thread_barrier *barrier){
if(!pthread_mutex_lock(&(barrier->lock))){
barrier->total_thread += 1;
pthread_mutex_unlock(&(barrier->lock));
}
while (barrier->total_thread < barrier->thread_barrier_number);
if(!pthread_mutex_lock(&(barrier->lock))){
barrier->total_thread -= 1; // Decrease one thread as it has passed the thread barrier
pthread_mutex_unlock(&(barrier->lock));
}
}
void thread_barrier_destroy(thread_barrier *barrier){
pthread_mutex_destroy(&(barrier->lock));
}
void *thread_func(void *ptr){
printf("thread id %ld is waiting at the barrier, as not enough %d threads are running ...\n", pthread_self(), THREAD_BARRIERS_NUMBER);
thread_barrier_wait(&barrier);
printf("The barrier is lifted, thread id %ld is running now\n", pthread_self());
}
int main()
{
pthread_t thread_id[TOTAL_THREADS];
thread_barrier_init(&barrier, PTHREAD_BARRIER_ATTR, THREAD_BARRIERS_NUMBER);
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_create(&thread_id[i], NULL, thread_func, NULL);
}
// As pthread_join() will block the process until all the threads it specified are finished,
// and there is not enough thread to wait at the barrier, so this process is blocked
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_join(thread_id[i], NULL);
}
thread_barrier_destroy(&barrier);
printf("Thread barrier is lifted\n"); // This line won't be called as TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}
이 프로그램에서 스레드 배리어는 struct _thread_barrier라는 구조체로 정의되며, 여기에는 다음이 포함된다:
- total_thread: 프로세스의 총 스레드 수
- thread_barrier_number: 스레드 배리어가 해제되기 위해 진입할 것으로 예상되는 총 스레드 수
- lock: POSIX 스레드 뮤텍스 락
배리어의 정의에 따라, 이 프로그램에서 배리어를 해제하기 위해 프로그램의 총 스레드 수를 "모니터링"할 thread_barrier_wait()와 같은 함수를 구현해야 한다.
이 프로그램에서 thread_barrier_wait()를 호출하는 모든 스레드는 THREAD_BARRIERS_NUMBER 수의 스레드가 스레드 배리어에 도달할 때까지 차단된다.
이 프로그램의 결과는 다음과 같다:
thread id <thread_id, e.g 139997337872128> is waiting at the barrier, as not enough 3 threads are running ...
thread id <thread_id, e.g 139997329479424> is waiting at the barrier, as not enough 3 threads are running ...
// (main process is blocked as not having enough 3 threads)
// Line printf("Thread barrier is lifted\n") won't be reached
프로그램에서 볼 수 있듯이, 생성된 스레드는 단 2개뿐이다. 이 두 스레드 모두 스레드 함수 핸들러로 thread_func()를 가지며, 이는 thread_barrier_wait(&barrier)를 호출한다. 반면 스레드 배리어는 해제되기 위해 3개의 스레드가 pthread_barrier_wait (THREAD_BARRIERS_NUMBER = 3)를 호출할 것으로 예상한다.
TOTAL_THREADS를 3으로 변경하면 스레드 배리어가 해제된다:
thread id <thread ID, e.g 140453108946688> is waiting at the barrier, as not enough 3 threads are running ...
thread id <thread ID, e.g 140453117339392> is waiting at the barrier, as not enough 3 threads are running ...
thread id <thread ID, e.g 140453100553984> is waiting at the barrier, as not enough 3 threads are running ...
The barrier is lifted, thread id <thread ID, e.g 140453108946688> is running now
The barrier is lifted, thread id <thread ID, e.g 140453117339392> is running now
The barrier is lifted, thread id <thread ID, e.g 140453100553984> is running now
Thread barrier is lifted
센스 반전 중앙 집중식 배리어
스레드 배리어를 성공적으로 통과한 모든 스레드에 대해 총 스레드 수를 1씩 감소시키는 것 외에도, 스레드 배리어는 스레드 상태를 통과 또는 중지로 표시하기 위해 반대 값을 사용할 수 있다.[4] 예를 들어, 상태 값이 0인 스레드 1은 배리어에서 중지되었음을 의미하고, 상태 값이 1인 스레드 2는 배리어를 통과했음을 의미하며, 스레드 3의 상태 값 = 0은 배리어에서 중지되었음을 의미하는 식이다.[5] 이는 센스 반전으로 알려져 있다.[1]
#include <stdio.h>
#include <stdbool.h>
#include <pthread.h>
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // pthread barrier attribute
typedef struct _thread_barrier
{
int thread_barrier_number;
int total_thread;
pthread_mutex_t lock;
bool flag;
} thread_barrier;
thread_barrier barrier;
void thread_barrier_init(thread_barrier *barrier, pthread_mutexattr_t *mutex_attr, int thread_barrier_number){
pthread_mutex_init(&(barrier->lock), mutex_attr);
barrier->total_thread = 0;
barrier->thread_barrier_number = thread_barrier_number;
barrier->flag = false;
}
void thread_barrier_wait(thread_barrier *barrier){
bool local_sense = barrier->flag;
if(!pthread_mutex_lock(&(barrier->lock))){
barrier->total_thread += 1;
local_sense = !local_sense;
if (barrier->total_thread == barrier->thread_barrier_number){
barrier->total_thread = 0;
barrier->flag = local_sense;
pthread_mutex_unlock(&(barrier->lock));
} else {
pthread_mutex_unlock(&(barrier->lock));
while (barrier->flag != local_sense); // wait for flag
}
}
}
void thread_barrier_destroy(thread_barrier *barrier){
pthread_mutex_destroy(&(barrier->lock));
}
void *thread_func(void *ptr){
printf("thread id %ld is waiting at the barrier, as not enough %d threads are running ...\n", pthread_self(), THREAD_BARRIERS_NUMBER);
thread_barrier_wait(&barrier);
printf("The barrier is lifted, thread id %ld is running now\n", pthread_self());
}
int main()
{
pthread_t thread_id[TOTAL_THREADS];
thread_barrier_init(&barrier, PTHREAD_BARRIER_ATTR, THREAD_BARRIERS_NUMBER);
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_create(&thread_id[i], NULL, thread_func, NULL);
}
// As pthread_join() will block the process until all the threads it specified are finished,
// and there is not enough thread to wait at the barrier, so this process is blocked
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_join(thread_id[i], NULL);
}
thread_barrier_destroy(&barrier);
printf("Thread barrier is lifted\n"); // This line won't be called as TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}
이 프로그램은 이전 중앙 집중식 배리어 소스 코드와 유사한 모든 기능을 가지고 있다. 단지 2개의 새로운 변수를 사용하여 다른 방식으로 구현할 뿐이다:[1]
- local_sense: THREAD_BARRIERS_NUMBER 스레드가 배리어에 도달했는지 확인하기 위한 스레드 로컬 부울 변수.
- flag: THREAD_BARRIERS_NUMBER 스레드가 배리어에 도달했는지 나타내는 struct _thread_barrier의 부울 멤버.
스레드가 배리어에서 멈추면 local_sense의 값이 토글된다.[1] THREAD_BARRIERS_NUMBER 미만의 스레드가 스레드 배리어에서 멈출 때, 해당 스레드들은 struct _thread_barrier의 flag 멤버가 개인 local_sense 변수와 같지 않다는 조건 하에 계속 기다린다.
THREAD_BARRIERS_NUMBER 스레드가 스레드 배리어에서 정확히 멈추면 총 스레드 수는 0으로 재설정되고, flag는 local_sense로 설정된다.
결합 트리 배리어
중앙 집중식 배리어의 잠재적인 문제는 모든 스레드가 통과/정지를 위해 전역 변수에 반복적으로 접근하기 때문에 통신 트래픽이 상당히 높아서 확장성이 저하된다는 점이다.
이 문제는 스레드를 재그룹화하고 다단계 배리어(예: 결합 트리 배리어)를 사용하여 해결할 수 있다. 또한 하드웨어 구현은 더 높은 확장성의 이점을 가질 수 있다.
결합 트리 배리어는 모든 스레드가 동일한 위치에서 스핀하는 상황을 피함으로써 확장성 문제를 해결하기 위해 계층적인 방식으로 배리어를 구현하는 방법이다.[4]
k-트리 배리어에서 모든 스레드는 k개 스레드의 서브그룹으로 균등하게 나뉘고, 이 서브그룹 내에서 1차 동기화가 이루어진다. 모든 서브그룹이 동기화를 마치면 각 서브그룹의 첫 번째 스레드는 2차 동기화를 위해 다음 레벨로 진입한다. 2차 레벨에서는 1차 레벨과 마찬가지로 스레드들이 k개 스레드의 새로운 서브그룹을 형성하고 그룹 내에서 동기화하며, 각 서브그룹에서 하나의 스레드를 다음 레벨로 보내는 방식으로 진행된다. 결국, 최종 레벨에는 하나의 서브그룹만 동기화된다. 최종 레벨 동기화 후, 해제 신호가 상위 레벨로 전송되고 모든 스레드가 배리어를 통과한다.[6][7]
하드웨어 배리어 구현
하드웨어 배리어는 위의 기본 배리어 모델을 구현하기 위해 하드웨어를 사용한다.[3]
가장 간단한 하드웨어 구현은 전용 와이어를 사용하여 신호를 전송함으로써 배리어를 구현한다. 이 전용 와이어는 OR/AND 연산을 수행하여 통과/차단 플래그 및 스레드 카운터 역할을 한다. 소규모 시스템에서는 이러한 모델이 작동하며 통신 속도가 주요 고려 사항이 아니다. 대규모 다중 프로세서 시스템에서 이 하드웨어 설계는 배리어 구현에 높은 지연 시간을 초래할 수 있다. 프로세서 간의 네트워크 연결은 지연 시간을 낮추는 한 가지 구현 방법이며, 이는 결합 트리 배리어와 유사하다.[8]
Remove ads
POSIX 스레드 배리어 함수
요약
관점
POSIX 스레드 표준은 직접적으로 스레드 배리어 함수를 지원하며, 이는 지정된 스레드 또는 전체 프로세스를 해당 배리어에 다른 스레드가 도달할 때까지 차단하는 데 사용될 수 있다.[2] POSIX가 스레드 배리어를 구현하기 위해 지원하는 세 가지 주요 API는 다음과 같다:
pthread_barrier_init()- 배리어를 해제하기 위해 배리어에서 대기해야 하는 스레드 수로 스레드 배리어를 초기화한다.[9]
pthread_barrier_destroy()- 스레드 배리어를 파괴하여 자원을 다시 해제한다.[9]
pthread_barrier_wait()- 이 함수를 호출하면
pthread_barrier_init()에서 지정한 수의 스레드가pthread_barrier_wait()를 호출하여 배리어를 해제할 때까지 현재 스레드가 차단된다.[10]
다음 예제(C로 pthread API를 사용하여 구현됨)는 스레드 배리어를 사용하여 메인 프로세스의 모든 스레드를 차단하고 따라서 전체 프로세스를 차단할 것이다:
#include <stdio.h>
#include <pthread.h>
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // pthread barrier attribute
pthread_barrier_t barrier;
void *thread_func(void *ptr){
printf("Waiting at the barrier as not enough %d threads are running ...\n", THREAD_BARRIERS_NUMBER);
pthread_barrier_wait(&barrier);
printf("The barrier is lifted, thread id %ld is running now\n", pthread_self());
}
int main()
{
pthread_t thread_id[TOTAL_THREADS];
pthread_barrier_init(&barrier, PTHREAD_BARRIER_ATTR, THREAD_BARRIERS_NUMBER);
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_create(&thread_id[i], NULL, thread_func, NULL);
}
// As pthread_join() will block the process until all the threads it specifies are finished,
// and there is not enough thread to wait at the barrier, so this process is blocked
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_join(thread_id[i], NULL);
}
pthread_barrier_destroy(&barrier);
printf("Thread barrier is lifted\n"); // This line won't be called as TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}
이 소스 코드의 결과는 다음과 같다:
Waiting at the barrier as not enough 3 threads are running ...
Waiting at the barrier as not enough 3 threads are running ...
// (main process is blocked as not having enough 3 threads)
// Line printf("Thread barrier is lifted\n") won't be reached
소스 코드에서 볼 수 있듯이, 생성된 스레드는 단 두 개뿐이다. 이 두 스레드는 모두 스레드 함수 핸들러인 thread_func()를 가지며, 이는 pthread_barrier_wait(&barrier)를 호출한다. 반면 스레드 배리어는 해제되기 위해 3개의 스레드가 pthread_barrier_wait (THREAD_BARRIERS_NUMBER = 3)를 호출할 것으로 예상한다.
TOTAL_THREADS를 3으로 변경하면 스레드 배리어가 해제된다:
Waiting at the barrier as not enough 3 threads are running ...
Waiting at the barrier as not enough 3 threads are running ...
Waiting at the barrier as not enough 3 threads are running ...
The barrier is lifted, thread id 140643372406528 is running now
The barrier is lifted, thread id 140643380799232 is running now
The barrier is lifted, thread id 140643389191936 is running now
Thread barrier is lifted
main()이 스레드로 취급되므로, 즉 프로세스의 "메인" 스레드이므로,[11] main() 안에서 pthread_barrier_wait()를 호출하면 다른 스레드가 배리어에 도달할 때까지 전체 프로세스가 차단된다. 다음 예제는 main() 안에서 pthread_barrier_wait()를 사용하여 프로세스/메인 스레드를 5초 동안 차단하며, 이는 2개의 "새로 생성된" 스레드가 스레드 배리어에 도달하기를 기다리는 동안이다:
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // pthread barrier attribute
pthread_barrier_t barrier;
void *thread_func(void *ptr){
printf("Waiting at the barrier as not enough %d threads are running ...\n", THREAD_BARRIERS_NUMBER);
sleep(5);
pthread_barrier_wait(&barrier);
printf("The barrier is lifted, thread id %ld is running now\n", pthread_self());
}
int main()
{
pthread_t thread_id[TOTAL_THREADS];
pthread_barrier_init(&barrier, PTHREAD_BARRIER_ATTR, THREAD_BARRIERS_NUMBER);
for (int i = 0; i < TOTAL_THREADS; i++){
pthread_create(&thread_id[i], NULL, thread_func, NULL);
}
pthread_barrier_wait(&barrier);
printf("Thread barrier is lifted\n"); // This line won't be called as TOTAL_THREADS < THREAD_BARRIERS_NUMBER
pthread_barrier_destroy(&barrier);
}
이 예제는 2개의 "새로 생성된" 스레드가 완료될 때까지 기다리기 위해 pthread_join()을 사용하지 않는다. 대신 main() 내에서 pthread_barrier_wait()를 호출하여 메인 스레드를 차단하므로, 2개의 스레드가 5초 대기(9행 - sleep(5)) 후 작업을 완료할 때까지 프로세스가 차단된다.
Remove ads
같이 보기
- 포크-조인 모델
- 랑데부 (플랜 9)
- 메모리 배리어
각주
외부 링크
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads