Files and links (1)
PDFOpen Access (License Unspecified), Open Access
Thesis
Cache miss analysis of Walsh-Hadamard transform algorithms
Master of Science (M.S.), Drexel University
Mar 2003
DOI:
https://doi.org/10.17918/etd-109
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.
Metrics
30 File views/ downloads
17 Record Views
Details
- Title
- Cache miss analysis of Walsh-Hadamard transform algorithms
- Creators
- Mihai Alexandru Furis - DU
- Contributors
- Jeremy Russell Johnson (Advisor) - Drexel University (1970-)
- Awarding Institution
- Drexel University
- Degree Awarded
- Master of Science (M.S.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Resource Type
- Thesis
- Language
- English
- Academic Unit
- College of Engineering (1970-2026); Electrical (and Computer) Engineering [Historical]; Drexel University
- Other Identifier
- 109; 991014632067604721