A probabilistic simulation of PRAMs on a bounded degree network
type: Item
instance of: scholarly article
title: A probabilistic simulation of PRAMs on a bounded degree network
zbMATH Open document ID: 0661.68049
DOI: 10.1016/0020-0190(88)90160-3
author: Fabrizio Luccio
author: Andrea Pietracaprina
author: Geppino Pucci
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: A simulation scheme for (n,m)-PRAM computation is devised, based on an interconnection network organized in the form of a mesh-of-trees (MT) of side n. The m memory cells are subdivided in n modules, each local to one of the n PRAM processors. The MT roots contain these processors and the memory modules, while the other MT nodes have the mere functions of packet switchers. Time complexity is probabilistically analysed. It is shown that, as n goes to infinity, the slow-down for each step of PRAM computation is O(log n) with probability tending to 1 and that, as either n or k go to infinity, the simulation time for k consecutive steps is O(k log n) with probability tending to 1. Area requirements are finally studied according to the VLSI grid model.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4080918
zbMATH Keywords: theory of computation
zbMATH Keywords: parallel processing
zbMATH Keywords: PRAM simulation
zbMATH Keywords: interconnection network
zbMATH Keywords: Time complexity
zbMATH Keywords: VLSI
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90160-3
OpenAlex ID: W1997142363
cites work: Q4727434
cites work: Parallelism in random access machines
cites work: Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
cites work: The complexity of deterministic PRAM simulation on distributed memory machines
cites work: Ultracomputers
cites work: How to share memory in a distributed system
description: scientific article; zbMATH DE number 4080918