데이터베이스 연구회지(SIGDB)
Current Result Document :
| 한글제목(Korean Title) |
제한된 메모리를 가진 GPU를 이용한 SSSP 그래프 알고리즘 처리 기법 |
| 영문제목(English Title) |
SSSP Graph Algorithm Processing Scheme using GPU with Limited Memory |
| 저자(Author) |
송상호
이현병
최도진
복경수
유재수
Sangho Song
Hyeonbyeong Lee
Dojin Choi
Kyongsoo Bok
Jaesoo Yoo
|
| 원문수록처(Citation) |
VOL 37 NO. 03 PP. 0029 ~ 0042 (2021. 12) |
한글내용
(Korean Abstract) |
최근 대용량 그래프를 처리하기 위해 GPU를 이용한 연구가 진행되고 있다. 대용량 그래프를 제한된 메모리를 갖는 GPU에서 효율적으로 처리할 수 없기 때문에 대용량 그래프를 여러 개의 서브그래프로 분할해서 처리해야 한다. 본 논문에서는 GPU 환경에서 효율적인 서브 그래프 분할을 통한 SSSP 그래프 알고리즘 처리 기법을 제안한다. 제안하는 기법은 대용량 그래프 분할 방법과 차등 서브그래프 스케줄링 방법으로 구성된다. 대용량 그래프 분할 방법은 대용량 그래프를 GPU에서 처리할 수 있는 서브 그래프로 효율적으로 어떻게 분할할 것인지를 결정한다. 차등 서브그래프 스케줄링 방법은 서브그래프의 가치를 정량화하여 서브 그래프의 연산량을 추정하고 데이터의 중복 전송을 줄이되 활성 간선의 전송률을 높여 HOST-GPU 전송 시 간을 줄일 수 있도록 한다. 제안하는 기법의 우수성을 보이기 위해 성능평가를 수행한다.
|
영문내용
(English Abstract) |
Recently, Research using GPU has been conducted to process large graph data. Since large graphs cannot be efficiently processed by GPUs with limited memory, they must be divided into multiple subgraphs. In this paper, we propose a SSSP graph algorithm processing scheme on GPU through efficient subgraph partitioning method. The large graph partitioning method determines how to efficiently divide the large graph into subgraphs that can be processed by the GPU. The value-driven subgraph scheduling method quantifies the value of subgraphs to estimate the computational volume of subgraphs. It reduces the duplicate transmission of data, by increasing the transmission rate of active edges to reduce HOST-GPU transmission time. We conduct various performance evaluations in order to show the superiority of the proposed scheme. |
| 키워드(Keyword) |
그래프 분할
서브 그래프 처리
GPU
서브 그래프 스케줄링
Graph partitioning
Subgraph processing
GPU
Subgraph Scheduling
|
| 파일첨부 |
PDF 다운로드
|
