Ideal and Predictable Hit Ratio for Matrix Transposition in Data Caches

Alba Pedro-Zapater, Clemente Rodríguez, Juan Segarra, Rubén Gran Tejero and Víctor Viñals-Yúfera
Additional contact information
Alba Pedro-Zapater: Departamento de Informática e Ing. de Sist., I3A, Universidad de Zaragoza, 50009 Zaragoza, Spain; HiPEAC
Clemente Rodríguez: Departamento de Arquitectura y Tecnología de Computadores, Universidad del País Vasco, 48940 Leioa, Spain
Juan Segarra: Departamento de Informática e Ing. de Sist., I3A, Universidad de Zaragoza, 50009 Zaragoza, Spain; HiPEAC
Rubén Gran Tejero: Departamento de Informática e Ing. de Sist., I3A, Universidad de Zaragoza, 50009 Zaragoza, Spain; HiPEAC
Víctor Viñals-Yúfera: Departamento de Informática e Ing. de Sist., I3A, Universidad de Zaragoza, 50009 Zaragoza, Spain; HiPEAC

Mathematics, 2020, vol. 8, issue 2, 1-23

Abstract: Matrix transposition is a fundamental operation, but it may present a very low and hardly predictable data cache hit ratio for large matrices. Safe (worst-case) hit ratio predictability is required in real-time systems. In this paper, we obtain the relations among the cache parameters that guarantee the ideal (predictable) data hit ratio assuming a Least-Recently-Used (LRU) data cache. Considering our analytical assessments, we compare a tiling matrix transposition to a cache oblivious algorithm, modified with phantom padding to improve its data hit ratio. Our results show that, with an adequate tile size, the tiling version results in an equal or better data hit ratio. We also analyze the energy consumption and execution time of matrix transposition on real hardware with pseudo-LRU (PLRU) caches. Our analytical hit/miss assessment enables the usage of a data cache for matrix transposition in real-time systems, since the number of misses in the worst case is bound. In general and high-performance computation, our analysis enables us to restrict the cache resources devoted to matrix transposition with no negative impact, in order to reduce both the energy consumption and the pollution to other computations.

Keywords: transposition; data cache memory; real-time; tiling; cache oblivious (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/2/184/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/2/184/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:2:p:184-:d:315797

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().