Hierarchical Sparse Graph Computations on Multicore
Platforms
SessionDoctoral Showcase Session 3
Presenter
Event Type
Doctoral Showcase
Applications
Architectures
Graph Algorithms
Heterogeneous Systems
TimeTuesday, November 14th4:42pm -
5pm
Location210-212
Descriptionk-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.
Presenter
