2014 · 50 citations · 40 references
ComputingComputer EngineeringComputer ScienceCompilersParallel AlgorithmsParallel ComputingData ParallelismGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingHardware AccelerationData PrefetchingGraph KernelsLatency ToleranceMemory Access LatencyMemory LatencyPrefetchingPrefetching MechanismsRegisters
More and more graph algorithms are being GPU enabled. Graph algorithm implementations on GPUs have irregular control flow and are memory-intensive with many irregular/data-dependent memory accesses. Due to these factors graph algorithms on GPUs have low execution efficiency. In this work we propose a mechanism to improve the execution efficiency of graph algorithms by improving their memory access latency tolerance. We propose a mechanism for prefetching data for load pairs that have one load dependent on the other - such pairs are common in graph algorithms. Our mechanism detects the target loads in hardware and injects instructions into the pipeline to prefetch data into spare registers that are not being used by any active threads. By prefetching data into registers, early eviction of prefetched data can be eliminated. We also propose a mechanism that uses the compiler to identify the target loads. Our mechanism improves performance over no prefetching by 10% on average and upto 51% for nine memory intensive graph algorithm kernels.
40
R-MAT: A Recursive Model for Graph Mining
Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos · 2004 · 1.3K citations · Full text
Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow
Wilson Wai Lun Fung, Ivan Sham, George L. Yuan et al. · 2007 · 727 citations
POWER4 system microarchitecture
Joel M. Tendler, J. S. Dodson, J. S. Fields et al. · IBM Journal of Research and Development · 2002 · 658 citations
Duane Merrill, Michael Garland, Andrew Grimshaw · 2012 · 512 citations
Compiler-based prefetching for recursive data structures
Chi-Keung Luk, Todd C. Mowry · 1996 · 399 citations · Full text