Cited 0 time in webofscience Cited 0 time in scopus

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

GStream: A Graph Streaming Processing Method for Large-scale Graphs on GPUs
Translated Title
GStream: GPU 에서 대규모 그래프 처리를 위한 스트리밍 방법
Seo, Hyun Seok
DGIST Authors
Seo, Hyun Seok; Kim, Min Soo; Choe, Seung Ho
Kim, Min Soo
Choe, Seung Ho
Issue Date
Available Date
Degree Date
2015. 2
Graph processingLarge-scaleGPUStream그래프 처리대규모스트림
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
Information and Communication Engineering
Information and Communication EngineeringThesesMaster

qrcode mendeley

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