http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
ThienLuan Ho(호 티엔 루안),HyunJin Kim(김현진),SeungRohk Oh(오승록) 대한전기학회 2017 전기학회논문지 Vol.66 No.6
In this paper, we propose a parallel approximate string matching algorithm with k-mismatches for multiple fixed-length patterns (PMASM) in DNA sequences. PMASM is developed from parallel single pattern approximate string matching algorithms to effectively calculate the Hamming distances for multiple patterns with a fixed-length. In the preprocessing phase of PMASM, all target patterns are binary encoded and stored into a look-up memory. With each input character from the input string, the Hamming distances between a substring and all patterns can be updated at the same time based on the binary encoding information in the look-up memory. Moreover, PMASM adopts graphics processing units (GPUs) to process the data computations in parallel. This paper presents three kinds of PMASM implementation methods in GPUs: thread PMASM, block-thread PMASM, and shared-mem PMASM methods. The shared-mem PMASM method gives an example to effectively make use of the GPU parallel capacity. Moreover, it also exploits special features of the CUDA (Compute Unified Device Architecture) memory structure to optimize the performance. In the experiments with DNA sequences, the proposed PMASM on GPU is 385, 77, and 64 times faster than the traditional naive algorithm, the shift-add algorithm and the single thread PMASM implementation on CPU. With the same NVIDIA GPU model, the performance of the proposed approach is enhanced up to 44% and 21%, compared with the naive, and the shift-add algorithms.
ThienLuan Ho(호 티엔 루안),Hyun-Jin Kim(김현진),Seung-Rohk Oh(오승록),Hong-Jue Youn(윤홍주),Hyung-Seok Heo(허형석) 대한전기학회 2015 대한전기학회 학술대회 논문집 Vol.2015 No.4
A parallel Aho-Corasick (AC) approach, named PAC-k, is proposed for the string matching in deep packet inspection (DPI). The proposed approach adopts graphic processing units (GPUs) to perform the string matching in parallel for high throughput. In the parallel string matching, the boundary detection problem happens when a pattern is matched across chunks. The PAC-k approach solves the boundary detection problem because the number of characters to be scanned by a thread is up to the longest pattern length. An input string is divided into multiple sub-chunks with k characters. By adopting the new starting position in each sub-chunk for the failure transition, the required number of threads is reduced by a factor of k. In addition, the number of terminated threads is decreased, computational resources are conserved. In order to avoid the unnecessary overlapped scanning with multiple threads, the checking module is proposed to decide whether a new starting position is in the sub-chunk. In the experiments with target patterns from Snort and realistic input strings from DEFCON, throughputs are enhanced greatly compared to those of previous AC-based string matching approaches.
Seung-Rohk Oh(오승록),Hong-Jue Youn(윤홍주),Hyung-Seok Heo(허형석),Hyun-Jin Kim(김현진),ThienLuan Ho(호 티엔 루안) 대한전기학회 2015 정보 및 제어 심포지엄 논문집 Vol.2015 No.4
A parallel Aho-Corasick (AC) approach, named PAC-k, is proposed for the string matching in deep packet inspection (DPI). The proposed approach adopts graphic processing units (GPUs) to perform the string matching in parallel for high throughput. In the parallel string matching, the boundary detection problem happens when a pattern is matched across chunks. The PAC-k approach solves the boundary detection problem because the number of characters to be scanned by a thread is up to the longest pattern length. An input string is divided into multiple sub-chunks with k characters. By adopting the new starting position in each sub-chunk for the failure transition, the required number of threads is reduced by a factor of k. In addition, the number of terminated threads is decreased, computational resources are conserved. In order to avoid the unnecessary overlapped scanning with multiple threads, the checking module is proposed to decide whether a new starting position is in the sub-chunk. In the experiments with target patterns from Snort and realistic input strings from DEFCON, throughputs are enhanced greatly compared to those of previous AC-based string matching approaches.