|
iDEA: Drexel E-repository and Archives >
Drexel Academic Community >
College of Engineering >
Department of Computer Science >
Faculty Research and Publications (Comp Sci) >
Performance analysis of a family of WHT algorithms
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1860/2541
|
| Title: | Performance analysis of a family of WHT algorithms |
| Authors: | Andrews, Michael
Johnson, Jeremy |
| Issue Date: | 22-Jan-2007 |
| Citation: | Paper presented at the 21st International Parallel and Distributed Processing Symposium, IPDPS 2007, Long Beach, CA |
| Abstract: | This paper explores the correlation of instruction
counts and cache misses to runtime performance for a
large family of divide and conquer algorithms to compute
the Walsh–Hadamard transform (WHT). Previous
work showed how to compute instruction counts
and cache misses from a high–level description of the
algorithm and proved theoretical results about their
minimum, maximum, mean, and distribution. While
the models themselves do not accurately predict performance,
it is shown that they are statistically correlated
to performance and thus can be used to prune
the search space for fast implementations. When
the size of the transform fits in cache the instruction
count itself is used; however, when the transform
no longer fits in cache, a linear combination of
instruction counts and cache misses is used. Thus for
small transforms it is safe to ignore algorithms which
have a high instruction count and for large transforms
it is safe to ignore algorithms with a high value
in the combined instruction count/cache miss model.
Since the models can be computed from a high–level
description of the algorithms, they can be obtained
without runtime measurement and the previous theoretical
results on the models can be applied to limit
empirical search. |
| URI: | http://dx.doi.org/10.1109/IPDPS.2007.370640
http://hdl.handle.net/1860/2541 |
| Appears in Collections: | Faculty Research and Publications (Comp Sci)
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
