Mihai Furis ; Paweł Hitczenko ; Jeremy Johnson - Cache miss analysis of WHT algorithms

dmtcs:3363 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3363
Cache miss analysis of WHT algorithmsArticle

Authors: Mihai Furis 1; Paweł Hitczenko 2; Jeremy Johnson 1

  • 1 Computer Science Department [Drexel]
  • 2 Department of mathematics [Philadelphie]

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.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Walsh-Hadamard Transform,Random Compositions,Performance Analysis,Cache,Divide and Conquer Recurrences,Geometric Distributions,Memory Access Patterns,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]
Funding:
    Source : OpenAIRE Graph
  • ITR/NGS-Intelligent HW/SW Compilers for DSP Applications; Funder: National Science Foundation; Code: 0325687

Consultation statistics

This page has been seen 203 times.
This article's PDF has been downloaded 170 times.