개요
멀티코어 프로세서와 GPU가 보편화됨에 따라, 프로그램에서 **병렬성**을 찾아내고 활용하는 것이 매우 중요해졌습니다. 컴파일러는 프로그램을 분석하여 안전하게 병렬 실행할 수 있는 부분을 자동으로 검출하고, 루프 변환을 통해 병렬성과 지역성을 모두 향상시킬 수 있습니다.
1. 병렬성의 유형
1.1 데이터 병렬성 (Data Parallelism)
같은 연산을 서로 다른 데이터에 대해 동시에 수행합니다.
// 데이터 병렬: 각 반복이 독립적
for (i = 0; i < n; i++) {
c[i] = a[i] + b[i];
}
// 4개 프로세서로 분할 실행:
// P0: i = 0..n/4-1
// P1: i = n/4..n/2-1
// P2: i = n/2..3n/4-1
// P3: i = 3n/4..n-1
1.2 태스크 병렬성 (Task Parallelism)
서로 다른 작업을 동시에 수행합니다.
// 태스크 병렬: 세 함수가 독립적
result1 = processA(data) // 태스크 1
result2 = processB(data) // 태스크 2
result3 = processC(data) // 태스크 3
// 세 태스크를 동시에 실행 가능
1.3 파이프라인 병렬성
데이터를 단계별로 처리하며, 각 단계를 서로 다른 프로세서가 담당합니다.
// 3단계 파이프라인:
// Stage 1: read -> P0
// Stage 2: process -> P1
// Stage 3: write -> P2
// 시간: 1 2 3 4 5
// P0: read1 read2 read3 read4 read5
// P1: proc1 proc2 proc3 proc4
// P2: wrt1 wrt2 wrt3
2. 의존성 분석 (Dependence Analysis)
루프를 병렬화하려면 반복 간의 의존성을 분석해야 합니다.
2.1 루프 의존성의 종류
// 흐름 의존성 (진정한 의존성)
for (i = 1; i < n; i++) {
a[i] = a[i-1] + 1; // 반복 i가 반복 i-1의 결과에 의존
}
// 의존 거리(distance) = 1, 병렬화 불가
// 반의존성
for (i = 0; i < n-1; i++) {
a[i] = a[i+1] + 1; // 읽기 후 쓰기
}
// 순서를 역전하면 해결 가능
// 출력 의존성
for (i = 0; i < n; i++) {
a[i % 2] = b[i]; // 같은 위치에 반복적으로 쓰기
}
2.2 의존 벡터와 의존 거리
다중 중첩 루프에서 의존성을 벡터로 표현합니다.
// 2중 루프에서의 의존 벡터
for (i = 1; i < n; i++) {
for (j = 1; j < m; j++) {
a[i][j] = a[i-1][j-1] + 1;
}
}
// a[i][j]는 a[i-1][j-1]에 의존
// 의존 벡터: (1, 1) (i방향 거리 1, j방향 거리 1)
2.3 배열 의존성 테스트
두 배열 접근이 같은 위치를 참조하는지 판별하는 테스트입니다.
**GCD 테스트** (필요 조건):
// a[c1*i + c2]와 a[c3*j + c4]가 같은 위치를 참조하려면
// c1*i + c2 = c3*j + c4를 만족하는 정수 i, j가 존재해야 함
// -> gcd(c1, c3)이 (c4 - c2)를 나누어야 함
// 예시:
// a[2*i + 1]과 a[2*j]
// gcd(2, 2) = 2, c4 - c2 = 0 - 1 = -1
// 2는 -1을 나누지 못함 -> 의존성 없음! (병렬화 가능)
**Banerjee 테스트** (더 정밀한 검사):
// 루프 범위를 고려하여 의존성을 검사
// a[i + 1]과 a[j] (0 <= i,j < n)
// i + 1 = j를 만족하는 (i,j) 쌍이 범위 내에 존재하는가?
// 0 <= i < n이고 0 <= i+1 < n이면 존재
// -> 의존성 있음
2.4 의존성 분석의 한계
// 정확한 의존성 분석이 어려운 경우:
// 1. 간접 배열 접근
a[b[i]] = ... // b[i]의 값을 알 수 없음
// 2. 포인터를 통한 접근
*p = ... // p가 가리키는 위치를 알 수 없음
// 3. 함수 호출
foo(a, i) // foo가 a를 수정하는지 알 수 없음
// 이런 경우 보수적으로 의존성이 있다고 가정 (안전하지만 병렬화 불가)
3. 루프 변환
3.1 루프 교환 (Loop Interchange)
중첩 루프의 순서를 바꾸는 변환입니다. 병렬성 노출이나 메모리 지역성 향상에 사용됩니다.
// 원본: 행 우선 접근 (C에서는 이미 최적)
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
a[i][j] = 0;
// 교환 후: 열 우선 접근
for (j = 0; j < m; j++)
for (i = 0; i < n; i++)
a[i][j] = 0;
교환이 합법적인 조건: **의존 벡터의 사전식 순서가 유지**되어야 합니다.
// 의존 벡터 (1, -1)인 경우:
// 교환 후 (-1, 1) -> 첫 성분이 음수 -> 불법!
//
// 의존 벡터 (1, 0)인 경우:
// 교환 후 (0, 1) -> 사전식 양수 -> 합법!
3.2 루프 타일링 / 블로킹 (Loop Tiling/Blocking)
루프를 작은 타일(블록)로 나누어 캐시 활용도를 높입니다.
// 원본: 행렬 곱셈
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j];
// 타일링 후 (타일 크기 T):
for (ii = 0; ii < n; ii += T)
for (jj = 0; jj < n; jj += T)
for (kk = 0; kk < n; kk += T)
for (i = ii; i < min(ii+T, n); i++)
for (j = jj; j < min(jj+T, n); j++)
for (k = kk; k < min(kk+T, n); k++)
c[i][j] += a[i][k] * b[k][j];
타일 크기 T를 캐시 크기에 맞추면:
- a, b, c의 T x T 부분 행렬이 캐시에 들어감
- 캐시 미스가 O(n^3)에서 O(n^3/T)로 감소
3.3 루프 융합 (Loop Fusion)
같은 범위를 순회하는 여러 루프를 하나로 합칩니다.
// 원본: 두 개의 별도 루프
for (i = 0; i < n; i++)
a[i] = b[i] + 1;
for (i = 0; i < n; i++)
c[i] = a[i] * 2;
// 융합 후: 하나의 루프
for (i = 0; i < n; i++) {
a[i] = b[i] + 1;
c[i] = a[i] * 2;
}
융합의 장점:
- 루프 오버헤드 감소
- `a[i]`를 레지스터에 유지 가능 (메모리 접근 감소)
- 데이터 지역성 향상
융합 조건: 두 루프 사이에 의존성 방향이 역전되지 않아야 합니다.
3.4 루프 분열 (Loop Fission/Distribution)
하나의 루프를 여러 루프로 나눕니다.
// 원본
for (i = 0; i < n; i++) {
a[i] = b[i] + 1; // 독립적 부분 1
c[i] = c[i-1] + a[i]; // 의존적 부분 2
}
// 분열 후
for (i = 0; i < n; i++)
a[i] = b[i] + 1; // 병렬화 가능!
for (i = 0; i < n; i++)
c[i] = c[i-1] + a[i]; // 순차 실행 필요
분열의 장점:
- 병렬화 가능한 부분만 분리하여 병렬 실행
- 각 루프의 작업 집합(working set)이 작아져 캐시 효율 향상
4. 아핀 변환 이론 기초
4.1 아핀 변환이란
루프의 반복 공간을 선형 변환하여 병렬성과 지역성을 동시에 최적화하는 통합 프레임워크입니다.
// 원본 반복 공간: (i, j)
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
S: a[i][j] = ...
// 아핀 변환: 새로운 반복 변수 (p, q) = T * (i, j)
// 예: (p, q) = (i+j, j) -> 기울어진 반복 공간
4.2 기울이기 변환 (Skewing)
의존성 방향을 변경하여 병렬성을 노출합니다.
// 원본: 의존 벡터 (0,1)과 (1,0) -> 두 차원 모두 순차적
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = (a[i-1][j] + a[i][j-1]) / 2;
// 기울이기: p = i + j, q = j
// 변환 후 같은 p 값을 가진 반복들은 병렬 실행 가능
// 변환 후 의존 벡터: (1,1), (1,0) -> p(외부 루프)는 순차, q(내부 루프)는 병렬 가능
4.3 다면체 모델 (Polyhedral Model)
아핀 변환을 일반화한 프레임워크로, 현대 자동 병렬화 컴파일러(Polly, Pluto)에서 사용됩니다.
각 문장의 반복 도메인을 다면체로, 의존성을 아핀 관계로, 스케줄을 아핀 함수로 표현합니다.
// 다면체 표현:
// 문장 S의 반복 도메인: 0 <= i < n, 0 <= j < m
// 이는 2차원 다면체(직사각형)
// 스케줄 함수: theta(i,j) = (i, j) (원본 순서)
// 또는 theta(i,j) = (i+j, j) (기울이기)
// 또는 theta(i,j) = (j, i) (교환)
5. 지역성 최적화 (Locality Optimization)
5.1 시간적 지역성 (Temporal Locality)
최근에 접근한 데이터를 곧 다시 접근하는 성질입니다.
// 시간적 지역성이 좋은 코드
for (i = 0; i < n; i++) {
sum += a[i]; // sum이 매 반복 재사용됨
}
// 시간적 지역성이 나쁜 코드 (타일링으로 개선 가능)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
b[j] += a[i][j]; // b[j]가 외부 루프에서만 재사용
5.2 공간적 지역성 (Spatial Locality)
인접한 메모리 위치를 연속으로 접근하는 성질입니다.
// 공간적 지역성이 좋은 코드 (행 우선 접근, C 배열 레이아웃과 일치)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = 0; // a[i][0], a[i][1], ... 순서로 접근
// 공간적 지역성이 나쁜 코드 (열 우선 접근)
for (j = 0; j < n; j++)
for (i = 0; i < n; i++)
a[i][j] = 0; // a[0][j], a[1][j], ... 순서로 접근
// 매 접근마다 캐시 라인이 다름
5.3 지역성과 루프 변환의 관계
| 변환 | 시간적 지역성 | 공간적 지역성 | 병렬성 |
| ----------- | ------------- | ------------- | ------ |
| 루프 교환 | 간접적 | 직접적 | 가능 |
| 루프 타일링 | 직접적 | 간접적 | 간접적 |
| 루프 융합 | 직접적 | 간접적 | 가능 |
| 루프 분열 | 간접적 | 직접적 | 직접적 |
5.4 행렬 곱셈의 최적화 효과
// 최적화 없음: O(n^3) 캐시 미스
// 루프 교환: 공간적 지역성 개선
// 타일링 (B x B): O(n^3 / B) 캐시 미스
// 타일링 + 교환: 최적에 가까운 성능
// 실제 성능 차이 (n = 1000, L1 캐시 32KB 기준):
// 최적화 없음: ~10초
// 루프 교환: ~5초
// 32x32 타일링: ~1초
// 성능 차이가 10배에 달할 수 있음!
6. 자동 병렬화의 실제
6.1 DOALL 루프
모든 반복이 독립적인 루프를 **DOALL** 루프라 합니다.
// DOALL: 완전 병렬화 가능
for (i = 0; i < n; i++)
a[i] = b[i] + c[i];
// OpenMP로 자동 변환:
// #pragma omp parallel for
// for (i = 0; i < n; i++)
// a[i] = b[i] + c[i];
6.2 DOACROSS 루프
반복 간에 의존성이 있지만 파이프라인 방식으로 병렬화할 수 있는 루프입니다.
// DOACROSS: 의존 거리 만큼의 병렬성 존재
for (i = 1; i < n; i++)
a[i] = a[i-1] + b[i]; // 의존 거리 1
// 파이프라인 병렬화:
// P0: a[0], a[4], a[8], ...
// P1: (대기) a[1], a[5], a[9], ...
// P2: (대기) (대기) a[2], a[6], ...
// P3: (대기) (대기) (대기) a[3], a[7], ...
정리
| 개념 | 설명 |
| ------------- | ------------------------------------------------ |
| 데이터 병렬성 | 같은 연산을 서로 다른 데이터에 동시 수행 |
| 의존성 분석 | 루프 반복 간의 데이터 의존 관계 파악 |
| GCD 테스트 | 배열 의존성의 필요 조건 검사 |
| 루프 교환 | 중첩 루프의 순서 변경 |
| 루프 타일링 | 루프를 작은 블록으로 분할하여 캐시 활용 극대화 |
| 루프 융합 | 여러 루프를 하나로 합침 |
| 루프 분열 | 하나의 루프를 여러 개로 분리 |
| 아핀 변환 | 반복 공간의 선형 변환으로 병렬성과 지역성 최적화 |
| 지역성 최적화 | 캐시 활용을 극대화하는 메모리 접근 패턴 최적화 |
병렬성 검출과 루프 변환은 멀티코어 시대의 핵심 컴파일러 기술입니다. 정확한 의존성 분석을 바탕으로 다양한 루프 변환을 적용하면, 프로그래머가 명시적으로 병렬화하지 않아도 컴파일러가 자동으로 병렬 코드를 생성할 수 있습니다. 다음 글에서는 프로시저 간 분석과 포인터 분석을 다루겠습니다.
현재 단락 (1/221)
멀티코어 프로세서와 GPU가 보편화됨에 따라, 프로그램에서 **병렬성**을 찾아내고 활용하는 것이 매우 중요해졌습니다. 컴파일러는 프로그램을 분석하여 안전하게 병렬 실행할 수 있는...