[컴파일러] 17. 병렬성 검출과 루프 변환

// 데이터 병렬: 각 반복이 독립적
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

// 태스크 병렬: 세 함수가 독립적
result1 = processA(data)    // 태스크 1
result2 = processB(data)    // 태스크 2
result3 = processC(data)    // 태스크 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

// 흐름 의존성 (진정한 의존성)
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중 루프에서의 의존 벡터
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)

// 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을 나누지 못함 -> 의존성 없음! (병렬화 가능)

// 루프 범위를 고려하여 의존성을 검사
// a[i + 1]과 a[j] (0 <= i,j < n)
// i + 1 = j를 만족하는 (i,j) 쌍이 범위 내에 존재하는가?
// 0 <= i < n이고 0 <= i+1 < n이면 존재
// -> 의존성 있음

// 정확한 의존성 분석이 어려운 경우:

// 1. 간접 배열 접근
a[b[i]] = ...  // b[i]의 값을 알 수 없음

// 2. 포인터를 통한 접근
*p = ...       // p가 가리키는 위치를 알 수 없음

// 3. 함수 호출
foo(a, i)      // foo가 a를 수정하는지 알 수 없음

// 이런 경우 보수적으로 의존성이 있다고 가정 (안전하지만 병렬화 불가)

// 원본: 행 우선 접근 (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) -> 사전식 양수 -> 합법!

// 원본: 행렬 곱셈
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];

// 원본: 두 개의 별도 루프
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;
}

// 원본
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];   // 순차 실행 필요

// 원본 반복 공간: (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) -> 기울어진 반복 공간

// 원본: 의존 벡터 (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(내부 루프)는 병렬 가능

// 다면체 표현:
// 문장 S의 반복 도메인: 0 <= i < n, 0 <= j < m
// 이는 2차원 다면체(직사각형)

// 스케줄 함수: theta(i,j) = (i, j)  (원본 순서)
//            또는 theta(i,j) = (i+j, j) (기울이기)
//            또는 theta(i,j) = (j, i)   (교환)

// 시간적 지역성이 좋은 코드
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]가 외부 루프에서만 재사용

// 공간적 지역성이 좋은 코드 (행 우선 접근, 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], ... 순서로 접근
                           // 매 접근마다 캐시 라인이 다름

// 최적화 없음: O(n^3) 캐시 미스
// 루프 교환: 공간적 지역성 개선
// 타일링 (B x B): O(n^3 / B) 캐시 미스
// 타일링 + 교환: 최적에 가까운 성능

// 실제 성능 차이 (n = 1000, L1 캐시 32KB 기준):
// 최적화 없음:   ~10초
// 루프 교환:     ~5초
// 32x32 타일링:  ~1초
// 성능 차이가 10배에 달할 수 있음!

// 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];

// 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], ...