Optimization tradeoffs (time vs. space)

One dramatic space/time tradeoff occurs in vectorizing and parallelizing
compilers. The transformation is called "scalar expansion". For example,
consider the loop:


do i = 1, n
      a = b + c
      d = a + e
      end


The loop cannot be run in parallel as written, since the value of
"a" used in the second statement will be indeterminate, as will the
final value of "d". If, however, the loop is transformed to:


do i = 1, n
      a'(i) = b + c
      d'(i) = a'(i) + e
      end


d = d'(n)
a = a`(n)


it can be run in parallel. A more complete discussion of this, and other
optimizing transformations, can be found in:


%A D. Padua
%A M. Wolfe
%T Advanced Compiler Optimization for Supercomputers
%J CACM
%V 29
%N 12
%P 1184-1201
%D December, 1986
[From midkiff@uicsrd.csrd.uiuc.edu (Sam Midkiff)]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.