Path: utzoo!mnetor!uunet!husc6!yale!lisper
From: lisper@yale.UUCP (Bjorn Lisper)
Newsgroups: comp.arch
Subject: Re: Was: RISC is a nasty no-no! More to the point: Supercomputer addresses
Message-ID: <24737@yale-celray.yale.UUCP>
Date: 8 Mar 88 17:10:07 GMT
References: <179@wsccs.UUCP: <696@nuchat.UUCP: <284@scdpyr.UUCP> <24605@yale-celray.yale.UUCP> <7690@pur-ee.UUCP>
Reply-To: lisper@yale-celray.UUCP (Bjorn Lisper)
Organization: Yale University Computer Science Dept, New Haven CT
Lines: 45
Summary: Changing storage order to speedup access

In article <7690@pur-ee.UUCP> hankd@pur-ee.UUCP (Hank Dietz) writes:
>In article <24605@yale-celray.yale.UUCP>, lisper@yale.UUCP (Bjorn Lisper)
>writes:
>> It seems that a smart compiler should be able to detect certain cases where
>> array elements are accessed in a order that cause slowdown due to memory
>> bank conflicts, and change the order of storage to speedup the access. Or
>> perhaps simply use a hash function to randomize the access pattern? This
>> is of course not possible in a language like FORTRAN where the order of
>> storage is strictly specified.
>
>Bjorn is quite correct, indeed, this is one of the main problems that
>we supercomputer compiler folk are looking at.  It turns out to be
>quite a nasty problem to re-arrange C data structures without changing
>the function of the program (see all the noise about just changing
>member order within a struct in comp.lang.c), but it is SOMETIMES
>do-able with a clever compiler.  FORTRAN is not really much easier
>than C, incidentally, because although it doesn't have multi-level
>indirection, it does have things like COMMONs and EQUIVALENCE which
>link layout of multiple data structures in complex ways.  I'm
>currently doing a lot of work on automatic parallelization for
>non-shared-memory machines... and this is a major concern.

One of the implications of my first posting that I didn't spell out is that
languages like C and FORTRAN maybe are not that suitable for programming
supercomputers for the reasons you mention; there are FORTRAN programs out
there whose correctness rely on matrix elements being stored in a certain
order, for instance. If we had a language that specifies nothing but the
functionality of accessing an array element, that is: the only thing we know
about a(i,j) is that it returns the current value of a(i,j) when referred
to, then an optimizing compiler for that language would have much more room
to play around with different storage orderings in order to minimize access
time. Isn't this a nice argument against using a language like FORTRAN in
scientific computing?

>Incidentally, the hash function idea works:  for a couple of years I've
>had a 95% completed paper sitting around on the use of nearly perfect
>hash functions to implement software address skewing...  maybe I ought
>to complete it and send it for publication somewhere?

Fun to hear that my idea wasn't totally out to lunch, it was just a flash I
got when writing my previous posting. I guess the trick is to find a hash
function that is cheap enough to evaluate while still not wasting too much
memory from the "imperfectness" of the hash function.

Bjorn Lisper