Optimal and efficient algorithms for summing and prefix summing on parallel machines

Research output: Contribution to journalArticlepeer-review

Abstract

The problem of designing efficient parallel algorithms for summing and prefix summing for certain classes of the LogP model is studied. We present optimal algorithms for summing and show that any optimal summing algorithm must have a certain inherent structure. Moreover, we present optimal or near-optimal algorithms for prefix summing for both non-commutative and commutative binary operators. Furthermore, we show that the optimal algorithms for prefix summing for these two types of operators are not equivalent.

Original languageEnglish (US)
Pages (from-to)517-543
Number of pages27
JournalJournal of Parallel and Distributed Computing
Volume62
Issue number4
DOIs
StatePublished - Jan 1 2002
Externally publishedYes

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Optimal and efficient algorithms for summing and prefix summing on parallel machines'. Together they form a unique fingerprint.

Cite this