Embedding of Hypercubes into Grids

We consider one-to-one embeddings of the n-dimensional hypercube into grids with 2 n vertices and present lower and upper bounds and asymptotic estimates for minimal dilation, edge-congestion, and their mean values. We also introduce and study two new cost-measures for such embeddings, namely the sum over i = 1; :::; n of dilations and the sum of edge congestions caused by the hypercube edges of ith dimension. It is shown that, in their simulation via the embedding approach, such measures are much more suitable for evaluating the slowdown of the uniaxial hypercube algorithms then the traditional cost measures. 1 Introduction and Motivation The power of message-passing multiprocessor systems strictly depends on the structure of their interconnection network. Various types of network topologies have gained favor and are in use today. Among these, grids are emerging as one of the most popular network architectures. Many distributed computing systems which appeared in the last few yea..