상위 질문
타임라인
채팅
관점
강도 감소
위키백과, 무료 백과사전
Remove ads
컴파일러 구성에서 강도 감소 또는 스트렝스 리덕션(strength reduction)은 비용이 많이 드는 연산을 동등하지만 비용이 적게 드는 연산으로 대체하는 컴파일러 최적화이다.[1] 강도 감소의 고전적인 예는 루프 내의 강한 곱셈을 약한 덧셈으로 변환하는 것으로, 이는 배열 주소 지정에서 자주 발생한다.(Cooper, Simpson & Vick 1995, 1쪽)
강도 감소의 예로는 루프 내의 곱셈을 덧셈으로 대체하고 루프 내의 거듭제곱을 곱셈으로 대체하는 것이 있다.
코드 분석
프로그램 실행 시간의 대부분은 일반적으로 코드의 작은 부분(핫 스팟이라고 불림)에서 소비되며, 이 코드는 종종 반복적으로 실행되는 루프 내에 있다.
컴파일러는 루프를 식별하고 해당 루프 내의 레지스터 값 특성을 인식하는 방법을 사용한다. 강도 감소를 위해 컴파일러가 관심을 갖는 것은 다음과 같다.
- 루프 불변: 루프 본문 내에서 변경되지 않는 값.
- 유도 변수: 루프를 통해 매번 반복되는 값.
루프 불변은 본질적으로 루프 내에서 상수이지만, 그 값은 루프 외부에서 변경될 수 있다. 유도 변수는 알려진 양만큼 변경된다. 이 용어는 특정 루프에 상대적이다. 루프가 중첩될 때, 바깥쪽 루프의 유도 변수는 안쪽 루프의 루프 불변이 될 수 있다.
강도 감소는 루프 불변과 유도 변수를 포함하는 표현식을 찾는다. 이러한 표현식 중 일부는 단순화될 수 있다. 예를 들어, 루프 불변 c와 유도 변수 i의 곱셈은
c = 7;
for (i = 0; i < N; i++)
{
y[i] = c * i;
}
연속적인 약한 덧셈으로 대체될 수 있다.
c = 7;
k = 0;
for (i = 0; i < N; i++)
{
y[i] = k;
k = k + c;
}
Remove ads
강도 감소 예제
요약
관점
다음은 배열 인덱싱 주소 계산에서 발생한 모든 루프 곱셈을 강도 감소시키는 예제이다.
배열을 단위 행렬로 설정하는 간단한 루프를 상상해 보자.
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
A[i,j] = 0.0;
}
A[i,i] = 1.0;
}
중간 코드
컴파일러는 이 코드를 다음과 같이 볼 것이다.
0010 ; for (i = 0, i < n; i++)
0020 ; {
0030 r1 = #0 ; i = 0
0040 G0000:
0050 load r2, n ; i < n
0060 cmp r1, r2
0070 bge G0001
0080
0090 ; for (j = 0; j < n; j++)
0100 ; {
0110 r3 = #0 ; j = 0
0120 G0002:
0130 load r4, n ; j < n
0140 cmp r3, r4
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0180 load r7, n
0190 r8 = r1 * r7 ; calculate subscript i * n + j
0200 r9 = r8 + r3
0210 r10 = r9 * #8 ; calculate byte address
0220 fr3 = #0.0
0230 fstore fr3, A[r10]
0240
0250 r3 = r3 + #1 ; j++
0260 br G0002
0270 ; }
0280 G0003:
0290 ; A[i,i] = 1.0;
0300 load r12, n ; calculate subscript i * n + i
0310 r13 = r1 * r12
0320 r14 = r13 + r1
0330 r15 = r14 * #8 ; calculate byte address
0340 fr4 = #1.0
0350 fstore fr4, A[r15]
0360
0370 ; i++
0380 r1 = r1 + #1
0390 br G0000
0400 ; }
0410 G0001:
이것은 2차원 배열 A를 n*n 크기의 1차원 배열로 표현하므로, 고수준 코드가 A[x, y]를 표현할 때마다 유효한 모든 인덱스 x와 y에 대해 내부적으로 A[(x*n)+y]가 된다.
많은 최적화
컴파일러는 강도 감소뿐만 아니라 많은 최적화를 시작한다. 루프 내에서 상수(불변)인 표현식은 루프 밖으로 끌어올려진다. 부동 소수점 레지스터 fr3 및 fr4와 같은 상수는 두 루프 외부에서 로드될 수 있다. 일부 변수가 변경되지 않는다는 인식은 레지스터를 병합할 수 있게 한다. n은 상수이므로 r2, r4, r7, r12는 끌어올려지고 병합될 수 있다. 공통 값 i*n은 (끌어올려진) r8과 r13에서 계산되므로, 이들은 합쳐진다. 가장 안쪽 루프(0120-0260)는 11개에서 7개의 중간 명령어로 감소되었다. 가장 안쪽 루프에 남아있는 유일한 곱셈은 0210번 줄의 8 곱셈이다.
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load r2, n
0130 ; load r4, n killed; use r2
0180 ; load r7, n killed; use r2
0300 ; load r12, n killed; use r2
0220 fr3 = #0.0
0340 fr4 = #1.0
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0190 r8 = r1 * r2 ; calculate subscript i * n
0310 ; r13 = r1 * r2 killed; use r8 ; calculate subscript i * n
0090 ; for (j = 0; j < n; j++)
0100 {
0110 r3 = #0 ; j = 0
0120 G0002:
0140 cmp r3, r2 ; j < n
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0200 r9 = r8 + r3 ; calculate subscript i * n + j
0210 r10 = r9 * #8 ; calculate byte address
0230 fstore fr3, A[r10]
0240
0250 r3 = r3 + #1 ; j++
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0390 br G0000
0400 }
0410 G0001:
더 많은 최적화가 필요하다. 레지스터 r3은 가장 안쪽 루프(0140-0260)의 주요 변수이다. 루프를 통과할 때마다 1씩 증가한다. 레지스터 r8(가장 안쪽 루프에서 불변)이 r3에 더해진다. 컴파일러는 r3 대신 r3을 제거하고 r9를 사용할 수 있다. 루프는 r3 = 0에서 n-1까지 제어되는 대신 r9=r8+0에서 r8+n-1까지 제어될 수 있다. 이는 4개의 명령어를 추가하고 4개의 명령어를 제거하지만, 루프 내부에는 하나의 명령어가 더 적다.
0110 ; r3 = #0 killed ; j = 0
0115 r9 = r8 ; new assignment
0117 r20 = r8 + r2 ; new limit
0120 G0002:
0140 ; cmp r3, r2 killed ; j < n
0145 cmp r9, r20 ; r8 + j < r8 + n = r20
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0200 ; r9 = r8 + r3 killed ; calculate subscript i * n + j
0210 r10 = r9 * #8 ; calculate byte address
0230 fstore fr3, A[r10]
0240
0250 ; r3 = r3 + #1 killed ; j++
0255 r9 = r9 + #1 ; new loop variable
0260 br G0002
이제 r9가 루프 변수이지만, 8을 곱하는 연산과 상호작용한다. 여기에서 우리는 강도 감소를 할 수 있다. 8을 곱하는 연산은 8을 연속적으로 더하는 것으로 줄일 수 있다. 이제 루프 안에 곱셈 연산이 없다.
0115 r9 = r8 ; new assignment
0117 r20 = r8 + r2 ; new limit
0118 r10 = r8 * #8 ; initial value of r10
0120 G0002:
0145 cmp r9, r20 ; r8 + j < r8 + n = r20
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0210 ; r10 = r9 * #8 killed ; calculate byte address
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0255 r9 = r9 + #1 ; loop variable
0260 br G0002
레지스터 r9와 r10(= 8*r9) 모두 필요하지 않다. 루프에서 r9를 제거할 수 있다. 이제 루프는 5개의 명령어로 구성된다.
0115 ; r9 = r8 killed
0117 r20 = r8 + r2 ; limit
0118 r10 = r8 * #8 ; initial value of r10
0119 r22 = r20 * #8 ; new limit
0120 G0002:
0145 ; cmp r9, r20 killed ; r8 + j < r8 + n = r20
0147 cmp r10, r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0255 ; r9 = r9 + #1 killed ; loop variable
0260 br G0002
바깥쪽 루프
전체 그림으로 돌아가서:
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0190 r8 = r1 * r2 ; calculate subscript i * n
0117 r20 = r8 + r2 ; limit
0118 r10 = r8 * #8 ; initial value of r10
0119 r22 = r20 * #8 ; new limit
0090 ; for (j = 0; j < n; j++)
0100 {
0120 G0002:
0147 cmp r10, r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0390 br G0000
0400 }
0410 G0001:
이제 r1을 증가시키는 외부 루프 내에 4개의 곱셈이 있다. 0190번 줄의 r8 = r1*r2는 루프 진입 전(0055번 줄)에 설정하고 루프 하단(0385번 줄)에서 r2만큼 증가시켜 강도 감소할 수 있다.
값 r8*8(0118번 줄)은 초기화(0056번 줄)하고 r8이 증가할 때 8*r2를 더하여(0386번 줄) 강도 감소할 수 있다.
레지스터 r20은 루프를 통과할 때마다 0117번 줄에서 불변/상수 r2에 의해 증가하고 있다. 증가된 후 8을 곱하여 0119번 줄에서 r22를 생성한다. 이 곱셈은 루프를 통과할 때마다 8*r2를 더함으로써 강도 감소할 수 있다.
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0190 ; r8 = r1 * r2 killed ; calculate subscript i * n
0117 ; r20 = r8 + r2 killed - dead code
0118 r10 = r40 ; strength reduced expression to r40
0119 ; r22 = r20 * #8 killed ; strength reduced
0090 ; for (j = 0; j < n; j++)
0100 {
0120 G0002:
0147 cmp r10, r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0390 br G0000
0400 }
0410 G0001:
마지막 곱셈
이제 두 루프는 외부 루프 내에 하나의 곱셈 연산(0330번 줄)만 남고 내부 루프에는 곱셈 연산이 없다.
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0118 r10 = r40 ; strength reduced expression to r40
0090 ; for (j = 0; j < n; j++)
0100 {
0120 G0002:
0147 cmp r10, r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0390 br G0000
0400 }
0410 G0001:
0320번 줄에서 r14는 r8과 r1의 합이며, r8과 r1은 루프 내에서 증가하고 있다. 레지스터 r8은 r2(=n)만큼 증가하고 r1은 1만큼 증가한다. 결과적으로 r14는 루프를 통과할 때마다 n+1만큼 증가한다. 0330번 줄의 마지막 루프 곱셈은 루프를 통과할 때마다 (r2+1)*8을 더함으로써 강도 감소될 수 있다.
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
005A r14 = r8 + r1 ; copied from 0320
005B r15 = r14 * #8 ; initial value of r15 (0330)
005C r49 = r2 + #1
005D r50 = r49 * #8 ; strength reduced increment
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0118 r10 = r40 ; strength reduced expression to r40
0090 ; for (j = 0; j < n; j++)
0100 {
0120 G0002:
0147 cmp r10, r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 ; r14 = r8 + r1 killed ; dead code
0330 ; r15 = r14 * #8 killed ; strength reduced
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0389 r15 = r15 + r50 ; strength reduce r15 = r14 * 8
0390 br G0000
0400 }
0410 G0001:
아직 더 남았다. 상수 폴딩은 프롤로그에서 r1=0임을 인식하여 여러 명령어를 정리할 것이다. r8은 루프에서 사용되지 않으므로 사라질 수 있다.
게다가, r1은 루프를 제어하기 위해서만 사용되므로, r1은 r40과 같은 다른 유도 변수로 대체될 수 있다. i가 0 <= i < n으로 갔던 곳에서, 레지스터 r40은 0 <= r40 < 8 * n * n으로 간다.
0010 ; for (i = 0, i < n; i++)
0020 {
0030 ; r1 = #0 ; i = 0, becomes dead code
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 ; r8 = #0 killed ; r8 no longer used
0056 r40 = #0 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 ; r20 = r2 killed ; r8 = 0, becomes dead code
0058 r22 = r2 * #8 ; r20 = r2
005A ; r14 = #0 killed ; r8 = 0, becomes dead code
005B r15 = #0 ; r14 = 0
005C r49 = r2 + #1
005D r50 = r49 * #8 ; strength reduced increment
005D r60 = r2 * r30 ; new limit for r40
0040 G0000:
0060 ; cmp r1, r2 killed ; i < n; induction variable replaced
0065 cmp r40, r60 ; i * 8 * n < 8 * n * n
0070 bge G0001
0080
0118 r10 = r40 ; strength reduced expression to r40
0090 ; for (j = 0; j < n; j++)
0100 {
0120 G0002:
0147 cmp r10, r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 ; r1 = r1 + #1 killed ; dead code (r40 controls loop)
0385 ; r8 = r8 + r2 killed ; dead code
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0389 r15 = r15 + r50 ; strength reduce r15 = r14 * 8
0390 br G0000
0400 }
0410 G0001:
Remove ads
다른 강도 감소 연산
연산자 강도 감소는 수학적 항등식을 사용하여 느린 수학 연산을 더 빠른 연산으로 대체한다. 이점은 대상 CPU와 때로는 주변 코드(CPU 내의 다른 기능 단위의 가용성에 영향을 미칠 수 있음)에 따라 달라진다.
- 2의 거듭제곱으로 하는 정수 나눗셈 또는 곱셈을 산술 시프트 또는 논리 시프트로 대체[2]
- 상수로 하는 정수 곱셈을 시프트, 덧셈 또는 뺄셈의 조합으로 대체
- 상수와 하는 정수 나눗셈을 곱셈으로 대체하여 기계 정수의 제한된 범위를 활용한다.[3] 이 방법은 나눗셈이 1보다 충분히 큰 비정수, 예를 들어 √2 또는 π인 경우에도 작동한다.[4]
유도 변수 (고아)
유도 변수 또는 재귀적 강도 감소는 체계적으로 변하는 변수의 함수를 함수의 이전 값을 사용하여 더 간단한 계산으로 대체한다. 절차형 프로그래밍 언어에서는 루프 변수를 포함하는 표현식에 적용되며, 선언형 프로그래밍 언어에서는 재귀 함수의 인수에 적용된다.[5] 예를 들어,
f x = ... (3 ** x) ... (f (x + 1)) ...
는 다음과 같이 된다.
f x = f' x 1
where
f' x z = ... z ... (f' (x + 1) (3 * z)) ...
여기서 수정된 재귀 함수 f′는 두 번째 매개변수 z = 3 ** x를 사용하여 비용이 많이 드는 계산 (3 ** x)을 더 저렴한 (3 * z)로 대체할 수 있게 한다.
같이 보기
- 고속 역 제곱근
- 해커의 즐거움
- 부분 평가
내용주
각주
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads