CUDA를 이용한 최장공통비상위문자열 그래프 모델의 병렬생성 = Parallel Construction for the Graph Model of the Longest Common Non-superstring using CUDA

국문 초록 (Abstract)

상수 크기의 문자집합에 대해 정의된 문자열 집합 F의 어느 문자열도 포함하지 않는 문자열을 공통비상위문자열이라 하고, 이들 중 가장 긴 유한길이의 문자열을 F의 최장공통비상위문자열(Longest Common Non-Superstring, LCNSS)이라 한다. LCNSS문제는 접두사 또는 접미사 기반의 그래프 모델링으로 해결할 수 있으며, 컴퓨터보안 분야에서 패킷 내의 악성 패턴 등을 검출하는 침입탐지시스템 또는 유전 질환을 발현시키는 DNA 세그먼트들을 검출하는 DNA 분석 문제에 활용될 수 있다. 한편 다중코어 프로세서의 발전으로 인해 병렬알고리즘의 연구도 활발히 진행되고 있다. 순차알고리즘들은 단일 단계에 하나의 연산만을 수행하지만 병렬알고리즘은 단일 단계에 여러 개의 연산을 수행하여 문제를 해결하는 시간을 단축시킨다. 최근에는 높은 연산 성능의 GPU를 이용하여 문제를 해결하는 GPU 기반 병렬알고리즘의 연구가 활발히 이루어지고 있다.
본 논문에서는 기존의 순차적 접두사 기반 LCNSS문제 해결 알고리즘에서 많은 연산이 필요한 그래프 모델링 부분을 nVidia CUDA(the Compute Unified Device Architecture)를 이용하여 구현한 후 실험을 통해 성능 향상을 확인한다. 또한 그래픽 카드의 전역메모리(global memory)만을 사용하였을 때와 공유메모리(shared memory)를 명시적으로 사용하였을 때의 성능을 비교한다.

다국어 초록 (Multilingual Abstract)

Given a set of strings F over a constant size alphabet, consider a string x such that x does not include any string in F as a substring. We call x a common non-superstring (CNSS for short) of F. Among the CNSSs, the longest one with finite length is called the longest common non-superstring (LCNSS for short) of F. The LCNSS problem can be solved by two graph-based models: the prefix-based model and the suffix-based model. The LCNSS problem can be applicable to intrusion detection systems and DNA analysis. Meanwhile, with the advance of the multi-core processors, parallel algorithms are being studied vigorously. Sequential algorithms perform only one operation in a single step, but parallel algorithms perform multiple operations in a single step to reduce the time to solve problems. Recently, especially GPU-based solutions are being studied actively due to the high computational power of GPUs.
In this paper, we present some results for the LCNSS problem. We implemented the prefix-based graph modeling algorithm for the LCNSS problem using nVidia CUDA (the Compute Unified Device Architecture). We give some experimental results to show the effectiveness of our implementation.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 그래프 모델 생성 알고리즘
• 4. 실험 결과 및 분석
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 최시원, "최장공통비상위문자열을 찾는 새로운 알고리즘" 한국정보과학회 15 (15): 67-71, 2009

2 조석현, "일반화접미사배열을 이용한 선형시간 최장공통비상위문자열 알고리즘" 한국정보과학회 38 (38): 216-222, 2011

3 윤현철, "동적 최장공통비상위문자열 문제 해결 알고리즘" 한국차세대컴퓨팅학회 6 (6): 35-43, 2010

4 M. Roesch, "Snort–Lightweight Intrusion Detection for Networks" 1999

5 "Snort rules"

6 David Kirk, "Programming massively parallel processors hands-on with CUDA" Morgan Kaufmann Publishers 2010

7 Barry Wilkinson, "Parallel programming : techniques and applications using networked workstations and parallel computers" Prentice Hall 1999

8 Guy E. Blelloch, "Parallel algorithms" 28 (28): 1996

9 Ziv M. Kedem, "Parallel Suffix-Prefix Matching Algorithm and Applications" 25 (25): 998-1923, 1996

10 J. Gallant, "On finding minimal length superstrings" 20 (20): 50-58, 1980

11 A. Blum, "Linear approximation of shortest superstrings" 41 (41): 630-647, 1994

12 J. C. Na, "Finding the longest common nonsuperstring in linear time" ELSEVIER SCIENCE BV 109 (109): 1066-1070, 200908

13 Alfred, V. Aho, "Efficient string matching: an aid to bibliographic search" 18 (18): 333-340, 1975

14 V. G. Timkovsky, "Complexity of common subsequence and supersequence problems and related problems" 25 (25): 565-580, 1990

15 D. S. Hirschberg, "Algorithms for the Longest Common Subsequence Problem" 24 (24): 664-675, 1977

16 Cheng-Hung Lin, "Accelerating String Matching Using Multi-threaded Algorithm on GPU" 2010

17 F. Kerschbaum, "A new way to think about secure Computation: Language-based Secure Computation" 33-42, 2007

18 Huang, N.-F., "A GPU-Based Multiple- Pattern Matching Algorithm for Network Intrusion Detection Systems" 2008