3.1 워크-그룹 및 워크-아이템 할당 최적화

GPU에서 병렬 KMP 알고리즘을 구현하기 위해서는 주어진 텍스트를 분할하여 탐색하는 데이터 병렬처리 기법을 활용한다. 텍스트는 작은 서브-텍스트 단위로 분할되어 각 워크-아이템에 할당이 되고 각 워크-아이템에서 주어진 패턴이 존재하는지를 검색하게 된다. 이 때 텍스트 분할 과정에서 서브-텍스트들 사이에 주어진 패턴이 존재할 경우 중간에 잘리는 경우가 있어 이를 고려하여 처리를 해야 한다⁽⁸⁾. 주어진 텍스트의 마지막 P-1 길이는 새로운 패턴의 탐색을 하지 않고 이전에 시작한 패턴이 일치하여 종료가 되는지 만을 확인하게 된다. 따라서 분할 영역에 P-1 만큼의 길이를 중복하여 추가할당을 하고 이 부분은 이전 패턴의 종료만을 확인하도록 하여 분할 과정에서 발생할 수 있는 패턴의 잘림을 방지할 수가 있다. 이렇게 할당된 워크-아이템은 워크-그룹 단위로 묶여 GPU내의 계산 유닛(Computing Unit)에 할당을 하게 된다. 전체 텍스트에 워크-그룹 및 워크-아이템을 할당하는 방법은 다음 그림. 3과 같다.

KMP 알고리즘의 OpenCL 처리 성능을 최적화하기 위하여, 워크-아이템과 워크-그룹을 GPU내에 프로세싱-엘리멘트(Processing Element: PE)와 계산-유닛에 효율적으로 할당하여야 한다. GPU는 동시에 실행이 가능한 여러 개의 계산-유닛으로 구성이 되어 있으며 각 계산-유닛은 다수의 프로세싱-엘리먼트들로 이루어져 있다. 하나의 워크-아이템은 GPU내에 프로세싱-엘리먼트에 할당이 되어 처리가 된다. 이 때, 프로세싱-엘레먼트에 할당된 하나의 워크-아이템은 각각 하나의 스레드와 같다. 이러한 워크-아이템을 워크-그룹으로 묶어 계산-유닛에 할당을 하게 된다. 이 때, 전체 워크-그룹의 개수를 총 계산-유닛의 배수로 할당하지 않으면 유휴 계산-유닛이 생겨 실행 시 최적으로 동작할 수 없다. 하나의 워크-그룹은 다수의 워크-아이템으로 이루어지므로 워크-아이템은 계산-유닛의 배수로 워크-그룹의 개수가 이루어지도록 묶여서 처리되어야 한다. 하나의 워크-그룹에 할당 가능한 워크-아이템의 개수는 계산 유닛 당 PE의 개수보다 작거나 같아야 한다. 따라서 총 워크-아이템과 워크-그룹은 다음과 같이 할당이 되게 된다.

여기서, W_item는 총 워크-아이템의 개수, W_group은 총 워크-그룹의 개수, W_item/CU는 계산-유닛 당 할당 된 워크-아이템의 개수, PE_CU는 각 계산-유닛 당 PE의 개수, CU_gpu는 GPU내의 총 계산-유닛의 개수를 의미한다. 따라서 최적의 성능을 내기 위해서는 워크-아이템 개수를 GPU내의 총 PE의 개수(PE_gpu=CU_gpu×PE_CU)로 할당하거나 그 배수로 할당함으로써 모든 PE가 같은 작업량을 처리하여 최적으로 동작할 수 있게 만든다⁽⁹⁾. 또한 이때 각 워크-아이템 당 할당되어 검색이 되는 서브-텍스트의 크기는 다음과 같다.

여기서, T는 주어진 텍스트의 길이, P는 검색하는 패턴의 길이, 그리고 T_sub는 각 워크-아이템에 할당되는 서브-텍스트의 길이를 의미한다. 총 텍스트에서 주어진 패턴이 시작할 수 있는 문자의 개수는 T-P+1 이고 이를 워크-아이템에 동등하게 분배(T_part)를 하여야 한다. 분배된 텍스트에 마지막 잘린 부분의 검사를 위하여 P-1 길이만큼을 중복 할당하여 검사를 하게 된다. 이때 하나의 워크-아이템이 처리하게 되는 서브 텍스트의 범위 i는 다음과 같다.

여기서, W_id는 각 워크-아이템의 아이디를 의미하며 그 값은 0 $\le$T_sub$\le$T_item-1 이다. 따라서 OpenCL 기반으로 처리할 경우의 시간 복잡도는 다음과 같이 개선된다.

3.2 CPU-GPU 메모리 계층 구조를 고려한 성능최적화

OpenCL을 이용하여 성능을 최적화하기 위하여서는 CPU- GPU 간의 메모리 계층구조를 이해하여 이를 최적화 하여한다. 일반적으로 OpenCL과 같은 GPGPU 컴퓨팅은 GPU 내의 글로벌 메모리를 통해 CPU와 데이터를 주고받으며 데이터를 처리한다. 따라서 그림. 4와 같이 GPU 내의 메모리 계층구조에 따른 최적화와 CPU-GPU 메모리 간의 이루어지는 데이터 통신의 최적화를 고려하여 전체 성능을 향상시켜야 한다.

GPU 메모리 계층 구조에 따르면 GPU 내에 글로벌 메모리에 접근하는 것은 로컬 메모리와 프라이빗 메모리의 접근 속도보다 약 10배가 느리다⁽⁹⁾. KMP 알고리즘은 패턴과 테스트 간에 반복적인 매칭을 실행하고 실패 때 마다 실패 테이블을 접근해야 한다. 이 과정에서 글로벌 메모리에 계속 접근하게 되고 이는 성능 저하의 원인이 된다. 그러므로 성능을 최적화하기 위해서 워크-아이템들이 글로벌 메모리에 접근하는 횟수를 줄여야 한다. 이를 위해 본 논문에서는 KMP 알고리즘 연산 과정에서 반복적으로 접근이 되는 패턴 그리고 실패 테이블을 로컬 메모리에 복사하여 처리한다. 각 워크-그룹 내 워크-아이템들은 워크-그룹별로 사용가능한 로컬 메모리를 통하여 데이터를 공유한다. 패턴 매칭이 진행되는 동안 로컬 메모리에 있는 패턴과 실패 테이블에 접근하여 글로벌 메모리에 있는 텍스트와 일치하는지의 여부를 검사한다. 그리고 일치하면 글로벌 메모리에 접근하여 전체 일치횟수를 카운팅하는 변수에 값을 써준다. 이를 통해 전체 글로벌 메모리 접근 횟수를 줄이고 성능을 향상시켰다.

KMP 알고리즘에서는 패턴에 비하여 텍스트의 크기는 크다고 할 수 있다. GPU 기반의 병렬 KMP 알고리즘의 전체 실행시간은 매칭을 하는 텍스트가 GPU에 전달되고 연산을 진행한 다음 결과 값을 넘겨받는 시간을 포함한다. 이에 따른 전체 성능은 다음과 같다.

여기서, T는 전체 텍스트의 크기, R은 반환되는 결과의 크기, τ_d는 CPU-GPU 간의 전송 속도(PCIE 속도), 그리고 EX_gpu는 GPU 실행시간을 의미한다. 따라서 모든 텍스트를 GPU에 전달하여 패턴 매칭을 실행하고 결과를 반환 받을 경우 텍스트의 크기가 커지게 되면 CPU-GPU 사이의 통신 시간이 커지게 되어 전체 성능에 영향을 주게 된다. 따라서 GPU 계산에 의하여 단축되는 성능 향상을 극대화하기 위해서는 CPU-GPU 간에 발생하는 전송 오버헤드를 최소화하여야 한다. 이러한 CPU-GPU간의 데이터 전송 오버헤드는 필연적으로 발생하는 것으로 이를 원천적으로 제거하거나 줄일 수는 없고 이를 숨기는 방안을 제안하고자 한다. 본 연구에서는 이를 위하여 GPU에 전달되는 텍스트를 분할하여 전송을 하고 각각 분할된 텍스트에 대한 패턴 매칭을 시행하는 동안 다음 분할될 텍스트를 전달하는 방법으로 CPU- GPU 사이에 계산과 전송을 중첩시키는 방법을 제안한다. 다음 그림. 5는 텍스트를 네 개로 분할하여 처리할 경우 CPU-GPU간에 계산-전송 중첩이 일어나는 과정을 보인다. 한 예로 첫 번째 데이터를 전송하고 패턴 매칭 실행을 하는 동안 두 번째 데이터를 전송한다. 또 두 번째 데이터를 가지고 연산이 진행되는 동안 세 번째 데이터를 전송하고 동시에 첫 번째 데이터를 가지고 연산이 진행된 결과 값을 반환받는 과정을 진행한다. CPU-GPU 전송 중첩을 통한 전체 성능은 다음과 같이 표현할 수 있다.

여기서, N_s는 텍스트가 분할된 스트리밍의 수이고 EX_gpu는 각 텍스트 스트리밍이 GPU에서 매칭 연산이 실행되는 시간을 의미한다. 이와 같이 실행할 경우 전체 패턴 매칭 연산 시간은 텍스트의 크기에 따라 중가하게 되지만 데이터를 전송하고 반환받는 시간은 패턴 매칭 연산시간과 중첩이 되어 숨기므로 전체 실행시간을 줄일 수 있다. 제시한 호스트 CPU에서 GPU의 글로벌 메모리에 데이터를 분할 전송하여 처리하는 방법은 텍스트의 크기가 커서 GPU 글로벌 메모리의 크기를 초과하는 경우에도 바로 적용을 할 수가 있다. 이 경우 전체 텍스트에 대한 패턴 매칭을 하기 위해서는 글로벌 메모리를 넘지 않는 크기나 성능 최적을 위한 텍스트 크기로 분할하여 제시한 중첩처리 방법으로 처리할 수가 있다.