Embedding Meshes Into Small Boolean Cubes
Description:... Abstract: "The embedding of arrays in Boolean cubes, when there are more array elements than nodes in the cube, can always be made with optimal load-factor by reshaping the array to a one-dimensional array. We show that the dilation for such an embedding is at most [formula] for the embedding of an l[subscript 0] x l1 x ... x l[subscript k-1] array in an n-cube. Dilation one embeddings can be obtained by splitting each axis into segments and assigning segments to nodes in the cube by a Gray code. The load-factor is optimal if the axis lengths contain sufficiently many powers of two. The congestion is minimized, if the segment lengths along the different axes are as equal as possible, for the cube configured with at most as many axes as the array.
Show description