Even without recording the cost of each leaf element, wouldn't the depth of an element in the tree be a pretty good indicator of relative cost?
Khryl
@hofstee, I think depth of an element is a good estimation. It reflects the density of particles in the neighborhood, which has direct relation to its cost. But depth also has some cons, it cannot reflect the density of the sibling nodes of itself or its ancestor nodes.
totofufu
How exactly do the sibling nodes or ancestor nodes affect the cost of an element though?
Khryl
@totofufu a particle's sibling node may contain many particles and be close enough to that particle, thus the density of sibling nodes should also be considered.
hofstee
@totofufu we get a reasonable estimate to some degree of these, but if the nodes fall into different quadtree portions they can diverge significantly and we might not know about it, without having to traverse more of the tree at least.
maxdecmeridius
We went through a couple approaches in lecture. We started with pure static assignment, where we assign a particle to a processor. Then we went to a dynamic work queue where each processor takes a particle from the dynamic queue when it finishes its current job. Kayvon also mentioned that we could use the tree to give us some information about how we could assign the work, so we use the tree and then statically assign from there. He then moved into a semi-static assignment, where we reassign at some interval (every once in a while) of time steps since the universe doesn't change reorganize itself radically ever time step.
Even without recording the cost of each leaf element, wouldn't the depth of an element in the tree be a pretty good indicator of relative cost?
@hofstee, I think depth of an element is a good estimation. It reflects the density of particles in the neighborhood, which has direct relation to its cost. But depth also has some cons, it cannot reflect the density of the sibling nodes of itself or its ancestor nodes.
How exactly do the sibling nodes or ancestor nodes affect the cost of an element though?
@totofufu a particle's sibling node may contain many particles and be close enough to that particle, thus the density of sibling nodes should also be considered.
@totofufu we get a reasonable estimate to some degree of these, but if the nodes fall into different quadtree portions they can diverge significantly and we might not know about it, without having to traverse more of the tree at least.
We went through a couple approaches in lecture. We started with pure static assignment, where we assign a particle to a processor. Then we went to a dynamic work queue where each processor takes a particle from the dynamic queue when it finishes its current job. Kayvon also mentioned that we could use the tree to give us some information about how we could assign the work, so we use the tree and then statically assign from there. He then moved into a semi-static assignment, where we reassign at some interval (every once in a while) of time steps since the universe doesn't change reorganize itself radically ever time step.