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