Path: utzoo!mnetor!uunet!husc6!tut.cis.ohio-state.edu!mailrus!ames!sgi!bron
From: bron@olympus.SGI.COM (Bron C. Nelson)
Newsgroups: comp.arch
Subject: Memory bank conflicts
Message-ID: <12514@sgi.SGI.COM>
Date: 10 Mar 88 17:20:37 GMT
References: <7690@pur-ee.UUCP> <3300021@uiucdcsm> <4712@lll-winken.llnl.gov>
Sender: daemon@sgi.SGI.COM
Organization: Silicon Graphics Inc, Mountain View, CA
Lines: 32
Summary: Frequency of various strides for arrays

In article <4712@lll-winken.llnl.gov>, brooks@lll-crg.llnl.gov (Eugene D. Brooks III) writes:
> In article <3300021@uiucdcsm> grunwald@uiucdcsm.cs.uiuc.edu writes:
> >
> >re: address hashing to randomize bank conflicts.
> >
> >I would think that this would be too slow in software. However, if I recall
> >correctly, randomized hashing was done in hardware on the RP-3 (it had some
> >sort of variable hashing so you could fiddle with the parameters).
> 
> Those who have been using supercomputers for the past decade have dealt
> with this sort of problem by carefully avoiding the undesired addressing
> modes.  Hashing takes care of the few pathological cases by slowing down
> the majority of cases which would normally stream at one word per clock.
> To slow down the machine to "random gather" speed for all of the normally
> high performance situtations is not desired.  This applies to shared memory
> multiprocessors as well as it does to single cpu supercomputers.

The issue regarding memory bank conflicts usually has to do (no
surprise) with array acesses.  I seem to recall that someone did a
study of array indexing (either LLNL or Cray I believe) and concluded
that for their test cases, about 60% of array accesses had a stride
of 1 (i.e. the code stepped sequentially through the array in memory
order), about 20% had stride 2, and about 20% "other".  WARNING: this
is off the top of my head; probably mis-remembered (the stride 2
number is suspiciously high).  This implies that relatively few jobs
benifit from randomizing the banks, and slowing down memory access
for everyone to get it may not be a win.

Can anyone (Brooks?) provide real stats about this?

Bron Nelson   bron@sgi.com
Don't blame my employers for my opinions.