Please use this identifier to cite or link to this item:
Title: A data locality methodology for matrix-matrix multiplication algorithm
Authors: Michail, Harris 
Alachiotis, Nikolaos
Kelefouras, Vasileios I.
Keywords: Memory management (Computer science);Scheduling;Matrices;Algorithms
Issue Date: 2010
Publisher: Springer
Source: Journal of Supercomputing, 2010, Volume 59, Issue 2, Pages 830-851
Abstract: Matrix-Matrix Multiplication (MMM) is a highly important kernel in linear algebra algorithms and the performance of its implementations depends on the memory utilization and data locality. There are MMM algorithms, such as standard, Strassen-Winograd variant, and many recursive array layouts, such as Z-Morton or U-Morton. However, their data locality is lower than that of the proposed methodology. Moreover, several SOA (state of the art) self-tuning libraries exist, such as ATLAS for MMM algorithm, which tests many MMM implementations. During the installation of ATLAS, on the one hand an extremely complex empirical tuning step is required, and on the other hand a large number of compiler options are used, both of which are not included in the scope of this paper. In this paper, a new methodology using the standard MMM algorithm is presented, achieving improved performance by focusing on data locality (both temporal and spatial). This methodology finds the scheduling which conforms with the optimum memory management. Compared with (Chatterjee et al. in IEEE Trans. Parallel Distrib. Syst. 13:1105, 2002; Li and Garzaran in Proc. of Lang. Compil. Parallel Comput., 2005; Bilmes et al. in Proc. of the 11th ACM Int. Conf. Super-comput., 1997; Aberdeen and Baxter in Concurr. Comput. Pract. Exp. 13:103, 2001), the proposed methodology has two major advantages. Firstly, the scheduling used for the tile level is different from the element level's one, having better data locality, suited to the sizes of memory hierarchy. Secondly, its exploration time is short, because it searches only for the number of the level of tiling used, and between (1, 2) (Sect. 4) for finding the best tile size for each cache level. A software tool (C-code) implementing the above methodology was developed, having the hardware model and the matrix sizes as input. This methodology has better performance against others at a wide range of architectures. Compared with the best existing related work, which we implemented, better performance up to 55% than the Standard MMM algorithm and up to 35% than Strassen's is observed, both under recursive data array layouts.
ISSN: 09208542
DOI: 10.1007/s11227-010-0474-3
Rights: © Springer Science+Business Media, LLC 2010
Type: Article
Appears in Collections:Άρθρα/Articles

Show full item record

Citations 20

checked on Feb 17, 2019

Citations 10

checked on Feb 17, 2019

Page view(s)

Last Week
Last month
checked on Feb 18, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.