Cache oblivious matrix transposition: Simulation and experiment

Dimitrios Tsifakis; Alistair P. Rendell; Peter E. Strazdins

doi:10.1007/978-3-540-24687-9_3

Cache oblivious matrix transposition: Simulation and experiment

Dimitrios Tsifakis^*, Alistair P. Rendell, Peter E. Strazdins

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

A cache oblivious matrix transposition algorithm is implemented and analyzed using simulation and hardware performance counters. Contrary to its name, the cache oblivious matrix transposition algorithm is found to exhibit a complex cache behavior with a cache miss ratio that is strongly dependent on the associativity of the cache. In some circumstances the cache behavior is found to be worst than that of a naïve transposition algorithm. While the total size is an important factor in determining cache usage efficiency, the sub-block size, associativity, and cache line replacement policy are also shown to be very important.

Original language	English
Pages (from-to)	17-25
Number of pages	9
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3037
DOIs	https://doi.org/10.1007/978-3-540-24687-9_3
Publication status	Published - 2004

Access to Document

10.1007/978-3-540-24687-9_3

Cite this

@article{445ee541413046b5b4a9d8e25ee0a457,

title = "Cache oblivious matrix transposition: Simulation and experiment",

abstract = "A cache oblivious matrix transposition algorithm is implemented and analyzed using simulation and hardware performance counters. Contrary to its name, the cache oblivious matrix transposition algorithm is found to exhibit a complex cache behavior with a cache miss ratio that is strongly dependent on the associativity of the cache. In some circumstances the cache behavior is found to be worst than that of a na{\"i}ve transposition algorithm. While the total size is an important factor in determining cache usage efficiency, the sub-block size, associativity, and cache line replacement policy are also shown to be very important.",

author = "Dimitrios Tsifakis and Rendell, \{Alistair P.\} and Strazdins, \{Peter E.\}",

year = "2004",

doi = "10.1007/978-3-540-24687-9\_3",

language = "English",

volume = "3037",

pages = "17--25",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Cache oblivious matrix transposition

T2 - Simulation and experiment

AU - Tsifakis, Dimitrios

AU - Rendell, Alistair P.

AU - Strazdins, Peter E.

PY - 2004

Y1 - 2004

N2 - A cache oblivious matrix transposition algorithm is implemented and analyzed using simulation and hardware performance counters. Contrary to its name, the cache oblivious matrix transposition algorithm is found to exhibit a complex cache behavior with a cache miss ratio that is strongly dependent on the associativity of the cache. In some circumstances the cache behavior is found to be worst than that of a naïve transposition algorithm. While the total size is an important factor in determining cache usage efficiency, the sub-block size, associativity, and cache line replacement policy are also shown to be very important.

AB - A cache oblivious matrix transposition algorithm is implemented and analyzed using simulation and hardware performance counters. Contrary to its name, the cache oblivious matrix transposition algorithm is found to exhibit a complex cache behavior with a cache miss ratio that is strongly dependent on the associativity of the cache. In some circumstances the cache behavior is found to be worst than that of a naïve transposition algorithm. While the total size is an important factor in determining cache usage efficiency, the sub-block size, associativity, and cache line replacement policy are also shown to be very important.

UR - https://www.scopus.com/pages/publications/35048820009

U2 - 10.1007/978-3-540-24687-9_3

DO - 10.1007/978-3-540-24687-9_3

M3 - Article

AN - SCOPUS:35048820009

SN - 0302-9743

VL - 3037

SP - 17

EP - 25

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Cache oblivious matrix transposition: Simulation and experiment

Abstract

Access to Document

Other files and links

Fingerprint

Cite this