Efficient two-level mesh based simulation of PRAMS
Martti J. Forsell, Ville Leppänen, Martti Penttonen · 2002
We consider time-processor optimal simulations of PRAM models on coated block meshes. A coated block mesh consists of n-processor blocks and /spl pi//spl times//spl pi/ or /spl radic/(/spl pi/)/spl times//spl radic/(/spl pi/)/spl times//spl radic/(/spl pi/) router blocks. The router blocks form a 2-dimensional or a 3-dimensional regular mesh, and the processor and memory blocks are located on the surface of the block mesh. As a generalization of the coated mesh, the 2-dimensional and 3-dimensional coated block meshes simulate EREW, CREW, and CRCW PRAM models time-processor optimally with moderate simulation cost. Using proper amount of parallel slackness, the cost can be decreased clearly below 2 routing steps per simulated PRAM processor. The coated block mesh is actually an instance of a more general two-level construction technique, which uses a seemingly inefficient but scalable solution on top of a non-scalable but efficient solution. Within blocks (chips) brute force techniques are applied, whereas the mesh structure on top makes the whole construction modular, simple, and scalable. The parameter /spl pi/ provides a method to balance the construction with respect to the two techniques. Keywords: PRAM, shared memory machine, simulation, time-processor optimal, mesh, interconnection network.