Data-movement-intensive problems: Two folk theorems in parallel computation revisited

DOI10.1016/0304-3975(92)90271-GzbMath0745.68052OpenAlexW2012722810WikidataQ127662621 ScholiaQ127662621MaRDI QIDQ1184985

Afonso G. Ferreira, Michel Cosnard, Selim G. Akl

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90271-g

zbMATH Keywords

PRAMRAMBrent's theoremdata-movement-intensive problemsspeedup theorem

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (2)

On XRAM and PRAM models, and on data-movement-intensive problems ⋮ Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees

Cites Work

• The actual complexity of parallel evaluation of low degree polynomials
• Optimal parallel algorithms for computing convex hulls and for sorting
• Superlinear speedup of an efficient sequential algorithm is not possible
• Parallel efficiency can be greater than unity
• Comments on the paper Parallel efficiency can be greater than unity
• A note on superlinear speedup
• Evaluating speedups on distributed memory architectures
• Anomalies in parallel branch-and-bound algorithms
• Combinatorially implosive algorithms
• The Parallel Evaluation of General Arithmetic Expressions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Data-movement-intensive problems: Two folk theorems in parallel computation revisited