디지털 라이브러리[ 검색결과 ]
멀티테넌트 GPU 환경에서 메모리 자원을 고려한 선제적 동시-스케줄링
http://doi.org/10.5626/JOK.2024.51.3.210
멀티테넌트 GPU에서는 높은 이용량과 처리량을 위해 여러 응용을 하나의 GPU에 동시-스케줄 한다. 이때 메모리 부족 에러가 발생할 수 있다. 선행 연구에서는 이를 방지하기 위해 GPU의 메모리가 수용할 수 있는 만큼 태스크를 스케줄 하는 방법을 사용했다. 본 연구에서는 메모리 부족 에러를 방지하면서도, 하나의 GPU에 더 많은 태스크를 동시-스케줄 할 수 있는 기법을 제안한다. 태스크 내 사용이 끝난 변수들을 즉시 할당 해제하여 GPU의 여유 메모리를 선제적으로 확보하고, GPU가 더 많은 태스크를 동시-스케줄 가능하게 한다. 또한, 통합 메모리 상에서 메모리 초과 사용을 허용하여 GPU의 전체 메모리를 넘는 수준까지 태스크를 스케줄링 할 수 있도록 한다. 앞서 언급한 두 가지 기법을 통해 제출된 응용 전체에 대한 실행 완료 시간이 앞당겨졌고 선행 연구대비 각각 7.3%, 1.9%의 성능 향상을 보였다.
정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘
http://doi.org/10.5626/JOK.2017.44.8.760
반복적인 문자열은 데이터압축, 생물정보학 등 여러 분야에서 연구되어 왔다. 본 논문에서는 음악서열이나 주가지수와 같이 정수로 표현될 수 있는 문자열에 대한 반복에 대해 연구한다. 최근 정수문자열의 최소 δ-근사주기와 최소 γ-근사주기를 찾는 문제들이 소개되었고, 문자열의 길이가 n일 때, 두 문제를 각각 O(n²)시간에 해결하는 알고리즘들이 제시되었다. 본 논문에서는 위의 두 문제에 대해 각각 O(n²)개의 스레드를 이용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 실험결과, n = 10,000일 때, 본 논문에서 제시하는 병렬알고리즘은 순차알고리즘보다 최소 δ-근사주기를 계산하는데 약 19.7배, 최소 γ-근사주기를 계산하는데 약 40.08배 빠른 수행시간을 보였다.
다중 GPU를 이용한 R-tree의 병렬 범위 질의 처리 기법
다차원의 데이터를 색인하기 위해 처음 R-tree가 제안된 이후 다양한 방법으로 질의 성능을 향상시키기 위한 많은 연구가 이루어졌다. 그 가운데 다중프로세서를 이용한 병렬 기법으로 질의 성능을 향상시킨 GPU기반의 R-tree가 제안되었다. 하지만 GPU가 갖는 물리적 메모리 크기의 한계가 있어 데이터의 크기가 제한된다. 이에 본 논문에서는 다중 GPU를 이용한 R-tree의 병렬 범위 질의 처리 기법인 MGR-tree 제안한다. 제안하는 MGR-tree는 기존의 GPU기반의 R-tree 질의 처리 기법을 기반으로 하여 다중 GPU에서 질의 처리를 가능하게 R-tree의 노드를 다중 GPU상에 분할하여 분산 처리 하였다. 실험을 통해 MGR-tree는 GPU에서의 선형검색에 비해 최대 9.1배, GPU기반 R-tree에 비해 최대 1.6배 가량의 성능이 향상된 것을 확인하였다.
환형문자열에 대한 대표문자열을 찾는 병렬 알고리즘
대표문자열 문제는 k 개의 문자열로 구성된 집합 S 가 주어졌을 때 S 를 대표하는 한 문자열인 대표문자열을 찾는 문제이다. 환형문자열은 일반적인 문자열과는 달리 문자열의 첫 글자와 마지막 글자가 연결되어 원 모양을 이루는 문자열이다. 본 논문에서는 먼저 k=3 이고 길이 n인 환형문자열들로 구성된 S에 대해, 거리반경과 거리합을 동시에 고려한 대표문자열 문제를 O(n) 개의 쓰레드를 사용하여 O(｜∑｜nlogn) 시간에 병렬적으로 해결하는 알고리즘을 제시한다. 이때, ∑ 는 각 문자열을 구성하는 문자집합이다. 다음으로 k=4 이고 길이 n인 환형문자열들로 구성된 S 에 대해 거리합 기반 대표문자열 문제를 O(n)개의 쓰레드를 사용하여 O(｜∑｜n²logn) 시간에 병렬적으로 해결하는 알고리즘을 제시한다. 이후 두 문제에 대한 병렬 알고리즘들을 CUDA를 이용하여 구현하고 순차 알고리즘들과의 실행 속도를 비교한 결과를 제시한다.
