DocumentCode :
875283
Title :
Parallel algorithms for geometric connected component labeling on a hypercube multiprocessor
Author :
Belkhale, K.P. ; Banerjee, P.
Author_Institution :
IBM, Hopewell Junction, NY, USA
Volume :
41
Issue :
6
fYear :
1992
fDate :
6/1/1992 12:00:00 AM
Firstpage :
699
Lastpage :
709
Abstract :
Parallel algorithms for the geometric connected component labeling (GCCL) problem on a hypercube multiprocessor can be designed by dividing the domain, consisting of a number of rectangles, into regions using a slice or rectangular partitioning scheme. Each processor in the hypercube is assigned one partition. The processor determines the connected sets of rectangles in its partition. The connected sets at different processors have to then be combined across processors into globally connected sets. This merging problem is defined as the GCCL problem. Different algorithms for the GCCL problem are presented. Each of the algorithms involves d stages of message passing, for a d-dimensional hypercube. The basic idea in these algorithms is that in each stage a processor increases its knowledge of the domain. The algorithms described in this paper differ in their run time, memory requirements, and message complexity. These algorithms have been implemented on an Intel iPSC2/D4/MX hypercube
Keywords :
computational geometry; hypercube networks; parallel algorithms; complexity; geometric connected component labeling; hypercube multiprocessor; memory requirements; merging problem; parallel algorithms; run time; Algorithm design and analysis; Circuits; Hypercubes; Labeling; Merging; Message passing; NASA; Parallel algorithms; Partitioning algorithms; Very large scale integration;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.144622
Filename :
144622
Link To Document :
بازگشت