Topic: Parallel Graph Algorithm Design Based on Efficient Parallel Data Structures
Speaker: WANG Letong, Department of Computer Science, University of California, Riverside (UCR)
Date and time: 10:00, March 13
Venue: Room 1A-200, SIST
Host: FAN Rui
Abstract:
Living in the world of big data, we, as computer scientists, are challenged by how to process the high volume of data efficiently. In most cases, we want fast response time (e.g., training large AI models like ChatGPT), as well as better accuracy within a certain budget of time (e.g., finding safer routes for autonomous driving). Parallel computing is a key solution to enable these possibilities. With the prevalence of parallel processors (e.g., multi-core CPUs, GPUs, and other accelerators), designing efficient algorithms and software is now of huge practical relevance and significant theoretical interest. This talk is about a collection of parallel algorithms on graphs that take advantage of novel parallel data structures. One is a parallel strong connectivity algorithm based on faster reachability, which uses parallel hash bags to avoid additional edge traversing. The other one is an algorithm to compute Influence Maximization on graphs, which uses parallel tree structures to keep track of the vertex with the maximum marginal influence.
Biography: