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

// Data parallel: each iteration is independent
for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

// Split execution across 4 processors:
// 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

// Task parallel: three functions are independent
result1 = processA(data)    // Task 1
result2 = processB(data)    // Task 2
result3 = processC(data)    // Task 3
// All three tasks can execute simultaneously

// 3-stage pipeline:
// Stage 1: read    -> P0
// Stage 2: process -> P1
// Stage 3: write   -> P2

// Time:   1      2      3      4      5
// P0:   read1  read2  read3  read4  read5
// P1:          proc1  proc2  proc3  proc4
// P2:                 wrt1   wrt2   wrt3

// Flow dependence (true dependence)
for (i = 1; i < n; i++) {
    a[i] = a[i-1] + 1;  // Iteration i depends on result of iteration i-1
}
// Dependence distance = 1, cannot parallelize

// Anti-dependence
for (i = 0; i < n-1; i++) {
    a[i] = a[i+1] + 1;  // Read then write
}
// Can be resolved by reversing order

// Output dependence
for (i = 0; i < n; i++) {
    a[i % 2] = b[i];    // Repeatedly writing to the same location
}

// Dependence vector in a doubly-nested loop
for (i = 1; i < n; i++) {
    for (j = 1; j < m; j++) {
        a[i][j] = a[i-1][j-1] + 1;
    }
}

// a[i][j] depends on a[i-1][j-1]
// Dependence vector: (1, 1)  (distance 1 in i-direction, distance 1 in j-direction)

// For a[c1*i + c2] and a[c3*j + c4] to reference the same location
// there must exist integers i, j satisfying c1*i + c2 = c3*j + c4
// -> gcd(c1, c3) must divide (c4 - c2)

// Example:
// a[2*i + 1] and a[2*j]
// gcd(2, 2) = 2, c4 - c2 = 0 - 1 = -1
// 2 does not divide -1 -> no dependence! (can parallelize)

// Tests dependence considering loop bounds
// a[i + 1] and a[j] (0 <= i,j < n)
// Does a pair (i,j) satisfying i + 1 = j exist within bounds?
// If 0 <= i < n and 0 <= i+1 < n, then yes
// -> dependence exists

// Cases where precise dependence analysis is difficult:

// 1. Indirect array access
a[b[i]] = ...  // Value of b[i] is unknown

// 2. Pointer-based access
*p = ...       // Location pointed to by p is unknown

// 3. Function calls
foo(a, i)      // Unknown whether foo modifies a

// In such cases, conservatively assume dependence exists (safe but cannot parallelize)

// Original: row-major access (already optimal in C)
for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
        a[i][j] = 0;

// After interchange: column-major access
for (j = 0; j < m; j++)
    for (i = 0; i < n; i++)
        a[i][j] = 0;

// Dependence vector (1, -1):
// After interchange (-1, 1) -> first component is negative -> illegal!
//
// Dependence vector (1, 0):
// After interchange (0, 1) -> lexicographically positive -> legal!

// Original: matrix multiplication
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];

// After tiling (tile size 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];

// Original: two separate loops
for (i = 0; i < n; i++)
    a[i] = b[i] + 1;

for (i = 0; i < n; i++)
    c[i] = a[i] * 2;

// After fusion: one loop
for (i = 0; i < n; i++) {
    a[i] = b[i] + 1;
    c[i] = a[i] * 2;
}

// Original
for (i = 0; i < n; i++) {
    a[i] = b[i] + 1;        // Independent part 1
    c[i] = c[i-1] + a[i];   // Dependent part 2
}

// After fission
for (i = 0; i < n; i++)
    a[i] = b[i] + 1;        // Can be parallelized!

for (i = 0; i < n; i++)
    c[i] = c[i-1] + a[i];   // Must execute sequentially

// Original iteration space: (i, j)
for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
        S: a[i][j] = ...

// Affine transformation: new iteration variables (p, q) = T * (i, j)
// Example: (p, q) = (i+j, j) -> skewed iteration space

// Original: dependence vectors (0,1) and (1,0) -> both dimensions are sequential
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        a[i][j] = (a[i-1][j] + a[i][j-1]) / 2;

// Skewing: p = i + j, q = j
// After transformation, iterations with the same p value can execute in parallel

// Transformed dependence vectors: (1,1), (1,0) -> p (outer loop) is sequential, q (inner loop) can be parallel

// Polyhedral representation:
// Iteration domain of statement S: 0 <= i < n, 0 <= j < m
// This is a 2D polyhedron (rectangle)

// Schedule function: theta(i,j) = (i, j)    (original order)
//                    or theta(i,j) = (i+j, j) (skewing)
//                    or theta(i,j) = (j, i)   (interchange)

// Good temporal locality
for (i = 0; i < n; i++) {
    sum += a[i];  // sum is reused every iteration
}

// Poor temporal locality (can be improved by tiling)
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        b[j] += a[i][j];  // b[j] is reused only in the outer loop

// Good spatial locality (row-major access, matches C array layout)
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        a[i][j] = 0;      // Access a[i][0], a[i][1], ... in order

// Poor spatial locality (column-major access)
for (j = 0; j < n; j++)
    for (i = 0; i < n; i++)
        a[i][j] = 0;      // Access a[0][j], a[1][j], ... in order
                           // Different cache line for each access

// No optimization: O(n^3) cache misses
// Loop interchange: improved spatial locality
// Tiling (B x B): O(n^3 / B) cache misses
// Tiling + interchange: near-optimal performance

// Actual performance difference (n = 1000, L1 cache 32KB):
// No optimization:   ~10 seconds
// Loop interchange:  ~5 seconds
// 32x32 tiling:      ~1 second
// Performance difference can be up to 10x!

// DOALL: fully parallelizable
for (i = 0; i < n; i++)
    a[i] = b[i] + c[i];

// Automatic conversion to OpenMP:
// #pragma omp parallel for
// for (i = 0; i < n; i++)
//     a[i] = b[i] + c[i];

// DOACROSS: parallelism exists up to the dependence distance
for (i = 1; i < n; i++)
    a[i] = a[i-1] + b[i];  // Dependence distance 1

// Pipeline parallelization:
// P0: a[0], a[4], a[8], ...
// P1: (wait) a[1], a[5], a[9], ...
// P2: (wait) (wait) a[2], a[6], ...
// P3: (wait) (wait) (wait) a[3], a[7], ...