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

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

2 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 - 1 Dec 2004
Externally published	Yes

Access to Document

10.1007/978-3-540-24687-9_3Licence: In Copyright

Fingerprint Dive into the research topics of 'Cache oblivious matrix transposition: Simulation and experiment'. Together they form a unique fingerprint.

Cite this

@article{44daf80c8513433db28cc5d5a5e477e3,

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",

month = dec,

day = "1",

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

language = "English",

volume = "3037",

pages = "17--25",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - JOUR

T1 - Cache oblivious matrix transposition

T2 - Simulation and experiment

AU - Tsifakis, Dimitrios

AU - Rendell, Alistair P.

AU - Strazdins, Peter E.

PY - 2004/12/1

Y1 - 2004/12/1

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 - http://www.scopus.com/inward/record.url?scp=35048820009&partnerID=8YFLogxK

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

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

M3 - Article

AN - SCOPUS:35048820009

VL - 3037

SP - 17

EP - 25

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -