Routing Permutations on Hypercube Machines with Half-Duplex Links
✍ Scribed by C.S. Raghavendra; M.A. Sridhar
- Publisher
- Elsevier Science
- Year
- 1994
- Tongue
- English
- Weight
- 466 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs (2|n / 2|) routing steps on an (n)-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs (n) routing steps. Also, algorithms are sketched for routing permutations in the classes (\Omega) and (\Omega^{-1}) in (3[n / 2]) routing steps, yielding an off-line algorithm for routing arbitrary permutations in (3 n) steps. 1994 Academic Press, Inc.