NDLI: A data locality methodology for matrix–matrix multiplication algorithm

Content Provider	Springer Nature Link
Author	Alachiotis, Nicolaos Kelefouras, Vasileios I. Athanasiou, George S. Michail, Harris E. Kritikakou, Angeliki S. Goutis, Costas E.
Copyright Year	2010
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.
Starting Page	830
Ending Page	851
Page Count	22
File Format	PDF
ISSN	09208542
Journal	The Journal of Supercomputing
Volume Number	59
Issue Number	2
e-ISSN	15730484
Language	English
Publisher	Springer US
Publisher Date	2010-09-07
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Compilers Memory management Data locality Data reuse Recursive array layouts Scheduling Strassen’s algorithm Matrix-matrix multiplication Programming Languages, Compilers, Interpreters Processor Architectures Computer Science
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Information Systems Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A high-performance matrix–matrix multiplication methodology for CPU and GPU architectures

A methodology for speeding up matrix vector multiplication for single/multi-core architectures

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

A Matrix–Matrix Multiplication methodology for single/multi-core architectures using SIMD

Scheduling GEN_BLOCK Array Redistribution

Parallel Complexity of Matrix Multiplication$^{1}$

Efficient representation of higher-dimensional arrays by dimension transformations

Improving performance of software transactional memory through contention locality

Precise Data Locality Optimization of Nested Loops

A data locality methodology for matrix–matrix multiplication algorithm

Similar Documents

A high-performance matrix–matrix multiplication methodology for CPU and GPU architectures

A methodology for speeding up matrix vector multiplication for single/multi-core architectures

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

A Matrix–Matrix Multiplication methodology for single/multi-core architectures using SIMD

Scheduling GEN_BLOCK Array Redistribution

Parallel Complexity of Matrix Multiplication$^{1}$

Efficient representation of higher-dimensional arrays by dimension transformations

Improving performance of software transactional memory through contention locality

Precise Data Locality Optimization of Nested Loops

A data locality methodology for matrix–matrix multiplication algorithm