Cited 0 time in webofscience Cited 0 time in scopus

GStream: A Graph Streaming Processing Method for Large-scale Graphs on GPUs

Title
GStream: A Graph Streaming Processing Method for Large-scale Graphs on GPUs
Translated Title
GStream: GPU 에서 대규모 그래프 처리를 위한 스트리밍 방법
Authors
Seo, Hyun Seok
DGIST Authors
Seo, Hyun Seok; Kim, Min Soo; Choe, Seung Ho
Advisor(s)
Kim, Min Soo
Co-Advisor(s)
Choe, Seung Ho
Issue Date
2015
Available Date
2015-01-12
Degree Date
2015. 2
Type
Thesis
Keywords
Graph processingLarge-scaleGPUStream그래프 처리대규모스트림
Abstract
Fast processing graph algorithms for large-scale graphs becomes increasingly important as graphs become popular in a wide range of applications and the sizes of graphs are growing rapidly. Due to the relatively low cost and high computational power of GPUs, there have been many attempts to process graph applications by exploiting the massive amount of paral-lelism of GPUs. However, most of the existing methods fail to process large-scale graphs that do not fit in GPU device memory, mainly due to the irregular structure and the complex graph processing algorithms. Although the state-of-the-art method TOTEM can process large-scale graphs by partitioning a graph into two parts: the main memory part processed by CPUs and the device memory part processed by GPUs, it still has several fundamental problems such as a large amount of synchronization overhead and lack of scalability. We propose a fast and scalable parallel processing method GStream that processes large-scale graphs (e.g., billion vertices) beyond the capacity of GPU device memory very efficiently by exploiting the concept of so-called nested-loop join operation and the asynchronous GPU streams. It exploits multiple GPUs by uniformly distributing the workload among GPUs and also ex-ploits available GPU device memory by caching streaming graph data. GStream is the first scalable method in terms of both the data size and the number of GPUs, to the best of our knowledge. Extensive experimental results show that GStream consistently and significantly outperforms TOTEM in terms of absolute performance, scalability, and graph size to pro-cess, for both synthetic graphs and real graphs. ⓒ 2015 DGIST
Table Of Contents
Ⅰ. INTRODUCTION 1-- Ⅱ. PREMINARIES 5-- Ⅲ. GSTREAM METHOD 6-- 3.1 Basic concept of GStream 6-- 3.2 Streaming topology data 8-- 3.3 Exploiting Multiple GPUs 12-- 3.4 Caching topology data 13-- 3.5 Framework of GStream 14-- 3.6 Cost model of GStream 16-- Ⅳ. OTHER TECHNIQUES 18-- 4.1 Fine-granular parallel processing in GStream 18-- 4.2 Extending to a disk-based method 18-- Ⅴ. PERFORMANCE EVALUATION 20-- 5.1 Experimental setup 20-- 5.2 Comparison with TOTEM 21-- 5.3 Characteristics of GStream 24-- Ⅵ. RELATED WORK 27-- VII. CONCLUSIONS 29
URI
http://dgist.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000001914717
http://hdl.handle.net/20.500.11750/1387
DOI
10.22677/thesis.1914717
Degree
Master
Department
Information and Communication Engineering
University
DGIST
Files:
Collection:
Information and Communication EngineeringThesesMaster


qrcode mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE