Correctness and determinism of parallel Monte Carlo processes (Q1186171)

The purpose of the paper is to investigate some of the problems raised by the implementation of the Monte Carlo method of simulation on multiprocessor (parallel) computers. The simulated processes are stochastic, like particle dynamics and population evolution. The ideas are exemplified with a population growth model (herrings and sharks in a toroidal ocean). Some of the problems under investigation are correctness and determinism. In order to exploit the parallel processing computer power, the problem is divided in smaller subproblems depending on area deliminations. There are two phases in view: first the calculus of the next moves and the communication to other processors and second, the execution of the moves. To reduce the impact of collision and inconsistencies the authors propose the unrolling technique. The unrolling technique occurs when, due to interactions with neighbor areas, the computed moves do not satisfy the initial constraints of the problem. So the simulation has to go back one or possible more steps. There are also in the paper some comparisons with other methods of synchronization (with semaphores) but they are not explained in detail. In order to help the avoidance of collisions, the authors introduce some new rules of simulations, like attracting and repelling forces depending on the distances between objects. And so some collisions are allowed but there is a great probability that they are resolved the next step. The examples show that statistic results for the proposed method are very close to that obtained with sequential method. The determinism is an important characteristic because output of the parallel programs must be reproducible at least for the testing phase. The random nature of the problem implied by the Monte Carlo method and the dynamic loading of the processors or the slight differences between processors speed (in case of MIMD architecture) make the reproduction of the results difficult. The authors propose a random generator which takes into account the possible different order of decisions for the next move in the repetitive simulation process.