Accelerating Branch-and-Bound Graph Algorithms with GPUs
This talk presents multiple techniques that we have developed to load balance the search tree traversal on GPUs and mitigate the strain on memory capacity and bandwidth.
Overview
Optimization problems on graphs are often solved using exponential-time algorithms that follow the branch-and-bound paradigm. These algorithms explore search trees that usually suffer from high imbalance and exponential growth, which make accelerating them with GPUs challenging. This talk presents multiple techniques that we have developed to load balance the search tree traversal on GPUs and mitigate the strain on memory capacity and bandwidth. The techniques will be presented in the context of multiple important problems including k-clique counting, maximal clique enumeration, minimum vertex cover, and others, with each problem exhibiting its own unique challenges. In all cases, our results show that GPUs are highly effective at accelerating these algorithms despite their irregular nature.
Presenters
Izzat El Hajj, Assistant Professor, Computer Science, American University of Beirut
Brief Biography
Izzat El Hajj is an Assistant Professor in the Department of Computer Science at the American University of Beirut. His research interests are in leveraging accelerator architectures to tackle challenging computations, with a focus on GPU computing, processing-in-memory, and performance modeling. He is a co-author of the widely used textbook on GPU computing titled “Programming Massively Parallel Processors: A Hands-on Approach”. He earned his M.S. and Ph.D. in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, where he received the Dan Vivoli Endowed Fellowship. Prior to that, he earned his B.E. in Electrical and Computer Engineering at the American University of Beirut, where he received the Distinguished Graduate Award.