Jianlong Zhong
Abstract
This paper demonstrates Medusa, a programming framework for parallel graph processing on graphics processors (GPUs). Medusa enables developers to leverage the massive parallelism and other hardware features of GPUs by writing sequential C/C++ code for a small set of APIs. This simplifies the implementation of parallel graph processing on the GPU. The runtime system of Medusa automatically executes the user-defined APIs in parallel on the GPU, with a series of graph-centric optimizations based on the architecture features of GPUs. We will demonstrate the steps of developing GPU-based graph processing algorithms with Medusa, and the superior performance of Medusa with both real-world and synthetic datasets.
- GTGraph generator. http://www.cse.psu.edu/~madduri/software/GTgraph/index.html, accessed on Feb 17th, 2013.Google Scholar
- Stanford large network dataset collections. http://snap.stanford.edu/data/index.html, accessed on Feb 17th, 2013.Google Scholar
- J. Berry, B. Hendrickson, S. Kahan, and P. Konecny. Software and algorithms for graph queries on multithreaded architectures. In IPDPS, March 2007.Google Scholar
- J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107-113, 2008. Google Scholar
- P. Harish and P. J. Narayanan. Accelerating large graph algorithms on the GPU using CUDA. In HiPC, 2007. Google Scholar
- B. He, W. Fang, Q. Luo, N. K. Govindaraju, and T. Wang. Mars: a MapReduce framework on graphics processors. In PACT, 2008. Google Scholar
- G. He, H. Feng, C. Li, and H. Chen. Parallel SimRank computation on large graphs with iterative aggregation. In SIGKDD, 2010. Google Scholar
- S. Hong, S. K. Kim, T. Oguntebi, and K. Olukotun. Accelerating CUDA graph algorithms at maximum warp. In PPoPP, 2011. Google Scholar
- J. Lin and M. Schatz. Design patterns for efficient graph algorithms in MapReduce. In MLG, 2010. Google Scholar
- Y. Low and et al. GraphLab: A new parallel framework for machine learning. In UAI, July 2010.Google Scholar
- G. Malewicz and et al. Pregel: A system for large-scale graph processing. In SIGMOD, 2010. Google Scholar
- S. Sengupta, M. Harris, and M. Garland. Efficient parallel scan algorithms for GPUs. NVIDIA, Tech. Rep. NVR-2008-003.Google Scholar
- M. C. Shebanow. Pervasive massively multithreaded GPU processors. In CF, 2009. Google Scholar
- J. Zhong and B. He. GViewer: GPU-accelerated graph visualization and mining. In SocInfo, pages 304-307, 2011. Google Scholar
- J. Zhong and B. He. Kernelet: High-throughput GPU kernel executions with dynamic slicing and scheduling, 2013.Google Scholar
- J. Zhong and B. He. Medusa: Simplified graph processing on GPUs. IEEE TPDS, 99(PrePrints):1, 2013.Google Scholar
Recommendations
Relational query coprocessing on graphics processors
Graphics processors (GPUs) have recently emerged as powerful coprocessors for general purpose computation. Compared with commodity CPUs, GPUs have an order of magnitude higher computation power as well as memory bandwidth. Moreover, new-generation GPUs ...
A survey of graph processing on graphics processing units
Graphics processing units (GPUs) have become popular high-performance computing platforms for a wide range of applications. The trend of processing graph structures on modern GPUs has also attracted an increasing interest in recent years. This article ...
Heterogeneous multicore parallel programming for graphics processing units
Software Development for Multi-core Computing SystemsHybrid parallel multicore architectures based on graphics processing units (GPUs) can provide tremendous computing power. Current NVIDIA and AMD Graphics Product Group hardware display a peak performance of hundreds of gigaflops. However, exploiting ...
Comments