PRAM is a very simple model of parallel computation that helps algorithm designers to focus in the essence of parallelism. There is no obvious way of constructing a PRAM - in particular, constructing a large and fast shared memory is believed to be difficult. On the contrary, it is easier to construct architectures with distributed memory. One of the simplest architectures representing the Distributed Memory Model (DMM) is the mesh of processors. Distributed memory model is, unfortunately, harder to program than the shared memory model.
We are interested in running PRAM programs automatically on distributed memory model. We have shown that with certain simulation techniques, a PRAM program can be executed with very small simulation cost. Indeed, simulation is work-optimal in the following sense: If a p-processor PRAM executes a program in time T, it is simulated by a q-processor DMM (with suitably smaller q) in time less than 2*(p/q)*T. A more detailed description of these ideas can be found in references.
For other ongoing research in parallel computing at the University of Joensuu, click here.