Accession Number : ADA332213

Title :   Scalable Data Parallel Algorithms and Implementations for Vision

Descriptive Note : Final rept. 15 Sep 95-14 Mar 97

Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES INST FOR ROBOTICS AND INTELLIGENT SYSTEMS

Personal Author(s) : Nevatia, R. ; Prasanna, V. K.

PDF Url : ADA332213

Report Date : 08 JUL 1997

Pagination or Media Count : 31

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.

Descriptors :   *ALGORITHMS, *PARALLEL PROCESSING, *COMPUTER VISION, DATA BASES, IMAGE PROCESSING, ROBOTICS, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, ASYNCHRONOUS SYSTEMS, ARTIFICIAL INTELLIGENCE, BANDWIDTH, FEATURE EXTRACTION.

Subject Categories : Computer Programming and Software
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE