Kang Chen (Master thesis, Computer Science, Drexel University, 2002)
A Prototypical Self-Optimizing Package for Parallel Implementation of Fast Signal Transforms
Published paper (link to publisher)
Bibtex

This thesis 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 fins the best combination of sequential and parallel code leading to effective granularity, load balance, and cache utilization. Experimental data are presented in the thesis showing the performance of the package on four different architectures. Results are also presented showing the optimizations required to obtain nearly linear speedup on these sample symmetric multiprocessors.

Keywords:
Multithreading, Walsh-Hadamard transform, Parallel processing