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

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.