루프 네스트 최적화

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : "Loop nest optimization"– 뉴스 · 신문 · 서적 · 학자 · JSTOR ( 2021년 1월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

컴퓨터 과학, 특히 컴파일러 설계에서 루프 네스트 최적화(LNO)는 지역 최적화 또는 병렬화 또는 루프 네스트의 다른 루프 오버헤드 감소를 목적으로 루프 변환 세트를 적용하는 최적화 기술입니다.(내스트된 루프는 어떤 루프가 다른 루프의 내부에 있을 때 발생합니다).일반적인 선형 대수 알고리즘의 캐시 재사용에 필요한 메모리 액세스 지연 또는 캐시 대역폭을 줄이는 것이 일반적인 사용 방법입니다.

이 최적화를 실현하기 위해 사용되는 기술을 루프 ^[1]타일링이라고 하며 루프^[2] 블로킹 또는 스트립 마이닝 및 인터체인지라고도 합니다.

개요

루프 타일링은 루프의 반복 공간을 더 작은 청크 또는 블록으로 분할하여 루프에서 사용되는 데이터가 재사용될 때까지 캐시에 유지되도록 합니다.루프 반복 공간을 분할하면 대규모 어레이가 더 작은 블록으로 분할되므로 액세스된 어레이 요소가 캐시 크기에 맞게 조정되므로 캐시 재사용이 향상되고 캐시 크기가 필요하지 않습니다.

통상 루프

위해서 (i=0; i< >N; ++i) {   ... } 

블록 사이즈 B로 치환하여 블록할 수 있다

위해서 (j=0; j< >N; j+=B) {   위해서 (i=j; i< >분(N, j+B); ++i) {     ....   } } 

어디에min()는 인수의 최소값을 반환하는 함수입니다.

예: 행렬-벡터 곱셈

다음은 행렬 벡터 곱셈의 예입니다.3개의 어레이가 있으며 각각 100개의 요소가 있습니다.이 코드는 어레이를 작은 크기로 분할하지 않는다.

  인트 i, j, a[100][100], b[100], c[100];   인트 n = 100;   위해서 (i = 0; i < > n; i++) {     c[i] = 0;     위해서 (j = 0; j < > n; j++) {       c[i] = c[i] + a[i][j] * b[j];     }   } 

2 x 2 블록을 사용하여 루프 타일링을 적용한 후 코드는 다음과 같습니다.

  인트 i, j, x, y, a[100][100], b[100], c[100];   인트 n = 100;   위해서 (i = 0; i < > n; i += 2) {     c[i] = 0;     c[i + 1] = 0;     위해서 (j = 0; j < > n; j += 2) {       위해서 (x = i; x < > 분(i + 2, n); x++) {         위해서 (y = j; y < > 분(j + 2, n); y++) {           c[x] = c[x] + a[x][y] * b[y];         }       }     }   } 

원래 루프 반복 공간은 nxn 입니다.어레이 a[i, j]의 액세스 청크도 n by n입니다.n이 너무 크고 시스템의 캐시 크기가 너무 작을 경우 액세스된 어레이 요소가 하나의 루프 반복에 포함됩니다(예:i = 1,j = 1 to n)가 캐시 회선을 교차하여 캐시 누락의 원인이 될 수 있습니다.

타일 크기

루프 내에서 액세스되는 어레이 영역과 타깃 머신의 캐시 크기를 정확하게 추정해야 하기 때문에 하나의 루프에 최적의 타일 크기 값을 결정하는 것이 항상 쉬운 일은 아닙니다.루프 네스트의 순서(루프 교환)도 캐시 퍼포먼스를 향상시키는 데 중요한 역할을 합니다.명시적 차단은 이러한 요인에 따라 타일 크기를 선택해야 합니다.반면 캐시 오비어스 알고리즘은 명시적인 차단 없이 캐시를 효율적으로 사용하도록 설계되었습니다.

예: 행렬 곱셈

컴퓨터의 많은 큰 수학 연산은 결국 행렬 곱셈에 많은 시간을 소비하게 됩니다.조작은 다음과 같습니다.

C = A×B

여기서 A, B 및 C는 N×N 배열입니다.아래 설명에 대한 첨자는 형식입니다.C[row][column].

기본 루프는 다음과 같습니다.

인트 i, j, k;  위해서 (i = 0; i < > N; ++i) {     위해서 (j = 0; j < > N; ++j)     {         C[i][j] = 0;          위해서 (k = 0; k < > N; ++k)             C[i][j] += A[i][k] * B[k][j];     } } 

해결해야 할 세 가지 문제가 있습니다.

• 부동 소수점 추가는 완료하는 데 몇 가지 사이클이 소요됩니다.여러 사이클의 지연이 있는 가산기를 계속 비지 상태로 유지하려면 코드가 여러 개의 누적기를 병렬로 업데이트해야 합니다.
• 일반적으로 시스템은 다중 추가당 메모리 작업을 한 번만 수행할 수 있으므로 로드된 값을 적어도 두 번 재사용해야 합니다.
• 일반적인 PC 메모리시스템은 10~30배 정밀도의 다중 애드당8바이트 더블워드를 1개밖에 유지할 수 없기 때문에 캐시에 로드된 값은 여러 번 재사용해야 합니다.

원래 루프는 결과 매트릭스 내의 1개의 엔트리에 대한 결과를 한 번에 계산합니다.엔트리의 작은 블록을 동시에 계산함으로써 다음 루프는 로드된 각 값을 2회 재사용하여 내부 루프가 4개의 부하와 4개의 곱셈을 가지도록 하여 문제 #2를 해결합니다.4개의 어큐뮬레이터를 동시에 반송함으로써 이 코드는 레이텐시가 4인 부동소수점 가산기 1개를 거의 항상 비지 상태로 유지할 수 있습니다(문제 #1).단, 이 코드는 세 번째 문제에 대응하고 있지 않습니다.(N이 홀수일 때 필요한 청소 작업도 다루지 않습니다.이러한 세부 사항은 다음 논의에서 제외됩니다.)

위해서 (i = 0; i < > N; i += 2) {     위해서 (j = 0; j < > N; j += 2)     {         액세스 = acc01 = 액세스 10 = 액세스 11 = 0;         위해서 (k = 0; k < > N; k++)         {             액세스 += B[k][j + 0] * A[i + 0][k];             acc01 += B[k][j + 1] * A[i + 0][k];             액세스 10 += B[k][j + 0] * A[i + 1][k];             액세스 11 += B[k][j + 1] * A[i + 1][k];         }         C[i + 0][j + 0] = 액세스;         C[i + 0][j + 1] = acc01;         C[i + 1][j + 0] = 액세스 10;         C[i + 1][j + 1] = 액세스 11;     } } 

이 코드에는,i그리고.j2배수로 차단되어 결과적으로 2배속 내부 루프가 모두 완전히 풀렸습니다.

이 코드는 메인 메모리에 대한 메모리 동작당 0.8배의 멀티애드를 유지할 수 있는 Cray Y-MP(1980년대 초에 제조)에서 상당히 허용 가능한 동작입니다.2003년에 제조된 2.8GHz Pentium 4와 같은 머신은 메모리 대역폭이 약간 적고 부동소수점이 대폭 향상되어 메모리 동작당 16.5배의 멀티애드를 유지할 수 있습니다.그 결과 위의 코드는 2.8GHz Pentium 4에서는 166MHz Y-MP보다 느려집니다.

부동 소수점 추가 지연 시간이 길거나 여러 개의 추가 지연 시간이 있는 시스템에서는 병렬로 실행하는 데 더 많은 누적기가 필요합니다.2x2 블록 대신 3x3 블록을 계산하기 위해 위의 루프를 변경하는 것은 쉽지만 결과 코드가 항상 더 빠른 것은 아닙니다.루프에는 누적기와 로드 및 재사용된 A 및 B 값을 모두 유지하는 레지스터가 필요합니다.2x2 블록에는 7개의 레지스터가 필요합니다.3x3 블록에는 13이 필요합니다.이것은 ISA에 부동소수점 레지스터가 8개밖에 없는 기계에서는 동작하지 않습니다.CPU에 충분한 레지스터가 없는 경우, 컴파일러는 추가 부하를 스케줄 하고 레지스터를 스택슬롯에 흘려보내기 위해 저장합니다.이것에 의해, 루프가 블록 된 작은 루프보다 느리게 동작합니다.

매트릭스 곱셈은 메모리 대역폭에 의해 제한될 수 있고, 더 많은 레지스터가 컴파일러와 프로그래머가 메모리 대역폭의 필요성을 줄이는 데 도움이 된다는 점에서 다른 많은 코드와 같습니다.이러한 레지스터 압력 때문에 범용 x86 및 68000 CPU보다 병렬로 머신을 구축하려는 RISC CPU 벤더가 32엔트리 부동소수점 레지스터 파일을 채택한 것입니다.

위의 코드는 캐시를 잘 사용하지 않습니다.C 결과의 가로 스트라이프 계산 중에 A의 가로 스트라이프 1개를 로드하고 매트릭스 B 전체를 로드한다.전체 계산에서 C는 한 번 저장되고(좋습니다), A는 한 번 캐시에 로드되지만(A의 스트라이프가 B의 스트라이프와 함께 캐시에 적합하다고 가정), B는 N/ib 회 로드됩니다(여기서 ib는 C 매트릭스 내의 스트라이프 크기). 메인 메모리로부터의 N/ib 이중 워드 로드의 합계입니다³.위의 코드에서 ib는 2입니다.

메모리 트래픽을 줄이기 위한 다음 단계는 ib를 가능한 한 크게 하는 것입니다.스트림에서 보고되는 "잔액" 수보다 커야 합니다.이 예에서 사용되는 특정 2.8GHz Pentium 4 시스템의 경우 잔액은 16.5입니다.위의 두 번째 코드 예는 더 많은 누적 레지스터가 필요하기 때문에 직접 확장할 수 없습니다.대신 루프는 i 위에 차단됩니다(기술적으로는 첫 번째가 2의 계수였기 때문에 실제로 두 번째 차단입니다).

위해서 (ii = 0; ii < > N; ii += 아이비) {     위해서 (j = 0; j < > N; j += 2)     {         위해서 (i = ii; i < > ii + 아이비; i += 2)         {             액세스 = acc01 = 액세스 10 = 액세스 11 = 0;             위해서 (k = 0; k < > N; k++)             {                 액세스 += B[k][j + 0] * A[i + 0][k];                 acc01 += B[k][j + 1] * A[i + 0][k];                 액세스 10 += B[k][j + 0] * A[i + 1][k];                 액세스 11 += B[k][j + 1] * A[i + 1][k];             }             C[i + 0][j + 0] = 액세스;             C[i + 0][j + 1] = acc01;             C[i + 1][j + 0] = 액세스 10;             C[i + 1][j + 1] = 액세스 11;         }     } } 

이 코드를 사용하면 ib를 원하는 파라미터로 설정할 수 있으며, B 매트릭스의 부하 수는 이 계수만큼 감소합니다.이 자유에는 다음과 같은 대가가 있습니다.A 매트릭스의 N×ib 슬라이스는 캐시에 보관되어 있습니다.이 코드가 들어맞는 한 이 코드는 메모리 시스템에 의해 제한되지 않습니다.

어떤 크기의 매트릭스가 적합할까요?샘플 시스템인 2.8GHz Pentium 4에는 16KB의 프라이머리 데이터 캐시가 있습니다.ib=20의 경우, 이 코드의 A 매트릭스의 슬라이스는 N > 100일 때 1차 캐시보다 커집니다.그보다 더 큰 문제에는 다른 요령이 필요합니다.

이 트릭은 스트라이프의 크기가 ib × kb가 되도록 k루프를 차단함으로써 B 매트릭스의 스트라이프 크기를 줄이는 것입니다.k 루프를 차단하는 것은 C 어레이가${\displaystyle }$N/kb 회 로드 및 저장되고 총 ${\displaystyle {2\mu N\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$/ ${\displaystyle \mathrm{kb}}$(\$style$ 2$*N^{3}$ / $kb)$의 메모리 전송이 이루어짐을 의미합니다.${\displaystyle {N\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$/ ${\displaystyle i}$ b$${ $displaystyle$ N$^{3$} $/ ib$ } 전송에$$ $대해서$는, B 는 N/ib 회 전송 됩니다.이면

2*N/kb + N/ib < N/balance

머신의 메모리 시스템이 부동소수점 단위를 따라가고 코드가 최대 성능으로 실행됩니다.Pentium 4의 16KB 캐시는 그다지 크지 않습니다.대신 ib=24 및 kb=64를 선택하면 12KB의 캐시가 사용됩니다.캐시를 완전히 채우는 것이 바람직합니다.따라서 C 어레이와 B 어레이는 어느 정도 통과할 수 있는 공간이 필요합니다.이 수치는 프로세서의 최대 부동 소수점 속도의 20% 이내입니다.

여기 루프가 있는 코드가 있습니다.k차단되었습니다.

위해서 (ii = 0; ii < > N; ii += 아이비) {     위해서 (ㅋㅋ = 0; ㅋㅋ < > N; ㅋㅋ += kb)     {         위해서 (j=0; j < > N; j += 2)         {             위해서 (i = ii; i < > ii + 아이비; i += 2)             {                 한다면 (ㅋㅋ == 0)                     액세스 = acc01 = 액세스 10 = 액세스 11 = 0;                 또 다른                 {                     액세스 = C[i + 0][j + 0];                     acc01 = C[i + 0][j + 1];                     액세스 10 = C[i + 1][j + 0];                     액세스 11 = C[i + 1][j + 1];                 }                 위해서 (k = ㅋㅋ; k < > ㅋㅋ + kb; k++)                 {                     액세스 += B[k][j + 0] * A[i + 0][k];                  acc01 += B[k][j + 1] * A[i + 0][k];                  액세스 10 += B[k][j + 0] * A[i + 1][k];                  액세스 11 += B[k][j + 1] * A[i + 1][k];                 }                 C[i + 0][j + 0] = 액세스;                 C[i + 0][j + 1] = acc01;                 C[i + 1][j + 0] = 액세스 10;                 C[i + 1][j + 1] = 액세스 11;             }         }     } } 

위의 코드 예에서는 블로킹계수의 배수가 아닌 N의 값을 처리하는 방법에 대한 자세한 내용은 나와 있지 않습니다.루프 네스트 최적화를 실행하는 컴파일러는 연산 가장자리를 정리하기 위해 코드를 내보냅니다.예를 들어, 대부분의 LNO 컴파일러는 kk ==0의 반복을 다른 컴파일러와 분리할 수 있습니다.kk반복, if 문을 삭제합니다.i루프. 이것은 컴파일러의 값 중 하나입니다.이 최적화의 간단한 사례를 코드화하는 것은 간단하지만 코드가 복제되고 변환될 때 모든 세부사항을 정확하게 유지하는 것은 오류가 발생하기 쉬운 프로세스입니다.

위의 루프는 16KB L1 캐시 크기로 차단되었을 때 예제 시스템에서 피크 플롭의 80%만 달성합니다.불균형 메모리 시스템이 있는 시스템에서는 더 나빠집니다.다행히 Pentium 4는 256KB(모델에 따라서는 그 이상)의 고대역폭 레벨 2 캐시와 레벨 1 캐시를 갖추고 있습니다.선택할 수 있습니다.

• 레벨 2 캐시의 블록사이즈를 조정합니다.이로 인해 프로세서가 많은 명령을 동시에 실행 상태로 유지할 수 있는 능력이 강조되어 레벨 2 캐시에서 완전한 대역폭을 얻을 수 없을 가능성이 높아집니다.
• 루프를 다시 차단합니다.레벨 2 캐시 사이즈도 마찬가지입니다.총 3가지 수준의 블로킹(레지스터 파일, L1 캐시 및 L2 캐시)을 통해 코드는 메모리 계층의 각 수준에서 필요한 대역폭을 최소화합니다.유감스럽게도 블록 레벨이 높아지면 루프 오버헤드가 더 많아집니다.일부 하드웨어의 문제 사이즈에서는 L2 캐시에서 데이터를 스트리밍하는 하드웨어 기능의 단점보다 시간이 더 걸릴 수 있습니다.

첫 번째 예시와 같이 캐시 오블리비아 알고리즘은 특정 캐시 크기에 맞게 특별히 조정하지 않고 사용 가능한 캐시를 모두 사용하도록 설계되어 있습니다.사용 가능한 경우, 메모리 계층이 2개 이상 자동으로 이용됩니다.행렬 곱셈을 위한 캐시 오블리비아 알고리즘이 알려져 있습니다.

「 」를 참조해 주세요.

• 더프 장치
• 루프 최적화

레퍼런스

추가 정보

1. 울프, M. More 반복 공간 타일링.슈퍼컴퓨팅'89, 655~664쪽, 1989년.
2. Wolf, M.E. 및 Lam, M.A 데이터 인접성 최적화 알고리즘.PLDI'91, 30~44쪽, 1991년.
3. 아이리고인, F., 트리엣, R.슈퍼노드 파티셔닝POPL'88, 319~329쪽, 1988년.
4. Xue, J. Loop Tiling for Parallelarism.클루어 학술 출판사.2000.
5. M. S. Lam, E. Rothberg, M. E. Wolf.차단된 알고리즘의 캐시 성능 및 최적화입니다.제4회 프로그래밍 언어 및 운영체제 아키텍처 지원에 관한 국제회의의 속행(p63~74쪽, 1991년 4월).

외부 링크

• 벤치마크 결과를 스트리밍하여 부동소수점 연산과 여러 컴퓨터의 메모리 연산 간의 전체적인 균형을 보여줍니다.
• CHILL: 구성 가능한 고급 루프 변환 프레임워크^{[영구 데드링크]}