|
iDEA: Drexel E-repository and Archives >
Drexel Theses and Dissertations >
Drexel Theses and Dissertations >
Cache miss analysis of Walsh-Hadamard transform algorithms
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1860/109
|
| Title: | Cache miss analysis of Walsh-Hadamard transform algorithms |
| Authors: | Furis, Mihai Alexandru |
| Issue Date: | 17-Apr-2003 |
| Abstract: | Processor speed has been increasing at a much greater rate than memory speed leading to the so called processor-memory gap. In order to compensate for this gap in performance, modern computers rely heavily on a hierarchical memory organization with a small amount of fast memory called cache. The true cost of memory access is hidden, provided data can be obtained from cache. Substantial performance improvement in the runtime of a program can be obtained by making intelligent algorithmic choices that better utilize cache. Previous work has largely concentrated on improving memory performance through better cache design and compiler techniques for generating code with better locality. Generally these improvements have been measured by using collections of benchmark programs, simulations and statistical methods. In contrast in this work investigates how the choice of algorithm affects cache performance. This is done for a family of algorithms for computing the Walsh-Hadamard transform a simple yet important algorithm for signal and image processing. The WHT is a particularly good starting point due to the large number of alternative algorithms that can be generated and studied. Moreover the WHT algorithms have an interesting strided memory access pattern that can be analyzed analytically. A procedure is developed to count the number of cache misses for an arbitrary WHT algorithm and this procedure is used to investigate the number of cache misses for different algorithms. |
| URI: | http://dspace.library.drexel.edu/handle/1860/109 |
| Appears in Collections: | Drexel Theses and Dissertations
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
