download0 view177
twitter facebook

공공누리This item is licensed Korea Open Government License

Title
Cache Locality-Centric Parallel String Matching on Many-Core Accelerator Chips
Author(s)
Nhat-Phuong Tran이명호최동훈
Publication Year
2015-10-30
Abstract
Aho-Corasick (AC) algorithm is a multiple patterns string matching algorithm commonly used in computer and network security and bioinformatics, among many others. In order to meet the highly demanding computational requirements imposed on these applications, achieving high performance for the AC algorithm is crucial. In this paper, we present a high performance parallelization of the AC on the many-core accelerator chips such as the Graphic Processing Unit (GPU) from Nvidia and the Intel Xeon Phi. Our parallelization approach significantly improves the cache locality of the AC by partitioning a given set of string patterns into multiple smaller sets of patterns in a space-efficient way. Using the multiple pattern sets, intensive pattern matching operations are concurrently conducted with respect to the whole input text data. Compared with the previous approaches where the input data is partitioned amongst multiple threads instead of partitioning the pattern set, our approach significantly improves the performance. Experimental results show that our approach leads up to 2.73 times speedup on the Nvidia K20 GPU and 2.00 times speedup on the Intel Xeon Phi compared with the previous approach. Our parallel implementation delivers up to 693 Gbps throughput performance on the K20.
Journal Title
Scientific Programming
Citation Volume
2015
ISSN
1058-9244
Files in This Item:
There are no files associated with this item.
Appears in Collections:
7. KISTI 연구성과 > 학술지 발표논문
URI
https://repository.kisti.re.kr/handle/10580/14480
http://www.ndsl.kr/ndsl/search/detail/article/articleSearchResultDetail.do?cn=NART76727736
Export
RIS (EndNote)
XLS (Excel)
XML

Browse