A probabilistic simulation of PRAMs on a bounded degree network (Q1113672): Difference between revisions
From MaRDI portal
m rollbackEdits.php mass rollback Tag: Rollback |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90160-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1997142363 / rank | |||
Normal rank |
Revision as of 18:43, 21 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