[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] PhD Candidate [an error occurred while processing this directive] Massachusetts Institute of Technology [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

Scientific Computing

Theory

Performance Engineering

[an error occurred while processing this directive] A Parallel Packed Memory Array to Store Dynamic Graphs [an error occurred while processing this directive] 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. [an error occurred while processing this directive] 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. [an error occurred while processing this directive] Personal home page [an error occurred while processing this directive] [an error occurred while processing this directive]