Scalable Data Parallel Algorithms and Implementations for Vision
Abstract
This effort is about designing, analyzing and implementing scalable and portable parallel solutions to problems in intermediate and high level vision. This is a difficult problem as computations are heterogeneous, symbolic and geometric in nature and use complex data structures such as lists and graphs. Simple data parallel approaches are not sufficient due to uneven distribution of symbolic features among the processors, unbalanced workload, and irregular interprocessor data dependency caused by the input image. In this work, a realistic model of distributed memory parallel machines which accurately models the features of a parallel machine was proposed. This includes the costs of communication latency, impact of communication patterns on network congestion, available bandwidth and time for synchronization. Using this model, the computation, communication and control characteristics and the memory requirements of the vision algorithms were analyzed. Based on these, an asynchronous parallel algorithm which enhances processor utilization and overlaps communication with computation by maintaining algorithmic threads in each processor was developed. Furthermore, the dynamic task migration technique at an algorithmic level can balance the unpredictable workload in parallelizing intermediate and high level vision problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 08, 1997
- Accession Number
- ADA332213
Entities
People
- R. Nevatia
- V. K. Prasanna
Organizations
- University of Southern California