병렬 프로그래밍의 의존성 분석과 동기화 설계
병렬 프로그래밍에서 의존성을 분석하고 데이터·태스크 병렬화, 동기화와 데드락 대응 방식을 정리합니다.
2026-08-14 · 최초 발행 2025-12-28
병렬화는 작업을 나누는 일에서 끝나지 않는다
단일 프로세서의 성능 향상에는 물리적 한계가 있고, 이를 보완하는 방법 가운데 하나가 병렬화다. 하나의 작업을 더 작은 단위로 분리해 여러 프로세서, 코어, 스레드에서 함께 실행하면 전체 처리 시간을 줄이고 처리량을 높일 수 있다.
다만 모든 작업이 동시에 실행될 수 있는 것은 아니다. 작업 간 독립성을 확인하고, 공유 자원이 있다면 통신과 동기화 방식을 설계해야 한다. 병렬 프로그램은 보통 다음 흐름으로 구성된다.
문제는 먼저 독립적인 작업(Task)으로 분해한다. 이후 각 작업을 처리 단위에 배분하고, 작업 사이의 통신과 동기화를 조율한 뒤, 실제 하드웨어 자원에 배치한다.
병렬성은 적용되는 층위도 다르다. 비트 수준에서는 워드 크기 확장으로 병렬성을 얻을 수 있으며, 예를 들어 8비트에서 64비트로 확장하는 방식이 있다. 명령어 수준에서는 파이프라이닝, 슈퍼스칼라, VLIW가 사용된다. 데이터 수준에서는 SIMD와 벡터 처리가, 태스크 수준에서는 멀티스레딩과 멀티프로세싱이 사용된다.
실행 순서를 결정하는 의존성
병렬화 가능성은 명령어와 작업 사이의 의존성에서 결정된다. 특히 데이터가 생성되고 읽히거나, 동일한 이름의 저장 위치를 공유하는 경우 실행 순서를 조정해야 한다.
RAW는 앞선 쓰기가 끝나야 한다
Flow Dependency, 즉 RAW(Read After Write)는 진정한 데이터 의존성이다. 한 명령어가 기록한 값을 다음 명령어가 읽는 상황이므로, 뒤의 명령어는 앞선 명령어가 완료될 때까지 기다려야 한다.
// 예시
a = x + y; // (1) a에 쓰기
b = a * 2; // (2) a를 읽기 - RAW 의존성이 경우 (2)는 (1)이 완료되기 전에는 실행할 수 없다.
WAR와 WAW는 이름 의존성이다
Anti-dependency인 WAR(Write After Read)는 한 명령어가 읽은 데이터를 다음 명령어가 덮어쓰는 경우다.
// 예시
b = a + 1; // (1) a 읽기
a = c * 2; // (2) a에 쓰기 - WAR 의존성이는 이름 의존성(Name Dependency)이며 레지스터 이름 변경(Register Renaming)으로 해결할 수 있다. Out-of-Order Execution에서는 이 문제가 나타날 수 있다.
Output Dependency인 WAW(Write After Write)도 이름 의존성이다. 두 명령어가 같은 변수에 순서대로 값을 쓴다.
// 예시
a = x + y; // (1) a에 쓰기
a = c + d; // (2) a에 쓰기 - WAW 의존성최종 값이 정확하려면 실행 순서를 보장해야 하며, 역시 레지스터 이름 변경으로 해결할 수 있다.
의존성 그래프는 병렬로 실행할 수 있는 구간과 기다려야 하는 구간을 드러낸다.
I1과 I3 사이에는 의존성이 없으므로 병렬 실행이 가능하다. I2는 I1 이후에, I4는 I2와 I3가 모두 끝난 뒤에 실행된다.
데이터와 작업을 나누는 방식
데이터 병렬화(Data Parallelism)는 같은 연산을 여러 데이터에 적용하는 방식이다. 벡터화(Vectorization)는 컴파일러 자동 벡터화 또는 명시적 벡터 명령어로 구현할 수 있다.
// 순차 코드
for(int i = 0; i < N; i++) {
C[i] = A[i] + B[i];
}
// 벡터화 (개념적)
for(int i = 0; i < N; i += 4) {
vec_C[i:i+3] = vec_A[i:i+3] + vec_B[i:i+3];
}SIMD(Single Instruction Multiple Data)는 하나의 명령어로 여러 데이터를 함께 처리하며, SSE, AVX, NEON 등의 벡터 레지스터를 활용한다. 멀티미디어와 과학 계산에 효과적이다.
GPGPU(General Purpose GPU)는 GPU의 대규모 병렬 처리 능력을 일반 계산에 활용한다. 수천 개의 작은 코어로 많은 데이터를 병렬 처리하며, CUDA, OpenCL, ROCm 등의 프레임워크가 사용된다. 딥러닝, 과학 시뮬레이션, 암호화가 대표적인 활용 영역이다.
태스크 병렬화(Task Parallelism)는 서로 다른 작업을 동시에 수행한다. 작업 사이에 독립성이 있거나 느슨하게 결합돼 있어야 하며, 파이프라인과 워크플로우 병렬화도 여기에 포함된다.
실행 환경에 따른 구현 선택
공유 메모리 환경에서는 여러 스레드가 같은 메모리 공간에 접근한다. Pthread는 저수준 스레드 라이브러리로 세밀한 제어가 가능하지만 복잡도가 높다.
// Pthread 예시
#include <pthread.h>
void* worker(void* arg) {
// 작업 수행
return NULL;
}
int main() {
pthread_t threads[4];
for(int i = 0; i < 4; i++) {
pthread_create(&threads[i], NULL, worker, NULL);
}
for(int i = 0; i < 4; i++) {
pthread_join(threads[i], NULL);
}
}OpenMP는 컴파일러 지시문 기반의 고수준 API다. 기존 코드에 점진적으로 병렬화를 적용할 수 있고, 루프 병렬화에 효과적이다.
// OpenMP 예시
#pragma omp parallel for
for(int i = 0; i < N; i++) {
C[i] = A[i] + B[i];
}TPL(Task Parallel Library)은 .NET 프레임워크의 병렬 라이브러리로, Task 기반 비동기 패턴과 LINQ의 병렬 버전인 PLINQ를 제공한다.
분산 메모리 환경에서는 메시지 패싱이 필요하다. MPI(Message Passing Interface)는 프로세스 사이에서 명시적으로 메시지를 주고받는 표준이며, 슈퍼컴퓨터와 클러스터 환경에서 사용된다.
// MPI 예시
#include <mpi.h>
int main(int argc, char** argv) {
MPI_Init(&argc, &argv);
int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
// 병렬 작업 수행
MPI_Finalize();
}MapReduce는 대규모 데이터 처리를 위한 프로그래밍 모델이다. Map 단계에서 데이터를 분산 처리하고, Reduce 단계에서 결과를 집계한다. Hadoop과 Spark 등에서 구현된다.
가속기를 활용하는 방식도 있다. CUDA(Compute Unified Device Architecture)는 NVIDIA GPU 전용 병렬 컴퓨팅 플랫폼으로, 커널 함수를 GPU에서 실행해 수천 개의 스레드를 동시에 실행한다.
// CUDA 커널 예시
__global__ void vectorAdd(float* A, float* B, float* C, int N) {
int i = blockDim.x * blockIdx.x + threadIdx.x;
if(i < N) {
C[i] = A[i] + B[i];
}
}OpenCL(Open Computing Language)은 CPU, GPU, DSP, FPGA 등 다양한 플랫폼을 지원하는 개방형 이기종 병렬 컴퓨팅 표준이다. 플랫폼 독립적인 대신 CUDA보다 복잡하다.
공유 자원에서 발생하는 문제
Data Race는 둘 이상의 스레드가 동시에 같은 메모리에 접근하고, 그중 하나 이상이 쓰기 작업을 수행할 때 발생한다. 결과는 비결정적(Non-deterministic)이며 예측하기 어렵다.
// Data Race 예시
int counter = 0;
void* increment(void* arg) {
for(int i = 0; i < 1000000; i++) {
counter++; // Race condition!
}
}counter++는 읽기, 수정, 쓰기의 3단계로 나뉘기 때문에 스레드가 인터리빙되면 업데이트가 손실될 수 있다.
뮤텍스(Mutex)는 임계 영역(Critical Section)을 보호하기 위한 상호 배제 잠금이다. 한 번에 하나의 스레드만 접근하게 한다.
// Mutex 사용 예시
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;
void* increment(void* arg) {
for(int i = 0; i < 1000000; i++) {
pthread_mutex_lock(&lock);
counter++;
pthread_mutex_unlock(&lock);
}
}세마포어(Semaphore)는 정수 카운터 기반의 동기화 도구다. 이진 세마포어(Binary)는 뮤텍스와 유사하며, 계수 세마포어(Counting)는 제한된 자원에 대한 접근을 제어한다.
// 세마포어 예시 (POSIX)
#include <semaphore.h>
sem_t semaphore;
sem_init(&semaphore, 0, 3); // 최대 3개 스레드 허용
sem_wait(&semaphore); // P 연산 (감소)
// 임계 영역
sem_post(&semaphore); // V 연산 (증가)조건 변수(Condition Variable)는 특정 조건이 만족될 때까지 스레드를 대기시키며, 뮤텍스와 함께 사용해 Busy-waiting을 막는다. Atomic Operations는 하드웨어 수준에서 분할할 수 없는 연산으로, Compare-and-Swap(CAS), Fetch-and-Add 등이 있으며 Lock-free 프로그래밍의 기초가 된다.
// Atomic 예시 (C11)
#include <stdatomic.h>
atomic_int counter = 0;
void* increment(void* arg) {
for(int i = 0; i < 1000000; i++) {
atomic_fetch_add(&counter, 1);
}
}순환 대기를 끊는 설계
데드락(Deadlock)은 둘 이상의 프로세스 또는 스레드가 서로가 보유한 자원을 기다리면서 무한 대기 상태에 빠지는 현상이다. 상호 배제, 점유와 대기, 비선점, 순환 대기가 모두 충족되면 발생할 수 있다.
상호 배제는 자원을 한 번에 하나의 프로세스만 사용하는 상태다. 점유와 대기는 자원을 보유한 채 다른 자원을 기다리는 상태이며, 비선점은 자원을 강제로 빼앗을 수 없다는 뜻이다. 순환 대기는 프로세스 사이에 순환 형태의 대기 관계가 형성되는 경우다.
// 데드락 발생 예시
pthread_mutex_t lock1, lock2;
void* thread1_func(void* arg) {
pthread_mutex_lock(&lock1);
sleep(1); // 의도적 지연
pthread_mutex_lock(&lock2); // Deadlock!
// 작업 수행
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
}
void* thread2_func(void* arg) {
pthread_mutex_lock(&lock2);
sleep(1);
pthread_mutex_lock(&lock1); // Deadlock!
// 작업 수행
pthread_mutex_unlock(&lock1);
pthread_mutex_unlock(&lock2);
}예방(Prevention)은 발생 조건 가운데 하나 이상을 원천적으로 차단하는 접근이다. 대표적으로 모든 스레드가 동일한 순서로 락을 획득하게 할 수 있다.
// 순서 강제 예시
void* safe_thread(void* arg) {
// 항상 lock1 먼저, lock2 나중에
pthread_mutex_lock(&lock1);
pthread_mutex_lock(&lock2);
// 작업 수행
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
}회피(Avoidance)는 Banker's Algorithm 등을 사용해 안전한 상태만 허용하고, 자원 요청마다 데드락 가능성을 검사한다. 탐지 및 복구(Detection and Recovery)는 주기적으로 탐지 알고리즘을 실행해 발견 시 프로세스를 종료하거나 자원을 선점한다. 무시(Ignore)는 Ostrich Algorithm으로, 데드락 발생 확률이 매우 낮을 때 택하는 방법이며 Unix/Linux의 일반적 접근 방식이다.
성능 판단에 남는 제약
암달의 법칙(Amdahl's Law)은 순차 부분이 전체 성능 향상의 한계를 결정한다는 점을 보여준다.
Speedup = 1 / [(1-P) + P/N]
여기서 P는 병렬화 가능한 비율이고 N은 프로세서 수다.
병렬화에는 스레드 생성과 소멸 비용, 동기화 오버헤드, 통신 비용, 캐시 일관성 비용이 따른다. 스레드 풀을 사용하고, 락 경합(Lock Contention)과 통신 횟수를 줄이며, 데이터 지역성을 높이고 False Sharing을 피하는 방식으로 이를 완화할 수 있다.
부하 균형(Load Balancing)도 함께 고려해야 한다. 모든 처리 단위가 균등한 작업량을 처리하도록 구성하고, 동적 스케줄링과 Work Stealing 기법으로 작업량 불균형을 완화한다. 병렬화 방식은 문제의 특성, 하드웨어 환경, 의존성 및 동기화 비용을 함께 보고 선택해야 한다.