MASSIVELY-PARALLEL STRATEGIES FOR LOCAL SPATIAL INTERPOLATION

An inverse distance weighted interpolation algorithm is implemented us ing three massively parallel SIMD computer systems. The algorithm, whi ch is based on a strategy that reduces search for control points to th e local neighborhood of each interpolated cell, attempts to exploit ha rdware communication paths provided by the system during the local sea rch process. To evaluate the performance of the algorithm a set of com putational experiments was conducted in which the number of control po ints used to interpolate a 240 x 800 grid was increased from 1000 to 4 0,000 and the number of k-nearest control points used to compute a val ue 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 p rocessor grid outperformed a faster but smaller configuration. The res ults obtained, however, are roughly comparable to those obtained using a superscalar workstation. To remedy such performance shortcomings, f uture work should explore spatially adaptive approaches to parallelism as well as alternative parallel architectures. (C) 1997 Published by Elsevier Science Ltd.