Programming Data-Parallel - Executing Process-Parallel

Most theoretical work is based on the PRAM-model which has a block of shared memory and executes in a synchronous lock-step mode. Real hardware usually executes asynchronously and uses local memory and message passing. The recent LogP-model reflects these architectural properties. We show that for a practically important subclass of PRAM-programs it is possible to transform them into LogP-programs. Our ultimate goal is to optimize the execution time on the LogP-machine. Although the problem is NP-hard it is often possible to achieve an approximation within a constant factor of two. 1 Introduction The PRAM-model consists of a shared memory and a number of processors with local memory. Processors only communicate via their shared memory. The computation steps are performed in a synchronous lock-step manner. Memory access to different memory locations can be performed at the same time. The PRAMs are distinguished by their ability to access in parallel the same memory location. In our pa..