アイテム詳細

要旨

The authors describe a nonuniform deterministic simulation of PRAMs on module
parallel computers (MPCs) and on processor networks of bounded degree. The
simulating machines have the same number $n$ of processors as the simulated
PRAM, and if the size of the PRAM's shared memory is polynomial in $n$, each
PRAM step is simulated by $O(\log n)$ MPC steps or by $O((\log n)^2)$ steps of
the bounded-degree network. This improves upon a previous result by Upfal and
Wigderson (1984). The authors prove an $\Omega((\log n)^2/\log\log n)$ lower
bound on the number of steps needed to simulate one PRAM step on a
bounded-degree network under the assumption that the communication in the
network is point to point. As an important part of the simulation of PRAMs on
MPCs, a new technique for dynamically averaging out a given work load among a
set of processors operating in parallel is used.