Connected components algorithms for mesh-connected parallel computers
Connected components algorithms for mesh-connected parallel computers
复制标题
用于网状连接并行计算机的连接组件算法
DOI：
10.1090/dimacs/030/03
复制
发表时间：
1994
影响因子：
3.7
通讯作者：
J. Prins
中科院分区：
文献类型：
--
作者：
S. Goddard;Subodh Kumar;J. Prins
我们提出了一个新的CREW PRAM算法的连接组件。对于n个顶点m条边的图G，算法A0最多需要O（logn）个并行步，在最坏情况下执行O（（n+m）logn）个工作.我们的算法的优点是，它可以适应于2-D网状连接的通信模型，其中所有的CREW操作被替换为O（logn）并行的行和列操作，而不增加时间复杂度。我们提出了A0到网状连接计算机的映射，并描述了两个实现，A1和A2。算法A1使用邻接矩阵来表示图，执行O（n logn）工作。因此，它只在稠密图上工作效率。第二个实现A2使用邻接矩阵的稀疏表示，并再次执行O（logn）行和列操作，但在所有图上将工作减少到O（（m + n）logn）。我们报告MasPar MP-1性能测试所描述的算法的实现。的实现是行使各种参数化生成的图形，diering在结构和连接。这些图是外部生成的，并作为算法的输入读入，允许在相同的图上比较不同的实现。
We present a new CREW PRAM algorithm for nding connected components. For a graphG with n vertices andm edges, algorithmA0 requires at mostO(logn) parallel steps and performsO((n+m) logn) work in the worst case. The advantage our algorithm has over others in the literature is that it can be adapted to a 2-D mesh-connected communication model in which all CREW operations are replaced byO(logn) parallel row and column operations without increasing the time complexity. We present the mapping of A0 to a mesh-connected computer and describe two implementations, A1 and A2. Algorithm A1, which uses an adjacency matrix to represent the graph, performs O(n logn) work. Hence, it only achieveswork e ciency on dense graphs. The second implementation,A2, uses a sparse representation of the adjacency matrix and again performs O(logn) row and column operations but reduces the work to O((m + n) logn) on all graphs. We report MasPar MP-1 performance gures for implementations of the algorithms described. The implementations are exercised on a variety of parametrically generated graphs, di ering in structure and connectivity. These graphs are generated externally and read in as input for the algorithms, permitting comparison of di erent implementations on identical graphs.