Massively parallel strategies for local spatial interpolation

An inverse distance weighted interpolation algorithm is implemented using three massively parallel SIMD computer systems. The algorithm, which is based on a strategy that reduces search for control points to the local neighborhood of each interpolated cell, attempts to exploit hardware communication paths provided by the system during the local search process. To evaluate the performance of the algorithm a set of computational experiments was conducted in which the number of control points used to interpolate a 240 x 800 grid was increased from 1000 to 40,000 and the number of k-nearest control points used to compute a value at each grid location was increased from one to eight. The results show that the number of processing elements used in each experimental run significantly affected performance. In fact, a slower but larger processor grid outperformed a faster but smaller configuration. The results obtained, however, are roughly comparable to those obtained using a superscalar workstation. To remedy such performance shortcomings, future work should explore spatially adaptive approaches to parallelism as well as alternative parallel architectures. (C) 1997 Published by Elsevier Science Ltd.