lindsay@K.GP.CS.CMU.EDU (Donald Lindsay) (03/03/88)
2-D arrays should not in general be implemented as vector-of-pointer-to- vector. The Burroughs 6700 had to do it this way, and it was a defect of the machine. This implementation method can be useful in specific cases. In general, it has bad properties. For one, Fortran can't use it. Fortran specifies that you can step past the end of one row and find yourself at the front of the next. (Or rather, columns .. ah, yes, Fortran! ) For another, it isn't uniform w.r.t. rows-versus-columns. One is preferred, the other penalized. The problem is that an algorithm may accidentally be coded to vary the "wrong" subscript more often than the "right" one. The performance hit (and the ensuing "optimization") are needless. -- Don lindsay@k.gp.cs.cmu.edu CMU Computer Science
eugene@eos.UUCP (Eugene Miya) (03/04/88)
In article <1020@PT.CS.CMU.EDU> lindsay@K.GP.CS.CMU.EDU (Donald Lindsay) writes: >2-D arrays should not in general be implemented as vector-of-pointer-to- >vector. The Burroughs 6700 had to do it this way, and it was a defect of the >machine. A defect? I'll pass that point of view on to the chief architect of the machine the next time I see him (two weeks). A feature! 8-) A good paper, BTW, is Duncan Lawrie's "Access and Alignment of Data" paper in IEEE TOC 1971. But he's over at the Cathedral Hill at COMPCON right now. Hey why we may have to divide comp.arch up, I got 25 articles to scan today. I can remember when comp.arch was near dead. From the Rock of Ages Home for Retired Hackers: --eugene miya, NASA Ames Research Center, eugene@ames-aurora.ARPA "You trust the `reply' command with all those different mailers out there?" "Send mail, avoid follow-ups. If enough, I'll summarize." {uunet,hplabs,hao,ihnp4,decwrl,allegra,tektronix}!ames!aurora!eugene
ram%shukra@Sun.COM (Renu Raman, Taco-Bell Microsystems) (03/05/88)
In article <244@eos.UUCP> eugene@eos.UUCP (Eugene Miya) writes: >A defect? I'll pass that point of view on to the chief architect of >the machine the next time I see him (two weeks). A feature! 8-) Is it D.J. Kuck or Stokes? 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). Only for succesive access to an array that had a displacement of 17, would there be conflicts and I doubt if 17 was a favourite of Fortran Programmers. The design is complicated by the Alignment network that is needed (you can find all the gory details in one of those refs.). An interesting application of this is in Frame Buffer design (more so with the multi-processor graphics engines) and probably for LIW machines. >A good paper, BTW, is Duncan Lawrie's "Access and Alignment of Data" paper >in IEEE TOC 1971. But he's over at the Cathedral Hill at COMPCON right now. > >From the Rock of Ages Home for Retired Hackers: > >--eugene miya, NASA Ames Research Center, eugene@ames-aurora.ARPA --------------------- Renukanthan Raman ARPA:ram@sun.com Sun Microsystems UUCP:{ucbvax,seismo,hplabs}!sun!ram M/S 5-40, 2500 Garcia Avenue, Mt. View, CA 94043
earl@mips.COM (Earl Killian) (03/08/88)
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).
Only for succesive access to an array that had a displacement of 17,
would there be conflicts and I doubt if 17 was a favourite of
Fortran Programmers.
But watch out for the diagonal of a 50x50 or 256x256 array :-)bron@olympus.SGI.COM (Bron C. Nelson) (03/09/88)
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.
eugene@pioneer.arpa (Eugene N. Miya) (03/10/88)
In article <12454@sgi.SGI.COM> bron@olympus.SGI.COM (Bron C. Nelson) writes: >A really great choice is 8191 banks, but it may be a year >or two before we see memories that big :-) If you count a memory attached to a CM processor as a bank, then we have 64K bank machines already. ;-) Sorry, you have two year data ;-). From the Rock of Ages Home for Retired Hackers: --eugene miya, NASA Ames Research Center, eugene@ames-aurora.ARPA "You trust the `reply' command with all those different mailers out there?" "Send mail, avoid follow-ups. If enough, I'll summarize." {uunet,hplabs,hao,ihnp4,decwrl,allegra,tektronix}!ames!aurora!eugene