Theoretical Results on Optimal Partitoning for Matrix-Matrix Multiplication with Two Processors
|Title:||Theoretical Results on Optimal Partitoning for Matrix-Matrix Multiplication with Two Processors||Authors:||DeFlumere, Ashley; Lastovetsky, Alexey||Permanent link:||http://hdl.handle.net/10197/12402||Date:||Sep-2011||Online since:||2021-08-09T16:07:25Z||Abstract:||In this report, we consider a simple but important linear algebra kernel, matrix-matrix multiplication. Building multi-core processors based on heterogeneous cores is an important current trend. In this context, it is of great interest to study optimal matrix partitioning algorithms for small cases (i.e. small number of cores). Indeed, the general case, with relatively high numbers of heterogeneous resources is now well understood, however the problem is in general NP-Complete when one aims at balancing the load while minimizing the communications. Nonetheless several approximation algorithms have been successfully designed. Nevertheless, negative complexity results do not apply for very few heterogeneous cores. Additionally, the case of a small number of processors is useful as a model for heterogeneous clusters and clusters of clusters. In this paper, we provide a complete study of 2 heterogeneous resources and we prove that in this case, the optimal partitioning is based on non-standard decomposition techniques.||Type of material:||Technical Report||Publisher:||University College Dublin. School of Computer Science and Informatics||Series/Report no.:||UCD CSI Technical Reports; ucd-csi-2011-09||Copyright (published version):||2011 the Authors||Keywords:||Linear algebra; Multiprocessor calculations; Processor optimisation; Processor partitioning; Communication/computation ratios||Other versions:||https://web.archive.org/web/20080226040105/http:/csiweb.ucd.ie/Research/TechnicalReports.html||Language:||en||Status of Item:||Not peer reviewed||This item is made available under a Creative Commons License:||https://creativecommons.org/licenses/by-nc-nd/3.0/ie/|
|Appears in Collections:||Computer Science and Informatics Technical Reports|
Show full item record
If you are a publisher or author and have copyright concerns for any item, please email email@example.com and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.