루프 인터체인지
Loop interchange컴파일러 이론에서 루프 교환은 중첩된 루프가 사용하는 두 반복 변수의 순서를 교환하는 과정입니다.내부 루프에서 사용되는 변수는 외부 루프로 전환되며, 그 반대도 마찬가지입니다.다차원 배열의 요소들이 메모리에 있는 순서대로 접근하여 참조의 인접성을 향상시키기 위해 종종 수행됩니다.
예를 들어, 코드 프래그먼트에서는 다음과 같습니다.
i가 0에서 10인 경우 j는 0에서 20 a[i,j] = i + j
루프 교환의 결과는 다음과 같습니다.
j가 0~20인 경우 i는 0~10 a[i,j] = i + j
이러한 변환에 의해서, 어레이 할당의 자동 벡터화 등, 한층 더 최적화할 기회가 생기는 경우가 있습니다.
루프 인터체인지 유틸리티
루프 교환의 주요 목적은 어레이 요소에 액세스할 때 CPU 캐시를 활용하는 것입니다.프로세서가 어레이 요소에 처음 액세스할 때 메모리에서 캐시로 데이터 블록 전체를 가져옵니다.이 블록은 첫 번째 블록 이후에 더 많은 연속적인 요소를 가질 가능성이 높기 때문에 다음 어레이 요소 액세스 시 캐시에서 직접 가져옵니다(이것은 느린 메인 메모리에서 가져오는 것보다 빠름).루프 내에서 연속적으로 액세스되는 어레이 요소가 다른 캐시 블록에서 온 경우 캐시 누락이 발생하며 루프 교환을 통해 이를 방지할 수 있습니다.루프 교환의 효율성은 기본 하드웨어에서 사용되는 캐시 모델과 컴파일러에서 사용되는 어레이 모델에 따라 달라지며 고려해야 합니다.
C프로그래밍 언어에서는, 같은 행의 어레이 요소가 메모리(a[1,1], a[1,2], a[1,3]) θ에 행 메이저 순서로 연속적으로 격납된다.한편, FORTRAN 프로그램은 같은 열의 배열 요소(a[1,1], a[2,1], a[3,1])를 줄자를 사용하여 함께 저장합니다.따라서 첫 번째 예에서 두 개의 반복 변수의 순서는 C 프로그램에 적합하지만 두 번째 예제는 [1]FORTRAN에 적합합니다.컴파일러를 최적화하면 프로그래머에 의한 부적절한 순서를 검출하여 캐시 성능을 향상시킬 수 있습니다.
경고
다른 컴파일러 최적화와 마찬가지로 캐시 성능은 일부에 불과하기 때문에 루프 교환은 성능 저하로 이어질 수 있습니다.다음 예를 들어 보겠습니다.
하니i = 1, 10000 하니j = 1, 1000 a[i] = a[i] + b[j,i] * c[i] end do를 하다 end do를 하다 이 예에서 루프 교환은 b(j,i)에 액세스하는 캐시 성능을 향상시킬 수 있지만, 각 반복 중에 2개의 추가 부하(a(i)와 c(i)에 대해)와 1개의 추가 스토어(a(i)에 대해)가 발생하기 때문에 내부 루프에서 a(i)와 c(i)의 재사용을 방해합니다.그 결과 루프 교환 후 전체적인 퍼포먼스가 저하될 수 있습니다.
안전.
반복 변수가 실행되는 순서에 대한 문 사이의 종속성으로 인해 반복 변수를 교환하는 것이 항상 안전한 것은 아닙니다.컴파일러가 루프를 안전하게 교환할 수 있는지 여부를 판단하려면 의존성 분석이 필요합니다.
「 」를 참조해 주세요.
레퍼런스
- ^ "Loop interchange" (PDF). Parallel Programming Guide for HP-UX Systems. HP. August 2003.
추가 정보
- Kennedy, Ken; Allen, Randy (2002). Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (2011 digital print of 1st ed.). Academic Press / Morgan Kaufmann Publishers / Elsevier. ISBN 978-1-55860-286-1. LCCN 2001092381.
