# Optimization tradeoffs (time vs. space)

## midkiff@uicsrd.csrd.uiuc.edu (Sam Midkiff)Tue, 9 Aug 88 09:34:13 CDT

From comp.compilers

Related articles
Optimization tradeoffs (time vs. space) roy@phri.uucp (1988-08-01)
Re: Optimization tradeoffs (time vs. space) markhall@pyramid.pyramid.com (1988-08-05)
Re: Optimization tradeoffs (time vs. space) ames!coherent!dplatt@ncar.UCAR.EDU (1988-08-05)
Re: Optimization tradeoffs (time vs. space) tekcrl.tek.com!willc@RELAY.CS.NET (Will Clinger) (1988-08-06)
Re: Optimization tradeoffs (time vs. space) gbs@nsc.nsc.com (1988-08-08)
Optimization tradeoffs (time vs. space) midkiff@uicsrd.csrd.uiuc.edu (1988-08-09)
Re: Optimization tradeoffs (time vs. space) roy@phri.uucp (1988-08-10)
Re: Optimization tradeoffs (time vs. space) mmengel@cuuxb.ATT.COM (1988-08-11)
| List of all articles for this month |
 Date: Tue, 9 Aug 88 09:34:13 CDT From: midkiff@uicsrd.csrd.uiuc.edu (Sam Midkiff)

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 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)]
--

Post a followup to this message