A Direct Approach to the Parallel Evaluation of Rational Expressions with a Small Number of Processors

Marc Snir, Amnon B. Barak

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we construct algorithms and investigate the time required for the parallel evaluation of rational expressions using small numbers of processors. We define algorithms which compute a polynomial with n operations in 3n/(2p+ 1) + Q(p2) time units with p processors and a general rational expression with n operations in 5n/(2p+ 3) +0(p2) time units. These algorithms are suitable for implementation on computers with restricted data access.

Original languageEnglish (US)
Pages (from-to)933-937
Number of pages5
JournalIEEE Transactions on Computers
VolumeC-26
Issue number10
DOIs
StatePublished - Oct 1977
Externally publishedYes

Keywords

  • Computational complexity
  • Parallel algorithms
  • Polynomial expressions
  • Rational expressions
  • Recursive doubling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A Direct Approach to the Parallel Evaluation of Rational Expressions with a Small Number of Processors'. Together they form a unique fingerprint.

Cite this