Theoretical Results on Optimal Partitoning for Matrix-Matrix Multiplication with Two Processors

Files in This Item:
 File SizeFormat
Downloaducd-csi-2011-09.pdf678.89 kBAdobe PDF
Title: Theoretical Results on Optimal Partitoning for Matrix-Matrix Multiplication with Two Processors
Authors: DeFlumere, AshleyLastovetsky, 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 algebraMultiprocessor calculationsProcessor optimisationProcessor partitioningCommunication/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

Page view(s)

77
Last Week
4
Last month
checked on Nov 28, 2021

Download(s)

7
checked on Nov 28, 2021

Google ScholarTM

Check


If you are a publisher or author and have copyright concerns for any item, please email research.repository@ucd.ie and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.