Re: latest trends in compiler optimization research?

Anton Lokhmotov <al407@cam.ac.uk> wrote:
# Dear SM Ryan,
# > I worked many years ago on the Cyber 205 Fortran vectoriser; as good
# > as we got the vectoriser, most people still preferred to directly
# > use the vector notation added to Fortran.
#
# I really like this comment of yours. I am writing a PhD on programming
# embedded SIMD architectures, and would love to quote something like
# that. Could you please let me know if there's any particular source I
# could quote (papers, manuals, memoires, etc.)?


I don't know if any documentation has survived; this was twenty to
thirty years ago. The 205 and Kuck vectorisers had the same problem
that is also hitting modern parallelisers: the transform cannot modify
the semantics of the original serial code, and the original serial
code contains more order constraints than the programmer
intended. Which means the programmer has to somehow tell the optimiser
that there are no conflicts, or the conflicts are not signficant.


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.


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.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
One of the drawbacks of being a martyr is that you have to die.

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