Dynamic Tree Embeddings in Butterflies and Hypercubes
Frank Thomson Leighton, Mark J. Newman, Abhiram Ranade, Eric J. Schwabe · SIAM Journal on Computing · 1992
This paper presents simple randomized algorithms for dynamically embedding M-node binary trees in either a butterfly or a hypercube network of N processors. These algorithms are dynamic in the sense that the tree to be embedded may start as one node and grow by dynamically spawning children. The nodes are incrementally embedded as they are spawned. Thus, the algorithm is especially suited for maintaining dynamic tree structures like those in divide-and-conquer and branch-and-bound algorithms. In the embeddings, the paper seeks to optimize the load on the processors of the network, the dilation of the tree edges, and the congestion on the network edges, in order to satisfy the demands of load balancing, process locality, and communication efficiency. The paper begins by presenting a simple level-by-level scheme for dynamically embedding trees in a butterfly network, and by successive modifications. The following results are obtained: 1. An embedding algorithm for the hypercube that achieves dilation 1 and, with high probability, load $O((M /N) + \log N)$. 2. An embedding algorithm for the butterfly that achieves dilation 2 and, with high probability, load $O((M/ N) + \log N)$. 3. An embedding algorithm for the hypercube that achieves dilation $O(1)$ and, with high probability, load $O((M/N) + 1)$ and congestion $O((M/ N) + 1)$. The third embedding simultaneously optimizes load and dilation to within constant factors, optimizing congestion as well when $M = O(N)$. The first two embeddings are also optimal to within constant factors when the tree to be embedded is large (i.e., $M = \Omega (N\log N)$. In addition, this paper proves a lower bound of $\Omega (\sqrt {\log N} )$ dilation for deterministic embedding algorithms that achieve load $O((M/ N) + 1)$, which implies that any embedding algorithm that simultaneously optimizes load and dilation must be randomized.