A technique for
emulating multicomputer interconnection networks that are based on
separable graphs (graphs having bounded degree and sublinear multicolor recursive bisectors) is presented. Efficient emulations among interconnection networks are necessary for porting programs designed for one network to another.Emulations are formalized as
graph embeddings, where the nodes (processors) of the
guest graph (emulated network) are assigned to nodes of the
host graph (emulator), while the edges (communication links) of the guest are routed via paths in the host. The communication slowdown in an emulation depens on the
dilation (length of the longest routing path) and the
congestion (number of paths that contend for a host edge) of the embedding. The
expansion of the embedding (the ratio of the sizes of the host to guest) determines the inefficiency of processor utilization.
Cell trees are introduced as interconnection networks whose special communication properties enable them to serve as intermediate devices in these emulations. Nodes in cell trees are organized into equinumerous parts called
cells; the cells are labeled by nodes of a complete binary tree. Communication in cell trees is restricted to two specific and distinct primitives:
cell communication is confined within cells, while
transfer communication occurs between adjacent cells. Rather than solved directly, the emulation problem for the original guest-host pair is decomposed into two independent parts: emulating the guest by the cell tree, and emulating the cell tree by the host.In emulations of separable graphs by cell trees, the node assignment that ensures small dilation is derived from the separator-based decomposition of guest graphs. The congestion-free edge routing is achieved by coordinating
global and
local phases, which are based on two characteristic cell-tree communication primitives.The technique is instantiated by emulating cell trees on specific host graphs. With
shuffle-like hypercube-derivative networks as hosts new constant-expansion emulations are obtained that have both dilation and congestion logarithmic in the size of the multicolor bisector of guest graphs. These emulations are the first such to have optimal (up to constants)
congestion; they provide the first
optimal algorithm for emulating arbitrary separable graphs on shuffle-like networks. The application of the technique to
hypercubes as hosts also produces optimal emulations that differ from those previously known by having smaller expansion constants.This research was supported in part by NSF Grants CCR-88-12567 and CCR-90-13184, and by the University of Massachusetts Graduate School Fellowship for the academic year 1991-92. A preliminary version of this paper was presented at the 3rd ACM Symposium on Parallel Algorithms and Architectures, July 22–24, 1991, in Hilton Head, South Carolina, USA.
相似文献