# Red/black for 2D..what for 3D?

• 12-07-2009
DerekC
Red/black for 2D..what for 3D?
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
• 12-07-2009
itCbitC
Quote:

Originally Posted by 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).

Nope! need more information to figure out what exactly you're trying to do.
• 12-07-2009
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.
• 12-07-2009
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.
• 12-08-2009
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.
• 12-08-2009
DerekC
I will check it out. Thanks!
• 12-09-2009
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

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