Path: utzoo!mnetor!uunet!husc6!mailrus!ames!sgi!bron
From: bron@olympus.SGI.COM (Bron C. Nelson)
Newsgroups: comp.arch
Subject: Re: 2-D arrays
Message-ID: <12454@sgi.SGI.COM>
Date: 9 Mar 88 04:41:54 GMT
References: <179@wsccs.UUCP: <696@nuchat.UUCP> <284@scdpyr.UUCP> <1797@gumby.mips.COM>
Sender: daemon@sgi.SGI.COM
Organization: Silicon Graphics Inc, Mountain View, CA
Lines: 21
Summary: Prime number of memory banks

In article <1797@gumby.mips.COM>, earl@mips.COM (Earl Killian) writes:
> In article <44258@sun.uucp> ram%shukra@Sun.COM (Renu Raman, Taco-Bell Microsystems) writes:
> 
>      In any case, in the BSP, Kuck et. al. designed a memory system
>      where the interleave size and bank size were relatively prime (16
>      & 17 I think. - ref: paper by kuck & Stokes on BSP in IEEE TOC,
>      May 82.  You can probably find it in Faye's book too).
> 
> But watch out for the diagonal of a 50x50 or 256x256 array :-)

The tricky part of course is figuring out which bank a particular
address lies in.  I don't know offhand how you do this for a 17 way
interleave, but there is a fast method for doing it if the interleave
is one less than a power of two (only takes an add or two).  This is
clearly not as fast as just masking off the low order bits, but its
not too bad.  This makes 31 banks (a prime that's 2^n-1) a good
choice.  A really great choice is 8191 banks, but it may be a year
or two before we see memories that big :-)

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