Speaker:Yihan Sun, Assistant Professor of Computer Science and Engineering, UCRiverside

Abstract:Recent hardware advances have brought multicore parallel machines to the mainstream. Although the progress in hardware advance seems promising, it does not provide free performance improvement as the increasing number of cores. For many applications, including seemingly straightforward ones in the sequential setting, state-of-the-art parallel implementations can be slower than a sequential algorithm. Many reasons contribute to the performance issues, such as the parallel overhead in space and thread synchronization, and the non-parallelizable components in conventional sequential algorithms (such as specific data structures and iterative processes).

In this talk, we share our recent work in improving the scalability of parallel graph algorithms. We select three examples: Strongly Connected Components (SCC), Bi-connected Components (BCC), and Influence Maximization (IM). For all three applications, we observe that existing parallel solutions can have poor scalability and can be slower than a sequential solution on certain graphs. Some of the applications suffer from multiple of the aforementioned challenges. Our solution tackles these issues by designing theoretically-efficient algorithms with practical considerations. Tested on more than 20 graphs with various sizes and degree distributions, our algorithms outperform the state-of-the-art solutions for each problem on almost all graphs due to better parallelism and strong theoretical guarantee.

Speaker 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 haswonthe Best Paper Award atPPoPP'23andESA'23, and the Distinguished Paper Award of SPAA'20.