Monday 24 June 2019
Martin Burtscher: A High-Quality and Fast Maximal Independent Set Implementation for GPUs
Time, Location: will be posted soon
Computing a maximal independent set is an important step in many parallel graph algorithms. We present ECL-MIS, a maximal independent set implementation that works well on GPUs. It includes optimizations to speed up the computation, reduce the memory footprint, and increase the set size. The CUDA code requires fewer than 30 kernel statements, runs asynchronously, and produces a deterministic result. It outperforms the maximal independent set implementations of Pannotia, CUSP, and IrGL on each of the 16 tested graphs of various types and sizes. On a Titan X, ECL-MIS is between 3.9 and 100 times faster (11 times on average). At the same time, it produces maximal independent sets that are over 10% larger on average. Whereas the other codes produce maximal independent sets that are, on average, about 15% smaller than the largest possible such sets, ECL-MIS’ sets are less than 6% smaller.
Martin Burtscher is a Professor in the Department of Computer Science at Texas State University. He received the BS/MS degree from ETH Zurich and the PhD degree from the University of Colorado at Boulder. His research focuses on developing general strategies for parallelizing complex and irregular programs, creating techniques to automatically synthesize fast and effective data-compression and other algorithms, and designing optimizations to improve performance and energy efficiency. Martin has co-authored over 100 peer-reviewed scientific publications. He is a distinguished member of the ACM and a senior member of the IEEE.