폴리토프 모형

다면 모델(폴리토프 방식이라고도 함)은 너무 커서 명시적으로 열거할 수 없는 많은 수의 연산을 수행하는 프로그램을 위한 수학적 프레임워크로서, 따라서 콤팩트한 표현이 필요하다.내포된 루프 프로그램은 전형적이지만 유일한 예는 아니며, 모델의 가장 일반적인 용도는 프로그램 최적화에서 루프 중첩 최적화를 위한 것이다.다면체 방법은 내포된 루프 내의 각 루프 반복을 다면체라고 불리는 수학적 객체 내부의 격자 점으로 처리하고, 아핀 변환이나 보다 일반적인 비아핀 변환을 수행하며, 변환된 다면체 변환을 등가지만 최적화(타겟 최적화에 따라 다름)로 변환한다.골인), 다면체 스캔을 통해 루프 보금자리.

간단한 예

C로 작성된 다음 예를 고려하십시오.

  경시하다 인트로 n = 100;   인트로 i, j, a[n][n];   을 위해 (i = 1; i < n; i++) {     을 위해 (j = 1; j < (i + 2) && j < n; j++) {       a[i][j] = a[i - 1][j] + a[i][j - 1];     }   } 

이 코드의 본질적인 문제는 내측 루프의 각 반복이a[i][j]이전 반복의 결과를 요구하지만a[i][j - 1], 이미 사용 가능.따라서 이 코드는 현재 작성된 것처럼 병렬화하거나 파이프라인으로 연결할 수 없다.

아핀 변환$({\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$, ${\displaystyle j{}^{}}$ ${\displaystyle {\prime }^{}}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle i}$+ j${\displaystyle }$, ${\displaystyle j}$) ${\displaystyle (i',\,j')=(i+j,\,j)=($i+j)}과 함께$$ 폴리토프 모델을 적용하면 위의 중첩된 루프가 다음과 같이 변환된다.

      a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1]; 

이 경우 내측 루프의 반복은 이전 반복의 결과에 따라 달라진다. 전체 내측 루프는 병렬로 실행될 수 있다.(단, 외부 루프의 각 반복은 이전 반복에 따라 달라진다.)

상세 예시

의 종속성src루프가 기울어지기 전에.빨간색 점은 다음과 같다.src[1][0]; 분홍색 점은 에 해당한다.src[2][2].

다음의 C 코드는 플로이드-스타인버그 디더링과 유사하지만 교육학적 이유로 수정된 오류 분배 디더링의 형태를 구현한다.2차원 배열src포함하다h한 줄로 늘어선w각 픽셀의 그레이스케일 값이 0에서 255 사이인 픽셀.루틴이 완료된 후 출력 어레이dst값이 0 또는 값이 255인 픽셀만 포함할 것이다.계산하는 동안 각 픽셀의 디더링 오차는 다시 에 추가함으로써 수집된다.src배열. (알림)src그리고dst계산 중에 읽거나 쓰일 수 있다.src읽기 전용이 아니며dst쓰기 전용이 아니다.)

내측 루프의 각 반복은 다음 값을 수정한다.src[i][j]의 가치에 근거하여src[i-1][j],src[i][j-1]그리고src[i+1][j-1]. (동일한 종속성이 적용됨dst[i][j]. 루프 왜곡의 목적으로, 우리는 다음과 같이 생각할 수 있다.src[i][j]그리고dst[i][j]같은 원소로)의 의존성을 설명할 수 있다.src[i][j]오른쪽의 도표와 같이 그래픽으로 표시한다.

#정의 ERR(x, y) (dst[x][y] - src[x][y])  공허하게 하다 디더더(서명이 없는 마를 뜨다** src, 서명이 없는 마를 뜨다** dst, 인트로 w, 인트로 h) {     인트로 i, j;     을 위해 (j = 0; j < h; ++j) {         을 위해 (i = 0; i < w; ++i) {             인트로 v = src[i][j];             만일 (i > 0)                 v -= ERR(i - 1, j) / 2;             만일 (j > 0) {                 v -= ERR(i, j - 1) / 4;                 만일 (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, 루프 왜곡 후.배열 요소는 회색, 빨간색, 녹색, 파란색, 노란색 순으로 처리된다.

원본 종속성 다이어그램에서$$ 아핀 변환$({\displaystyle p}$, ${\displaystyle t}$)${\displaystyle }$=${\displaystyle }$( i${\displaystyle }$, ${\displaystyle 2}$ ${\displaystyle j\mathrm{}}$+ i${\displaystyle }$) ${\displaystyle(p,\,t)=(i,\,2j+i)}$을 수행하면 다음 이미지에 나와 있는 새로운 다이어그램이 제공된다.그런 다음 코드를 다시 작성해서p그리고t대신에i그리고j다음과 같은 "혼인" 루틴을 얻는다.

 공허하게 하다 디더_스위드(서명이 없는 마를 뜨다 **src, 서명이 없는 마를 뜨다 **dst, 인트로 w, 인트로 h)    {      인트로 t, p;      을 위해 (t = 0; t < (w + (2 * h)); ++t) {          인트로 pmin = 맥스.(t % 2, t - (2 * h) + 2);          인트로 pmax. = 분(t, w - 1);          을 위해 (p = pmin; p <= pmax.; p += 2) {              인트로 i = p;              인트로 j = (t - p) / 2;              인트로 v = src[i][j];              만일 (i > 0)                v -= ERR(i - 1, j) / 2;              만일 (j > 0)                v -= ERR(i, j - 1) / 4;              만일 (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;          }      }  } 

참고 항목

• 다면 모델을 지원하는 프레임워크
• 루프 중첩 최적화
• 루프 최적화
• 루프 언롤링
• 루프 타일링

외부 링크 및 참조

• 위의 유사 코드 예제의 다이어그램을 포함하는 마틴 그리블의 "기본 폴리토프 방법" 자습서
• "폴리토프 모델에서의 코드 생성"(1998년).마틴 그리블, 크리스티안 렝가워, 사빈 웨첼
• "CLOOG 다면 코드 생성기"
• "CodeGen+: Z-폴리헤드라 스캔"^{[영구적 데드링크]}
• PoCC: 다면 컴파일러 모음
• 명왕성 - 부착 루프 둥지를 위한 자동 병렬 처리기 및 위치 최적화 도구
  • Bondhugula, Uday; Hartono, Albert; Ramanujam, J.; Sadayappan, P. (2008-01-01). A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '08. New York, NY, USA: ACM. pp. 101–113. doi:10.1145/1375581.1375595. ISBN 9781595938602. S2CID 7086982.
• polyhedral.info - 다면체 컴파일에 대한 정보를 수집하는 웹 사이트
• Polly - 높은 수준의 루프 및 데이터 인접성 최적화를 위한 LLVM 프레임워크
• MIT 티라미수 다면체 프레임워크.