On saving space in parallel computation

DOI10.1016/0020-0190(88)90233-5MaRDI QIDQ1114403zbMATH OpenOpenAlexFDO

Authors Torben Hagerup

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90233-5

zbMATH Keywords

CRCW PRAM model of computationparallel algorithmspace requirements

Mathematics Subject Classification ID

Review text

The literature on parallel computing describes a number of algorithms whose space requirements exceed their time-processor product. Generalizing an idea by \textit{R. Cole} and \textit{U. Vishkin} [Approximate parallel scheduling II, Preprint (1987)] and combining it with a well known trick for avoiding initialization of memory areas, we show that in the CRCW PRAM model of computation, such anomalies can always be kept within bounds.

Recommendations

• Trade-Offs between Depth and Width in Parallel Computation
• Dynamic parallel memories
• Space-efficient parallel merging
• scientific article; zbMATH DE number 176748
• Parallelism Always Helps

Cited in

(9)

• Multiplication, division, and shift instructions in parallel random access machines
• Parallel construction and query of index data structures for pattern matching on square matrices
• Memory requirements for parallel programs
• Fast and practical approximate string matching
• Managing space as virtual parallel space
• Dynamic parallel memories
• Trade-Offs between Depth and Width in Parallel Computation
• Optimal parallel algorithms for Prefix Matching
• Optimal parallel algorithms on planar graphs

This page was built for publication: On saving space in parallel computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114403)