루프 핵분열과 핵융합

Loop fission and fusion

컴퓨터 과학에서 루프 핵분열(또는 루프 분포)은 동일한 지수 범위에 걸쳐 루프가 여러 개의 루프로 분해되는 컴파일러 최적화로 각각은 원래 루프 본체의 일부만 취한다.[1][2]큰 루프 본체를 작은 루프 본체로 분해하여 참조 위치의 활용도를 높이는 것이 목표다.이러한 최적화는 각 프로세서에 대해 작업을 여러 작업으로 분할할 수 있는 멀티 코어 프로세서에서 가장 효율적이다.

반대로 루프 융접(또는 루프 걸림)은 컴파일러 최적화 및 루프 변환으로 여러 루프를 단일 루프로 대체한다.[3][2]루프 융접이 런타임 속도를 항상 향상시키는 것은 아니다.어떤 아키텍처에서는, 예를 들어, 각 루프 내에서 데이터 인접성이 증가하기 때문에 실제로 두 루프가 한 루프보다 더 잘 수행될 수 있다.루프 융합의 주요 이점 중 하나는 일시적 할당을 피할 수 있다는 것인데, 이는 배열에서 요소별 연산을 할 때 줄리아와 같은 수치 컴퓨팅 언어에서 엄청난 성능 이득을 가져올 수 있다(그러나 줄리아의 루프 융접은 기술적으로 컴파일러 최적화가 아니라 언어의 통사적 보증이다).[4]

루프 융합의 다른 이점은 루프 제어 구조의 오버헤드를 방지하고, 또한 명령 레벨 병렬화를 이용하여 루프 본체를[5] 프로세서에 의해 병렬화할 수 있다는 것이다.이것은 두 루프의 본체 사이에 데이터 의존성이 없을 때 가능하다(이는 결과를 저장하기 위해 중간 배분이 필요한 데이터 의존성이 있을 때만 그 자체를 제시하는 위에서 설명한 루프 융합의 다른 주요 이익과는 극명한 대조를 이룬다).루프 융합이 중복 할당을 제거할 수 있다면 성능 증가가 클 수 있다.[4]그렇지 않으면, 데이터 지역성, 명령 수준 병렬화 및 루프 오버헤드(분지, 증분 등) 사이에 더 복잡한 트레이드오프가 있어 루프 융복합, 루프 핵분열 또는 둘 다 선호되는 최적화를 만들 수 있다.

핵분열

C의 예

인트로 i, a[100], b[100]; 을 위해 (i = 0; i < 100; i++) {     a[i] = 1;     b[i] = 2; }

다음 항목과 동일하다:

인트로 i, a[100], b[100]; 을 위해 (i = 0; i < 100; i++) {     a[i] = 1; } 을 위해 (i = 0; i < 100; i++) {     b[i] = 2; }

퓨전

C++ 및 MATLAB의 예

다음 MATLAB 코드를 고려하십시오.

x = 0:999; % 0 ~ 999 사이의 숫자 배열 생성(범위 포함) y = 죄를 짓다(x) + 4; % x의 사인(기본값)을 취하고 각 요소에 4를 추가하십시오.

기능 과부하와 연산자 과부하를 사용하여 C++에서 동일한 구문을 얻을 수 있다.

#include <cmath> #include <캐서트> #include <기억> #include <아이오스트림>  계급 배열 {     size_t 길이;     찌꺼기::유니크_ptr<둥둥 뜨다[]> 자료의;          // 초기화되지 않은 배열을 생성하는 내부 생성자     배열(size_t n) : 길이(n), 자료의(새로운 둥둥 뜨다[n]) { }      공중의:     // 정수 범위(상단)에 걸쳐 배열을 생성하는 공장 방식     // MATLAB의 범위와 달리 바운드는 배타적이다.     정태의 배열 범위(size_t 출발하다, size_t 종지부를 찍다) {         주장하다(종지부를 찍다 > 출발하다);         size_t 길이 = 종지부를 찍다 - 출발하다;         배열 a(길이);         을 위해 (size_t i = 0; i < 길이; ++i) {             a[i] = 출발하다 + i;         }         돌아오다 a;     }          // 기본 어레이 작업     size_t 사이즈를 맞추다() 경시하다 { 돌아오다 길이; }     둥둥 뜨다& 운영자[](size_t i) { 돌아오다 자료의[i]; }     경시하다 둥둥 뜨다& 운영자[](size_t i) 경시하다 { 돌아오다 자료의[i]; }      // 과부하된 추가 연산자를 자유 친구 함수로 선언(이것)     // 구문에서는 오퍼레이터+를 친구인 자유 함수로 정의한다.     // class, 그것이 회원 기능 선언으로 등장함에도 불구하고).     친구 배열 운영자+(경시하다 배열& a, 둥둥 뜨다 b) {         배열 c(a.사이즈를 맞추다());         을 위해 (size_t i = 0; i < a.사이즈를 맞추다(); ++i) {             c[i] = a[i] + b;         }         돌아오다 c;     }          // 마찬가지로 죄() 함수에 대한 과부하를 정의할 수 있다.실제로.     // 과부하될 수 있는 모든 수학 연산을 다음과 같이 정의하는 것은 무리일 것이다.     // 이런 반 친구들, 하지만 이것은 예에 불과하다.     친구 배열 죄를 짓다(경시하다 배열& a) {         배열 b(a.사이즈를 맞추다());         을 위해 (size_t i = 0; i < a.사이즈를 맞추다(); ++i) {             b[i] = 찌꺼기::죄를 짓다(a[i]);         }         돌아오다 b;     } };  인트로 본래의(인트로 argc, 마를 뜨다* 아그브[]) {     // 여기서는 MATLAB의 예와 동일한 계산을 수행한다.     자동차로 x = 배열::범위(0, 1000);     자동차로 y = 죄를 짓다(x) + 4;          // 결과 출력 - 최적기가 제거되지 않는지 확인     // 모든 것(만약 그렇게 할 수 있을 만큼 똑똑하다면).     찌꺼기::뻐드렁니가 나다 << "결과는: " << 찌꺼기::끝을 맺다;     을 위해 (size_t i = 0; i < y.사이즈를 맞추다(); ++i) {         찌꺼기::뻐드렁니가 나다 << y[i] << 찌꺼기::끝을 맺다;     }          돌아오다 0; }

그러나 위의 예에서는 결과물에 대해 불필요하게 임시 배열을 할당한다.sin(x). 보다 효율적인 구현으로 단일 어레이를 할당하여y, 및 계산y한 고리로이를 최적화하려면 C++ 컴파일러는 다음을 수행해야 한다.

  1. 인라인 더sin그리고operator+함수 호출
  2. 루프를 단일 루프로 퓨즈하십시오.
  3. 사용하지 않는 저장소를 임시 배열로 제거하십시오(대신 레지스터 또는 스택 변수를 사용할 수 있음).
  4. 사용되지 않는 할당을 제거하고 무료로 사용하십시오.

이 모든 단계는 개별적으로 가능하다.심지어 4단계는 다음과 같은 기능이 있음에도 불구하고 가능하다.malloc그리고free일부 컴파일러 하드코드 기호(예: 다음과 같은)가 있기 때문에 세계적인 부작용이 있다.malloc그리고free코드에서 사용되지 않는 할당을 제거할 수 있도록.[6]그러나 cang 12.0.0 및 gcc 11.1을 기준으로, 이러한 루프 융접 및 중복 할당 제거는 최고 최적화 수준에서도 발생하지 않는다.[7][8]

Julia와 같이 수치 컴퓨팅을 특별히 목표로 하는 몇몇 언어들은 높은 수준에서 그것의 안에 루프 융합의 개념을 가지고 있을 수 있는데, 여기서 컴파일러는 인접한 요소들의 작동을 알아차리고 그것들을 하나의 루프에 융합시킬 것이다.[9]현재, C++와 같은 범용어에서도 같은 구문을 달성하기 위해, 다음과 같이 한다.sin그리고operator+함수는 어떤 컨텍스트에서 호출될지 모르기 때문에 결과를 저장하기 위해 비관적으로 배열을 할당해야 한다.이 문제는 컴파일러에 의존하지 않는 다른 구문을 사용하여 불필요한 임시 할당을 제거함으로써(예를 들어, 다음과 같은 내부 작업에 대해 함수 및 과부하 사용) C++에서 피할 수 있다.operator+=또는std::transform).

참고 항목

참조

  1. ^ Y.N. Srikant; Priti Shankar (3 October 2018). The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition. CRC Press. ISBN 978-1-4200-4383-9.
  2. ^ a b Kennedy, Ken & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
  3. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. loop fusion.
  4. ^ a b Johnson, Steven G. (21 January 2017). "More Dots: Syntactic Loop Fusion in Julia". julialang.org. Retrieved 25 June 2021.{{cite web}}: CS1 maint : url-status (링크)
  5. ^ "Loop Fusion". Intel. Retrieved 2021-06-25.
  6. ^ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)". godbolt.org. Retrieved 2021-06-25.
  7. ^ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)". godbolt.org. Retrieved 2021-06-25.
  8. ^ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 gcc 11.1)". godbolt.org. Retrieved 2021-06-25.
  9. ^ "Functions · The Julia Language". docs.julialang.org. Retrieved 2021-06-25.