Complexity Results for Permuting Data and Other Computations on Parallel Processors

Allan Gottlieb, Clyde P. Kruśkal

Research output: Contribution to journalArticlepeer-review

Abstract

For a wide class of problems, we obtain lower bounds for algorithms executed on certain parallel processors. These bounds show that for sufficiently large problems many known algorithms are optimal. The central result of the paper is the following sharper lower bound for permutation algorithms. Any permutation algorithm for N data items on a P processor parallel machine without shared memory requires time on the order of NlogxP/P, where K is the maximum number of processors directly connected to a single processor. In particular, a speedup on the order of P is impossible if K is bounded.

Original languageEnglish (US)
Pages (from-to)193-209
Number of pages17
JournalJournal of the ACM (JACM)
Volume31
Issue number2
DOIs
StatePublished - Mar 30 1984

Keywords

  • Lower bounds
  • parallel computation
  • permutations
  • routing
  • shuffle-exchange machine

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Complexity Results for Permuting Data and Other Computations on Parallel Processors'. Together they form a unique fingerprint.

Cite this