Path: utzoo!attcan!uunet!husc6!bloom-beacon!tut.cis.ohio-state.edu!mailrus!ames!oliveb!pyramid!markhall
From: markhall@pyramid.pyramid.com (Mark Hall)
Newsgroups: comp.std.c
Subject: Re: Question about regrouping of operands
Summary: out of order execution wanted
Keywords: small-grained parallel execution
Message-ID: <24334@pyramid.pyramid.com>
Date: 23 May 88 17:16:23 GMT
References: <16490001@hpcllz2.HP.COM> <881@actnyc.UUCP> <19000@watmath.waterloo.edu> <7952@brl-smoke.ARPA>
Reply-To: markhall@pyramid.UUCP (Mark Hall)
Organization: Pyramid Technology Corp., Mountain View, CA
Lines: 26

In article <7952@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>In article <19000@watmath.waterloo.edu> rbutterworth@watmath.waterloo.edu (Ray Butterworth) writes:
>>[ a + b + c + ... + x + y + z ]
>>Now if integer overflow checking is enabled, the compiler is
>>no longer free to do the additions in any order it wants.  It
>>must do them in precisely the order that the programmer has
>>requested, since the programmer might have specificly requested
>>that order to prevent overflow.
>
>This is correct.  However, it has not been demonstrated that a
>serious loss of efficiency will necessarily result from removal
>of this kind of optimization.  
>

A `perfect' Multi-Flow type machine (or any machine which 
supports fine-grain parallel execution), is able to evaluate 
this expression (assuming N is the number of operations) in 
		log N
		   2
instructions, given no restriction on execution order.  Constraining
such a machine to the serial execution order of the above expression,
which requires N instructions, is indeed a serious loss of efficiency.

I'll concede, however, that such expressions with large N are rare.
 
Mark Hall {seismo | sun | decwrl}!pyramid!markhall