2015 · 130 citations · 27 references
ComputingComputer EngineeringComputer ScienceComputer GraphicsParallel AlgorithmsParallel ComputingData ParallelismGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsHardware AccelerationGraph ProcessingMulti-gpu ArchitecturesMulti-gpu ComputingMulti-gpu SystemsParallel Prefix SumPrefix SumSimd ExecutionSimd Parallelism
The vast computing power of GPUs makes them an attractive platform for accelerating large scale data parallel computations such as popular graph processing applications. However, the inherent irregularity and large sizes of real-world power law graphs makes effective use of GPUs a major challenge. In this paper we develop techniques that greatly enhance the performance and scalability of vertex-centric graph processing on GPUs. First, we present Warp Segmentation, a novel method that greatly enhances GPU device utilization by dynamically assigning appropriate number of SIMD threads to process a vertex with irregular-sized neighbors while employing compact CSR representation to maximize the graph size that can be kept inside the GPU global memory. Prior works can either maximize graph sizes (VWC uses the CSR representation) or device utilization (e.g., CuSha uses the CW representation, however, CW is roughly 2.5x the size of CSR). Second, we further scale graph processing to make use of multiple GPUs while proposing Vertex Refinement to address the challenge of judiciously using the limited bandwidth available for transferring data between GPUs via the PCIe bus. Vertex refinement employs parallel binary prefix sum to dynamically collect only the updated boundary vertices inside GPUs' outbox buffers for dramatically reducing inter-GPU data transfer volume. Whereas existing multi-GPU techniques (Medusa, TOTEM) perform high degree of wasteful vertex transfers. On a single GPU, our framework delivers average speedups of 1.29x to 2.80x over VWC. When scaled to multiple GPUs, our framework achieves up to 2.71x performance improvement compared to inter-GPU vertex communication schemes used by other multi-GPU techniques (i.e., Medusa, TOTEM).
27
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations
The dynamics of viral marketing
Jure Leskovec, Lada A. Adamic, Bernardo A. Huberman · ACM Transactions on the Web · 2007 · 2.1K citations · Full text
Group formation in large social networks
Lars Bäckström, D.P. Huttenlocher, Jon Kleinberg et al. · 2006 · 1.8K citations