Bilkent University
Department of Computer Engineering

---

MS THESIS PRESENTATION

 

Parallel Streaming Graph Partitioning utilizing Multilevel Framework

 

Nazanin Jafari
MS Student
(Supervisor: Prof. Dr. Cevdet Aykanat)
Computer Engineering Department
Bilkent University

Graph partitioning is widely used for efficient parallelization of a variety of applications. Streaming graph partitioning is a one pass partitioning solution provided to overcome high computation costs of offline graph partitioners. Even though these streaming algorithms can be used for successively repartitioning, aiming at further improvements in partitioning qualities, quality improvements is limited to few passes that make offline graph partitioning tools still a desirable solution for graph partitioning due to the generated high-quality partitions.

We propose a multilevel approach using streaming algorithms that can alleviate the tradeoff between quality and performance in graph partitioning problem. Moreover, our OpenMP based multi-threaded implementation can generate fast and highly scalable solutions compared to mt-metis, a multi-threaded solution for METIS, the state-of-the-art offine high-quality graph partitioning tool. Our results show that our method can produce up to fifteen times faster and more scalable results in large graph datasets. We also show that our method can improve the quality of partitions signifficantly compared to state-of-the-art streaming graph partitioning algorithm LDG after repartitioning several times. On average we produce partitions with 29% better qualities than the LDG algorithm.

 

DATE: 08 August 2018, Wednesday @ 15:00
PLACE: EA-409