Work-optimal simulation of PRAM models on meshes
Ville Leppänen, Martti Penttonen · 1995
In this paper we consider work-optimal simulations of PRAM models on coated meshes. Coated meshes consist of a mesh connected routing machinery with processors on the surface of the mesh. We prove that coated meshes with 2-dimensional or 3-dimensional routing machinery can work-optimally simulate EREW, CREW, and CRCW PRAM models. The general idea behind this simulation is to use Valiant's XPRAM approach, and ignore the work-complexity of simple nodes of the routing machinery. 1 Introduction There are a wide variety of approaches to parallelism in general [40], and even to general purpose parallelism [39] -- reflecting the prevailing uncertainty of the correct approach. One model aiming at general purpose parallelism is the PRAM (Parallel Random Access Machine) model, which is a natural generalization of the classical RAM model. It consists of N processors, each of which may have some local memory and registers, and a global shared memory of size m. A step of PRAM is often seen to con...