Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Kang Chen and Jeremy Johnson (Proc. IEEE 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 transformMore information: