nicelhc13
commented
2 years ago Hi, Unfortunately, I am not an expert on this app and @insertinterestingnamehere graduated his degree, who is the most expert. (Ian, may you give any suggestion on this issue?)
I believe there is a missing .5 constant when recursively inserting a node into a tree.
My understanding of the BH algorithm is that the octants handle a voxel that is an eigth of the volume of the larger space (half as small in each x/y/z dimension). The radius argument in the insert method tracks this dimension.
Therefore, when recursing down the tree, the code should reduce the radius by half each level that it descends. However, as written, it only does this when it inserts a new node (or loses when collecting the lock). This means that when there are many nodes traversed before a new one is inserted, the new node will likely be created with a radius value from a higher level.
(I believe my rough understanding is consistent with the GPU code, but I'm not a GPU or a BarnesHut Expert)
When I make this change, the number of Oct nodes in a tree with 4096 bodies decreases from ~15K to about 6K (roughly). I think this is much more in line with the expected number of nodes in a balanced tree.
The sampled MSE also decreases from 10^-3 to 10^-11.
TL;DR, I believe this call should be
.5 * radius: https://github.com/IntelligentSoftwareSystems/Galois/blob/07514b288f708082430304f3d8b934fb3e2a821f/lonestar/scientific/cpu/barneshut/Barneshut.cpp#L163