Abstract: Computing biconnected components (BCC) of a graph is a fundamental graph problem. The canonical parallel BCC algorithm is the Tarjan-Vishkin algorithm, which has optimal work (total number of operations) and polylogarithmic span (parallel time). However, Tarjan-Vishkin is not widely used in practice due to space-inefficiency. In practice, existing parallel implementations are based on breadth-first search (BFS), which has span proportional to the diameter of the graph. As a result, existing parallel BCC implementations suffer from poor performance on large-diameter graphs and can be slower than the sequential algorithm on many real-world graphs.In this talk, we propose the first parallel biconnectivity algorithm (FAST-BCC) that has optimal work, polylogarithmic span, and is space-efficient. Due to theoretical-efficiency, FAST-BCC outperforms existing algorithms on all tested graphs in our experiments. Testing on a 96-core machine and 27 graphs with varying edge distributions, FAST-BCC is 1.3-12x faster than the best existing implementations on each graph.
Bio: Yihan Sun is an Assistant Professor in the Computer Science and Engineering (CSE) Department at the University of California, Riverside (UCR). She received her Ph.D. degree from Carnegie Mellon University in 2019, advised by Guy Blelloch. Prior to that, she received her Bachelor’s degree in Computer Science from Tsinghua University in 2014.Her research interests include broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, programming tools and their applications. Much of her work aims at bridging the gap between theory and practice of parallel computing. She is a recipient of the NSF CAREER Award in 2023, and the Google Research Scholar program in 2024. Her work has won the Best Paper Award at PPoPP'23 and ESA'23.
Abstract: Computing biconnected components (BCC) of a graph is a fundamental graph problem. The canonical parallel BCC algorithm is the Tarjan-Vishkin algorithm, which has optimal work (total number of operations) and polylogarithmic span (parallel time). However, Tarjan-Vishkin is not widely used in practice due to space-inefficiency. In practice, existing parallel implementations are based on breadth-first search (BFS), which has span proportional to the diameter of the graph. As a result, existing parallel BCC implementations suffer from poor performance on large-diameter graphs and can be slower than the sequential algorithm on many real-world graphs.In this talk, we propose the first parallel biconnectivity algorithm (FAST-BCC) that has optimal work, polylogarithmic span, and is space-efficient. Due to theoretical-efficiency, FAST-BCC outperforms existing algorithms on all tested graphs in our experiments. Testing on a 96-core machine and 27 graphs with varying edge distributions, FAST-BCC is 1.3-12x faster than the best existing implementations on each graph.
Bio: Yihan Sun is an Assistant Professor in the Computer Science and Engineering (CSE) Department at the University of California, Riverside (UCR). She received her Ph.D. degree from Carnegie Mellon University in 2019, advised by Guy Blelloch. Prior to that, she received her Bachelor’s degree in Computer Science from Tsinghua University in 2014.Her research interests include broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, programming tools and their applications. Much of her work aims at bridging the gap between theory and practice of parallel computing. She is a recipient of the NSF CAREER Award in 2023, and the Google Research Scholar program in 2024. Her work has won the Best Paper Award at PPoPP'23 and ESA'23.