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 journalArticle

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 - 1977
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Software
  • Theoretical Computer Science
  • Electrical and Electronic Engineering

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