Path: utzoo!mnetor!uunet!husc6!uwvax!oddjob!gargoyle!ihnp4!inuxc!iuvax!pur-ee!hankd
From: hankd@pur-ee.UUCP (Hank Dietz)
Newsgroups: comp.arch
Subject: Re: Was: RISC is a nasty no-no! More to the point: Supercomputer addresses
Message-ID: <7690@pur-ee.UUCP>
Date: 7 Mar 88 19:45:08 GMT
References: <179@wsccs.UUCP: <696@nuchat.UUCP: <284@scdpyr.UUCP> <24605@yale-celray.yale.UUCP>
Organization: Purdue University Engineering Computer Network
Lines: 26
Summary: Software address skewing is good

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.

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?

						-hankd