Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!apple!amdcad!sun!pitstop!sundc!seismo!uunet!mcvax!kth!draken!bjornl From: bjornl@octopus.tds.kth.se (Bj|rn Lisper) Newsgroups: comp.arch Subject: Re: Multi-Processor Serializability Message-ID: Date: 3 Feb 89 11:06:18 GMT References: <3492@cloud9.Stratus.COM> <1066@cmx.npac.syr.edu> <88088@sun.uucp> Sender: news@nada.kth.se Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden. Lines: 45 In-reply-to: khb%chiba@Sun.COM's message of 2 Feb 89 19:17:05 GMT In article <88088@sun.uucp> khb%chiba@Sun.COM (Keith Bierman - Sun Tactical Engineering) writes: >In article <1066@cmx.npac.syr.edu> billo@snacpac.npac.syr.edu.UUCP (Bill >O'Farrell) writes: >> ..... Both the Alliant >>and Encore compiler also perform "good old" global optimization, and both >>never NEVER perform an optimization if it would change the meaning of a >>program. >This is not quite true. Most very highly optimizing compilers have >(often undocumented) unsafe modes which intentionally change the >semantics of the code. .... The problem is, of course, the difference between the semantics of the programming language and what the programmer considers to be the meaning. In scientific/numerical applications I think the intended meaning often is a function (e.g. the solution vector to a system of linear equations, which is a function of the system matrix and the right-hand side vector). The semantics of an imperative program (read: Fortran) is, however, based on states and state transitions. Since the state is comprised of the values of all the variables in a program and the value of the program counter, this means that an optimizing or parallelizing compiler really must take ALL variables into account, including those just intended as temporary work areas, if it is not to violate the semantics. Thus, a compiler for an imperative language can either be very conservative and abide to the semantics of the programming language, or try to guess the real intention of the programmer in order to allow itself a richer set of transformations. >In addition, even modest levels of optimization can cause subtle >changes in numerical results. On ieee 64-bit mode this is seldom seen, >but in 32-bits it can often be observed. Yes, this is another problem. For instance, a typical parallelizing operation is to use associativity to change a linear, inherently serial n-chain of binary operations into a balanced tree with O(log n) height. Sums can be treated this way PROVIDED THAT ADDITION IS ASSOCIATIVE. Floating point addition is, however, NOT associative. Changing the order of summation will give slightly different results, because round-off and cancellation errors depend on the magnitude of the added numbers. One can, in fact, easily construct examples where reordering of summations give disastrous results from a numerical point of view. Thus, a compiler should not use algebraic laws for real numbers to transform floating-point expressions without the consent of the programmer. Bjorn Lisper