다항식 곱셈을 이용한 근사패턴매칭의 CUDA 구현 (A CUDA Implementation of Approximate Pattern Matching Using Polynomial Multiplication)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 40권 / 6호 / 290 ~ 295페이지
· 저자명 : 심정섭, 김동희

초록

근사패턴매칭은 패턴매칭을 불일치를 허용하도록 확장한 문제이며 데이터압축, 컴퓨터보안, 생물정보학 등 다양한 분야에서 연구되고 있다. 해밍거리는 길이가 인 두 문자열 사이의 불일치 정도를 나타내기 위한 잘 알려진 거리함수로서 시간에 계산할 수 있다. 본 논문에서 다룰 (해밍거리 기반) 근사패턴매칭은 길이 인 패턴 와 길이 인 텍스트 가 주어졌을 때 길이 인 의 모든 부분문자열과 사이의 해밍거리를 구하는 문제이다. 이 문제는 단순비교 기반의 알고리즘으로 시간에 간단히 해결할 수 있다. 알파벳의 크기를 라 할 때, Amir 등은 패턴매칭 문제를 다항식 곱셈 문제로 변환하여 시간에 근사패턴매칭 문제를 해결하는 알고리즘(이하 PM 알고리즘)을 제시하였다. 본 논문에서는 PM 알고리즘을 CUDA를 이용하여 병렬 구현한 시간 알고리즘(이하 PPM 알고리즘)을 제시한다. 수행시간을 측정한 결과, PPM 알고리즘은 PM 알고리즘에 비해 약 40～2,000배 빨랐으며, 단순비교 기반 알고리즘에 비해서는 최대 7,000배 정도 빠른 성능을 보였다.

영어초록

Approximate pattern matching, a natural extension of exact pattern matching, is allowing errors. It has been studied in such diverse fields as data compression, computer security and bioinformatics. The Hamming distance is one of the well-known distance functions being used to measure the errors between two strings of length , which can be computed in time. The (Hamming distance based) approximate pattern matching problem of pattern and text is finding Hamming distances between and all substrings of whose lengths are . The approximate pattern matching problem can be easily solved in time using a naive approach. By transforming the approximate pattern matching problem into the polynomial multiplication problem, Amir et al. proposed an time algorithm (PM algorithm for short) where is the size of the alphabet. In this paper, we propose a CUDA implementation of a parallelized PM algorithm (PPM algorithm for short) running in time. The experimental results show that the PPM algorithm runs about 40～2,000 times faster than the PM algorithm and runs upto 7,000 times faster than the naive approach, respectively.

참고자료

· 없음