Routing Permutations on Hypercube Machines with Half-Duplex Links |
| |
Affiliation: | 1. Department of Industrial Engineering and Management, Ming Chi University of Technology, New Taipei City, Taiwan;2. Institute of Information and Decision Sciences, National Taipei University of Business, Taipei, Taiwan;3. Department of Industrial Management, Lunghwa University of Science and Technology, Taoyuan, Taiwan |
| |
Abstract: | 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 Ω and Ω−1 in 3⌈n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3n steps. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|