ttw@lanl.gov (Tony Warnock) (12/07/90)
In a 1000 by 1000 by 1000 by 1000 by 50 array, would
someone please post the pointer structure that allows
access sequentially in each dimension?
How big is the resulting set of pointers?
How many memory accesses per element?
If the 50 is the last dimension accessed, one needs at least
240240240240000 pointers which is half the number of data
elements in order to access each of the other dimensions
in any of the 24 orders. If there is a better orgainzation,
it would be good if someone would post it.
The requirements are that each dimension may be accessed
in the 5-dimensional loop in any order.buckland@cheddar.ucs.ubc.ca (Tony Buckland) (12/08/90)
In article <8086@lanl.gov> ttw@lanl.gov (Tony Warnock) writes: > > In a 1000 by 1000 by 1000 by 1000 by 50 array, would > someone please post the pointer structure that allows > access sequentially in each dimension? > > How big ... Please tell me this is just a theoretical question. At least tell me this a *very* sparse array, of which you only plan to store a tiny fraction of the elements, and that you're asking how to get from one stored element to the next stored one along any dimension. Full storage of this array, assuming you need only fullword precision, would require 2 * 10**5 Gigabytes, more than can conveniently be attached to most workstations. About ten thousand times the size of my installation's mainframe disk farm. A 300-Mby disk for every man, woman and child in a mid-sized U.S. city. A lot.
ttw@lanl.gov (Tony Warnock) (12/08/90)
Tony Buckland asks: >In article <8086@lanl.gov> ttw@lanl.gov (Tony Warnock) writes: >> >> In a 1000 by 1000 by 1000 by 1000 by 50 array, would >> someone please post the pointer structure that allows >> access sequentially in each dimension? >> >> How big ... > > Please tell me this is just a theoretical question. At least > tell me this a *very* sparse array, of which you only plan to > store a tiny fraction of the elements, and that you're asking > how to get from one stored element to the next stored one > along any dimension. Full storage of this array, assuming > you need only fullword precision, would require 2 * 10**5 > Gigabytes, more than can conveniently be attached to most > workstations. About ten thousand times the size of my > installation's mainframe disk farm. A 300-Mby disk for every > man, woman and child in a mid-sized U.S. city. A lot. No, I mean a 1000x1000x1000x1000x50 array in main memory. I know that current technology does not provided such sizes. Such arrays are small compared with what one wants in computation of weather models, fluid flow, QCD, etc. The question arises in that one Dan Bernstein has claimed that only 2050 pointers are necessary to access such an array and that this style of data structure is 5% faster than using normal Fortran array addressing. I simply want to see how 2050 pointers suffice. If the data be accessed as an array in a 5-dimensional loop, no memory accesses are needed except to get the actual element desired. Using pointers, the usual method would require at least 4 extra accessed. If the array be accessed randomly in all five dimensions at once, four multiplies are necessary as compared to four memory accesses. As I have posted for CRAY's, address multiplies are much faster than memory accesses so I fail to see any improvement in speed in either case. There are 120 ways of ordering the dimensional accessing of the data. All of these ways are equivalent using ordinary array addressing, strength-reduction uses just a constant addition to a base address. With pointer addressing, I am interested in seeing how the 120 accessing orders fit within the 2050 pointers. I think that 2050 is a bit small by about 10 orders of magnitude. If the proponents of using pointers for this type of problems are If the proponents of pointer-style accessing can err this much in such a simple case, why should their other claims be believed? (In practice, I have only been able to use 72x48x24x24x24 arrays because memories are not yet large enough.) I am choosing five dimensions because a typical physical problem has natural dimensions of X, Y, Z, Time, and the fifth dimension ranges over the variables needed at each XYZT point.