Please use this identifier to cite or link to this item: http://ktisis.cut.ac.cy/handle/10488/7309
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.
URI: http://ktisis.cut.ac.cy/handle/10488/7309
ISSN: 09208542
DOI: 10.1007/s11227-010-0474-3
Rights: © Springer Science+Business Media, LLC 2010
Appears in Collections:Άρθρα/Articles

Show full item record

SCOPUSTM   
Citations 20

4
checked on Jan 19, 2017

WEB OF SCIENCETM
Citations 50

2
checked on Dec 24, 2016

Google ScholarTM

Check

Altmetric


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