A probabilistic simulation of PRAMs on a bounded degree network (Q1113672)

From MaRDI portal
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
    0 references
    0 references
    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

    Identifiers