Re: latest trends in compiler optimization research?

On Aug 7, 2:03 pm, SM Ryan <wyrm...@tsoft.org> wrote:
> Anton Lokhmotov <al...@cam.ac.uk> wrote:
><sni>
> A rather simple example, is that the 205 had vector instructions for
>
> do 1 i=1,n
> 1 a(x(i)) = s*a(x(i))
>
> with vector gather, vector multiply, and vector scatter, but it's
> impossible in general to prove the loop is interference free. So a
> vectoriser cannot vectorise it. However the programmer may know
> absolutely that x has no repeated values and is actually interference
> free, but the serial notation does not permit this to be expressed.
>
> Fortran programmers instead of trying to craft serial loops that
> could be recognised, often wrote exactly what they wanted
> in the vector notation extension to the compiler. I don't recall
> exactly what it was, but it was something like
>
> call v8gathr(t,a,x,n)
> t(1;n) = s*t(1;n)
> call v8scatr(a,t,x,n)
>
> so the programmer expresses exactly what they intend and take
> full responsibility for proving no interference upon themselves.
>
> I eventually realised it's better use of everyone's effort to give
> programmers a good notation for expressing themselves accurately and
> clearly without unnecessary constraints to express their algorithm at
> a high level. (The 205 vector notation was not very good; in
> retrospect it would've been a better use of resources to improve the
> vector notation than to worry about the vectoriser.)
>
> I lost track of Fortran before 90 was standarised, but the array
> notation of 8X was seriously broken: while theoretically letting
> programmers express themselves at a high level, it forced serial
> semantics whether the programmer intended that or no; thus the
> notation could not be vectorised or parallelised any easier than if
> explicit do loops had been used.


I would not call the array notation seriously broken. Yes it does not
provide semantics that are not present in the equivlent assignment
using do loops, and optimizing array expression code is equivalent to
optimizing the equivalent loops. But it does provide a more compact way
of writing that equivalent code, and that code is as a result quicker
to write, easier to read, and less prone to errors. The most
straightforward optimizations for such codes were also already
imlemented inthe Fortran banckend (optimizations involving examining
sequences of such assignments took awhile). Further sequential
semantics is the safest semantics for this type of notation.


FWIW Fortran 95 and 2003 have the FORALL assignment statement that
provides the semantics you desire, however it has not been popular in
the modern codebase for a variety of reasons. Novices tend to view the
FORALL syntax as an alternative form of DO syntax, and not an
assignment statement, i.e., they might use it in error prone ways.
Most processors in use today, particularly the desktop machines
commonly used in early development, do not have gather/scatter
capabilities, so that semantics in practice often does not provide the
optimization that it allows. (Although similar semantics are useful
for networks of such processors.) While the gather/scatter semantics is
useful for some types of codes, e.g., sparse matrix calculations, they
are only a subset of scientific codes, and not always the time
critical parts.
>
> Transforming code to a parallel version assuming no conflicts is
> always trivial. There is no real advantage to a special array notation
> just for that. The intractable part is proving there is no
> interference so that the reordered execution of the parallelised code
> is semantically equivalent to the serial code; a notation that does
> not require that often impossible proof is a big win for the
> programmer, assuming the programmer accepts the proof responsibility
> for themselves.

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