대표어
한국학술지인용색인(NRF)
권호기사보기
| 기사명 | 저자명 | 페이지 | 원문 | 기사목차 |
|---|
국회도서관 홈으로
정보검색
소장정보 검색
결과 내 검색
동의어 포함
목차보기
목차
GPU를 이용한 R-tree에서의 범위 질의의 병렬 처리 / 유보선 ; 김현덕 ; 최원익 ; 권동섭 1
요약 1
ABSTRACT 1
1. 서론 2
2. GPU 2
2.1. GPU overhead 2
2.2. R-tree의 GPU 적용 3
3. 관련 연구 4
3.1. R-tree 4
3.2. MXR-tree 4
3.3. MR-tree and MCR-tree 5
3.4. In-Memory Grid File 5
3.5. GPU-CSSTree 5
4. 제안 기법 6
4.1. GPU의 적용 6
4.2. Update 전략 8
5. 실험 8
6. 결론 및 향후 연구 과제 10
참고문헌 10
[저자소개] 12
초록보기
R-tree는 데이터베이스 시스템에서 가장 많이 사용되는 색인 구조로 다차원의 데이터를 관리하는데 매우 효율적이다. 하지만 데이터베이스 시스템이 처리해야 하는 데이터의 용량이 증가함에 따라, 기존의 R-tree에서의 범위 질의의 처리는 디스크의 접근 지연 등의 이유로 인하여 수행 시간이 증가하게 되었다. 이러한 문제들을 해결하기 위하여 버퍼를 사용하거나 혹은 다수의 디스크와 프로세서를 사용하여 병렬로 질의를 수행하고자 하는 많은 연구들이 진행되었다. 이러한 연구들의 일환으로 최근 Graphics Processing Unit (GPU)을 이용한 병렬화 기법들에 대한 연구들이 진행되고 있다. 이러한 GPU의 적용을 통한 병렬화는 계산 속도의 증가와 디스크 접근 횟수의 감소를 통하여 수행 속도의 개선을 가능하게 하지만 GPU와 CPU사이의 메모리 교환 및 GPU 메모리의 접근 지연 등에 의한 오버헤드를 발생시킨다. 본 논문에서는 이러한 오버헤드를 해결하고 효과적으로 GPU를 적용하기 위하여, GPU를 버퍼로 사용하여 범위 질의를 병렬화하는 기법을 제안하였다. 버퍼 알고리즘을 통하여 메모리 교환 횟수를 줄이고, 동시 접근 가능한 메모리의 용량을 증가시켜 메모리의 접근 지연을 최소화 할 수 있었다. 제안 기법과 기존의 인덱스의 비교 실험에서 최대의 경우 5배 정도의 성능이 개선되는 것을 확인 할 수 있었다.
R-trees are widely used in various areas such as geographical information systems, CAD systems and spatial databases in order to efficiently index multi-dimensional data. As data sets used in these areas grow in size and complexity, however, range query operations on R-tree are needed to be further faster to meet the area-specific constraints. To address this problem, there have been various research efforts to develop strategies for acceleration query processing on R-tree by using the buffer mechanism or parallelizing the query processing on R-tree through multiple disks and processors. As a part of the strategies, approaches which parallelize query processing on R-tree through Graphics Processor Units (GPUs) have been explored. The use of GPUs may guarantee improved performances resulting from faster calculations and reduced disk accesses but may cause additional overhead costs caused by high memory access latencies and low data exchange rate between GPUs and the CPU. In this paper, to address the overhead problems and to adapt GPUs efficiently, we propose a novel approach which uses a GPU as a buffer to parallelize query processing on R-tree. The use of buffer algorithm can give improved performance by reducing the number of disk access and maximizing coalesced memory access resulting in minimizing GPU memory access latencies. Through the extensive performance studies, we observed that the proposed approach achieved up to 5 times higher query performance than the original CPU-based R-trees.
R-trees are widely used in various areas such as geographical information systems, CAD systems and spatial databases in order to efficiently index multi-dimensional data. As data sets used in these areas grow in size and complexity, however, range query operations on R-tree are needed to be further faster to meet the area-specific constraints. To address this problem, there have been various research efforts to develop strategies for acceleration query processing on R-tree by using the buffer mechanism or parallelizing the query processing on R-tree through multiple disks and processors. As a part of the strategies, approaches which parallelize query processing on R-tree through Graphics Processor Units (GPUs) have been explored. The use of GPUs may guarantee improved performances resulting from faster calculations and reduced disk accesses but may cause additional overhead costs caused by high memory access latencies and low data exchange rate between GPUs and the CPU. In this paper, to address the overhead problems and to adapt GPUs efficiently, we propose a novel approach which uses a GPU as a buffer to parallelize query processing on R-tree. The use of buffer algorithm can give improved performance by reducing the number of disk access and maximizing coalesced memory access resulting in minimizing GPU memory access latencies. Through the extensive performance studies, we observed that the proposed approach achieved up to 5 times higher query performance than the original CPU-based R-trees.
권호기사
참고문헌 (16건) : 자료제공( 네이버학술정보 )
| 번호 | 참고문헌 | 국회도서관 소장유무 |
|---|---|---|
| 1 | A Survey of General‐Purpose Computation on Graphics Hardware  |
미소장 |
| 2 | CUDA programming Guide 2.2. | 미소장 |
| 3 | R-trees |
미소장 |
| 4 | Parallel R-trees |
미소장 |
| 5 | Xiaodong Fu, Dingxing Wang, Weimin Zheng, and Meiming Sheng, “GPR-Tree: A Global Parallel Index Structure for Multiattribute Declustering on Cluster of Workstations,” Proc. Of APDC, pp.300-306, 1997. | 미소장 |
| 6 | Efficient parallel processing of range queries through replicated declustering |
미소장 |
| 7 | N. Koudas, C. Faloutsos, and I. Kamel, “Declustering Spatial Databases on A Multi- Computer Archetecture,” Proc. Of EDBT, 1996. | 미소장 |
| 8 | B. Schnitzer and Scott T. Leutenegger, “Master-Client R-Trees: A New Parallel R-Tree Architecture,” Scientific and Statistical Database Management, pp.68-77, 1999. | 미소장 |
| 9 | Shuhua Lai, Fenghua Zhu, and Yongqiang Sun, “A Design of Parallel R-tree on Cluster of Workstations,” Proc. Of IWDNIS, pp. 119-133, 2000. | 미소장 |
| 10 | Botao Wang, Hiroyuki Horinokuchi, Junihiko Kaneko, and Akifui Makinouchi, “Parallel R-tree Search Algorithm on DSVM. Database Systems for Advanced Applications,” Proc. Of SICDSAA, Hsinchu, Taiwan 1999. | 미소장 |
| 11 | J. Nievergelt, H. Hinterberger, and K. Sevcik, “The Grid File: An Adaptable, Symmetric Multikey File Structure,” Proc. Of 3rd ECI Conf., Number 123 in LNCS Springer-Verlag, pp.236-251, 1981. | 미소장 |
| 12 | K. Yang, B. He, R. Fang, M. Lu, N. Govindaraju, Q. Luo, P. Sander, and J. Shi, “In-memory Grid Files on Graphics ProcesSors,” Proc. Of the 3rd international workshop on Data management on new hardware, 2007. | 미소장 |
| 13 | Jun Rao and Kenneth A. Ross, “Cache Conscious Indexing for Decision-Support in Main Memory,” Proc. Of VLDB, pp.78-89, 1999. | 미소장 |
| 14 | R. Fang, B. He, M. Lu, K. Yang, N. K. Govindaraju, Q. Luo, and P. V. Sander. “Gpuqp: Query Co-processing Using Graphics Processors,” Proc. Of the ACM SIGMOD, pp. 1061-1063, 2007. | 미소장 |
| 15 | Performance Analysis and Enhancing Techniques of Kd-Tree Traversal Methods on GPU | 소장 |
| 16 | GPU based Maximum Intensity Projection using clipping plane Re-rendering method | 소장 |
MARC 보기
오류 데이터 정정요청
*표시는 필수 입력사항입니다.
알림톡 발송
| 전화번호 |
|---|
개인정보 수정 바로가기
연속간행물 권호 선택
우편복사 안내
- ◾ 도서관을 방문하지 못할 경우 인터넷, 팩스 등으로 자료 복사를 신청하고, 복사물을 우편·팩스 등으로 제공받는 서비스
- ◾ 대상자료: 일반도서, 연속간행물 및 학위논문
- ※ 고서, 고잡지, 훼손될 우려가 있는 자료, 마이크로폼 자료 및 신문 등 제외
- ◾ 신청 책수: 1인 5책 이하(1일 기준)
- ◾ 신청 절차: 자료 검색 → 우편복사 목록담기 → 복사 범위 입력 → 우편복사 주문서 입력 → 접수 및 확인
- ※ 저작권법에 의거하여 부분 복사(전체 페이지 수의 1/3 범위 이내)만 가능
- ◾ 복사 범위 입력 예시: (연속 페이지) 1-30, (부분 페이지) 25, 30-40
| 번호 | 발행일자 | 권호명 | 제본정보 | 자료실 | 원문 | 신청 페이지 |
|---|
도서위치안내(서울관)
도서위치안내: 정기간행물실(524호) / 서가번호: 국내04
2021년 이전 정기간행물은 온라인 신청(원문 구축 자료는 원문 이용)
0
확인
우편복사 목록담기를 완료하였습니다.
내서재에 담기
새로운 서재
*표시는 필수 입력사항입니다.
저장
저장 되었습니다.