Truss Decomposition on Shared-Memory Parallel Systems
| Shaden Smith, Xing Liu, Nesreen K. Ahmed, Ancy Sarah Tom, Fabrizio Petrini, and George Karypis |
| IEEE High Performance Extreme Computing Conference (HPEC), 2017 |
Download Paper  |
| Abstract The scale of data used in graph analytics grows at an unprecedented rate. More than ever, domain experts require efficient and parallel algorithms for tasks in graph analytics. One such task is the truss decomposition, which is a hierarchical decomposition of the edges of a graph and is closely related to the task of triangle enumeration. As evidenced by the recent GraphChallenge, existing algorithms and implementations for truss decomposition are insufficient for the scale of modern datasets. In this work, we propose a parallel algorithm for computing the truss decomposition of massive graphs on a shared-memory system. Our algorithm breaks a computation efficient serial algorithm into several bulk-synchronous parallel steps which do not rely on atomics or other fine-grained synchronization. We evaluate our algorithm across a variety of synthetic and real-world datasets on a 56-core Intel Xeon system. Our serial implementation achieves over 1400x speedup over the provided GraphChallenge serial benchmark implementation and is up to 28x faster than the state-of-the-art shared-memory parallel algorithm. |
| Comments GraphChallenge 2017 Finalist |
| Research topics: Data mining | Graph mining | Parallel processing |