Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms
|Title:||Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms||Authors:||Beaumont, Olivier
Becker, Brett A.
|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 algorithms; Approximation algorithms; Shape; Optimization; Linear algebra; Kernel; Load 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
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.