APPROXIMATING HYPERCUBES BY INDEX-SHUFFLE GRAPHS VIA DIRECT-PRODUCT EMULATIONS

摘要

Index-shuffle graphs are a family of bounded-degree hypercube-like interconnection networks for parallel computers, introduced by [Baumslag and Obrenic (1997): Index-Shuffle Graphs, ...], as an efficient substitute for two standard families of hypercube derivatives: butterflies and shuffle-exchange graphs. In the theoretical framework of graph embedding and network emulations, this paper shows that the index-shuffle graph efficiently approximates the direct-product structure of the hypercube, and thereby has a unique potential to approximate efficiently all of its derivatives. One of the consequences of our results is that any member of the following group of standard bounded-degree hypercube derivatives: butterflies, shuffles, tori, meshes of trees, is emulated by the index-shuffle graph with a slowdown in the order of the logarithm of the slowdown of the most efficient emulation achieved by any other member of this group. Emulation algorithms are presented where the emulation host is the n-dimensional index-shuffle graph Ψ_n, having N = 2~n nodes. The emulated graph G is a direct product of the form: G = F_0 x F_1 x ··· x F_(k-1) where k is a power of 2, and each factor F_i is an instance of any of the following three graph families: cycle, complete binary tree, X-tree. Let the size of each factor be |F_i| ≤ 2~(n_f), where k · n_f ≤ n. The index-shuffle graph Ψ_n emulates any factor F_i in the product G with slowdown: O(log k) + O(log n_f), which is O(log n) = O(log log N). Any collection of 2~l copies of the product G, such that: l + k · n_f ≤ n is emulated by the index-shuffle graph Ψ_n simultaneously, without any additional slowdown. Relaxing the assumption that k is a power of 2 introduces an additional factor of O(lo~* N) into the slowdown.