In many tree-structured parallel computations, the size and structure of a tree that represents a parallel computation is unpredictable at compile-time; the tree evolves gradually during the course of the computation. When such a computation is performed on a static network, the dynamic tree embedding problem is to distribute the tree nodes to the processors of the network such that all the processors receive roughly the same amount of load and that communicating nodes are assigned to neighboring processors. Furthermore, when a new tree node is generated, it should be immediately assigned to a processor for execution without any information on the further evolving of the tree; and load distribution is performed by all processors in a totally distributed fashion.We study the problem of embedding dynamically evolving trees in butterflies. We evaluate the performance of a random-walk-based algorithm. Our performance data demonstrate that butterflies have comparable performance with hypercubes in supporting tree-structured parallel computations.
['Keqin Li']
Performance evaluation of a random-walk-based algorithm for embedding dynamically evolving trees in butterflies