DerekC

I am trying to find an algorithm that is an efficient way to update the 6 "neighbors" of a point in threespace.
Is this enough information to explain the problem? I suppose it is referred to as an n-body problem, where each n has 6 neighbors (cube).

What is the most efficient storage scheme for updating each n value based on it's neighbors, where every n must be iterated over. That is, the innermost loop will be forward and backward looking, in two directions. I have heard of 2D grids use a "red-black" scheme for this kind of update, but I am not sure what exists for 3D.

Thanks

Derek

itCbitC

Nope! need more information to figure out what exactly you're trying to do.

DerekC

So the red black method could be used where the east/west/north/south neighbors are needed in a 2D grid to update the n'th member of the grid. I am trying to find out what people use when we are now in a 3D grid and there is an "up/down" neighbor that has to be considered for the n'th member of the grid, with the exception of boundary members, of course.

Essentially I am computing the interaction that N-bodies are exerting on each other in 3D space. The problem is, all of my grid points are stored in a 1D array, call it P[1..N]

To update P[k] for 0<k<n (but not on the boundary) I might have a computation like

P[k] = P[k] + xp + xm + yp + ym + zp + zm

where xp denotes plus one in the X direction on the grid, xm is minus one in the X direction, etc.

But since all of my points are in one array, P, those are really denoted as indices to the array , so it is really

P[k] = P[k] + P[xp] + P[xm] + P[yp] + P[ym] + P[zp] + P[zm]

Well, this looks like it should be fast, but since I am in threespace, xp and xm are really close to P[k], but P[yp] might actually be say, 30 spaces away in memory, and P[zp] might be 400 spaces away from P[k] in memory, so I am getting a ton of cache misses going on, because the stride is all messed up, I guess?

And as you can see, when I move to P[k+1], P[xm] might actually be the original P[k] now, which just got updated, so it's not like I can store all of the P[xm] ahead of time before the computes.

DerekC

Parallel Programming In C. Chap. IX

This is not exactly like what I am doing, but it may give you an idea of the 2D problem.

iMalc

To boost cache locality as much as possible, you could use 3D Morton numbers to compute the index to store data for each (x,y,z) coordinate.
How to compute a 3D Morton number (interleave the bits of 3 ints) - Stack Overflow
Then whichever direction you go (either way in x, y, or z), you're pretty close in memory to where you just were, most of the time.

__________________
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger

Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

DerekC

I will check it out. Thanks!

DerekC

So, I think here is the crux of the problem: How do you optimize a forward and backward looking loop? I am not too concerned with memory here, so I had an idea.

The problem has n total nodes in it. There are nx nodes in x, ny nodes in y, nz nodes in z. nx*ny*nz=n

To update the point n with neighbors above, below, and to each side, When going through the loop, the assignment statement looks like this:

a[n] = a[n-1] + a[n+1] + a[n-nx] + a[n+nx] + a[n-nx*ny] + a[n+nx*ny]
^x- ^x+ ^y- ^y+ ^z- ^z+

So as you can see, it's forward looking on x, forward looking on y, and forward looking on z (backwards too).

In psuedo code, would this help with some of the stride issues:

//load an array to hold original values, and "y-major" and "z-major" versions of it
// in other words, put y- and y+ right next to n in the copied arrays
load an
load an_y
load an_z


copy an into an_y and an_z

for all n
swap y- and y+ with x- and x+ in an_y
swap z- and z+ with x- and x+ in an_z
end loop

for all n
perform calculation a[n] = a[n] = a[n-1] + a[n+1] + an_y[n-1] + an_y[n+1] + an_z[n-1] + an_z[n+1]
update an_z[n] with new a[n]
update an_y[n] with new a[n]
end loop


I think this is an ok idea, but I am not sure exactly of the details just yet. If anyone has any ideas on how to pre-load those forward and backward looking values from the an array, i'd love to hear them