Embedding Hypercubes and Related Networks into Mesh-Connected Processor Arrays
✍ Scribed by F. Annexstein
- Publisher
- Elsevier Science
- Year
- 1994
- Tongue
- English
- Weight
- 736 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we study the problem of how computations programmed for hypercubes, and their bounded-degree relatives, the shuffle-exchange and cube-connected-cycles, can be efficiently emulated by mesh-connected arrays of processing elements. The emulations we present are implemented via graph embeddings. The graph embeddings we present are all optimal with respect to congestion, and are also noteworthy for they yield efficient emulation programs that are written in a SIMD style without the use of indirect addressing. The paper includes the three following emulation results, where each emulation algorithm requires no indirection. For any (n \geq 1) and fixed (r \geq 1), an (n)-sided (r)-dimensional mesh can emulate an (n 2^{n})-node cube-connected-cycles network with slowdown (\Theta\left(2^{n} / n^{r-1}\right)), a (2^{n})-node shuffle-exchange network with slowdown (\Theta\left(2^{n} / n^{r}\right)), and a (2^{n})-node hypercube network operating in a weak model, with slowdown (\Theta\left(2^{n} \log n / n^{r}\right)). O 1994 Academic Press, Inc.