Abstract: Graphs containing millions of vertices and billions of edges are now commonplace in fields like social network analysis, computational biology, information security, and recommendation systems. Writing programs to efficiently process these graphs is not easy. First, as CPU speeds have stagnated, programmers must turn to accelerators such as Graphics Processing Units (GPUs) to obtain reasonable performance on increasingly larger graphs. Second, since graphs are irregular data structures, traditional compiler techniques like auto-parallelization do not work. Thus, programmers must manually implement complicated parallel algorithms using low-level accelerator-specific programming languages while hoping that the code they are writing will be fast enough. Ideally, we would like programmers to write graph algorithms in a high-level language while a "sufficiently-smart" compiler performs the hard work of producing high-performance code.
In this talk I present IrGL, an explicitly-parallel notation for graph algorithms, and the IrGL compiler, which uses three key throughput optimizations to produce highly optimized code for GPUs. These optimizations reduce the cost of fine-grained synchronization, eliminate serialization bottlenecks in nested parallel loops, and overcome CPU--GPU communication bottlenecks in iterative algorithms. Most handwritten implementations do not implement these optimizations due to their complexity and by automating these optimizations, the IrGL compiler makes it significantly easier to write high-performance graph algorithms on GPUs. Evaluated on eight core graph algorithms, IrGL programs are up to 6x faster (median 1.4x) than corresponding expert-written code.
The IrGL compiler demonstrates that domain-specific compilers can significantly improve the experience and lower the complexity of writing high-performance programs on current heterogeneous architectures even for complex problem domains like graph algorithms.
Bio: Sreepathi Pai is currently a Postdoctoral Fellow at the University of Texas at Austin. He received his PhD from the Indian Institute of Science (IISc), Bangalore in 2015. His research interests are in compilers, computer architecture and programming systems for heterogeneous systems that contain accelerators like GPUs. At the University of Texas, he co-wrote the LonestarGPU 2.0 benchmark suite, and developed the IrGL compiler to generate high-performance graph analytics applications for GPUs. His PhD research described the first full coherence scheme for minimally-redundant automatic memory transfers between the CPU and GPU, and proposed improvements to concurrent execution capabilities in GPUs.