상위 질문
타임라인
채팅
관점
루프 언롤링
위키백과, 무료 백과사전
Remove ads
루프 언롤링(Loop unrolling) 또는 루프 언와인딩(loop unwinding)은 프로그램의 이진 크기를 늘리는 대신 실행 속도를 최적화하려는 루프 변환 기술로, 이는 공간-시간 트레이드오프라고 알려진 접근 방식이다. 변환은 프로그래머가 수동으로 수행하거나 최적화 컴파일러가 수행할 수 있다. 최신 프로세서에서는 루프 언롤링으로 인해 코드 크기가 증가하여 캐시 미스가 더 많이 발생할 수 있으므로 역효과를 낼 때가 많다. 더프의 장치를 참고하라.[1]
루프 언와인딩의 목표는 각 반복에서 포인터 연산 및 "루프 끝" 테스트와 같이 루프를 제어하는 명령어를 줄이거나 제거하여 프로그램의 속도를 높이는 것이다.[2] 분기 페널티를 줄이고, 메모리에서 데이터를 읽는 지연을 포함한 대기 시간을 숨기는 것이다.[3] 이러한 계산 오버헤드를 제거하기 위해 루프는 유사한 독립적인 명령문의 반복 시퀀스로 다시 작성될 수 있다.[4]
Remove ads
장점
"타이트한" 루프의 오버헤드는 종종 배열의 다음 요소에 대한 포인터나 인덱스를 증가시키는 명령어(포인터 연산)와 "루프 종료" 테스트로 구성된다. 최적화 컴파일러나 어셈블러가 개별적으로 참조되는 각 배열 변수에 대한 오프셋을 미리 계산할 수 있다면, 이들은 기계어 명령어에 직접 내장될 수 있으므로 런타임에 추가적인 산술 연산이 필요하지 않다.
- 실행되는 명령어의 감소가 프로그램 크기 증가로 인한 성능 저하를 상쇄하면 상당한 이득을 얻을 수 있다.
- 분기 페널티가 최소화된다.[6]
- 루프 내의 명령문이 서로 독립적이라면(즉, 루프에서 먼저 발생하는 명령문이 그 뒤에 오는 명령문에 영향을 주지 않는 경우), 명령문은 잠재적으로 병렬로 실행될 수 있다.
- 배열 요소의 수가 컴파일 타임에 알려져 있지 않은 경우(더프의 장치에서와 같이) 동적으로 구현할 수 있다.
최적화 컴파일러는 때때로 자동으로 또는 요청에 따라 언롤링을 수행한다.
Remove ads
단점
- 코드 크기 증가: 언롤링은 명령어 수를 늘려 프로그램 이진 파일을 더 크게 만든다.
- 높은 저장 요구 사항: 확장된 코드는 더 많은 메모리를 차지하며, 이는 마이크로컨트롤러나 제한된 저장 공간을 가진 임베디드 시스템에 문제가 될 수 있다.
- 명령어 캐시 압력: 언롤링된 루프는 명령어 캐시에서 더 많은 공간을 소비한다. 캐시 크기를 초과하면 빈번한 캐시 미스가 발생하여 값비싼 메모리 접근으로 인해 심각한 성능 저하가 발생할 수 있다.
- 코드 가독성 저하: 최적화 컴파일러 대신 수동으로 루프 언롤링을 수행하면 코드를 이해하고 유지 관리하기가 더 어려워질 수 있다.
- 함수 인라이닝과의 충돌: 루프 본문에 함수 호출이 포함된 경우, 언롤링은 과도한 코드 확장으로 인해 인라이닝을 방해할 수 있으며, 이 두 최적화 간에 상충 관계를 초래한다.
- 레지스터 압력 증가: 성능을 위해 소프트웨어 파이프라이닝에 의존하는 하드웨어(예: 레지스터 이름 변경이 없거나 순서 내 슈퍼스칼라 실행을 사용하는 시스템)에서 언롤링은 반복 간에 임시 변수를 저장하기 위해 추가 레지스터를 필요로 하여 레지스터 재사용을 제한할 수 있다.[7]
- 분기 예측: 최신 CPU는 분기 예측을 사용하여 분기가 어느 방향으로 갈지 추측하려고 한다. 예측이 정확하면 CPU는 분기가 해결될 때까지 기다리지 않고 명령어를 계속 실행할 수 있다. 그러나 예측이 잘못되면 CPU는 파이프라인을 비우고 올바른 명령어를 실행하기 시작해야 하며, 이는 성능 저하를 초래할 수 있다. 루프 언롤링은 코드 내 분기 수를 증가시켜 더 많은 분기 오예측과 낮은 성능으로 이어질 수 있다.[8]
Remove ads
정적/수동 루프 언롤링
요약
관점
수동 (또는 정적) 루프 언롤링은 프로그래머가 루프를 분석하고 반복을 루프 오버헤드를 줄이는 일련의 명령어로 해석하는 것을 포함한다. 이는 컴파일러에 의해 수행되는 동적 언롤링과는 대조된다.
C 언어의 간단한 수동 예시
컴퓨터 프로그램의 한 절차는 컬렉션에서 100개의 항목을 삭제하는 것이다. 이는 일반적으로 delete(item_number) 함수를 호출하는 `for` 루프를 통해 수행된다. 이 프로그램 부분이 최적화되어야 하고, 루프의 오버헤드가 delete(x) 함수에 비해 상당한 리소스를 요구하는 경우, 언와인딩을 사용하여 속도를 높일 수 있다.
이 수정의 결과로 새 프로그램은 100번 대신 20번만 반복하면 된다. 그 후에는 점프와 조건부 분기의 20%만 수행하면 되며, 이는 많은 반복에 걸쳐 루프 관리 오버헤드의 잠재적으로 상당한 감소를 나타낸다. 최적의 이점을 얻으려면 언롤링된 코드에 포인터 연산이 필요한 변수를 지정해서는 안 된다. 이는 일반적으로 인덱스 참조 방식 대신 "기준 주소 + 오프셋" 주소 지정을 필요로 한다.
반면에 이 수동 루프 언롤링은 원본 코드 크기를 3줄에서 7줄로 확장하며, 이는 작성, 확인, 디버깅해야 한다. 또한 컴파일러는 확장된 루프 반복에서 변수를 저장하기 위해 더 많은 레지스터를 할당해야 할 수도 있다. 게다가, 언롤링된 루프 구조 내의 루프 제어 변수와 연산 횟수는 결과가 원래 코드와 동일하도록 신중하게 선택해야 한다(이미 작동하는 코드에 대한 후속 최적화라고 가정할 때). 예를 들어, 반복 횟수가 5로 나누어지지 않는 경우의 영향을 고려해 보라. 테스트 조건이 변수인 경우 수동 수정 사항은 다소 더 복잡해진다. 더프의 장치도 참조하라.
초기 복잡성
간단한 경우, 루프 제어는 생산적인 명령문을 배열하는 단순한 관리 오버헤드이다. 루프 자체는 원하는 결과에 아무런 기여도 하지 않으며, 단지 프로그래머가 코드를 백 번 복제하는 지루함을 덜어줄 뿐이다. 이는 전처리가 복제를 생성하거나 텍스트 편집기가 수행할 수 있었던 일이다. 마찬가지로, `if` 문 및 기타 흐름 제어 문은 코드 복제로 대체될 수 있지만, 코드 블롯이 발생할 수 있다. 컴퓨터 프로그램은 조합을 쉽게 추적하지만, 프로그래머는 이러한 반복을 지루해하며 실수를 저지른다. 고려해 보자:
그러나 물론 수행되는 코드가 프로시저 호출일 필요는 없으며, 다음 예시에서는 계산에 인덱스 변수가 포함된다.
이것이 컴파일되면 많은 코드를 생성할 수 있지만(프린트 문이 악명 높음), 추가 최적화가 가능하다. 이 예시는 루프에서 x(i)와 x(i - 1)만을 참조한다(후자는 새로운 값 x(i)를 개발하기 위해서만). 따라서 여기서 개발된 배열 x에 대한 나중 참조가 없다고 가정하면, 그 사용은 단순 변수로 대체될 수 있다. 그러나 그러한 변경은 값이 변경되는 단순 변수를 의미할 것이지만, 배열을 유지한다면 컴파일러의 분석은 배열의 값이 상수이며, 각각 이전 상수에서 파생되었음을 인지하고 상수 값을 전달하여 코드가 다음과 같이 될 것이다.
print 2, 2; print 3, 6; print 4, 24; ...etc.
일반적으로 루프의 내용은 크고 복잡한 배열 인덱싱을 포함할 수 있다. 이러한 경우는 최적화 컴파일러가 언롤링하는 것이 가장 좋다. 내부 루프를 복제하면 많은 최적화가 가능하지만, n이 크지 않으면 작은 이득만 얻을 수 있다.
WHILE 루프 언롤링
다음과 유사한 의사코드 WHILE 루프를 고려해 보자.
이 경우, ENDWHILE(루프 시작으로 점프)이 66% 덜 실행되므로 언롤링이 더 빠르다.
심지어 더 좋은 것은 일부 최적화 컴파일러가 자동으로 수행할 수 있는 "조정된" 의사코드 예시로, 무조건 점프를 완전히 제거한다.
Remove ads
동적 언롤링
요약
관점
루프 언롤링의 이점은 종종 배열의 크기에 따라 달라지며, 이는 런타임까지 알 수 없는 경우가 많기 때문에 JIT 컴파일러는 (예를 들어) "표준" 루프 시퀀스를 호출할지 아니면 각 요소에 대해 (상대적으로 짧은) 개별 명령어 시퀀스를 생성할지 결정할 수 있다. 이러한 유연성은 루프 언롤링의 맥락에서 정적 또는 수동 최적화와 비교하여 JIT 기술의 장점 중 하나이다. 이 상황에서는 n의 값이 비교적 작을 때 절약 효과가 여전히 유용하며, 프로그램 크기 전체적으로 거의 (또는 전혀) 증가시키지 않는다 (이는 표준 라이브러리의 일부로 한 번만 포함될 수 있다).
어셈블리어 프로그래머(최적화 컴파일러 개발자 포함)도 효율적인 분기 테이블에 사용되는 방법과 유사한 방법을 사용하여 동적 루프 언롤링 기술의 이점을 얻을 수 있다. 여기서 장점은 특정 배열에서 참조되는 필드의 최대 오프셋이 기계어 명령어로 지정할 수 있는 최대 오프셋보다 작은 경우에 가장 크다(초과하면 어셈블러가 플래그를 표시한다).
어셈블러 예시 (IBM/360 또는 Z/아키텍처)
이 예시는 IBM/360 또는 Z/아키텍처 어셈블러를 위한 것으로, FROM 배열에서 TO 배열로 100바이트 필드(오프셋 0)를 복사하는 것을 가정한다. 두 배열 모두 50개의 항목을 가지며 각 요소의 길이는 256바이트이다.
* The return address is in R14.
* Initialize registers R15, R0, R1, and R2 from data defined at the end of
* the program starting with label INIT/MAXM1.
LM R15,R2,INIT Set R15 = maximum number of MVC
* instructions (MAXM1 = 16),
* R0 = number of entries of array,
* R1 = address of 'FROM' array, and
* R2 = address of 'TO' array.
*
* The loop starts here.
LOOP EQU * Define LOOP label.
* At this point, R15 will always contain the number 16 (MAXM1).
SR R15,R0 Subtract the remaining number of
* entries in the array (R0) from R15.
BNP ALL If R15 is not positive, meaning we
* have more than 16 remaining entries
* in the array, jump to do the entire
* MVC sequence and then repeat.
*
* Calculate an offset (from start of MVC sequence) for unconditional branch to
* the 'unwound' MVC loop below.
* If the number of remaining entries in the arrays is zero, R15 will be 16, so
* all the MVC instructions will be bypassed.
MH R15,=AL2(ILEN) Multiply R15 by the length of one
* MVC instruction.
B ALL(R15) Jump to ALL+R15, the address of the
* calculated specific MVC instruction
* with drop through to the rest of them.
*
* MVC instruction 'table'.
* First entry has maximum allowable offset with single register = hexadecimal F00
* (15*256) in this example.
* All 16 of the following MVC ('move character') instructions use base-plus-offset
* addressing and each to/from offset decreases by the length of one array element
* (256). This avoids pointer arithmetic being required for each element up to a
* maximum permissible offset within the instruction of hexadecimal FFF
* (15*256+255). The instructions are in order of decreasing offset, so the last
* element in the set is moved first.
ALL MVC 15*256(100,R2),15*256(R1) Move 100 bytes of 16th entry from
* array 1 to array 2 (with
* drop-through).
ILEN EQU *-ALL Set ILEN to the length of the previous
* MVC instruction.
MVC 14*256(100,R2),14*256(R1) Move 100 bytes of 15th entry.
MVC 13*256(100,R2),13*256(R1) Move 100 bytes of 14th entry.
MVC 12*256(100,R2),12*256(R1) Move 100 bytes of 13th entry.
MVC 11*256(100,R2),11*256(R1) Move 100 bytes of 12th entry.
MVC 10*256(100,R2),10*256(R1) Move 100 bytes of 11th entry.
MVC 09*256(100,R2),09*256(R1) Move 100 bytes of 10th entry.
MVC 08*256(100,R2),08*256(R1) Move 100 bytes of 9th entry.
MVC 07*256(100,R2),07*256(R1) Move 100 bytes of 8th entry.
MVC 06*256(100,R2),06*256(R1) Move 100 bytes of 7th entry.
MVC 05*256(100,R2),05*256(R1) Move 100 bytes of 6th entry.
MVC 04*256(100,R2),04*256(R1) Move 100 bytes of 5th entry.
MVC 03*256(100,R2),03*256(R1) Move 100 bytes of 4th entry.
MVC 02*256(100,R2),02*256(R1) Move 100 bytes of 3rd entry.
MVC 01*256(100,R2),01*256(R1) Move 100 bytes of 2nd entry.
MVC 00*256(100,R2),00*256(R1) Move 100 bytes of 1st entry.
*
S R0,MAXM1 Reduce the number of remaining entries
* to process.
BNPR R14 If no more entries to process, return
* to address in R14.
AH R1,=AL2(16*256) Increment 'FROM' array pointer beyond
* first set.
AH R2,=AL2(16*256) Increment 'TO' array pointer beyond
* first set.
L R15,MAXM1 Reload the maximum number of MVC
* instructions per batch into R15
* (destroyed by the calculation in the
* first instruction of the loop).
B LOOP Execute loop again.
*
* Static constants and variables (these could be passed as parameters, except
* MAXM1).
INIT DS 0A 4 addresses (pointers) to be
* pre-loaded with the 'LM' instruction
* in the beginning of the program.
MAXM1 DC A(16) Maximum number of MVC instructions
* executed per batch.
N DC A(50) Number of actual entries in array (a
* variable, set elsewhere).
DC A(FROM) Address of start of array 1
* ("pointer").
DC A(TO) Address of start of array 2
* ("pointer").
*
* Static arrays (these could be dynamically acquired).
FROM DS 50CL256 Array of 50 entries of 256 bytes each.
TO DS 50CL256 Array of 50 entries of 256 bytes each.
이 예시에서는 "기존" 루프(50회 반복)를 사용하면 약 202개의 명령어가 필요하지만, 위 동적 코드는 약 89개의 명령어만 필요하므로 약 56%의 절약 효과가 있다. 배열에 두 개의 항목만 포함되어 있었다면, 원래 언롤링된 루프와 거의 같은 시간으로 실행되었을 것이다. 배열에 수천 개의 항목이 있더라도 코드 크기 증가는 약 108바이트에 불과하다.
여러 명령어가 관련되어 있는 경우에도 결합된 명령어 길이가 그에 따라 조정되는 한 유사한 기술을 사용할 수 있다. 예를 들어, 이 동일한 예시에서 복사된 100바이트 필드 직후에 각 배열 항목의 나머지를 널 문자로 지워야 하는 경우, 추가 지우기 명령어인 `XC xx*256+100(156,R1),xx*256+100(R2)`를 시퀀스의 모든 MVC 바로 뒤에 추가할 수 있다(여기서 `xx`는 위 MVC의 값과 일치한다).
물론, 단일 어셈블러 매크로 명령문을 사용하여 위 코드를 "인라인"으로 생성하고 네다섯 개의 피연산자만 지정하거나(또는 간단한 호출로 접근할 수 있는 라이브러리 서브루틴으로 만들어 매개변수 목록을 전달하는 방식으로), 최적화를 쉽게 사용할 수 있도록 하는 것이 완벽하게 가능하다.
C 언어 예시
다음 예시는 C로 작성된 간단한 프로그램에 대한 동적 루프 언롤링을 보여준다. 위 어셈블러 예시와 달리, 이 예시에서는 변수 (i)가 여전히 배열 요소를 주소 지정하는 데 사용되므로 컴파일러가 여전히 포인터/인덱스 연산을 생성한다. 완전한 최적화는 대체 명령문에서 절대 인덱스를 사용하는 경우에만 가능하다.
#include <stdio.h>
/* The number of entries processed per loop iteration. */
/* Note that this number is a 'constant constant' reflecting the code below. */
enum {
BUNCHSIZE = 8
};
int main(void)
{
int i = 0; /* counter */
int entries = 50; /* total number to process */
/* If the number of elements is not divisible by BUNCHSIZE, */
/* get repeat times required to do most processing in the while loop */
int repeat = (entries / BUNCHSIZE); /* number of times to repeat */
int left = (entries % BUNCHSIZE); /* calculate remainder */
/* Unroll the loop in 'bunches' of 8 */
while (repeat--)
{
printf("process(%d)\n", i );
printf("process(%d)\n", i + 1);
printf("process(%d)\n", i + 2);
printf("process(%d)\n", i + 3);
printf("process(%d)\n", i + 4);
printf("process(%d)\n", i + 5);
printf("process(%d)\n", i + 6);
printf("process(%d)\n", i + 7);
/* update the index by amount processed in one go */
i += BUNCHSIZE;
}
/* Use a switch statement to process remaining by jumping to the case label */
/* at the label that will then drop through to complete the set */
switch (left)
{
case 7 : printf("process(%d)\n", i + 6); /* process and rely on drop
through */
case 6 : printf("process(%d)\n", i + 5);
case 5 : printf("process(%d)\n", i + 4);
case 4 : printf("process(%d)\n", i + 3);
case 3 : printf("process(%d)\n", i + 2);
case 2 : printf("process(%d)\n", i + 1); /* two left */
case 1 : printf("process(%d)\n", i); /* just one left to process */
case 0 : ; /* none left */
}
}
코드 중복은 더프의 장치와 같이 두 부분을 함께 작성하여 피할 수 있다.
C에서 MIPS 어셈블리어 루프 언롤링 예시
출처:[9]
다음 예시는 double 타입의 100개 항목 벡터 A와 B의 스칼라곱을 계산할 것이다. C 언어 코드는 다음과 같다:
double dotProduct = 0;
for (int i = 0; i < 100; i++) {
dotProduct += A[i]*B[i];
}
MIPS 어셈블리어로 변환
다음은 루프 언롤링을 구현하기 전에 100개 항목의 벡터 A와 B의 스칼라곱을 계산하는 MIPS 어셈블리어 코드이다. 아래 코드는 루프 초기화를 생략한다.
- 루프 카운트($7)를 100으로 초기화한다.
- 스칼라곱($f8)을 0으로 초기화한다.
- `A[i]` 포인터($5)를 `A`의 기본 주소로 초기화한다.
- `B[i]` 포인터($6)를 `B`의 기본 주소로 초기화한다.
배열의 한 요소 크기(a `double`)는 8바이트이다.
loop3:
l.d $f10, 0($5) ; $f10 ← A[i]
l.d $f12, 0($6) ; $f12 ← B[i]
mul.d $f10, $f10, $f12 ; $f10 ← A[i]*B[i]
add.d $f8, $f8, $f10 ; $f8 ← $f8 + A[i]*B[i]
addi $5, $5, 8 ; increment pointer for A[i] by the size
; of a double.
addi $6, $6, 8 ; increment pointer for B[i] by the size
; of a double.
addi $7, $7, -1 ; decrement loop count
test:
bgtz $7, loop3 ; Continue if loop count > 0
MIPS에서 루프 언롤링
다음은 위와 같지만, 4배로 루프 언롤링을 구현한 것이다. 배열의 한 요소 크기(a `double`)는 8바이트이므로 0, 8, 16, 24 변위와 각 루프의 32 변위를 다시 참고한다.
loop3:
l.d $f10, 0($5) ; iteration with displacement 0
l.d $f12, 0($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 8($5) ; iteration with displacement 8
l.d $f12, 8($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 16($5) ; iteration with displacement 16
l.d $f12, 16($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 24($5) ; iteration with displacement 24
l.d $f12, 24($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
addi $5, $5, 32
addi $6, $6, 32
addi $7, $7, -4
test:
bgtz $7, loop3 ; Continue loop if $7 > 0
Remove ads
같이 보기
- 중복배제
- 명령어 수준 병렬성
- JIT 컴파일
- 루프 퓨전
- 루프 분할
- 루프 언스위칭
- 병렬 컴퓨팅
각주
추가 자료
외부 링크
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads