Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy

February 8, 2023
3:00-4:00pm ET
Cummings 402
Speaker: Helen Xu
Host: Diane Souvaine


Developing fast codes to solve large problems (on the order of gigabytes and up to terabytes) efficiently on multicores requires taking advantage of underlying multicore hardware features. Specifically, software systems must be optimized simultaneously to take advantage of the multiple cores via parallelism and the memory subsystem via locality. Optimizing for either of these features is notoriously difficult, however, and combining them only adds to the complexity.

This talk will contend that in order to create parallel algorithms for multicores that are theoretically and practically efficient, practitioners should use a locality-first strategy. That is, they should first understand and exploit locality as much as possible before introducing parallelism. As an example, the talk will cover dynamic-graph data structures as a case study for the locality-first strategy. Real-world dynamic graphs present challenges to locality and parallelism due to their naturally-occurring sparse and skewed structure.

I will conclude with future research directions using the locality- first strategy and my research mission and vision towards developing fast and accessible codes.


Helen Xu (https://itshelenxu.github.io/) is the 2022 Grace Hopper Postdoctoral Scholar at Lawrence Berkeley National Laboratory. She completed her PhD at MIT in 2022 with Professor Charles E. Leiserson. Her main research interests are in parallel and cache-friendly algorithms and data structures. Her work has previously been supported by a National Physical Sciences Consortium fellowship and a Chateaubriand fellowship. She has interned at Microsoft Research, NVIDIA Research, and Sandia National Laboratories.