HIERARCHICAL SPARSE GRAPH COMPUTATIONS ON MULTICORE PLATFORMS

Open Access
Author:
Kabir, Humayun
Graduate Program:
Computer Science and Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
March 01, 2018
Committee Members:
  • Kamesh Madduri, Dissertation Advisor
  • Kamesh Madduri, Committee Chair
  • Mahmut T. Kandemir, Committee Member
  • Wang-Chien Lee, Committee Member
  • Vasant Honavar, Outside Member
Keywords:
  • k-core
  • k-truss
  • multicore
  • sparse matrix
  • network analysis
  • graph analysis
Abstract:
Graph analysis is widely used to study connectivity, centrality, community and path analysis of social networks, biological networks, communication networks and any interacting objects that can be represented as graphs. Graphs are ubiquitous and particularly they are common in social and physical sciences. The graphs are continuously becoming larger and complex; so scalable and parallel algorithms need to be developed to process and analyze such large graphs. Additionally, the high performance computing (HPC) systems are also becoming complex with multiple cores in a processor and multiple levels in the memory subsystems. We need to utilize HPC systems to develop scalable, parallel and high performing algorithms to analyze large and complex graphs. To analyze connectivity, centrality and robustness of a graph, it is useful to find the densely connected subgraphs (cohesive subgraphs) of a graph. One of the contributions of this thesis is to design parallel algorithms for computing cohesive subgraphs and using them to analyze graphs. The cohesive subgraphs considered are k-core and k-truss of a graph. A parallel algorithm PKC is developed to compute k-core decomposition on shared memory systems. PKC uses less memory and has less synchronization overhead as compared to state-of-the-art algorithms. A parallel k-truss decomposition algorithm PKT is also developed that computes trusses of a large social network graph in minutes where as state-of-the-art algorithms take hours. These algorithms are used to sparsify and reorder social networks. In centrality analysis and scientific computing, an important kernel is sparse matrix-vector multiplication (SpMV). Another contribution of this thesis, is to develop a multi-level data structure (CSR-k) to store sparse matrices/graphs to speedup sparse kernels. CSR-k represents the parallelism present in the sparse kernels and also decreases the work load imbalance among the threads. SpMV using CSR-k achieves a speedup of 2x compared to pOSKI on 32 cores. Sparse triangular solution (STS) is also a very useful kernel in scientific computing. We have used CSR-k and graph coloring to represent sparse triangular solution. STS using CSR-k achieves 2x speedup compared to coloring.