Embedding 3-dimensional Grids into Optimal Hypercubes

The hypercube is a particularly versatile network for parallel computing. It is wellknown that 2-dimensional grid machines can be simulated on a hypercube with a small constant communication overhead. We introduce new easily computable functions which embed many 3-dimensional grids into their optimal hypercubes with dilation 2. Moreover, we show that one can reduce the open problem to recognize whether it is possible to embed every 3-dimensional grid into its optimal hypercube with dilation at most 2 by constructing embeddings for a particular class of grids. We embed some of these grids, and thus for the first time one can guarantee that every 3-dimensional grid with at most 2 9 \Gamma 18 nodes is embeddable into its optimal hypercube with dilation 2. Key words: embedding, hypercubes, 3-dimensional grids, dilation, GrayCode 1 Introduction Within the last decade parallel computing has received considerable attention in computer science. The main reasons for the growing interest are..