Geodesic
Cache miss analysis of WHT algorithms
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_249_a11,
     author = {Furis, Mihai and Hitczenko, Pawe{\l} and Johnson, Jeremy},
     title = {Cache miss analysis of {WHT} algorithms},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3363},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3363/}
}
TY  - JOUR
AU  - Furis, Mihai
AU  - Hitczenko, Paweł
AU  - Johnson, Jeremy
TI  - Cache miss analysis of WHT algorithms
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3363/
DO  - 10.46298/dmtcs.3363
LA  - en
ID  - DMTCS_2005_special_249_a11
ER  - 
%0 Journal Article
%A Furis, Mihai
%A Hitczenko, Paweł
%A Johnson, Jeremy
%T Cache miss analysis of WHT algorithms
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3363/
%R 10.46298/dmtcs.3363
%G en
%F DMTCS_2005_special_249_a11
Furis, Mihai; Hitczenko, Paweł; Johnson, Jeremy. Cache miss analysis of WHT algorithms. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3363. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3363/

Cité par Sources :