SC17 Denver, CO

Hierarchical Sparse Graph Computations on Multicore Platforms

Student: Humayun Kabir (Pennsylvania State University)
Advisor: Kamesh Madduri (Pennsylvania State University)
Abstract: k-core and k-truss are cohesive subgraphs used for visualization, community detection and centrality analysis. These cohesive subgraphs have hierarchical structures and can be computed exactly in polynomial time. We have developed PKC and PKT algorithms for k-core and k-truss decompositions respectively. PKC decreases atomic operations and uses less memory. PKT uses a well-designed data structure that updates trusses concurrently, is memory efficient and avoids using hash-table. On 24 threads, PKT is more than one magnitude faster than a state-of-art algorithm. Sparse matrix computations are useful for scientific computing and engineering. We have developed a multilevel data structure CSR-k to store a sparse matrix that enhances locality in memory access pattern and decreases work load imbalance. On a 32 core node, sparse matrix-vector multiplication using CSR-k is 2.41x faster than state-of-art pOSKI and sparse triangular solution using CSR-k is 2.18x faster than coloring method.

Summary: pdf
Presentation: pdf
Poster: pdf

Doctoral Showcase Index