Ph.D DISSERTATION: Partitioning Models for Scaling Distributed Graph Computations<\/p>\n
G\u00fcnd\u00fcz Vehbi Demirci
\nPh.D Candidate
\n(Supervisor: Prof. Dr. Cevdet Aykanat)
\nComputer Engineering Department<\/p>\n
The focus of this thesis is intelligent partitioning models and methods for scaling the performance of parallel graph computations on distributed-memory systems.Distributed databases utilize graph partitioning to provide servers with data-locality and workload-balance. Some queries performed on a database may form cascades due to the queries triggering each other. The current partitioning methods consider the graph structure and logs of query workload. We introduce the cascade-aware graph partitioning problem with the objective of minimizing the overall cost of communication operations between servers during cascade processes. We propose a randomized algorithm that integrates the graph structure and cascade processes to use as input for large-scale partitioning. Experiments on graphs representing real social networks demonstrate the effectiveness of the proposed solution in terms of the partitioning objectives.<\/p>\n
Sparse-general-matrix-multiplication (SpGEMM) is a key computational kernel used in scientific computing and high-performance graph computations. We propose an SpGEMM algorithm for Accumulo database which enables high performance distributed parallelism through its iterator framework. The proposed algorithm provides write-locality and avoids scanning input matrices multiple times by utilizing Accumulo\u2019s batch scanning capability and node-level parallelism structures. We also propose a matrix partitioning scheme that reduces the total communication volume and provides a workload-balance among servers. Extensive experiments performed on both real-world and synthetic sparse matrices show that the proposed algorithm and matrix partitioning scheme provide significant performance improvements.<\/p>\n
Scalability of parallel SpGEMM algorithms are heavily communication bound. Multidimensional partitioning of SpGEMM\u2019s workload is essential to achieve higher scalability. We propose hypergraph models that utilize the arrangement of processors and also attain a multidimensional partitioning on SpGEMM\u2019s workload. Thorough experimentation performed on both realistic as well as synthetically generated SpGEMM instances demonstrates the effectiveness of the proposed partitioning models.<\/p>\n
DATE: 08 August 2019, Thursday @ 13:15
\nPLACE: EA-409<\/p>\n","protected":false},"excerpt":{"rendered":"
Ph.D DISSERTATION: Partitioning Models for Scaling Distributed Graph Computations G\u00fcnd\u00fcz Vehbi Demirci Ph.D Candidate (Supervisor: Prof. Dr. Cevdet Aykanat) Computer Engineering Department The focus of this thesis is intelligent partitioning models and methods for scaling the performance of parallel graph computations on distributed-memory systems.Distributed databases utilize graph partitioning to provide [\u2026] <\/p>\n