Original scientific paper

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

Abstract

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.

Keywords

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

Hrčak ID:

163811

URI

https://hrcak.srce.hr/163811

Publication date:

16.8.2016.

Article data in other languages: croatian

Visits: 1.906 *