Options
Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms
Date Issued
2018-07-05
Date Available
2019-01-07T09:52:25Z
Abstract
The problem of partitioning dense matrices into sets of sub-matrices has received increased attention recently and is crucial when considering dense linear algebra and kernels with similar communication patterns on heterogeneous platforms. The problem of load balancing and minimizing communication is traditionally reducible to an optimization problem that involves partitioning a square into rectangles. This problem has been proven to be NP-Complete for an arbitrary number of partitions. In this paper, we present recent approaches that relax the restriction that all partitions be rectangles. The first approach uses an original mathematical technique to find the exact optimal partitioning. Due to the complexity of the technique, it has been developed for a small number of partitions only. However, even at a small scale, the optimal partitions found by this approach are often non-rectangular and sometimes non-intuitive.
Sponsorship
Science Foundation Ireland
Other Sponsorship
COST Program Action IC1305: Network for Sustainable Ultrascale Computing (NESUS)
Type of Material
Journal Article
Publisher
IEEE
Journal
IEEE Transactions on Parallel and Distributed Systems
Volume
30
Issue
1
Start Page
218
End Page
229
Copyright (Published Version)
2018 IEEE
Language
English
Status of Item
Peer reviewed
ISSN
1045-9219
This item is made available under a Creative Commons License
File(s)
Owning collection
Scopus© citations
20
Acquisition Date
Mar 28, 2024
Mar 28, 2024
Views
817
Last Week
1
1
Last Month
4
4
Acquisition Date
Mar 28, 2024
Mar 28, 2024
Downloads
503
Last Month
11
11
Acquisition Date
Mar 28, 2024
Mar 28, 2024