Tehnički vjesnik, Vol. 23 No. 4, 2016.
Izvorni znanstveni članak
https://doi.org/10.17559/TV-20150314132647
A fast parallel algorithm for finding the largest common 4-connected component from two matrices
Ying Gao
; School of Computer Science and Engineering, South China University of Technology, Waihuan Dong Road No. 382, Panyu District, Guangzhou, China
Haoshen Liu
; School of Computer Science and Engineering, South China University of Technology, Waihuan Dong Road No. 382, Panyu District, Guangzhou, China
Jiancong Huang
; School of Computer Science and Engineering, South China University of Technology, Waihuan Dong Road No. 382, Panyu District, Guangzhou, China
Jiajie Duan
; YunNan Electric Power Test & Research Institute Group CO. Ltd, China
Lei Mu
; Huanggang Dong Road, Tiaoqiao District, JiNan, Shangdong Province, China
Sažetak
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.
Ključne riječi
CUDA; largest common 4-connected component; parallel algorithm; 2DLCS
Hrčak ID:
163811
URI
Datum izdavanja:
16.8.2016.
Posjeta: 1.414 *