Access Restriction

Author Lam, John ♦ Chin, Francis Y. ♦ Chen, I-Ngo
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Simd ♦ Optimal algorithms ♦ Parallel algorithms ♦ Complexity ♦ Graph problems
Abstract We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log2 n) time bound can be achieved using only K = n⌈n/log2 n⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
Description Affiliation: Univ. of Alberta, Edmonton, Alberta, Canada (Chin, Francis Y.; Lam, John; Chen, I-Ngo)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 25
Issue Number 9
Page Count 7
Starting Page 659
Ending Page 665

Open content in new tab

   Open content in new tab
Source: ACM Digital Library