루프 언롤링

**루프 언롤링**(Loop unrolling) 또는 **루프 언와인딩**(loop unwinding)은 프로그램의 이진 크기를 늘리는 대신 실행 속도를 최적화하려는 루프 변환 기술로, 이는 공간-시간 트레이드오프라고 알려진 접근 방식이다. 변환은 프로그래머가 수동으로 수행하거나 최적화 컴파일러가 수행할 수 있다. 최신 프로세서에서는 루프 언롤링으로 인해 코드 크기가 증가하여 캐시 미스가 더 많이 발생할 수 있으므로 역효과를 낼 때가 많다. 더프의 장치를 참고하라.quote = Jim Gettys has a wonderful explanation of this effect in the X server. It turns out that with branch predictions and the relative speed of CPU vs. memory changing over the past decade, loop unrolling is pretty much pointless. In fact, by eliminating all instances of Duff's Device from the XFree86 4.0 server, the server shrunk in size by _half_ _a_ _megabyte_ (!!!), and was faster to boot, because the elimination of all that excess code meant that the X server wasn't thrashing the cache lines as much. 루프 언와인딩의 목표는 각 반복에서 포인터 연산 및 "루프 끝" 테스트와 같이 루프를 제어하는 명령어를 줄이거나 제거하여 프로그램의 속도를 높이는 것이다.isbn=0-201-10073-8 분기 페널티를 줄이고, 메모리에서 데이터를 읽는 지연을 포함한 대기 시간을 숨기는 것이다.page=10 이러한 계산 오버헤드를 제거하기 위해 루프는 유사한 독립적인 명령문의 반복 시퀀스로 다시 작성될 수 있다.oclc=14638257 루프 언롤링은 또한 특정 형식 검증 기술, 특히 유한 모델 검사의 일부이다.Model Checking Using SMT and Theory of Lists
# 장점
"타이트한" 루프의 오버헤드는 종종 배열의 다음 요소에 대한 포인터나 인덱스를 증가시키는 명령어(포인터 연산)와 "루프 종료" 테스트로 구성된다. 최적화 컴파일러나 어셈블러가 개별적으로 참조되는 각 배열 변수에 대한 오프셋을 미리 계산할 수 있다면, 이들은 기계어 명령어에 직접 내장될 수 있으므로 런타임에 추가적인 산술 연산이 필요하지 않다. * 실행되는 명령어의 감소가 프로그램 크기 증가로 인한 성능 저하를 상쇄하면 상당한 이득을 얻을 수 있다. * 분기 페널티가 최소화된다.publisher=Copenhagen University College of Engineering * 루프 내의 명령문이 서로 독립적이라면(즉, 루프에서 먼저 발생하는 명령문이 그 뒤에 오는 명령문에 영향을 주지 않는 경우), 명령문은 잠재적으로 병렬로 실행될 수 있다. * 배열 요소의 수가 컴파일 타임에 알려져 있지 않은 경우(더프의 장치에서와 같이) 동적으로 구현할 수 있다. 최적화 컴파일러는 때때로 자동으로 또는 요청에 따라 언롤링을 수행한다.
# 단점
* 코드 크기 증가: 언롤링은 명령어 수를 늘려 프로그램 이진 파일을 더 크게 만든다. ** 높은 저장 요구 사항: 확장된 코드는 더 많은 메모리를 차지하며, 이는 마이크로컨트롤러나 제한된 저장 공간을 가진 임베디드 시스템에 문제가 될 수 있다. ** 명령어 캐시 압력: 언롤링된 루프는 명령어 캐시에서 더 많은 공간을 소비한다. 캐시 크기를 초과하면 빈번한 캐시 미스가 발생하여 값비싼 메모리 접근으로 인해 심각한 성능 저하가 발생할 수 있다. * 코드 가독성 저하: 최적화 컴파일러 대신 수동으로 루프 언롤링을 수행하면 코드를 이해하고 유지 관리하기가 더 어려워질 수 있다. * 함수 인라이닝과의 충돌: 루프 본문에 함수 호출이 포함된 경우, 언롤링은 과도한 코드 확장으로 인해 인라이닝을 방해할 수 있으며, 이 두 최적화 간에 상충 관계를 초래한다. * 레지스터 압력 증가: 성능을 위해 소프트웨어 파이프라이닝에 의존하는 하드웨어(예: 레지스터 이름 변경이 없거나 순서 내 슈퍼스칼라 실행을 사용하는 시스템)에서 언롤링은 반복 간에 임시 변수를 저장하기 위해 추가 레지스터를 필요로 하여 레지스터 재사용을 제한할 수 있다.s2cid=3353104 * 분기 예측: 최신 CPU는 분기 예측을 사용하여 분기가 어느 방향으로 갈지 추측하려고 한다. 예측이 정확하면 CPU는 분기가 해결될 때까지 기다리지 않고 명령어를 계속 실행할 수 있다. 그러나 예측이 잘못되면 CPU는 파이프라인을 비우고 올바른 명령어를 실행하기 시작해야 하며, 이는 성능 저하를 초래할 수 있다. 루프 언롤링은 코드 내 분기 수를 증가시켜 더 많은 분기 오예측과 낮은 성능으로 이어질 수 있다.Adam Horvath "Code unwinding - performance is far away"
# 정적/수동 루프 언롤링
수동 (또는 정적) 루프 언롤링은 프로그래머가 루프를 분석하고 반복을 루프 오버헤드를 줄이는 일련의 명령어로 해석하는 것을 포함한다. 이는 컴파일러에 의해 수행되는 동적 언롤링과는 대조된다.
## C 언어의 간단한 수동 예시
컴퓨터 프로그램의 한 절차는 컬렉션에서 100개의 항목을 삭제하는 것이다. 이는 일반적으로 delete(item_number) 함수를 호출하는 `for` 루프를 통해 수행된다. 이 프로그램 부분이 최적화되어야 하고, 루프의 오버헤드가 delete(x) 함수에 비해 상당한 리소스를 요구하는 경우, 언와인딩을 사용하여 속도를 높일 수 있다. {| class="wikitable" !일반 루프 !루프 언롤링 후 |-| int x; for (x = 0; x 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
# 추가 자료
*isbn=1-55860-286-0