Thread: Red/black for 2D..what for 3D?

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    24

    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

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by DerekC View Post
    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.

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    24
    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.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    24
    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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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"

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    24
    I will check it out. Thanks!

  7. #7
    Registered User
    Join Date
    Nov 2009
    Posts
    24
    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

Popular pages Recent additions subscribe to a feed