Hierarchical Sparse Graph Computations on Multicore Platforms
Presenter
Event Type
Doctoral Showcase
Applications
Architectures
Graph Algorithms
Heterogeneous Systems
TimeTuesday, November 14th10am - 5:15pm
LocationFour Seasons Ballroom
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.
