Parallel Algorithms for the Classes of ±2b DESCEND and ASCEND Computations on a SIMD Hypercube

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

There is a wide class of parallel algorithms which require communications in the form of a 2b permutation and — 2b permutation. (A 2b permutation of X elements, where N = 2n, moves the element from position i to position i + 2b mod N. The inverse is called a -2b permutation.) We first examine the complexity of performing a 2b 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 2bpermutation. This lower bound suggests that if a parallel algorithm requires f(N) communication steps of type ±2bit may require Q(f(N) log N) steps on a SIMD hypercube. We identify an important class of parallel computations, called ±2b 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 + 2b] and A[i — 2b]. 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 ±2b -ascend. A computation in this class has a structure similar to ±2b-descend, except that the iterations run in the increasing order of b. We develop a simple O(log2N/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, ±2b -ascend, ±2b -descend, 2b permutation, PM2I interconnection, SIMD hypercube.

Original languageEnglish (US)
Pages (from-to)1372-1381
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Volume4
Issue number12
DOIs
StatePublished - 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<sup>b</sup> DESCEND and ASCEND Computations on a SIMD Hypercube'. Together they form a unique fingerprint.

Cite this