Performance evaluation of a random-walk-based algorithm for embedding dynamically evolving trees in hypercubic networks

摘要

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 hypercubic networks, including shuffle-exchange, de Bruijn, cube-connected cycles, wrapped butterfly, and hypercube networks. The performance of a random-walk-based randomized tree embedding algorithm is evaluated. Several random tree models are considered. We develop recurrence relations for analyzing the performance of embedding of complete-tree-based random trees and randomized complete trees, and linear systems of equations for reproduction trees. We present more efficient recurrence relations and linear systems of equations for symmetric networks. We also demonstrate extensive numerical data of the performance ratio and make a number of interesting observations of randomized tree embedding in the five hypercubic networks.