Tue, 07 Aug 2007 20:03:34 -0000

From: | SM Ryan <wyrmwif@tsoft.org> |

Newsgroups: | comp.compilers |

Date: | Tue, 07 Aug 2007 20:03:34 -0000 |

Organization: | Quick STOP Groceries |

References: | 07-08-016 |

Keywords: | optimize, parallel |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.