A probabilistic simulation of PRAMs on a bounded degree network (Q1113672): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
m rollbackEdits.php mass rollback Tag: Rollback |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90160-3 / rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1997142363 / rank | |||
Revision as of 08:47, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A probabilistic simulation of PRAMs on a bounded degree network |
scientific article |
Statements
A probabilistic simulation of PRAMs on a bounded degree network (English)
0 references
1988
0 references
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.
0 references
theory of computation
0 references
parallel processing
0 references
PRAM simulation
0 references
interconnection network
0 references
Time complexity
0 references
VLSI
0 references