Optimizing Data Movement in Sparse Computations via Cache-Friendly Layouts

BU Computer Systems Seminar

Talk Title: Optimizing Data Movement in Sparse Computations via Cache-Friendly Layouts

Speaker: Helen Xu, Assistant Professor, Georgia Tech

Abstract: Sparse matrix and graph computations are foundational to modern workloads spanning scientific computing, machine learning, and network analytics. They are bottlenecked by irregular memory access and excessive data movement.

This talk presents two examples of how to optimize data layouts and mitigate memory bottlenecks in sparse computations: 1) compression and 2) reordering. Specifically, we cover two recent advances: the Compressed Packed Memory Array (CPMA) for dynamic graphs [Wheatman, Burns, Buluc, and Xu, PPoPP ‘24] and hierarchical reordering for sparse matrix-sparse matrix multiplication (SpGEMM) [Islam, Xu, Dai, and Buluc, SC ‘25].

The CPMA is a compressed, pointer-free dynamic structure that preserves ordering while enabling efficient batch-parallel updates, reducing indirection and improving cache utilization in sparse set and graph representations. In contrast, recent work on SpGEMM demonstrates how hierarchical row reordering and cluster-wise computation can significantly improve reuse of matrix data, achieving up to 1.39× speedup by aligning computation with locality in the memory hierarchy.

Together, these works illustrate the potential for efficient data layouts to improve the performance of sparse computations.

Bio: Helen Xu is an assistant professor in Georgia Tech’s School of Computational Science and Engineering. Previously, she was the Grace Hopper Postdoctoral Scholar at Lawrence Berkeley National Laboratory. She completed her Ph.D. at MIT 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.