CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers
This paper introduces the batch-parallel Compressed Packed Memory Array (CPMA), a compressed dynamic ordered batch-parallel set data structure based on the Packed Memory Array (PMA). Traditionally, batch-parallel sets are built on pointer-based data structures such as trees because pointer-based structures enable fast parallel unions via pointer manipulation. When compared to cache-optimized trees, PMAs were slower to update but faster to scan.
The batch-parallel CPMA overcomes this tradeoff between updates and scans by optimizing for cache-friendliness. On average, the CPMA achieves 3× faster batch-insert throughput and 4× faster range-query throughput compared to compressed PaC-trees, a state-of-the-art batch-parallel set library based on cache-optimized trees.
We further evaluate the CPMA compared to compressed PaC-trees and Aspen, a state-of-the-art system, on a real world application of dynamic-graph processing. The CPMA is on average 1.2× faster on a suite of graph algorithms and 2× faster on batch inserts when compared with compressed PaC-trees. Furthermore, the CPMA is on average 1.3× faster on graph algorithms and 2× faster on batch inserts compared to Aspen.
Tue 5 MarDisplayed time zone: London change
16:10 - 17:10 | Optimizing for MemoryMain Conference at Moorfoot Chair(s): Yan Gu University of California, Riverside | ||
16:10 20mTalk | ConvStencil: Transform Stencil Computation to Matrix Multiplication on Tensor CoresBest Paper Award Main Conference Yuetao Chen Microsoft Research, Kun Li Microsoft Research, Yuhao Wang Microsoft Research, Donglin Bai Microsoft Research, Lei Wang Microsoft Research, Lingxiao Ma Microsoft Research, Liang Yuan Chinese Academy of Sciences, Yunquan Zhang Zhang, Ting Cao Microsoft Research, Mao Yang Microsoft Research Link to publication DOI | ||
16:30 20mTalk | CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers Main Conference Brian Wheatman Johns Hopkins University, Randal Burns Johns Hopkins, Aydin Buluc University of California at Berkeley & Lawrence Berkeley National Lab, Helen Xu Lawrence Berkeley National Laboratory Link to publication DOI | ||
16:50 20mTalk | Gallatin: A General-Purpose GPU Memory Manager Main Conference Link to publication DOI | ||