고성능 RDF Join Query 처리를 위한 GPU 기반의 병렬처리 알고리즘 및 Data Representation Parallel algorithm and data representation for high-performance join query processing using GPU
- 주제(키워드) RDF , GPGPU
- 발행기관 아주대학교
- 지도교수 오상윤
- 발행년도 2016
- 학위수여년월 2016. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000021783
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
Semantic Web에 대한 관심이 증가하면서 RDF(The Resource Description Framework)와 RDF 데이터 검색 언어인 SPARQL Query에 대한 관심이 증가하고 있다. SPARQL Query를 처리 하는 방법 중에 하나인 처리 하는 방법 중에 하나인 Join Processing은 병렬 처리를 통해 빠른 Query 처리가 가능하고 대용량 데이터에 대한 Query 처리가 Graph Explorations에 비해 비교적 쉽다는 장점을 가지고 있다. 그러나 처리할 데이터가 커질수록 Join 과정에서 많은 연산이 요구되지만 현재의 RDF 시스템의 Join Processing은 싱글 머신에서 이루어져 처리 속도 향상에 한계를 가지게 된다. 처리 속도의 향상 한계를 극복하기 위해 극복하기 위해 GPGPU 적용이 연구되었지만, GPU 활용에 있어 GPU의 메모리 공간과 동적 할당 문제로 인해 실제 GPU를 통해 RDF 데이터를 처리하는 시스템에 적용에는 어려움을 가진다. 이에 본 논문에서는 기존의 Join Processing에 대한 GPU 적용의 제한 사항에 문제점을 파악하고 이를 해결하기 위한 GPU 기반의 Join Processing과 압축된 3차원의 좌표 형식의 RDF Representation 제안하였다. 제안한 Join Processing 방법은 Join Processing에 있어 Computation이 많이 필요한 RDF 데이터에 대한 처리를 GPU를 통해 진행하여 높은 처리 성능 향상을 보인다. 또한, 압축된 3차원의 좌표 형식의 RDF Representation을 통해 Query 처리에 필요한 데이터를 최소화하여 Query 처리에 과정에서 적은 메모리 공간을 활용하고, CPU와 GPU 간의 추가적인 데이터 전송을 방지하여 Query 처리에 있어 GPU의 메모리 공간과 데이터 전송 문제를 효율적으로 처리하였다. 제안한 시스템을 평가하기 위해 RDF 데이터인 Uniport, LUBM를 활용하여 CPU 기반의 RDF 처리 시스템인 RDF-3x, BitMat, TripleBit과 SPARQL Query 처리 시간과 Query 처리를 위한 메모리 사용량을 측정하였다. 실험 결과 제안한 Join Processing은 대용량의 데이터를 요구하는 대부분의 Query에 대해 제안 알고리즘과 GPU 적용을 통해, 기존 CPU만을 사용하는 시스템 대비 1.5 ~ 60배의 빠른 처리 속도 향상을 보였으며 메모리 사용량에 있어서도 2배에서 18배까지의 적은 메모리 사용량을 보였다. 이 결과를 통해 대용량 RDF 데이터를 요구하는 Query에 있어 제안한 Join Processing과 RDF Representation은 효과적인 처리가 가능한 것으로 판단된다.
more목차
1. 서 론
1.가. RDF & SPARQL
1.나. 연구범위 및 논문 구성
2. 관련 연구
2.가. SPARQL Query 처리 방법
2.가.1) Graph Explorations
2.가.2) Join
2.나. Join Processing에 대한 GPU 활용 및 제한사항
2.나.1) GPU 활용 사례 및 제한 사항
2.나.2) Intermediate Result
2.다. Join 기반 RDF 처리 시스템의 RDF Representation
3. GPU 특성을 고려한 데이터 구조와 Join 알고리즘
3.가. 제안한 RDF Representation
3.나. 제안한 Join Processing
3.나.1) Grouping
3.나.2) Pruning
3.나.3) Merging
3.나.3).가) Intermediate Result 내의 Info 배열
3.나.3).나) Intermediate Result 내의 Value 배열
3.나.3).4) Group 간의 Pruning
3.나.3).5) Preparing Result
4. 성능 평가
4.가. 성능 평가 환경
4.나. 성능 평가 검사
5. 결론 및 향후 과제
