환형문자열에 대한 대표문자열을 찾는 병렬 알고리즘

김동희, 심정섭

http://doi.org/

대표문자열 문제는 k 개의 문자열로 구성된 집합 S 가 주어졌을 때 S 를 대표하는 한 문자열인 대표문자열을 찾는 문제이다. 환형문자열은 일반적인 문자열과는 달리 문자열의 첫 글자와 마지막 글자가 연결되어 원 모양을 이루는 문자열이다. 본 논문에서는 먼저 k=3 이고 길이 n인 환형문자열들로 구성된 S에 대해, 거리반경과 거리합을 동시에 고려한 대표문자열 문제를 O(n) 개의 쓰레드를 사용하여 O(｜∑｜nlogn) 시간에 병렬적으로 해결하는 알고리즘을 제시한다. 이때, ∑ 는 각 문자열을 구성하는 문자집합이다. 다음으로 k=4 이고 길이 n인 환형문자열들로 구성된 S 에 대해 거리합 기반 대표문자열 문제를 O(n)개의 쓰레드를 사용하여 O(｜∑｜n²logn) 시간에 병렬적으로 해결하는 알고리즘을 제시한다. 이후 두 문제에 대한 병렬 알고리즘들을 CUDA를 이용하여 구현하고 순차 알고리즘들과의 실행 속도를 비교한 결과를 제시한다.