Title :
Parallelization of perceptual grouping on distributed memory machines
Author :
Wang, Cho-Li ; Prasanna, Viktor K. ; Lim, Young Won
Author_Institution :
Dept. of Electr. Eng. Syst., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
We propose architecture independent parallel algorithms for solving perceptual grouping tasks on distributed memory machines. Given an n×n image, using P processors, we show that these tasks can be performed in O(n2/P) computation time and 20√(P)Td +8(logP)Td+(40n/√(P)+20P)τd communication time, where Td is the communication startup time and τd is the transmission rate. Our implementations show that, given 7K line segments extracted from a 1K×1K image, the line grouping task can be performed in 1.115 seconds using a partition of CM-5 having 256 processing nodes and in 0.382 seconds using a 16 node Cray T3D. Our code is written in C and MPI message passing standard and can be easily ported to other high performance computing platforms
Keywords :
communication complexity; computational complexity; distributed memory systems; edge detection; feature extraction; message passing; parallel algorithms; 16 node Cray T3D; CM-5; MPI message passing standard; architecture independent parallel algorithms; communication startup time; communication time; computation time; distributed memory machines; high performance computing platforms; line segment extraction; perceptual grouping; processing nodes; transmission rate; Application software; Code standards; Computer vision; Data communication; High performance computing; Humans; Image segmentation; Message passing; Parallel algorithms; Workstations;
Conference_Titel :
Computer Architectures for Machine Perception, 1995. Proceedings. CAMP '95
Conference_Location :
Como
Print_ISBN :
0-8186-7134-3
DOI :
10.1109/CAMP.1995.521056
