Nearly Logarithmic-Time Parallel Algorithms for the Class of ±2b ASCEND Computations on a SIMD Hypercube

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Recently, we studied two important classes of algorithms requiring ±2b communications: ±2b-descend, and ±2b-ascend. Given an N-element input A[0 : N - 1], where N = 2n, the descend class consists of n iterations. For b = n - 1, n - 2, …, 0, iteration b computes the new value of each A [i] as a function of the previous-iteration values of A[i], A[i + 2b mod N], and A[i - 2b mod N]. (Batcher′s odd-even merge falls into this class.) The ascend class is similar except that the iterations are for b = 0, 1, …, n - 1. Let N = 2n be the number of processors in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. For the descend class, we developed an efficient O(n) algorithm on a SIMD hypercube. And for the ascend class, we obtained a simple O(n2/log n) algorithm, requiring O(n) words of local memory per processor. In this paper, we develop two new algorithms for the ascend class on a SIMD hypercube. The first algorithm runs in O(n1.5) time and requires O(1) space per PE. The second algorithm runs in [formula] time and requires O(log n) space per PE.

Original languageEnglish (US)
Pages (from-to)289-302
Number of pages14
JournalJournal of Parallel and Distributed Computing
Volume20
Issue number3
DOIs
StatePublished - Jan 1 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Nearly Logarithmic-Time Parallel Algorithms for the Class of ±2b ASCEND Computations on a SIMD Hypercube'. Together they form a unique fingerprint.

Cite this