Skip to Main content Skip to Navigation
Conference papers

Cache miss analysis of WHT algorithms

Abstract : On modern computers memory access patterns and cache utilization are as important, if not more important, than operation count in obtaining high-performance implementations of algorithms. In this work, the memory behavior of a large family of algorithms for computing the Walsh-Hadamard transform, an important signal processing transform related to the fast Fourier transform, is investigated. Empirical evidence shows that the family of algorithms exhibit a wide range of performance, despite the fact that all algorithms perform the same number of arithmetic operations. Different algorithms, while having the same number of memory operations, access memory in different patterns and consequently have different numbers of cache misses. A recurrence relation is derived for the number of cache misses and is used to determine the distribution of cache misses over the space of WHT algorithms.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184035
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 3:52:06 PM
Last modification on : Friday, June 28, 2019 - 1:40:04 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:28 AM

File

dmAD0111.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184035, version 1

Collections

Citation

Mihai Furis, Paweł Hitczenko, Jeremy Johnson. Cache miss analysis of WHT algorithms. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.115-124. ⟨hal-01184035⟩

Share

Metrics

Record views

145

Files downloads

630