대규모 연산을 수행하는 중첩 루프 프로그램을 격자점과 폴리토프로 모델링하고, 아핀/비아핀 변환(예: 스큐잉, 타일링)으로 병렬화와 지역성 향상을 달성하는 폴리헤드럴(폴리토프) 모델을 C 예제와 함께 설명한다.
위키백과, 우리 모두의 백과사전
폴리헤드럴 모델(폴리토프 방법이라고도 함)은 너무 많아 명시적으로 열거할 수 없는 대량의 연산을 수행하는 프로그램을 위해, 압축된(compact) 표현을 제공하는 수학적 프레임워크이다. 중첩 루프 프로그램이 대표적이지만 유일한 예는 아니며, 이 모델의 가장 일반적인 활용은 프로그램 최적화에서의 루프 중첩 최적화이다. 폴리헤드럴 기법은 중첩 루프 내의 각 루프 반복을 폴리토프라고 불리는 수학적 객체 내부의 격자점으로 취급하고, 폴리토프에 아핀 변환 또는 타일링과 같은 보다 일반적인 비아핀 변환을 수행한 뒤, 변환된 폴리토프를 폴리토프 스캐닝을 통해 동등하지만 목표 최적화 목적에 따라 최적화된 루프 중첩으로 되돌린다.
다음은 C로 작성된 예제이다:
const int n = 100; int i, j; int a[n][n] = {{0,1}};
for (i = 1; i < n; i++) { for (j = 1; j < (i + 2) && j < n; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1]; } }
for (i = 0; i < n; i++) { for (j = 0; j < n; ++j) { printf("%4d ", a[i][j]); } puts(""); }
이 코드의 본질적 문제는, 내부 루프의 각 반복에서 a[i][j]를 계산하려면 이전 반복의 결과인 a[i][j - 1]이 이미 준비되어 있어야 한다는 점이다. 따라서 이 코드는 현재 형태로는 병렬화하거나 파이프라인화할 수 없다.
아핀 변환 (i', j') = (i + j, j)와 경계의 적절한 변경을 적용하면, 위의 중첩 루프는 다음과 같이 변환된다:
a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];
이 경우, 내부 루프의 어떤 반복도 이전 반복의 결과에 의존하지 않는다. 즉, 내부 루프 전체를 병렬로 실행할 수 있다. 실제로 a(i, j) = a[i - j][j]라고 두면, a(i, j)는 x ∈ {j - 1, j}인 a(i - 1, x)에만 의존한다. (다만, 외부 루프의 각 반복은 이전 반복들에 의존한다.)
루프 스큐잉 전에 src의 의존성. 빨간 점은 src[1][0]에, 분홍 점은 src[2][2]에 해당한다.
다음 C 코드는 Floyd–Steinberg 디더링과 유사한 오차 분배 디더링을 구현하되, 교육적 목적을 위해 일부 수정된 형태이다. 2차원 배열 src에는 높이 h, 너비 w의 픽셀이 들어 있으며, 각 픽셀은 0부터 255 사이의 그레이스케일 값을 가진다. 루틴이 끝난 뒤 출력 배열 dst에는 값 0 또는 255만 남게 된다. 계산 중 각 픽셀의 디더링 오차는 src 배열에 되돌려 더하는 방식으로 누적된다. (src와 dst는 계산 중 읽기와 쓰기를 모두 수행한다. 즉, src는 읽기 전용이 아니고 dst는 쓰기 전용이 아니다.)
내부 루프의 각 반복은 src[i - 1][j], src[i][j - 1], src[i + 1][j - 1]의 값을 바탕으로 src[i][j]의 값을 변경한다. (동일한 의존성이 dst[i][j]에도 적용된다. 루프 스큐잉의 관점에서는 src[i][j]와 dst[i][j]를 동일한 요소로 볼 수 있다.) 이러한 src[i][j]의 의존성을 오른쪽 그림처럼 그래프로 나타낼 수 있다.
#define ERR(x, y) (dst[x][y] - src[x][y])
void dither(unsigned char** src, unsigned char** dst, int w, int h) { int i, j; for (j = 0; j < h; ++j) { for (i = 0; i < w; ++i) { int v = src[i][j]; if (i > 0) v -= ERR(i - 1, j) / 2; if (j > 0) { v -= ERR(i, j - 1) / 4; if (i < w - 1) v -= ERR(i + 1, j - 1) / 4; } dst[i][j] = (v < 128) ? 0 : 255; src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255; } } }
루프 스큐잉 후 src의 의존성. 배열 원소들은 회색, 빨강, 초록, 파랑, 노랑… 순서로 처리된다.
원래의 의존성 다이어그램에 아핀 변환 (p, t) = (i, 2j + i)를 적용하면 새로운 다이어그램을 얻을 수 있으며, 다음 그림에 제시되어 있다. 그런 다음 i와 j 대신 p와 t에 대해 루프를 돌도록 코드를 다시 작성하면 다음과 같은 “스큐된(skewed)” 루틴을 얻는다.
void dither_skewed(unsigned char **src, unsigned char **dst, int w, int h) { int t, p; for (t = 0; t < (w + (2 * h)); ++t) { int pmin = max(t % 2, t - (2 * h) + 2); int pmax = min(t, w - 1); for (p = pmin; p <= pmax; p += 2) { int i = p; int j = (t - p) / 2; int v = src[i][j]; if (i > 0) v -= ERR(i - 1, j) / 2; if (j > 0) v -= ERR(i, j - 1) / 4; if (j > 0 && i < w - 1) v -= ERR(i + 1, j - 1) / 4; dst[i][j] = (v < 128) ? 0 : 255; src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255; } } }
[편집]
"The basic polytope method", 위의 의사코드 예제를 포함한 Martin Griebl의 튜토리얼
"Code Generation in the Polytope Model" (1998). Martin Griebl, Christian Lengauer, and Sabine Wetzel
PLUTO - 아핀 루프 중첩을 위한 자동 병렬화 및 지역성 최적화 도구
polyhedral.info - 폴리헤드럴 컴파일에 관한 정보를 모으는 웹사이트
MIT Tiramisu Polyhedral 프레임워크.
