Bilkent University
Department of Computer Engineering

---

CS 590/690 SEMINAR

 

Fast and Scalable Edge-Based Graph Partitioning

 

Ahmet Şahin
Master Student
(Supervisor:Prof.Dr.Cevdet Aykanat)

Computer Engineering Department
Bilkent University

Abstract: Effective and efficient graph partitioning algorithms play a fundamental role in the scalability of parallel computations on large, sparse, and irregular graphs in distributed environments. Even though vertex-based partitioning gives balanced partitions for most graphs, it struggles to balance irregular graphs. Edge-based partitioning is an alternative to vertex-based partitioning for achieving computational balance. However, vertex-based approaches often require careful modeling, such as hypergraph formulations, which introduce significant memory overhead and result in slow partitioning times. Previous work on streaming edge partitioning algorithms, including DBH, provides fast and balanced partitions but incurs drastically high communication costs due to the limited perspective of the partitioning process. The offline partitioning method SPAC, the state-of-the-art edge-based model, converts vertex-based partitions into edge-based partitions but suffers from memory overhead due to graph expansion. We propose a fast, scalable, and memory-efficient offline algorithm, the proposed algorithm, and compare it against previous work up to 32K processors. When scaled to 32K processes, the proposed algorithm runs 4.46 times faster than SPAC on the largest test graph.

 

DATE: November 24, Monday @ 15:50 Place: EA 502