Near-Optimal, Path-Level Parallelization for Sequential Geostatistical Simulation

Sequential geostatistical simulation methods are widely used for probabilistic spatial modeling in Earth sciences and engineering. These methods are typically formulated as serial procedures due to their reliance on neighborhood conditioning. Among the existing approaches to parallelizing sequential simulation, path-level parallelization (where multiple grid nodes are simulated concurrently) is the most attractive strategy in terms of computational efficiency and performance. However, parallelization at the path level is challenging due to data dependencies between simulation steps. Although several effective solutions to this problem have been proposed, none can efficiently manage and utilize available resources without incurring overhead. In this work, we describe a simple, efficient, and general-purpose strategy for path-level parallelization based on a precomputed Path Index Grid (PIG). Each grid node holds its position in the simulation path, allowing each thread to determine whether its conditioning neighbors have already been simulated, using only read-only access to the PIG and the simulation grid. No locking, mutexes, or synchronization primitives are required. The proposed approach is exact, reproducible, and applicable to all sequential simulation frameworks and across arbitrary grid dimensionalities. Although it has already been used in practical implementations, it has not yet been described or documented in the literature. The goal of this paper is to formalize the methodology, demonstrate its practicality and accessibility for parallelizing sequential simulation, and establish it, to the best of our knowledge, as the most efficient solution to date. In addition to describing the method, we evaluate its performance against a theoretically optimal scheduling path and show that the overhead of unmanaged concurrency is minimal: the proposed approach remains within 1% of the theoretical scheduling optimum, even though the absolute speedup achievable through path optimization itself is small.