Original scientific paper

https://doi.org/10.17559/TV-20150314132647

Brzi paralelni algoritam za pronalaženje najveće zajedničke 4-spojene komponente iz dviju matrica

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

Opisujemo novi dizajn paralelnog algoritma za rješavanje problema dvodimenzionalnog najduljeg zajedničkog podniza (2D LCS), iskoristivši arhitekturu grafičke obradne jedinice s više jezgri (multi-core graphic processing unit) ponuđene od Compute Unified Device Architecture (CUDA). U ovom radu također definiramo 2D LCS problem pronalaženjem najveće zajedničke 4-spojene komponente iz dvije ulazne matrice i predstavljamo algoritam koji može točno riješiti ovaj problem u 0 (mnst/P) vremenu s P-core GPU.

Keywords

2DLCS; CUDA; najveća zajednička 4-spojena komponenta; paralelni algoritam

Hrčak ID:

163811

URI

https://hrcak.srce.hr/163811

Publication date:

16.8.2016.

Article data in other languages: english

Visits: 1.906 *