Optimally bipartitioning sparse matrices with reordering and parallelization

Mumcuyan, Aras and Usta, Baran and Kaya, Kamer and Yenigün, Hüsnü (2018) Optimally bipartitioning sparse matrices with reordering and parallelization. Concurrency and Computation: Practice and Experience (SI), 30 (21). ISSN 1532-0626 (Print) 1532-0634 (Online)

Full text not available from this repository. (Request a copy)


A good task‐to‐processor assignment is crucial for parallel efficiency since the communication between the tasks is usually the main bottleneck for scalability. A fundamental approach to solve this problem is modeling the tasks as a hypergraph where the pins correspond to the tasks and the nets represent the communication among them. The vertices in this hypergraph is partitioned into a number of parts, which correspond to processors, in a way that the total number of vertices for each part is balanced and the amount of edges having endpoints in different parts is minimized. Sparse matrix‐vector multiplication is an extensively used kernel in many applications. Recently, a novel, purely combinatorial branch‐and‐bound–based approach has been proposed for sparse‐matrix bipartitioning which can handle hypergraphs that cannot be optimally partitioned by using existing methods due to the problem's complexity. Our work extends the previous study with three ideas. We use 1) matrix ordering techniques to use more information in the earlier branches of the tree, 2) a machine learning approach to choose an ordering based on the matrix features, and 3) a parallelization technique to search an optimal bipartitioning. As our experiments show, these techniques make the bipartitioning process significantly faster.
Item Type: Article
Uncontrolled Keywords: hypergraphs; machine learning; parallel branch-and-bound; sparse-matrix bipartitioning
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 21 Aug 2019 22:01
Last Modified: 30 Jul 2023 23:29
URI: https://research.sabanciuniv.edu/id/eprint/37391

Actions (login required)

View Item
View Item