PhD Candidate
Massachusetts Institute of Technology
Areas of Interest
- Scientific Computing
- Theory
- Performance Engineering
Poster
A Parallel Packed Memory Array to Store Dynamic Graphs
Abstract
Data structures for storing dynamic graphs must support fast updates as well as fast range queries which underlie graph traversals such as breadth-first search. The Packed Memory Array (PMA) seems like a good candidate for this setting because it supports fast updates as well as cache-efficient range queries. Concurrently updating a PMA raises challenges, however, because an update may require rewriting the entire structure in the worst case.
This paper introduces a parallel PMA with intra and inter-operation parallelism with deadlock-free polylogarithmic-span operations. Our main observation is that the PMA is well-suited to concurrent updates despite occasionally requiring a rewrite of the entire structure because 1) most of the updates only write to a small part of the structure and 2) the worst case is highly parallel and cache-efficient. To evaluate our data structure, we implemented Parallel Packed Compressed Sparse Row (PPCSR), a dynamic-graph processing framework that extends the Ligra interface with graph updates. We show that PPCSR is on average about 1.6x faster on graph kernels than Aspen, a state-of-the-art graph-streaming system. PPCSR achieves up to 80 million updates per second and is 2-5x faster than Aspen on most batch sizes. Finally, PPCSR is competitive with Ligra and Ligra+, two state-of-the-art static graph-processing frameworks.
Bio
Helen Xu is a fifth-year PhD candidate in computer science at MIT in the Supertech group advised by Charles E. Leiserson. Her research focuses on efficient algorithms in theory and in practice. Specifically, her primary research interests include parallel computing, cache-friendly algorithms, and performance engineering. Previously, she received a B.S. in computer science from Stony Brook University.
