Embedding Leveled Hypercube Algorithms into Hypercubes

David Bruce Wilson

When a leveled hypercube algorithm (one dimension used at a time) is mapped in the straightforward way into a hypercube in which all edges are useable at once, most of the host machine's bandwidth is unused. This paper shows how to construct embeddings which better utilize the host's edges. In particular, I show how to map an n-dimensional leveled hypercube algorithm into an n-dimensional host hypercube so that the communication throughput of every guest edge is Theta((n/log n)log_6 2) = omega(n0.386) times the communication throughput of a host edge. Furthermore, the routing can be done on edge-disjoint paths of length at most n. This result can be applied to other algorithms that are run on hypercubes. For example, if an algorithm runs on a mesh with a axes each of length 2l, but uses only one axis at a time, then it can be embedded in an la-dimensional hypercube so that each mesh edge has throughput Theta(l(a/log a)log_6 2).

SPAA '92, 4th Annual ACM Symposium on Parallel Algorithms and Architectures , pp. 264-270, 1992.
PostScript version

Scanned version in the ACM's Digital Library