KR101196145B1 - Ｃｕｄａ를 이용한 최장공통비상위문자열 그래프 모델의 병렬 생성 방법 - Google Patents

Abstract

CUDA를 이용한 최장공통비상위문자열 그래프 모델의 병렬 생성 방법이 개시된다. 문자열 집합에서 가장 긴 문자열에 해당되는 최장공통비상위문자열(Longest Common Non-Superstring)을 검색하기 위하여 문자열 집합에 대한 그래프 모델을 생성하는 방법은 문자열 집합에 대하여 각 문자열의 접두사(prefix)를 기준으로 접두사 그래프를 생성하는 단계를 포함한다. 이때, 접두사 그래프를 생성하는 단계는 CUDA(Compute Unified Device Architecture)를 이용하여 문자열 집합에 대한 접두사 그래프를 생성할 수 있다.

Description

ＣＵＤＡ를 이용한 최장공통비상위문자열 그래프 모델의 병렬 생성 방법{PARALLEL CONSTRUCTION FOR GRAPH MODEL OF LONGEST COMMON NON-SUPERSTRING USING COMPUTE UNIFIED DEVICE ARCHITECTURE}

본 발명의 실시예들은 순차적 접두사 기반의 최장공통비상위문자열 문제 해결 알고리즘에서 많은 연산이 필요한 그래프 모델링 부분을 엔비디아(nVidia) CUDA(Compute Unified Device Architecture)를 이용하여 구현하는 방법에 관한 것이다.

문자열 불포함 문제는 컴퓨터 보안, 분자 생물학 등의 분야에서 필요성이 대두되어 연구가 진행되고 있다. 문자열 불포함 문제는 최장공통비상위서열(Longest Common Non-Supersequence), 최단공통비부분서열(Shortest Common Non-Subsequence), 최장공통비상위문자열(Longest Common Non-Superstring)과 최단공통비부분문자열(Shortest Common Non-Substring) 등이 연구되어 왔다.

상수 크기의 문자집합에 대해 정의된 문자열 집합 F가 입력으로 주어졌을 때, F의 모든 문자열들을 포함하지 않는 문자열을 공통비상위문자열(Common Non-Superstring)(이하, 'CNSS'라 약칭함) 이라 하고, 이들 CNSS 중 가장 긴 문자열을 F의 최장공통비상위문자열(Longest Common Non-Superstring)(이하, 'LCNSS'라 약칭함) 이라 한다.

예를 들어, 문자 집합 Σ={a,b}에서 F={aaa, baa, bab, bbb}일 때, F의 CNSS 집합은 {λ, a, b, aa, ab, ba, bb, aab, aba, abb, bba, aaba, aabb, abba, aabba}이며, 이들 중 LNCSS는 'aabba'이다.

만약, CNSS의 집합이 공집합이거나 무한집합일 경우 LCNSS는 존재하지 않는다.

이와 같은 LCNSS 문제는 접두사 또는 접미사 기반의 그래프 모델링으로 해결할 수 있다. 또한, 문자열집합 F에 하나 이상의 문자열을 추가 또는 삭제한 후 문자열 집합의 변경된 부분만을 그래프 모델에 적용하여 LCNSS를 구하는 동적 최장공통비상위문자열 문제가 접두사 기반의 모델로 연구되었다. 이러한 LCNSS 문제 및 해결 알고리즘은 컴퓨터보안 분야에서 패킷 내의 악성패턴 등을 검출하는 침입탐지시스템(Intrusion Detection System)에 활용될 수 있다. 악성패턴으로 알려진 문자열들을 F로 정의하고 네트워크 내의 패킷 내에 악성패턴(문자열)이 존재하면 이를 검출하는 것이다. 또한, 생물정보학 분야에서 유전 질환을 발생 시키는 특정 DNA 세그먼트(segment)를 분석하는 DNA 분석 문제에도 응용될 수 있다.

한편, 처리해야 할 정보의 양이 기하급수적으로 늘어남에 따라 다중코어프로세서를 활용한 병렬알고리즘(parallel algorithm)이 등장하였다. 순차알고리즘(sequential algorithm)이 단일코어프로세서를 이용하여 단일 단계에 하나의 연산만을 수행하였다면, 병렬알고리즘은 다중코어프로세서를 이용하여 단일 단계에 여러 개의 연산을 수행하여 같은 문제를 해결하는데 걸리는 시간을 단축시킨다. 최근에는 CPU보다 다중처리 성능이 뛰어난 GPU들이 등장하였고, GPU의 많은 스레드를 이용한 병렬알고리즘들이 연구되고 있다.

LCNSS 문제를 해결하기 위한 접두사 기반의 알고리즘은 순차알고리즘이기 때문에 그래프 모델링 부분에서 많이 시간이 소요되는 문제가 있다.

본 발명에서는 기존의 순차적 LCNSS 문제 해결 알고리즘 중 접두사 기반의 알고리즘에서 시간이 많이 소요되는 그래프 모델링 부분을 엔비디아(nVidia) CUDA(Compute Unified Device Architecture)를 이용하여 병렬적으로 구현하는 방법을 제시한다.

문자열 집합에서 가장 긴 문자열에 해당되는 최장공통비상위문자열(Longest Common Non-Superstring)을 검색하기 위하여 문자열 집합에 대한 그래프 모델을 생성하는 방법은 문자열 집합에 대하여 각 문자열의 접두사(prefix)를 기준으로 접두사 그래프를 생성하는 단계를 포함한다. 이때, 접두사 그래프를 생성하는 단계는 CUDA(Compute Unified Device Architecture)를 이용하여 문자열 집합에 대한 접두사 그래프를 생성할 수 있다.

일 측면에 따르면, 문자열 집합에 대한 접두사 그래프를 생성하는 단계는 문자열 집합 내의 문자열들을 병렬기수정렬(parallel radix sort) 형태로 정렬하는 단계; 및 병렬기수정렬에 대응하여 접두사 그래프의 정점 집합을 생성하는 단계를 포함할 수 있다.

다른 측면에 따르면, 문자열 집합 내의 문자열들을 병렬기수정렬 형태로 정렬하는 단계는 문자열들을 n번째 위치의 문자 종류 별로 정렬하여 n번째 위치의 문자 종류 별 블록으로 분할하는 (1) 단계를 포함할 수 있다.

또 다른 측면에 따르면, 문자열 집합 내의 문자열들을 병렬기수정렬 형태로 정렬하는 단계는 n이 1부터 N까지 순차적으로 증가하면서 분할된 각 블록 내의 문자열에 대하여 (1) 단계를 반복하는 (2) 단계를 더 포함할 수 있다. 이때, N은 문자열 집합 내의 문자열 중 문자의 수가 가장 많은 문자열의 문자 수일 수 있다.

또 다른 측면에 따르면, 병렬기수정렬에 대응하여 접두사 그래프의 정점 집합을 생성하는 단계는 분할된 각 블록 내의 문자열에 대응되는 정점을 생성할 수 있다.

또 다른 측면에 따르면, 병렬기수정렬에 대응하여 접두사 그래프의 정점 집합을 생성하는 단계는 아호 코라식 오토마타(Aho-Corasick Automata)에 의한 각 프로세서에 문자열 집합 내의 문자열 각각을 대응시키고, 분할된 각 블록 내의 문자열에 대응되는 프로세서 중 해당 블록에 가장 먼저 기록된 프로세서가 정점을 생성할 수 있다.

본 발명의 실시예에 따르면, 기존의 LCNSS 문제를 해결하는 접두사 그래프 모델링의 순차 알고리즘을 nVidia CUDA를 이용하여 병렬로 구현함으로써, LCNSS 문제에 대한 해결 성능이 향상되며 정보의 양이 늘어날수록 전역 메모리만 사용하였을 때 보다 공유 메모리를 명시적으로 사용할 경우 그 성능이 향상될 수 있다.

도 1은 금지문자열 집합 F={aaa, baa, bab, bbb}를 접두사 그래프 모델로 생성한 그래프를 도시한 것이다.
도 2는 도 1의 접두사 그래프 모델에서 정점 $를 삭제한 그래프를 도시한 것이다.
도 3 내지 도 5는 LCNSS 문제의 접두사 기반 그래프 모델을 순차 알고리즘으로 구현한 경우 소요되는 시간 비율을 도시한 것이다.
도 6은 본 발명의 일실시예에 있어서, CUDA를 이용하여 LCNSS 문제를 해결하는 병렬 알고리즘을 도시한 것이다.
도 7은 본 발명의 일실시예에 있어서, 병렬기수정렬에 대응하는 아호 코라식 오토마타(Aho-Corasick Automata)의 정점을 생성하는 과정을 설명하기 위한 도면이다.
도 8 및 도 9는 본 발명의 일실시예에 있어서, LCNSS 문제의 접두사 기반 그래프 모델을 병렬 알고리즘으로 구현한 경우 소요되는 시간 변화를 도시한 것이다.

이하, 본 발명의 실시예를 첨부된 도면을 참조하여 상세하게 설명한다.

본 발명의 실시예에서는 문자열 불포함 관련 문제들 중 최장공통비상위문자열(Longest Common Non-Superstring)(이하, 'LCNSS'라 약칭함) 문제에 관한 것이다.

먼저, 관련 용어들과 기존의 LCNSS 문제를 해결하는 순차 알고리즘에 대하여 간략히 설명하기로 한다.

문자열(string)이란 문자 집합 Σ에서 0개 이상의 문자들이 연결된 형태를 말하고, 이 문자열들이 속한 집합을 Σ*라 표기한다. 문자열 A의 길이를 |A|로 나타내며 공백문자열은 λ로 나타낸다. 이때, λ의 길이 |λ|는 0이다. 문자열 A의 i번째 문자를 A[i]로 나타낸다. A의 i번째 문자부터 j번째 문자까지의 연결(concatenation)을 A[i..j]로 나타내고 이를 A의 부분문자열(substring)이라고 한다. 문자열 A가 문자열 B의 부분문자열일 때 B는 A의 상위문자열(superstring)이라 하고 A

B로 표시한다. 반대로, 문자열 A가 문자열 B의 부분문자열이 아닐 때 A

B로 표기한다. 예를 들어, bcd

abcde이고, cdef

abcde이다. 문자열 A에서 i≤|A|일 때 A[1..i]를 A의 접두사(prefix)라 하고, i<|A|일 때 A[1..i]를 A의 진접두사(proper prefix)라 한다. 유사하게 i≥1일 때 A[i..|A|]를 A의 접미사(suffix)라 하고, i>1일 때 A[i..|A|]를 A의 진접미사(proper suffix)라 한다. 편의상 공백문자열 λ는 모든 문자열의 접두사이며 접미사로 정의한다. 예를 들어, A=abcd일 때 A[3]=c이고, A[1..2]=ab이다. A의 접두사는 {λ, a, ab, abc, abcd}이고 진접두사는 {λ, a, ab, abc}이다. 유사하게 A의 접미사는 {λ, abcd, bcd, cd, d}이고 진접미사는 {λ, bcd, cd, d }이다.

상수크기의 문자 집합 Σ에 대한 문자열 집합 F={f₁, f₂, ..., f_n}가 주어졌을 때, F의 모든 공통비상위문자열(CNSS)들의 집합을 CNSS_F라 한다. 즉, CNSS_F={A|A∈Σ*이고, f_i

A, 1≤i≤n}이다. 이때, 각 f_i는 F의 CNSS가 포함하지 않아야 할 문자열이므로 금지문자열이라 부르도록 한다. 그리고, F의 모든 문자열의 길이의 합을 ?F?으로 표기한다.

일반화를 위해 F는 몇 가지 조건을 만족한다고 가정한다. 먼저, F는 공백문자열을 포함하지 않고, j≠i일 때 f_i

f_j이다. 또한, 각 σ(∈Σ)는 F의 원소가 아니며 모든 σ(∈Σ)에 대해, σ^k(k≥2)가 F에 포함된다.

최장공통비상위문자열 문제의 정의는 다음과 같다.

문제 1. 최장공통비상위문자열 문제

- 입력: 상수크기의 문자 집합 Σ에 대한 금지문자열 집합 F={f₁, f₂, ..., f_n}.

- 출력: CNSS_F에서 유한 길이의 LCNSS_F의 존재 여부. 만약 존재할 경우 LCNSS_F를 출력.

접두사 기반의 그래프 모델을 이용하여 LCNSS문제를 해결하는 알고리즘은 다음과 같다. 먼저 F의 문자열들의 접두사를 이용한 유향그래프 G_F=(V, E)를 정의하고 이를 이용하여 CNSS_F를 모델링 한다. 도 1은 F={aaa, baa, bab, bbb}에 대한 그래프 G_F를 도시한 것이다.

G_F의 정점집합과 간선집합은 다음과 같이 정의된다. 먼저, 정점집합 V는 F의 진접두사 집합을 P={p₀, ..., p_m}라 할 때, F∪P의 문자열들에 대응되는 정점들로 구성된다. F∪P에서 각 금지문자열 f_i(1≤i≤n)는 모든 정점 $에 대응시키고, 각 진접두사 p_j(0≤j≤m)에 대해 정점 v_j를 대응시킨다. F∪P의 원소(문자열) s에 대응되는 정점을 ver(s)라 표기하자. 그리고, p_j에 대해 p_j=str(v_j)로 표기한다. 특별히 혼동되지 않는 한 앞으로 정점 v가 나타내는 문자열과 문자열 A의 연결 str(v)A를 편의상 단순히 v

A로 표기하기로 한다.

간선집합 E를 정의하기 위해 다음의 함수들을 이용한다. 먼저, 문자열 A∈Σ*가 주어졌을 때, LS(A)는 A의 접미사 중 F∪P에 속하는 가장 긴 문자열을 나타낸다. LS(A)에 대응되는 ver(LS(A))는 편의상 LSV(A)로 축약하여 사용한다. 다음으로 모든 v∈V, x∈Σ에 대해 δ(v,x)는 다음과 같이 정의된다.

이때, E는 하나의 간선이 연결하는 두 정점 v_i, v_j와 문자 x의 쌍의 집합이며 다음과 같이 나타낼 수 있다.

위와 같이 G_F를 정의한 후 G_F에서 정점 $ 및 $와 연결된 간선들을 삭제하여 도 2와 같이 그래프 G_F'를 생성한다. 생성된 G_F'에서의 경로를 따라가며 간선들의 문자들을 차례로 연결하여 생성한 문자열은 F의 CNSS임이 증명되었고, 따라서 G_F에서 최장경로를 찾아 문자열을 생성하면 LCNSS임을 알 수 있다. 다만, 생성된 그래프에서 사이클(cycle)이 존재할 경우 LCNSS는 존재하지 않는다. 하지만, 사이클이 존재하지 않을 경우 최장경로는 O(|V|+|E|) 시간에 찾을 수 있으므로 이 경우 LCNSS 문제는 O(|V|+|E|) 시간에 해결이 가능하다.

LCNSS 문제의 접두사 기반 그래프 모델을 순차알고리즘으로 구현하였을 때 소요되는 시간의 비율은 다음과 같다. 도 3은 |F|=300, |f_i|=2, ?F?=600, |Σ|=26일 때, 정점 개수는 360이고, LCNSS 계산에 성공한 케이스이고, 도 4는 |F|=1,000, |f_i|=100, ?F?=100,000, |Σ|=26일 때, 정점 개수는 97,600이고, LCNSS 계산에 성공한 케이스이다. 도 3과 도 4에서 알 수 있듯이 ?F?이 커질수록 생성되는 그래프의 정점의 수가 많아지고, 정점이 많아질수록 그래프 생성에 소요되는 시간이 증가한다. 또한 그래프의 크기가 커질수록 그래프를 순회함으로써 계산되는 LCNSS의 계산 시간 역시 증가한다. 하지만 그래프 모델의 생성에 소요되는 시간의 증가율이 LCNSS 계산에 소요되는 시간의 증가율 보다 크기 때문에 ?F?이 커질수록 LCNSS를 구하는 전체의 시간에서 그래프 생성에 소요되는 시간의 비율이 커지게 된다. 도 5는 |F|=50,000, |f_i|=10, ?F?=500,000, |Σ|=26일 때, 정점 개수는 364,400이고, LCNSS 계산에 성공한 케이스이다. 5와 같이 LCNSS가 존재하지 않을 경우에는 LCNSS 계산에 시간을 거의 사용하지 않는 경우도 존재한다. 각 실험 결과, LCNSS 문제를 해결하기 위해 접두사 기반의 그래프 모델을 이용할 경우, 실제 구현에서 그래프 모델 생성에 많은 시간이 소요됨을 확인할 수 있다.

그래프 모델 생성 알고리즘을 구체적으로 설명하면 다음과 같다.

본 발명의 실시예들은 접두사 그래프 모델을 이용하여 LCNSS 문제를 해결하는 알고리즘에서 그래프 모델링 부분을 병렬로 구현하는 방법에 관한 것이다. 특히, 본 발명의 일실시예에 따른 최장공통비상위문자열 그래프 모델의 병렬 생성 방법은 컴퓨터보안 분야에서 패킷 내의 악성패턴(즉, 금지문자열)을 검출하는 침입탐지시스템, 또는 특정 DNA 세그먼트(segment)를 분석하는 DNA 분석 시스템 등에 적용될 수 있다.

먼저, 접두사 기반의 그래프 모델은 아호 코라식 오토마타(Aho-Corasick Automata)를 이용하여 생성할 수 있다. 오토마타의 시작 정점을 λ라 표기하고, 정점 r에서 문자 σ에 대한 정점 s로의 goto함수를 g(r,σ)=s로 표기한다. 또한, 정점 λ에서부터 임의의 정점 r까지의 길이를 깊이라 부른다.

일 예인 CRCW(Concurrent Read Concurrent Write) PRAM(Parallel Random Access Machine) 모델에서 아호 코라식 오토마타를 생성하기 위한 알고리즘의 개략적인 구성은 다음과 같다.

1. 각 프로세서에 문자열 집합 F의 각 원소들을 대응시킨다.

2. 정점 r에서 s로의 goto함수 g(r,σ)=s가 존재한다면, s의 깊이는 d+1이고, 이 정점은 길이가 d+1인 접두사를 갖는 문자열에 해당하는 프로세서들 중 하나가 생성한다.

3. 정점 생성이 완료된 후 정점 λ에서부터 각 정점마다 실패함수를 생성한다. 이때 깊이가 같은 정점들은 동시에 실패함수가 생성된다.

집합 F의 크기를 n이라 하고, F의 원소 중 가장 긴 원소의 길이를

라 할 때, 위 알고리즘은 n개의 프로세서를 사용하여 O(

)의 시간에 문제를 해결할 수 있다.

한편, CUDA(Compute Unified Device Architecture)는 CRCW PRAM 모델이 아니므로, 위의 2번 단계에서 어떤 프로세서가 정점 s를 생성할지 결정하는 문제를 해결해야 한다. 이를 위해 문자열 집합 F를 병렬기수정렬(parallel radixsort)을 이용하여 정렬하여 알고리즘을 진행한다. 본 실시예에서, 문자열 집합 F를 병렬기수정렬 형태로 정렬한다는 것은 문자열 집합 F 내의 문자열들을 n번째 위치의 문자 종류 별로 정렬하여 n번째 위치의 문자 종류 별 블록으로 분할하는 것(이하, '블록 분할 과정'이라 함)을 의미한다. 이때, n을 1부터 N까지 순차적으로 증가시키면서 분할된 각 블록 내의 문자열에 대하여 상기한 블록 분할 과정을 반복하게 된다. 여기서, n과 N은 정수에 해당되며, 특히 N은 문자열 집합 내의 문자열 중 문자의 수가 가장 많은 문자열의 문자 수일 수 있다.

예를 들어, Σ={a,b,c}일 때 정렬의 진행은 도 6과 같이 간략하게 도식화 할 수 있다. 단계1에서 문자열들이 첫 번째 위치의 문자에 대해 정렬되어 블록별로 분할되고, 단계2에서 두 번째 위치의 문자에 대해 각 블록별로 정렬되어 분할된다. 단계는

만큼 진행되며, 각 단계 i가 종료될 때 마다 접두사 길이 i만큼에 해당하는 정점의 생성이 완료된다(도 7 참조). 단, 도 7의 정점에 표기된 번호는 정점을 가리키기 위함이지, 정점의 생성순서를 의미하는 것은 아니다.

단계 1에서 블록별로 분할이 완료되었다면, 각 블록에 속한 프로세서들 중 블록에 가장 먼저 기록된 프로세서가 정점들을 생성하도록 한다. 예를 들면, 단계 1에서 문자 a에 의해 분할된 블록에서 가장 먼저 기록된 프로세서가 도 7의 1번 정점을 생성한다. CRCW PRAM 모델에서는 O(

)시간에 모든 정점의 생성이 완료되지만, CUDA에서는 더 많은 시간이 필요하다.

아호 코라식 오토마타의 실패함수를 생성하는 과정은 CRCW PRAM 모델에서의 진행을 따른다. 이 과정은 최대 O(

)의 시간이 걸림이 증명되어 있다. 이후, 완성된 아호 코라식 오토마타를 λ로부터 병렬적으로 한번 순회하여 O(

) 시간에 결정적 유한오토마타로 변환하고(G_F 생성), 이를 G_F'으로 변환함으로 알고리즘은 종료된다.

실험 환경은 다음과 같다. CPU는 Intel Core i7 860, RAM은 4GB, 그래픽카드는 nVidia GeForce GTS 450 1GB, OS는 Windows 7을 이용하였다. |Σ|는 26으로 고정시키고 실험을 진행하였다. 금지문자열 집합 F에 속한 문자열의 길이를 10, 20으로 정한 후 F의 크기를 변화시키며 단일코어프로세서를 이용하였을 때의 그래프 모델의 생성 시간과 다중코어프로세서를 이용하였을 때의 그래프 모델의 생성 시간을 비교하였다.

실험 결과는 다음과 같다. 도 8은|f_i|=10일 때, |F|를 변화시키며 시간을 측정한 결과이다. 전체적으로 1.2배에서 4.5배의 성능 향상을 얻을 수 있었으며, |F|=25,000 부근에서 가장 높은 효율을 보였다. 도 9는 |f_i|=20일 때, |F|를 변화시키며 시간을 측정한 결과이다. 전체적으로 1.9배에서 6.6배의 성능 향상을 얻을 수 있었으며, 역시 |F|=25,000 부근에서 가장 높은 효율을 보였다. 도 8과 도 9로써 |f_i|의 크기가 커질수록 더 많은 시간이 필요함을 알 수 있고, 따라서 LCNSS 문제를 해결하는 순차알고리즘에서와 같이 ?F?의 크기에 비례하여 시간이 소요되지만 증가율이 매우 낮음을 확인할 수 있었다.

다음으로, 표 1 에서 그래픽카드의 전역 메모리(global memory)를 사용하였을 경우와 공유 메모리(shared memory)를 명시적으로 사용하였을 경우에 대해 성능을 비교하여 나타내었다. 이 때 |f_i|=20으로 고정하고 실험을 하였다. ?F?=10,000 에서는 오히려 1.40%의 성능 하락이 나타났으나, ?F?이 커질수록 점점 성능이 향상되었고, ?F?=30,000 이후 실제 수행시간이 빨라짐을 확인하였다. 성능 향상 수치는 점차적으로 증가하여 마지막 테스트인 ?F?=500,000 일 때 4.48%의 성능 향상을 확인할 수 있었다.

이와 같이, 본 발명의 실시예에 따르면 기존의 LCNSS 문제를 해결하는 접두사 그래프 모델링의 순차알고리즘을 nVidia CUDA를 이용하여 병렬로 구현함으로써, GPU를 이용할 경우 문제해결 성능이 향상되며, 정보의 양이 늘어날수록 전역 메모리만 사용하였을 때보다 공유 메모리를 명시적으로 사용할 때 성능이 더욱 향상될 수 있다.

본 발명의 실시예에 따른 방법들은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 또한, 상술한 파일 시스템은 컴퓨터 판독이 가능한 기록 매체에 기록될 수 있다.

이상과 같이 본 발명은 비록 한정된 실시예와 도면에 의해 설명되었으나, 본 발명은 상기의 실시예에 한정되는 것은 아니며, 본 발명이 속하는 분야에서 통상의 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형이 가능하다.

그러므로, 본 발명의 범위는 설명된 실시예에 국한되어 정해져서는 아니 되며, 후술하는 특허청구범위뿐 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.

Claims (6)

1. 삭제
2. 문자열 집합에서 가장 긴 문자열에 해당되는 최장공통비상위문자열(Longest Common Non-Superstring)을 검색하기 위하여 상기 문자열 집합에 대한 그래프 모델을 생성하는 방법에 있어서,
   상기 문자열 집합에 대하여 각 문자열의 접두사(prefix)를 기준으로 접두사 그래프를 생성하는 단계
   를 포함하고,
   상기 접두사 그래프를 생성하는 단계는,
   CUDA(Compute Unified Device Architecture)를 이용하여 상기 문자열 집합에 대한 접두사 그래프를 생성하는 것으로,
   상기 문자열 집합 내의 문자열들을 병렬기수정렬(parallel radix sort) 형태로 정렬하는 단계; 및
   상기 병렬기수정렬에 대응하여 상기 접두사 그래프의 정점 집합을 생성하는 단계
   를 포함하는 최장공통비상위문자열 그래프 모델의 병렬 생성 방법.
3. 제2항에 있어서,
   상기 문자열 집합 내의 문자열들을 병렬기수정렬 형태로 정렬하는 단계는,
   상기 문자열들을 n번째 위치의 문자 종류 별로 정렬하여 상기 n번째 위치의 문자 종류 별 블록으로 분할하는 (1) 단계
   를 포함하는 최장공통비상위문자열 그래프 모델의 병렬 생성 방법.
4. 제3항에 있어서,
   상기 문자열 집합 내의 문자열들을 병렬기수정렬 형태로 정렬하는 단계는,
   상기 n이 1부터 N까지 순차적으로 증가하면서 상기 분할된 각 블록 내의 문자열에 대하여 상기 (1) 단계를 반복하는 (2) 단계
   를 더 포함하고,
   상기 N은 상기 문자열 집합 내의 문자열 중 문자의 수가 가장 많은 문자열의 문자 수인 것
   을 특징으로 하는 최장공통비상위문자열 그래프 모델의 병렬 생성 방법.
5. 제3항에 있어서,
   상기 병렬기수정렬에 대응하여 상기 접두사 그래프의 정점 집합을 생성하는 단계는,
   상기 분할된 각 블록 내의 문자열에 대응되는 정점을 생성하는 것
   을 특징으로 하는 최장공통비상위문자열 그래프 모델의 병렬 생성 방법.
6. 제3항에 있어서,
   상기 병렬기수정렬에 대응하여 상기 접두사 그래프의 정점 집합을 생성하는 단계는,
   아호 코라식 오토마타(Aho-Corasick Automata)에 의한 각 프로세서에 상기 문자열 집합 내의 문자열 각각을 대응시키고, 상기 분할된 각 블록 내의 문자열에 대응되는 프로세서 중 해당 블록에 가장 먼저 기록된 프로세서가 정점을 생성하는 것
   을 특징으로 하는 최장공통비상위문자열 그래프 모델의 병렬 생성 방법.

Images