Best way to share BCs for the kD-tree?
![](https://secure.gravatar.com/avatar/b279d746f54e2cd6062e8279a767c4bc.jpg?s=120&d=mm&r=g)
Hi all, especially Sam, Is there a good way to share boundary conditions between nodes of the kD-tree? I'm particularly interested in either speeding up vertex value generation or storing an additional layer of values that correspond to (expensive to compute) values on other processors, for the purposes of the contour finder. Basically, I think we can parallelize the contour finder in yt-3.0 PR 120 if we can share boundary conditions between processors. But, I'm not sure how to do that. Alternately, if we could double-count boundary nodes between processors, that would work as well. For instance, if processors 1 has a tile that borders a tile from processor 4, that tile would be "owned" by 4 but would be replicated on 1. Any ideas? -Matt
![](https://secure.gravatar.com/avatar/abbf30a6e2a3b5a2641e8c41f75c4e15.jpg?s=120&d=mm&r=g)
Hi Matt, There isn't currently an easy way to share boundary conditions. However, I think we could attempt to address this with a few easy-ish changes. I can think of three ways, and there may be more. 1) Provide tools for neighbor location + communication Here we would use the structure of the tree to quickly identify which processor owns the neighboring region and send across whatever is needed. This is fairly straightforward since the tree is built out to the point where domain decomp is done, so this is super fast to just traverse to find the owner. Once known, request a a boundary layer. This would probably require coming up with some sort of data object that acts as a boundary layer. I guess this could actually be an AMR2DData object that gets filled out, sent over, but that might be overkill? 2) Build the full tree on all procs, but only only own the data for a subset. I think the AMRKDTree build may be fast enough at this point to just build the entire thing on each processor, then later decide which nodes to populate with data. This could be done by just setting a buffer around the initial parallel decomp. 3) Build the tree once up until the point where you have Nprocs leafs. Then build a second tree that has left and right edges that are buffered around the original tree decomp. This would be much like option 2, but necessary if the tree build time became dominant. I think option 2 and 3 would probably be the easiest, though I think it would be a neat to set up communication between nodes through option 1. I'd be happy to sprint on this sometime if you'd like. Sam On Tue, Nov 26, 2013 at 12:29 PM, Matthew Turk <matthewturk@gmail.com>wrote:
Hi all, especially Sam,
Is there a good way to share boundary conditions between nodes of the kD-tree? I'm particularly interested in either speeding up vertex value generation or storing an additional layer of values that correspond to (expensive to compute) values on other processors, for the purposes of the contour finder.
Basically, I think we can parallelize the contour finder in yt-3.0 PR 120 if we can share boundary conditions between processors. But, I'm not sure how to do that. Alternately, if we could double-count boundary nodes between processors, that would work as well. For instance, if processors 1 has a tile that borders a tile from processor 4, that tile would be "owned" by 4 but would be replicated on 1.
Any ideas?
-Matt _______________________________________________ yt-dev mailing list yt-dev@lists.spacepope.org http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
![](https://secure.gravatar.com/avatar/b279d746f54e2cd6062e8279a767c4bc.jpg?s=120&d=mm&r=g)
Hi Sam, On Tue, Nov 26, 2013 at 3:57 PM, Sam Skillman <samskillman@gmail.com> wrote:
Hi Matt,
There isn't currently an easy way to share boundary conditions. However, I think we could attempt to address this with a few easy-ish changes. I can think of three ways, and there may be more.
1) Provide tools for neighbor location + communication Here we would use the structure of the tree to quickly identify which processor owns the neighboring region and send across whatever is needed. This is fairly straightforward since the tree is built out to the point where domain decomp is done, so this is super fast to just traverse to find the owner. Once known, request a a boundary layer. This would probably require coming up with some sort of data object that acts as a boundary layer. I guess this could actually be an AMR2DData object that gets filled out, sent over, but that might be overkill?
This is interesting, but I agree, might be the hardest. The way contouring currently works requires traversing from finest-to-coarsest, so that the mapping of cell to neighbor zone is always 1:1, rather than 1:refine_by**(2*d_level). Under this assumption, I have a method for looking at neighbors in the contouring already, where it calls the _find_node() function of a perturbed vector.
2) Build the full tree on all procs, but only only own the data for a subset. I think the AMRKDTree build may be fast enough at this point to just build the entire thing on each processor, then later decide which nodes to populate with data. This could be done by just setting a buffer around the initial parallel decomp.
3) Build the tree once up until the point where you have Nprocs leafs. Then build a second tree that has left and right edges that are buffered around the original tree decomp. This would be much like option 2, but necessary if the tree build time became dominant.
I think option 2 and 3 would probably be the easiest, though I think it would be a neat to set up communication between nodes through option 1.
Either 2 or 3 would work for me as is, but I agree that 1 would be the most fun and potentially the most rewarding in the long run. For the purposes of what I'm looking at right now, 2 would probably be the way to go, since my recollection is that the tree-building is not dominant anymore.
I'd be happy to sprint on this sometime if you'd like.
Let's do that. Maybe sometime in the new year, as it sounds like it might require some work. But I'll try to leave as much open as possible for this as I update the PR for contouring, which I think is just about ready to go (and includes inline extracted regions now.)
Sam
On Tue, Nov 26, 2013 at 12:29 PM, Matthew Turk <matthewturk@gmail.com> wrote:
Hi all, especially Sam,
Is there a good way to share boundary conditions between nodes of the kD-tree? I'm particularly interested in either speeding up vertex value generation or storing an additional layer of values that correspond to (expensive to compute) values on other processors, for the purposes of the contour finder.
Basically, I think we can parallelize the contour finder in yt-3.0 PR 120 if we can share boundary conditions between processors. But, I'm not sure how to do that. Alternately, if we could double-count boundary nodes between processors, that would work as well. For instance, if processors 1 has a tile that borders a tile from processor 4, that tile would be "owned" by 4 but would be replicated on 1.
Any ideas?
-Matt _______________________________________________ yt-dev mailing list yt-dev@lists.spacepope.org http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
_______________________________________________ yt-dev mailing list yt-dev@lists.spacepope.org http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
participants (2)
-
Matthew Turk
-
Sam Skillman