Embedding grids into hypercubes

摘要

We consider efficient simulations of mesh connected networks (or good representations of array structures) by hypercube machines. In particular, we consider embedding a mesh or grid G into the smallest hypercube that at least as many points as G, called the optimal hypercube for G. In order to minimize simulation time we derive embeddings which minimize dilation, i.e., the maximum distance in the hypercube between images of adjacent points of G. Our results are: (1) There is a dilation 2 embedding of the [m × k] grid into its optimal hypercube, provided that ⌈logm⌉+logmk2⌈logm⌉+logm2⩽⌈logmk⌉ and (2) For any k < d, there is a dilation k + 1 embedding of a [a1 × a2 × … × ad] grid into its optimal hypercube, provided that Σi=1d − 1 ⌈log Bk⌉ ≤ ⌈Σi=1d log ai⌉, where Bk=ad∏ki=1ai∏ki=12⌈logai⌉+∑i=1k⌊loga1⌋2⌉