Dynamic Spanning Trees in HPC

This entry will be from the perspective of the Charm++ runtime and is intended to serve as a basis for wider discussion on the use of spanning trees, possibly dynamic, in other HPC software/middleware systems. As they stand, these are my personal thoughts and speculation. They are more questions than answers. Hopefully, as time goes by, they become more answers than questions.

I assume the reader (myself included) understands the idea behind a spanning tree (and minimum spanning tree). In Charm++, we tend to construct spanning trees over the object communication graph in Charm++ applications. These spanning trees then serve as the backbone for broadcasts and reductions, where the root can be any vertex of the spanning tree.

As I understand it, most other HPC runtimes use binary trees for their broadcast and reductions. If I am not wrong, this is because they do not need to deal with the dynamic nature of their applications. In Charm++, objects can migrate. As such, we have a dynamic runtime environment. Broadcasts and reductions happen in the background of application computation and other communication. I do not, however, know if spanning tree construction in Charm++ takes existing communication graph and volume into account. However, if broadcasts and reductions are to be efficient, they need to be woven around more static communication patterns. Hence, the construction of a minimum spanning tree, using the application's more static object communication volume as edge-weights.

So, the questions, I suppose are:

1. Are parallel spanning trees useful in general HPC software/middleware?

2. Can our experience with spanning trees in Charm++ be directly applicable to other HPC systems that attempt to provide dynamic application behavior?