An evaluation of domain decomposition strategies for parallel spatial interpolation of surfaces

The objective of this paper is to investigate static and dynamic methods for spatially subdividing the work required to interpolate a gridded surface into a set of subtasks that are allocated to separate processors for execution in parallel. A description of the parallel implementation and testing procedures is preceded by a review of the serial version of the particular neighborhood-based, inverse-distance-weighted interpolation (Clarke) algorithm chosen for interpolation. The effects on serial program execution time of data distribution (dispersed or clustered) are documented and these results are used to inform a partial parallelization process. Next, six problem decomposition and task scheduling strategies are evaluated on a shared memory multiprocessor. The choice of problem decomposition and task scheduling combination is shown to exercise a significant role in. determining parallel program performance, with a medium-grained, dynamically scheduled approach showing the best adaptability to variable spatial workload and uneven processor power.