Path: utzoo!attcan!uunet!ns-mx!iowasp!maverick.ksu.ksu.edu!zaphod.mps.ohio-state.edu!think!snorkelwacker!spdcc!esegue!compilers-sender
From: larus@primost.cs.wisc.edu (James Larus)
Newsgroups: comp.compilers
Subject: Re: Unsafe Optimizations (WAS: Compiler Design in C How about it?)
Keywords: optimize, parallel
Message-ID: <1990Jun7.010349.2097@esegue.segue.boston.ma.us>
Date: 7 Jun 90 01:03:49 GMT
References: <1990Jun6.032145.5495@esegue.segue.boston.ma.us> <1990Jun4.044255.14857@esegue.segue.boston.ma.us> <1990Jun1.194941.5781@esegue.segue.boston.ma.us> <1990Jun4.212226.18389@esegue.segue.boston.ma.us>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: larus@primost.cs.wisc.edu (James Larus)
Organization: University of Wisconsin--Madison
Lines: 39
Approved: compilers@esegue.segue.boston.ma.us

OK, now that everybody is interested in this argument, let me continue it.
Previously, I contended that "unsafe optimizations" are necessary for parallel
machines because without them, a programmer cannot express parallel
algorithms.  A number of people jump on me and pointed out that what is really
needed is a new language that allows a programmer to express his or her
intent.  I agree entirely, however a lot of programmers are stuck using
Fortran and C and will be using these languages for a long time.

Let's make this argument more concrete.  Consider the example of summing the
elements of a vector:

	for i <- 1 to n do
	  sum <- sum + A[i]

This operation takes O(n) time.  However, on a parallel computer with
sufficient processors, it can take O(lg n) time by using a parallel prefix
algorithm that builds up a tree of additions.  The problem is that this
optimization requires addition to be associative.  Integer and floating point
addition isn't associative.  However, how many programmers have carefully
analyzed their algorithm and convinced themselves that summing the elements
from 1 to N will produce the least error?  When was the last time you did
that?  Most programmers simply write the above loop as the most convenient
idiom for summing the vector. Although parallel prefix may produce a different
result, which is right and which is wrong?

Of course, some languages such as Fortran 90 permit a programmer to express
his intent in a manner that gives the compiler information about when order
matters.  Unfortunately, such languages are rare and only include a few common
idioms.

/Jim
[I suppose there is merit to this suggestion, but the thought of an optimizer
that second guesses the programmer and attempts to generate code for what the
program would have said if the source language was different fills me with
considerable unease. -John]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue.  Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.