Thu, 09 Aug 2007 11:44:25 -0700

From: | wclodius@lanl.gov |

Newsgroups: | comp.compilers |

Date: | Thu, 09 Aug 2007 11:44:25 -0700 |

Organization: | Compilers Central |

References: | 07-08-01607-08-021 |

Keywords: | optimize, parallel |

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.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.