A FAST PARALLEL ALGORITHM FOR FINDING THE LARGEST COMMON 4-CONNECTED COMPONENT FROM TWO MATRICES

作者：Gao, Ying^*; Liu, Haoshen; Huang, Jiancong; Duan, Jiajie; Mu, Lei

来源：Tehnicki Vjesnik, 2016, 23(4): 979-984.

DOI：10.17559/TV-20150314132647

• CUDA
• largest common 4-connected component
• parallel algorithm
• 2DLCS

We describe a new design of parallel algorithm for solving the two-dimensional longest common substring (2D LCS) problem, taking advantage of the multi-core graphic processing unit architecture offered by Compute Unified Device Architecture (CUDA). In this article we also define the 2D LCS problem as finding the largest common 4-connected component from two input matrices and present an algorithm which can exactly solve this problem in 0 (mnst/P) time with a P-core GPU.

• 出版日期2016-8
• 单位华南理工大学