Embedding meshes into cubes

We present efficient simulations of mesh connected networks by binary, ternary, and quaternary hypercube machines. In particular, we consider the case of embedding a grid G into the smallest hypercube that has at least as many points as G, called the optimum-hypercube for G. In order to minimize simulation time, we derive embeddings that assign the nodes of G to nodes of its optimum hypercube that keep grid-neighbors as close as possible in the hypercube. The maximum distance between images of grid-neighbors is called the dilation of the embedding. We show that (1) there is a dilation 2 embedding of 2-dimensional grids into their optimum binary hypercubes, under certain conditions; (2) for any $d\geq 2$, there is a dilation d embedding of a d-dimensional grid into its optimum binary hypercube, under certain conditions; (3) there is a dilation 3 embedding of 2-dimensional grids into their optimum ternary hypercube, under certain conditions; (4) for any $d\geq 2$, there is a dilation d embedding of a d-dimensional grid into its optimum ternary hypercube, under certain conditions; (5) there is a dilation 2 embedding of 2-dimensional grids into their optimum k-ary hypercubes, for k = 3, 4.