Kang Chen and Jeremy Johnson (Proc. International Parallel and Distributed Processing Symposium (IPDPS), pp. 58-63, 2002)
A Prototypical Self-Optimizing Package for Parallel Implementation of Fast Signal Transforms
Preprint (262 KB)
Published paper (link to publisher)
Bibtex

This paper presents a self-adapting parallel package for computing the Walsh-Hadamard transform (WHT), a prototypical fast signal transform, similar to the fast Fourier transform. Using a search over a space of mathematical formulas representing different algorithms to compute the WHT the package finds the best parallel implementation on a given shared-memory multiprocessor. The search automatically finds the best combination of sequential and parallel code leading to the optimal granularity, load balance, and cache utilization. Experimental results are presented showing the optimizations required to obtain nearly linear speedup on a sample symmetric multiprocessor.

Keywords:
Multithreading, Walsh-Hadamard transform

More information:

Self-adaptable Walsh-Hadamard transform library