## Abstract

There is a wide class of parallel algorithms which require communications in the form of a 2^{b} permutation and — 2^{b} permutation. (A 2^{b} permutation of X elements, where N = 2^{n}, moves the element from position i to position i + 2^{b} mod N. The inverse is called a -2^{b} permutation.) We first examine the complexity of performing a 2^{b} permutation of X elements on an X -PE SIMD hypercube. (The hypercube model assumes that all data movements are restricted to a single dimension at a time.) We prove that, given any mapping of the elements to processors, log N - b steps are needed to perform a 2^{b}permutation. This lower bound suggests that if a parallel algorithm requires f(N) communication steps of type ±2^{b}it may require Q(f(N) log N) steps on a SIMD hypercube. We identify an important class of parallel computations, called ±2^{b} descend, which includes Batcher’s odd-even merge and many other algorithms. A computation in this class performs log X iterations on an N -element input A[0: N - 1]. For b =log N - 1. • • •. 0. iteration b computes the new value of each A[i] as a function of A[i]. A[i + 2^{b}] and A[i — 2^{b}]. We obtain an efficient O(log N) algorithm for this class on a SIMD hypercube. We discuss several problems which are solved elegantly using this general algorithm. We also study a related class of parallel computations called ±2^{b} -ascend. A computation in this class has a structure similar to ±2^{b}-descend, except that the iterations run in the increasing order of b. We develop a simple O(log^{2}N/log log N) algorithm for this class on a SIMD hypercube, assuming Ω(log log N) space per PE. It remains open whether this class can be implemented on a SIMD hypercube in O(log N) time. Index Terms— Cyclic shift, odd-even merge, parallel prefix, ±2^{b} -ascend, ±2^{b} -descend, 2^{b} permutation, PM2I interconnection, SIMD hypercube.

Original language | English (US) |
---|---|

Pages (from-to) | 1372-1381 |

Number of pages | 10 |

Journal | IEEE Transactions on Parallel and Distributed Systems |

Volume | 4 |

Issue number | 12 |

DOIs | |

State | Published - Dec 1993 |

## All Science Journal Classification (ASJC) codes

- Signal Processing
- Hardware and Architecture
- Computational Theory and Mathematics

## Fingerprint

Dive into the research topics of 'Parallel Algorithms for the Classes of ±2^{b}DESCEND and ASCEND Computations on a SIMD Hypercube'. Together they form a unique fingerprint.