Global Optimization for Mapping Parallel Image Processing Tasks onDistributed Memory Machines

Many parallel algorithms and library routines are available for performingcomputer vision and image processing (CVIP) tasks on distributed-memorymultiprocessors. The typical image distribution may use column, row, and blockbased mapping. Integrating a set of library routines for a CVIP applicationrequires a global optimization for determining the data mapping of individualtasks by considering inter-task communication. The main difficulty in derivingthe optimal image data distribution for each task is that CVIP task computationmay involve loops, and the number of processors available and the size of theinput image may vary at the run time. In this paper, a CVIP application ismodeled using a task chain with nested loops, specified by conventional visuallanguages such as Khoros and Explorer. A mapping algorithm is proposed thatoptimizes the average run-time performance for CVIP applications with nestedloops by considering the data redistribution overheads and possible run-timeparameter variations. A taxonomy of CVIP operations is provided and used forfurther reducing the complexity of the algorithm. Experimental results on bothlow-level image processing and high-level computer vision applications arepresented to validate this approach.