Scalable high performance computing: A poly-algorithmic approach to computer vision and image processing libraries on parallel systems

Parallel computers hold enormous promise for achieving high performance at a reasonable cost for many application areas. However, exploiting the potential of current parallel machines requires a detailed understanding of parallel algorithms and programming, as well as an intimate knowledge of the underlying architecture. Parallel computing will not be successful if it requires researchers in different application areas to become experts in parallel processing. Towards this end, Cloner has recently been proposed as a library-based algorithm prototyping environment tailored to the areas of computer vision and image processing (CVIP). Cloner seeks to provide CVIP researchers with tools to develop efficient applications on currently available parallel computers. This thesis addresses the issues involved in realizing the Cloner environment. We begin with a study of the scalability of CVIP algorithms on parallel systems. We have performed analytical and experimental comparisons of the scalability of three algorithms in CVIP--2-D convolution, 2-D FFT, and list ranking on image edges. We show that scalability, in the sense of preserving performance, can only be achieved by varying the algorithm approach based on the problem and machine parameters. We present an object-oriented framework for the Cloner library, in which the relevant algorithm and architecture-related scalability information is embedded within the environment. We describe how Cloner uses information about the CVIP application domain to achieve software reuse in the context of parallel processing. Finally, we demonstrate algorithm prototyping in Cloner by implementing the 2-D wavelet transform from templates of existing library code