Parallel-Prefix Remapping for Efficient Data-Parallel Implementation of Unbalanced Simulations.
Melissa C. Smith, Eric Renshaw · 1993
This paper reports on a new data-parallel algorithm, called parallel-prefix remapping (PPR), that has been developed to overcome the extreme load-imbalance problems in our applications. Using this new approach we can ensure that all processors are evenly loaded, no matter how spatially imbalanced the reactants become, nor how dynamic the hot-spots behave. However PPR does introduce a computational overhead into our 2 implementation, and thus, if used on an inherently balanced simulation, could result in a performance degradation when compared to a standard spatial decomposition. It therefore becomes vital to be able to predict the expected behaviour of our Monte Carlo simulations in order to decide on the best implementation strategy, as well as to estimate the expected simulation time. We have therefore developed a statistical analysis of a general stochastic spatial reaction system. This provides us with expected values for the spatial and temporal structure of reactant distributions in terms of known system parameters, from which we can then extract measures of population imbalance, as well as hot-spot growth and decay rates. 2. MATHEMATICAL REPRESENTATION