Conference proceeding
Cache miss analysis of WHT algorithms
Discrete Mathematics and Theoretical Computer Science, v DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms(Proceedings), pp 115-124
01 Jan 2005
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.
Metrics
16 Record Views
Details
- Title
- Cache miss analysis of WHT algorithms
- Creators
- Mihai Furis - Laboratoire d'Informatique de Paris-NordPaweł Hitczenko - Department of mathematics [Philadelphie]Jeremy Johnson - Laboratoire d'Informatique de Paris-Nord
- Publication Details
- Discrete Mathematics and Theoretical Computer Science, v DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms(Proceedings), pp 115-124
- Conference
- 2005 International Conference on Analysis of Algorithms (2005)
- Series
- DMTCS Proceedings
- Publisher
- DMTCS
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science; Mathematics
- Other Identifier
- 991020532106204721