루프 최적화

컴파일러 이론에서 루프 최적화는 실행 속도를 높이고 루프와 관련된 오버헤드를 줄이는 과정이다.캐쉬 성능을 향상시키고 병렬 처리 기능을 효과적으로 사용하는 데 중요한 역할을 한다.과학 프로그램의 실행 시간은 대부분 루프에 소요된다. 따라서, 많은 컴파일러 최적화 기법이 루프를 더 빨리 만들기 위해 개발되었다.

계산 및 변환의 표현

루프 내부의 지침은 반복적으로 실행될 수 있기 때문에, 루프 최적화의 영향을 받을 명령 실행 횟수에 제한을 두는 것은 종종 불가능하다.이는 루프 최적화의 정확성과 편익, 특히 최적화 중인 연산 및 수행 중인 최적화에 대한 추론 시 난제를 제시한다.^[1]

일련의 루프 변환을 통한 최적화

루프 최적화는 각 변환이 합법성에 대한 관련 시험을 갖는 소스 코드 또는 중간 표현에 대한 특정 루프 변환(고성능 컴퓨팅을^[2] 위한 컴파일러 변환 아래 또는 컴파일러 변환에 나열됨)의 시퀀스를 적용하는 것으로 볼 수 있다.변환(또는 변환 순서)은 일반적으로 프로그램의 결과를 보존하려면(즉, 법적 변환이 되어야 한다) 모든 종속성의 시간적 순서를 보존해야 한다.하나의 유익한 변환을 적용하려면 성능 저하를 초래하는 하나 이상의 다른 변환을 사전에 사용해야 할 수 있기 때문에 변환의 효익을 평가하는 것은 이 접근법 내에서 상당히 어려울 수 있다.

일반적인 루프 변환은 다음과 같다.

• 핵분열 또는 분포 – 루프 핵분열은 동일한 지수 범위에 걸쳐 루프를 여러 루프로 분해하려고 시도하지만, 각각의 새로운 루프는 원래 루프 본체의 일부만 차지한다.이것은 루프에서 접근하는 데이터와 루프 본체의 코드 둘 다 참조의 위치를 개선할 수 있다.
• 융접 또는 결합 – 이것은 동일한 횟수를 반복하는 두 개의 인접한 루프의 본문을 결합한다(이 숫자는 컴파일 시간에 알 수 있든 없든 상관없이). 그들이 서로의 데이터를 참조하지 않는 한.
• 교환 또는 순열 – 이러한 최적화는 내부 루프를 외부 루프와 교환한다.루프 변수가 배열로 색인화되면, 그러한 변환은 배열의 레이아웃에 따라 참조의 위치성을 개선할 수 있다.
• 반전 – 이 기법은 루프를 if 조건부로 감싸면서 do/ while(예: repeat/ ~ )로 루프하는 동안 표준을 변경하여, 루프 실행의 경우 점프 횟수를 2회 줄인다.이렇게 하면 상태 점검(코드 크기 증가)이 중복되지만 점프는 대개 파이프라인 스톨을 유발하기 때문에 더 효율적이다.또한 컴파일 시간에 초기 조건을 알고 부작용이 없는 것으로 알려진 경우 초기 if-guard를 건너뛸 수 있다.
• 루프 인바리어트 코드 운동 – 계산의 결과 수량이 모든 루프 반복에 대해 동일할 경우(즉, 루프 인바리어트 수량) 루프의 내부에서 외부로 연산을 이동하여 루프가 시작되기 바로 전에 값을 계산함으로써 효율을 크게 향상시킬 수 있다.이는 배열의 루프에 의해 생성된 주소 계산 식에서 특히 중요하다.모든 코드가 루프 밖으로 이동하기에 안전하지 않기 때문에 정확한 구현을 위해 이 기법을 반전하여 사용해야 한다.
• 병렬화 – 루프를 중심으로 한 자동 병렬화, 멀티프로세서 시스템에서 효율적으로 실행되도록 재구성하는 특별한 경우.컴파일러(자동 병렬화) 또는 수동으로(OpenMP와 같은 병렬 지시문 삽입)에 의해 자동으로 수행될 수 있다.
• 반전 – 값이 인덱스 변수에 할당되는 순서를 역전시키는 미묘한 최적화.이것은 의존성을 제거하여 다른 최적화를 가능하게 할 수 있다.특정 아키텍처는 단일 방향으로만 계산되는 조립품 수준의 루프 구조를 활용한다(예: 감소-점프-if-zero-not-z [DJNZ]).^[3]
• 스케줄링 – 루프를 여러 프로세서에서 동시에 실행할 수 있는 여러 부분으로 나뉜다.
• Skedwing – 이 기법은 다차원 배열 위에 중첩된 루프 반복에 적용되며, 여기서 내측 루프의 각 반복은 이전 반복에 의존하고, 어레이 액세스를 다시 조정하여 외측 루프의 반복 사이에 유일한 종속성이 있도록 한다.
• 소프트웨어 파이프라인 – 프로세서 기능 유닛의 지연 시간을 숨기기 위한 루프 반복의 순서가 맞지 않는 실행 유형.
• 분할 또는 벗겨짐 – 이 시도는 루프를 동일한 본체를 가지지만 인덱스 범위의 다른 부분에 걸쳐 반복되는 여러 루프로 분해하여 루프를 단순화하거나 종속성을 제거하려고 시도한다.특별한 경우는 루프 필링으로, 루프에 들어가기 전에 별도로 반복을 수행하여 문제가 있는 첫 번째 반복으로 루프를 단순화할 수 있다.
• 타일링 또는 차단 – 루프를 재구성하여 캐시에 맞게 크기가 지정된 데이터 블록에 반복하십시오.
• 벡터화 – SIMD 시스템에서 가능한 한 많은 루프 반복을 동시에 실행하려고 시도한다.
• 풀림 – 루프 조건을 테스트하는 횟수와 점프 횟수를 줄이기 위해 루프 본체를 여러 번 복제하여 명령 파이프라인을 손상시켜 성능을 저하시킬 수 있다.루프를 완전히 풀면 모든 오버헤드가 제거되지만(여러 명령 가져오기 및 프로그램 로드 시간 증가 제외), 컴파일 시 반복 횟수를 알 수 있어야 한다(Just-in-time 컴파일 경우 제외).또한 인덱스 변수의 다중 재계산도 원래 루프 내에서 전진하는 포인터보다 큰 오버헤드가 되지 않도록 주의해야 한다.
• 언스위치 – 루프 본체를 복제하고 조건부의 if 및 기타 절에 각각 버전을 배치하여 루프 내부에서 외부로 조건부를 이동시킨다.
• 단면 또는 스트립 마이닝 – 벡터 프로세서에 도입된 루프 단면은 루프에 대한 SIMD(단일 명령, 다중 데이터)를 활성화하고 메모리 성능을 향상시키기 위한 루프 변환 기법이다.여기에는 주어진 벡터 기계의 최대 벡터 길이보다 작거나 같은 크기에 대해 수행되는 각 벡터 작동이 포함된다.^[4][5]

단변형 변환

단변형 변환 접근방식은^[6] 단변형 행렬을 사용하여 위의 변환 중 많은 수의 시퀀스의 결합 결과를 설명한다.이 접근방식의 중심은 n 루프 내에서 모든 문장의 실행을 n차원 공간의 정수 점 집합으로 보는 것이며, 점들은 사전순으로 실행된다.예를 들어, 인덱스 i가 있는 외부 루프와 인덱스 j가 있는 내부 루프의 내부에 중첩된 문장의 실행은 정수 ${\displaystyle 쌍(i}$ ,${\displaystyle }$j ) ${\displaystyle (i,j)}$과 연관될 수 있다$.$ 단변형 변환의 적용은 이 공간 내에서 매트릭스에 의한 점의 곱셈에 해당한다.예를 들어, 두 루프의 교환은 매트릭스[ ${\$에 해당한다

단변형 변환은 모든 종속성의 시간적 순서를 보존한다면 합법적이다; 단변형 변환의 성능 영향을 측정하기가 더 어렵다.불완전하게 중첩된 루프와 일부 변형(타일링 등)은 이 프레임워크에 쉽게 들어맞지 않는다.

다면체 또는 제약에 기반한 프레임워크

다면 모델은^[7] 단면체 프레임워크보다 더 넓은 등급의 프로그램과 변환을 처리한다.불완전하게 내포된 루프 집합 내에서 일련의 진술 집행이 진술 집행을 나타내는 일련의 폴리토페스를 결합한 것으로 보인다.아핀 변환은 이러한 폴리토페스에 적용되어 새로운 실행 순서에 대한 설명을 생성한다.폴리토페스의 경계, 데이터 의존성 및 변환은 제약의 시스템을 사용하여 기술되는 경우가 많으며, 이러한 접근방식은 루프 최적화에 대한 제약조건 기반 접근방식이라고 일컬어진다.예를 들어, 외부 루프 내의 단일 문 'i := 0 ~ n'에 대해 'j := 0 ~ i+2에 대해' 내부 루프는 0 <= i <= n>과 0 <= i+2>와 같은 각 (i, j) 쌍에 대해 한 번 실행된다.

다시 한번 말하지만, 변환은 모든 의존성의 시간적 순서를 보존한다면 합법적이다.변환의 이점을 추정하거나 특정 컴퓨터에서 주어진 코드에 대한 최상의 변환을 찾는 것은 이 작성 시점(2010년) 현재 진행 중인 연구의 대상으로 남아 있다.

참고 항목

• 루프 중첩 최적화
• 폴리토프 모형
• 확장 가능한 병렬 처리
• 확장 가능한 지역성

참조