On saving space in parallel computation
type: Item
instance of: scholarly article
title: On saving space in parallel computation
zbMATH Open document ID: 0662.68047
DOI: 10.1016/0020-0190(88)90233-5
author: Torben Hagerup
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4082978
zbMATH Keywords: parallel algorithm
zbMATH Keywords: space requirements
zbMATH Keywords: CRCW PRAM model of computation
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90233-5
OpenAlex ID: W137867423
cites work: Q4773298
cites work: Q3219751
description: scientific article; zbMATH DE number 4082978