A Coarse-Grained, Architecture-Independent Approach for Connected Component Labeling
Mikhail J. Atallah, Frank Dehne, Susanne E. Hambrusch · Purdue e-Pubs (Purdue University System) · 1993
Lr-t I be a binary image' of size fii x Vii stored in a coarse-grained p-processor parallel machine ill which each processor has O(ll/p) local memory and stores a JnJp x J7I/p sllbimage of I. \,VC' consider the problem of determining the connected components of TOur algorithm makes no assumptions abont the architecture of the parallel machine, aml it is exprrssed in terms of local cOlilputations and c.ommunication roulHls. CornmunicatiOll rounds tend to be expensive ill any parallel archileclure, and thus the objective is to wiuimize the numbN of comnllHlication rounds. It is e , when one assumes 11 2: p:l. When no assnmptions about the relative sizes of 11 and p are made, simulating any of the published solutions lVould r('sult in at least logp commuuication rounds. We givl. a solution for determining the connected components that requires at most log[ogp c_ommunicatioll rounds. 'Research sllpported in part by the Air Force OJlice of Scientific Research under Contrad AfOSR-90-0]07 and hy tht: Naliolla.! Science Foundation under Grant CCR_9202807. 1Research snllporteu in part by the Natura.! Science.'> aud Eligilleerill~ Research Council of Canada. IResearch sllpported in part hy DARPA under contracl DABT63-92-C-00220NR.