GPU의 공유메모리를 활용한 확장편집거리 병렬계산
Parallel Computation for Extended Edit Distances Using the Shared Memory on GPU
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
알파벳 ∑로 구성된 길이가 각각 m, n인 두 문자열 X, Y가 주어졌을 때, X, Y의 확장편집거리는 동적프로그래밍을 이용하여 O(mn) 시간과 공간을 계산할 수 있다. 최근 m개의 쓰레드를 이용하여 O(m+n) 시간과 O(mn) 공간을 사용하여 X, Y의 확장편집거리를 계산하는 병렬알고리즘이 제시되었다. 본 논문에서는 GPU의 공유메모리를 활용하여 수행시간을 개선한 병렬알고리즘을 제시한다. 실험 결과, 개선된 병렬알고리즘이 기존의 병렬알고리즘보다 약 19~25배 이상 빠른 수행시간을 보였다.
Abstract
Given two strings X and Y (|X|=m, |Y|=n) over an alphabet ∑, the extended edit distance between X and Y can be computed using dynamic programming in O(mn) time and space. Recently, a parallel algorithm that takes O(m+n) time and O(mn) space using m threads to compute the extended edit distance between X and Y was presented. In this paper, we present an improved parallel algorithm using the shared memory on GPU. The experimental results show that our parallel algorithm runs about 19~25 times faster than the previous parallel algorithm.
참고문헌 (11)
- R. Baeza-Yates, "Fast approximate string matching in a dictionary", Proc. South Am. Symp. String Proc. Information Retrieval (SPIR ’98), pp.14~22 (1998)
- S. Forrest, "Self-nonself discrimination in a computer", Proc. of the IEEE Symposium on Research in Security and Privacy, pp.202~212 (1994)
- M. Roesch, "Snort-Lightweight Intrusion Detection for Networks", Proceedings of the 13th Conference on Systems Administration(LISA ’99), pp.229~238 (1999)
- T. F. Smith, "Identification of Common Molecular Subsequences", Journal of molecular biology, 147(1), pp.195~197 (1981)
- W. Liu, "Bio-Sequence Database Scanning on a GPU", 20th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2006) (HICOMB Workshop) (2006)
- R. A. Wagner, "On the complexity of the extended stringto-string correction problem", Proc. of seventh annual ACM symposium on Theory of computing, pp.218~223 (1975)
- R. Lowrance, "An extension of the string-to-string correction problem", Journal of the ACM, 22(2), pp.177~183 (1975)
- D. K. Kim, "Efficient algorithms for approximate string matching with swaps", Journal of complexity, 15(1), pp.128~147 (1999)
- 윤현철, "CUDA를 이용한 최장공통비상위문자열 그래프 모델의 병렬생성", 정보과학회논문지 : 시스템 및 이론, 39(3), pp.202~208 (2012), 한국정보과학회[DOI]
- 강대웅, "교환연산을 포함한 확장편집거리 병렬계산", 정보과학회논문지 : 시스템 및 이론, 41(4), pp.175~181 (2014), 한국정보과학회
- "Lectures 5 and 6: Memory model and Locality"[URL]