Optimal hypergraph partitioning

Usta, Baran (2018) Optimal hypergraph partitioning. [Thesis]

[thumbnail of 10207524_BaranUsta.pdf] PDF
10207524_BaranUsta.pdf

Download (1MB)

Abstract

Hypergraph partitioning into K parts has many applications in practice such as distributed algorithms and very large scale integrated circuit (VLSI) design. There are various tools proposed in the literature which can partition a given hypergraph very fast. However, since the problem is NP-Hard and the traditional approaches heavily use heuristics, these tools do not provide an optimal partition. There is limited research on partitioning hypergraphs optimally. In this thesis, we propose PHaraoh, a parallel hypergraph partitioner that can provide optimal partitions for many metrics used in the literature. Such a partitioner is important in practice since it enables us to evaluate the true performance of the existing tools. Furthermore, PHaraoh can be started with an initial partition. Thanks to that, even an optimal solution is not found within the given time limit, PHaraoh improves the cost of the provided initial partition. Experimental results on hypergraphs obtained from real-life matrices show that the quality of the partitions of existing tools can be improved significantly for most of the hypergraphs. In order to increase the speed up the search-space exploration, we experimented with both master-slave and workstealing parallelization. It also has been shown that the runtime of the algorithm highly depends on the order of the items in the branch and bound tree. In this study, we propose different ordering strategies which can offer great speed ups depending on the characteristics of the hypergraph
Item Type: Thesis
Uncontrolled Keywords: K-way hypergraph partitioning. -- Parallel branch and bound. -- Branch and bound reordering. -- Combinatorial algorithms. -- K parçalı hiperçizge parçalama. -- Dal ve sınır. -- Paralel hesaplama. -- Dal ve sınır sıralaması. -- Kombinatoryal algoritmalar
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 06 Oct 2018 14:46
Last Modified: 26 Apr 2022 10:26
URI: https://research.sabanciuniv.edu/id/eprint/36612

Actions (login required)

View Item
View Item