Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms

Files in This Item:
File Description SizeFormat 
TPDS2018-1.pdf2.87 MBAdobe PDFDownload
Title: Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms
Authors: Beaumont, Olivier
Becker, Brett A.
DeFlumere, Ashley
Eyraud-Dubois, Lionel
Lambert, Thomas
Lastovetsky, Alexey
Permanent link: http://hdl.handle.net/10197/9579
Date: 5-Jul-2018
metadata.dc.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.
Funding Details: Science Foundation Ireland
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
Keywords: Partitioning algorithmsApproximation algorithmsShapeOptimizationLinear algebraKernelLoad management
DOI: 10.1109/TPDS.2018.2853151
Language: en
Status of Item: Peer reviewed
Appears in Collections:Computer Science Research Collection

Show full item record

Google ScholarTM

Check

Altmetric


This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.