Nearly logarithmic-time parallel algorithms for the class of ±2b ASCEND computations on a SIMD hypercube

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

2 Scopus citations

Abstract

Recently, we have studied two important classes of algorithms requiring ±2b communications: ±2b-descend, and ±2b-ascend. Let N = 2n be the number of PEs in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. In [5], we developed an efficient O(n) algorithm for the descend class. In [6], we obtained a simple O(n2/log n) algorithm for the ascend class, requiring O(log n) words of local memory per PE. In this paper, we present 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, which is discussed only briefly here, runs in O(n√n/log n) time and requires O(log n) space per PE.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
PublisherPubl by IEEE
Pages122-129
Number of pages8
ISBN (Print)0818626720
StatePublished - 1992
EventProceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA
Duration: Mar 23 1992Mar 26 1992

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProceedings of the 6th International Parallel Processing Symposium
CityBeverly Hills, CA, USA
Period3/23/923/26/92

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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