| author: | Mihai Furis, Paweł Hitczenko and Jeremy Johnson |
|---|---|
| title: | Cache miss analysis of WHT algorithms |
| keywords: | Cache, Divide and Conquer Recurrences, Geometric Distributions, Memory Access Patterns, Performance Analysis, Random Compositions, Walsh-Hadamard Transform |
| 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. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Mihai Furis and Paweł Hitczenko and Jeremy Johnson (2005), Cache miss analysis of WHT algorithms, in 2005 International Conference on Analysis of Algorithms, Conrado Martínez (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AD, pp. 115-124 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dmAD0111.ps.gz (89 K) |
| ps-source: | dmAD0111.ps (227 K) |
| pdf-source: | dmAD0111.pdf (126 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.