2016년 11월 29일 화요일

루프 전개

루프 전개

루프 전개(루프라고 야, 영어: Loop Unwinding)는, 프로그램의 사이즈를 희생에 실행 속도를 최적화하는(시간과 공간의 트레이드 오프), 루프 변환(영문판)으로 불리는 수법의 하나이다.loop unrolling(영어: Loop Unrolling)이라고도 부른다.프로그래머가 수동으로 실시하기도 하고, 컴파일러가 실시하기도 한다.

루프 전개의 목적은, 매회가 반복할 것에 발생하는 「루프의 종료」조건의 테스트를 감소시키는(혹은 없앤다) 일에 의해서, 실행 속도를 향상시키는 것이다[1][2].루프는, 루프 자체를 제어하기 위한 오버헤드가 없어지도록(듯이), 독립한 명령 블록의 연속으로 고쳐 쓸 수 있는[3].

목차

이점

루프의 오버헤드는, 포인터 또는 인덱스를 인크리먼트 해 배열의 다음 요소를 가리키기 위한 명령군(포인터 연산)과 「루프 종료 조건」의 테스트에 유래한다.최적화 컴파일러등에서 배열의 개개의 요소에의 참조를 위한 오프셋을 사전에 계산할 수 있어 그것을 직접 기계어 명령열로 할 수 있다면, 실행시의 여분의 연산을 생략할 수 있다.

  • 루프 전개에 의해서 프로그램이 길어졌다고 해도, 그 이상으로 실질적인 실행 명령수가 삭감되면, 전체적으로는 성능이 강화된다.
  • 분기 패널티가 최소화되는[4].
  • 루프내의 각 문이 서로 의존하고 있지 않는 경우(즉, 루프가 있는 주회의 결과가 그 후의 주회로 필요하게 되지 않는 경우), 그러한 문장은 병렬 계산할 수 있을 가능성이 있다.
  • 컴파일시에 루프 회수(배열 요소수)가 불명한 경우에서도, 동적 루프 전개를 실장 가능하다(Duff's device).

최적화 컴파일러에는 자동적 또는 요구에 따라 루프 전개할 수 있는 것도 있다.

결점

  • 프로그램의 코드 사이즈가 증대하기 위해(때문에), 편입 시스템 등 메모리 용량이 작은 경우는 적절하지 않다.
    • 명령 캐쉬 미스 회수가 증가해 성능을 저하시키는 일이 있다.
  • 최적화 컴파일러는 투과적으로 루프 전개하지만, 전개 후의 코드는 가독성이 저하한다.
  • 루프내의 처리가 함수 호출이었던 경우, 인 라인 전개를 수반한 루프 전개는 코드가 방대하게 너무 되어서 현실적이지 않은 것이 있다.따라서 그것들 2개의 최적화동안에는 트레이드 오프의 관계가 있다고도 말할 수 있다.
  • 전개 후에 어떠한 최적화가 가능한가에도 의존하지만, 일시 변수용으로 레지스터를 많이 필요로 하는 경우는 성능이 저하할 가능성도 있는[5].
  • 작고 단순한 루프는 예외지만, 루프 본체내에 분기가 있는 경우는 재귀 호출보다 늦어지는 일이 있는[6].

정적/수동 루프 전개

일손에 의한(또는 정적인) 루프 전개는, 프로그래머가 루프를 분석해 전개하는 것으로 루프의 오버헤드를 저감 시키는 것이다.한편 컴파일러가 실시하는 루프 전개를 동적 루프 전개라고 부른다.

C언어로의 간단한 예

어느 프로그램의 수속으로, 데이터의 집합체로부터 100개의 요소를 삭제(delete)할 필요가 있다고 한다.이 때문에, for 루프내에서 함수 delete(요소의 번호)을 호출한다.이 부분을 최적화하는 경우, 루프에 필요한 오바헷드가 자원을 다대하게 소비하고 있다면, 루프 전개로 성능이 향상한다.

통상의 루프 루프 전개 후 
  int x;  for (x = 0; x < 100; x++)  {      delete(x);  } 
  int x;   for (x = 0; x < 100; x+=5)  {      delete(x);      delete(x+1);      delete(x+2);      delete(x+3);      delete(x+4);  }

이 수정의 결과, 새로운 프로그램의 루프 회수는 100회부터 20회에 삭감된다.점프 명령과 조건부 분기 명령의 실행 회수는 5분의 1이 되어, 루프 그 자체의 처리에 걸리는 시간은 큰폭으로 삭감될 가능성이 있다.그 효과를 최대로 하기 위해, 전개된 코드로는 포인터 계산을 하지 않게 하는 것이 중요하다.그 때문에 통상은 인덱스에 의한 참조로부터 베이스와 오프셋에 의한 참조로 전환할 필요가 있다.

한편, 루프 전개에 의해서 코드 사이즈는 3행에서 7행에 증가해 컴파일러는 전개된 부분에서 필요한 변수를 격납하는 레지스터를 한층 더 필요로 하게 될 가능성이 있다.더하고, 전개전과 전개 나중에 처리 결과가 같게 되도록(듯이), 루프 변수의 루프내에서의 조작은 주의 깊게 실시하지 않으면 안 된다.예를 들면, 위의 예로 6회 만큼의 루프를 전개했을 경우, 100은 6으로 나뉘어 떨어지지 않기 때문에, 전개전과 같은 결과를 얻으려면 세공이 필요하다.또, 루프의 종료 조건이 변수였던 경우에는 한층 더 문제는 복잡화 한다.Duff's device가 참조되고 싶다.

complex system

단순한 루프로는, 루프 제어는 단순한 관리 오바헷드이다.루프 자체는 필요한 결과에 직접 공헌할 것은 없고, 단지 프로그래머가 같은 코드를 얼마든지 코딩 하는 수고를 생략하는 것만으로 있다.그 만큼이면, 코드의 복제는 프리프로세서나 에디터의 기능을 사용해도 실현될 수 있다.이와 같이 if문등의 다른 제어 구조도 코드의 복제로 옮겨놓을 수도 있지만, 결과적으로 터무니없음 차 마시기 내기인 코드가 완성되어 버린다.프로그램은 편성에 끊임 없이 주의할 수 있지만, 인간은 지루한 작업에 참지 못하고, 실수를 범한다.

통상의 루프 루프 전개 후 
   for i:=1:8 do    if i mod 2 = 0 then do_evenstuff(i)                    else do_oddstuff(i);    next i; 
  do_oddstuff(1); do_evenstuff(2);  do_oddstuff(3); do_evenstuff(4);  do_oddstuff(5); do_evenstuff(6);  do_oddstuff(7); do_evenstuff(8);

그러나, 물론 전개되는 내용은 수속 호출일 필요는 없다.다음 예로는 인덱스 변수의 계산이 관련되고 있다.

통상의 루프 루프 전개 후 
  x(1) = 1;  For i:=2:9 do            x(i):=x(i - 1)*i;            print i,x(i);            next i; 
  x(1):=1;  x(2):=x(1)*2; print 2,x(2);  x(3):=x(2)*3; print 3,x(3);  ...etc.  .

컴파일러의 루프 전개에 의해서 대량의 코드(특히 print문)가 생성된다고 해도, 한층 더 최적화가 가능하다.이 예로는 루프내에서 x(i)와 x(i - 1) 밖에 참조하고 있지 않고(후자는 x(i)의 값을 만들기 위해서 마셔 참조), 배열 x에 외로부터 참조하는 것이 없으면, 배열의 각 요소를 단순한 변수에 옮겨놓을 수도 있다.게다가 이 코드로는 각 변수의 값을 정수로부터 요구하고 있고, 모두 정수로 간주할 수도 있다.그러자(면) 다음 같게 최적화할 수 있다.

 print 2,2; print 3,6; print 4,24; ...etc.

컴파일러가 x를 계승의 테이블이라고 인식했다고 하면 놀라움이다.

일반적으로 루프의 내용은 크고, 복잡한 배열의 인덱스부에 관련하고 있다.그 경우는 최적화 컴파일러에 전개를 맡기는 것이 최선일 것이다.가장 안쪽의 루프를 전개하는 것으로 여러가지 최적화가 가능해질지도 모르지만, 루프 회수가 많지 않은 한 효과는 한정적이다.

WHILE 루프의 전개

WHILE 루프의 의사 코드의 예를 나타낸다.

통상의 루프 루프 전개 후 전개해 「조정」한 루프 
   WHILE (condition) DO          action   ENDWHILE . . . . . . 
   WHILE (condition) DO          action          IF NOT(condition) THEN GOTO break          action          IF NOT(condition) THEN GOTO break          action  ENDWHILE  LABEL break: . 
  IF (condition) THEN   REPEAT {          action          IF NOT(condition) THEN GOTO break          action          IF NOT(condition) THEN GOTO break           action          } WHILE (condition)  LABEL break:

전개한 예로는 ENDWHILE(컴파일 되면 루프 선두에의 점프가 된다)의 실행 회수가 66%적게 되어, 고속화된다.

한층 더 「조정」을 더한 의사 코드의 예로는, 최적화 컴파일러를 사용하면 무조건 점프를 전혀 사용하지 않는 형태에 최적화될 것이다.

동적 루프 전개

루프 전개의 유효성은 대상이 되는 배열의 크기에 의존하지만, 실행시가 되지 않으면 그 크기가 판명 하지 않는 것도 많다.실행시 컴파일러(JIT) 등은, 통상의 루프에 해야 하는가, 전개해야할 것인가를 판단할 수 있다.루프 전개의 관점에서는, 이 유연성이 정적 또는 수동의 최적화에 비해 JIT 방식의 강점이 되고 있다.

어셈블리 언어로는, 효율적인 점프 테이블을 사용하는 기법으로 동적 루프 전개를 실시할 수 있다.여기서 중요해지는 것은, 배열의 최대 오프셋이 기계어 명령으로 나타낼 수 있는 범위인지 어떤지이다.그 범위외의 경우, 최적화의 효과가 희미해진다.다음 예는 System/360또는 Z/Architecture의 어셈블리 언어로 쓰여져 있다.FROM 배열과 TO배열은 각각 1 요소 256바이트로 50 요소 있어, 각 요소의 선두로부터 100바이트를 FROM로부터 TO에 카피하는 것이다.

어셈블리 언어(System/360)의 예

 * 배열등을 가리키도록(듯이) 전레지스터를 초기화해 두는(R14는 리턴 주소) LM    R15,R2,INIT                       load R15= '16', R0=배열 요소수, R1--> FROM 배열, R2--> TO배열 LOOP     EQU   *          SR    R15,R0                            배열 요소수를 16으로부터 빼는 BNP ALL                               n > 16이라면 전명령열을 실행해, 반복한다 * MVC 명령열의 선두로부터의 오프셋을 계산해, 전개된 MVC 루프의 소정의 위치에 무조건 점프 하는 MH    R15,=AL2(ILEN)                    MVC 명령의 길이(이 예로는 6)를 걸치는 B     ALL(R15)                          인덱스  분기 명령(그 위치로부터 MVC 명령을 실행) * 전송 테이블- 1개째가 최대 오프셋이며, 이 예로는 X'F00' ALL      MVC   15*256(100,R2),15*256(R1)         * 16번째의 엔트리의 100바이트를 FROM로부터 TO에 전송 ILEN     EQU   *-ALL                                         MVC 명령의 길이.이 예로는 6          MVC   14*256(100,R2),14*256(R1)         *          MVC   13*256(100,R2),13*256(R1)         *          MVC   12*256(100,R2),12*256(R1)         * 이것들 16개의 문자 전송 명령(MVC)은 베이스+오프셋의 애드레싱이며 MVC 11*256(100, R2),11*256(R1)         * 오프셋은 배열의 요소장(256) 두개 줄어 들고 있다.          MVC   10*256(100,R2),10*256(R1)         * System/360으로는 명령으로 지정할 수 있는 오프셋의 최대치는 X'FFF'여 MVC 09*256(100, R2),09*256(R1)         * 그것을 넘지 않는 범위에서 전개 가능한 최대가 16 요소라는 것이 된다.          MVC   08*256(100,R2),08*256(R1)         * 오프셋의 큰 분으로부터 전송 하므로, 선두의 요소가 마지막에 전송 된다.          MVC   07*256(100,R2),07*256(R1)         *          MVC   06*256(100,R2),06*256(R1)         *          MVC   05*256(100,R2),05*256(R1)         *          MVC   04*256(100,R2),04*256(R1)         *          MVC   03*256(100,R2),03*256(R1)         *          MVC   02*256(100,R2),02*256(R1)         *          MVC   01*256(100,R2),01*256(R1)         2번째의 요소의 100바이트를 전송 MVC 00*256(100, R2),00*256(R1)         1번째의 요소의 100바이트를 전송 *          S     R0,MAXM1                          나머지 요소수를 당기는 BNPR R14                               전부 전송 끝마쳤으므로, R14의 리턴 주소로 호출해 바탕으로 복귀 AH    R1,=AL2(16*256)                   FROM에의 포인터를 1 반복 만큼만 늦추는 AH    R2,=AL2(16*256)                   TO에의 포인터를 1 반복 만큼만 늦추는 L     R15,MAXM1                         R15를 MVC 명령수(16)에 재설정하는(계산으로 망가져 있기 때문에) B     LOOP                              루프의 선두로 돌아온다 * * -----정수와 변수의 정의(인수로서 건네줄 수도 있다) ---------------------------------  * INIT     DS    0A                                LM명령으로 사전 로드 되는 4개의 주소(포인터) MAXM1    DC    A(16)                             MVC 명령수 N        DC    A(50)                             배열의 요소수(변수이며, 변경 가능)          DC    A(FROM)                           배열 1의 선두 주소(포인터) DC    A(TO)                             배열 2의 선두 주소(포인터) * -----배열의 정의(동적으로 확보하는 일도 가능) --------------------------------------------------  * FROM     DS    50CL256                          256바이트×50 엔트리의 배열 TO       DS    50CL256                          256바이트×50 엔트리의 배열

이 예를 통상의 50회 반복하는 루프로 기술하면 202 명령을 필요로 하지만, 이와 같이 동적 코드로 하면 약 89 명령으로 끝난다( 약56%의 코드 삭감).배열이 2 요소 밖에 없는 경우에서도, 단순한 루프 전개와 동일한 정도의 명령수가 된다.바이너리 사이즈의 증대는 약 108바이트 정도여, 배열의 요소수가 수천이어도 대응 가능하다.이 경우는 MVC 명령의 반복을 전개했을 뿐이지만, 복수 명령의 경우도 같은 기법이 적용 가능하다.예를 들면, 이 예로 각 요소의 선두 100바이트를 카피한 후, 나머지의 부분을 눌 문자로 클리어 하고 싶은 경우, 'XC xx*256+100(156, R1), xx*256+100(R2)'라고 하는 명령을 각 MVC 명령의 뒤에 추가하면 좋다('xx'는 직전의 MVC 명령과 같은 값으로 한다. ILEN의 위치에 주의).

4또는 5개의 인수를 가지는 매크로로 상기 코드를 인 라인 전개하는 것도 가능하고, 써브루틴화하는 것도 가능하다.

C언어의 예

다음 예는 C언어로 쓰여진 간단한 프로그램을 동적 루프 전개한 것이다.어셈블리 언어의 상게의 예와는 달라, 변수(i)가 배열의 요소를 가리키는데 사용되고 있기 때문에, 컴파일러는 포인터/인덱스의 계산 코드를 생성하게 된다.최대한 최적화하려면 , 모든 인덱스 지정을 정수에 옮겨놓지 않으면 안 된다.

 #include<stdio.h>  #define TOGETHER (8)  int main(void) {  int i = 0;   int entries = 50;                                 /*총처리 회수*/ int repeat;                                       /*루프 회수*/ int left = 0;                                     /*나머지(나중에 처리한다) */ /*요소수가 BLOCKSIZE로 나뉘어 떨어지지 않는다고 해도,*/ /*처리의 대부분을 while 루프로 실시하도록(듯이), 반복 회수를 얻는다. */   repeat = (entries / TOGETHER);                    /*반복 회수*/ left = (entries % TOGETHER);                    /*나머지를 계산*/   /* 8회 만큼의 처리를 전개*/  while( repeat-- > 0 )   {     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);       /*인덱스를 정리해 갱신*/     i += TOGETHER;    }   /* switch문을 사용해, case 라벨의 점프 하는 것으로 넘치는 부분을 처리한다. */  /*포르스르에 의해, 넘치는 만큼을 전부 처리한다. */  switch (left)   {      case 7 : printf("process(%d)\n", i + 6);       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);      /*나머지가 2의 경우*/ case 1 : printf("process(%d)\n", i    );      /*나머지가 1의 경우*/ case 0 :                               ;      /*나뉘어 떨어졌을 경우*/   } }

각주

  1. ^ Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. pp. 471□2. ISBN 0-201-10073-8. 
  2. ^ Petersen, W.P., Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. p. 10. 
  3. ^ Nicolau, Alexandru (1985). Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257. 
  4. ^ Fog, Agner (2012년 2월 29일). "Optimizing subroutines in assembly language". Copenhagen University College of Engineering. pp. 100. 2012년 9월 22일 열람. "12.11 Loop unrolling"
  5. ^ Sarkar, Vivek (2001). "Optimized Unrolling of Nested Loops". International Journal of Parallel Programming 29 (5): 545–581. doi:10.1023/A:1012246031671. http://www.springerlink.com/content/g36002133451w774/. 
  6. ^ Adam Horvath "Code unwinding - performance is far away"

참고 문헌

Kennedy, Ken; & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0. 

관련 항목

외부 링크

「https://ja.wikipedia.org/w/index.php? title=루프 전개&oldid=61560277」으로부터 취득

This article is taken from the Japanese Wikipedia 루프 전개

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.

0 개의 댓글:

댓글 쓰기

피드 구독하기: 댓글 (Atom)