The optimisation of higher order resampling methods in a multiprocessor environment

The processing of images obtained from satellites often involves highly repetitive calculations on very large amounts of data. This processing is extremely time consuming when these calculations are performed on sequential machines. Parallel computers are well suited to handling computationally expensive operations such as higher order interpolations on large data sets. This paper decribes work undertaken to develop parallel implementations of a set of resampling procedures on an Alliant VFX/4. Each resampling procedure implemented has been optimised in three stages. First, the algorithm has been restructured, where two-dimensional resampling is performed by two one-dimensional resampling operations. Second, each procedure has been reprogrammed in such a way that the autoparallelisation provided by the FX/Fortran compiler has been exploited. Thirdly, data dependent analysis of each procedure has been performed in order to achieve full optimization of each procedure; each procedure has been restructured where appropriate to circumvent vectorisation and concurrency inhibiting data dependencies. The nature and extent of the code optimization achieved for each procedure is presented in this paper. The original code for the most computationally expensive procedure, as targeted at a sequential machine, was found to have an execution time of 4900 seconds on the Alliant VFX/4 when compiled with regular compiler optimization options. Following algorithmic redesigning and reprogramming of the code, as indicated in stage 1 and stage 2, the execution time was reduced to 248 seconds. Restructuring of the code following data dependency analysis indicated in stage 3 in order to avoid data dependencies and allow concurrency and vectorisation, further reduced execution time to 162 seconds. The consequence of this work is that higher-order resampling methods which had not previous been practical are now routinely performed on the Alliant VFX/4 at the University of Dundee.