Strength Reduction

Posted 2006. 9. 18. 01:19
strength reduction은 타겟 머신에서 무거운(expensive) 연산을 가벼운(cheap) 연산으로 바꾸는 컴파일러 최적화 기법을 말한다. 쉬운 예로, 곱하기 연산을 더하기 연산으로 바꾸는 경우를 들 수 있다.

썬 마이크로시스템즈에서 나온 다음 논문(
Operator Strength Reduction)에 자세한 설명이 있다.

Operator strength reduction is a technique that improves compiler-generated code by reformulating
certain costly computations in terms of less expensive ones. A common case arises in array
addressing expressions used in loops. The compiler can replace the sequence of multiplies generated
by a direct translation of the address expression with an equivalent sequence of additions.


구체적인 예로는

for i from 1 to n do
   z= i*x
  ...
end

위와 같은 코드를 다음과 같이 바꿔 주는 것이다.

z=0;
for i from 1 to n do
  z=z+x
  ..
end
 

Loop Unrolling(unwinding)

Posted 2006. 9. 13. 01:31
직관적으로 쉽게 이해할 수 있는 최적화 중에 하나는 루프를 푸는 loop unrolling이 있다.

Loop: 루프를 100번 돈다
for (i = 0; i < 100; i++)
  g ();

Unrolled loop : 루프를 50번 돈다
for (i = 0; i < 100; i += 2)
{
  g ();
  g ();
}

g()를 두 번 실행하지만 루프의 길이는 반으로 줄였다. 이 최적화의 기본 아이디어는 루프를 실행하는데 드는 오버헤드를 줄이는데 있다. 루프는 loop condition을 검사하고 jump하는 오버헤드가 있기 때문에 루프 수를 줄이면 branching을 줄이고 cache hit ratio를 높여주는 효과가 있다.

물론 다음과 같은 부작용도 있다.

1) 코드 사이즈의 증가

2) 루프가 길어지면서 레지스터 사용량이 증가 (결국 일부가 spill out 됨)

최적화 컴파일러

Posted 2006. 9. 13. 01:20
최적화 컴파일러(Optimzing Compiler)는 전산계의 로켓 과학이므로 많은 개발자의 로망일 것입니다. 앞으로 공부도 할 겸 시간날 때마다 컴파일러 최적화에 대한 글을 써보려고 합니다! 관심 부탁드려요.
« PREV : 1 : ··· : 73 : 74 : 75 : 76 : 77 : 78 : 79 : ··· : 82 : NEXT »