| Title | : | Algorithmic Approximations for Graphs on GPUs |
| Speaker | : | Somesh Singh (IITM) |
| Details | : | Thu, 22 Jun, 2017 2:00 PM @ BSB 361 |
| Abstract: | : | Abstract: Graph algorithms are being widely used in several application domains. It has been established that analyzing and parallelizing graph algorithms are challenging. The parallelization issues get exacerbated when graphics processing units (GPUs) are used to execute graph algorithms. While former research has shown effective parallelization of several graph algorithms on GPUs, a few algorithms still take up considerable amount of time. In this work, we address the scalability issues in graph parallelization. In particular, we wish to improve execution performance by tolerating a little approximation in the computation. We study the effect of four approximations on five graph algorithms with six graphs, and illustrate that if an application allows for small inaccuracy, it can offer considerable performance benefits. We also study how approximations affect GPU-based processing, and offer interesting takeaways. |
