Efficient implementations of a class of ±2b parallel computations on a SIMD hypercube

David Nassimi, Yuh Dong Tsai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We identify an important class of parallel computations, called ±2b - descend, with an efficient implementation on a hypercube. Given the input A[0: N - 1], a computation in this class consists of log N iterations. Iteration 6, 6 = logN - 1,.,0, computes the new value of each A[i] as a function of A[i], A[i+2b] and A[i-2b]. We obtain a general algorithm for implementing any computation in this class in O(logN) time on a SIMD hypercube. Our general descend algorithm results in an efficient O(log N) implementation of Batcher's odd-even merge algorithm on a hypercube. The best previously known implementation of odd-even merge on a SIMD hypercube requires O(log2 N) time.

Original languageEnglish (US)
Title of host publicationProceedings - 5th International Parallel Processing Symposium, IPPS 1991
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2-9
Number of pages8
ISBN (Electronic)0818691670, 9780818691676
DOIs
StatePublished - Jan 1 1991
Event5th International Parallel Processing Symposium, IPPS 1991 - Anaheim, United States
Duration: Apr 30 1991May 2 1991

Publication series

NameProceedings - 5th International Parallel Processing Symposium, IPPS 1991

Conference

Conference5th International Parallel Processing Symposium, IPPS 1991
Country/TerritoryUnited States
CityAnaheim
Period4/30/915/2/91

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Efficient implementations of a class of ±2<sup>b</sup> parallel computations on a SIMD hypercube'. Together they form a unique fingerprint.

Cite this