SPIRAL WHT Package
What is it?
A very efficient C package for computing the Walsh-Hadamard transform (WHT) of arbitrary size 2n. The package is adaptable, i.e., it optimizes itself to the computing platform where it is installed. The package easily installs (configure - make) on Unix/Linux platforms including SMP platforms.
Overview
The WHT (Walsh-Hadamard transform) of size 2n is defined as the matrix-vector multiplication WHT(2n)*x, where
where 
denotes the 2-point DFT. We compute the WHT by using different recursive breakdown strategies. Combination of these strategies yields a large number of different breakdown trees corresponding to different algorithms. These algorithms differ in their data access during computation, but have all the same arithmetic cost (exactly n * 2n for a WHT(2n)). We adapt the package by searching in this algorithm space for the best match to the given computing platform. For more information we refer to the README file in the package. The design of our WHT package is based on an FFT package by Sebastian Egner.
Benchmarks
Have a look at the best trees and runtimes for different architectures, found using dynamic programming. Note the big differences: the best trees are very platform-dependent.
- Alpha 21264, 500 MHz
- Alpha 21264, 500 MHz (using splitddl)
- Athlon, 1100 MHz
- Athlon, 1100 MHz (using splitddl)
- Pentium II MMX, 450 MHz (no improvement through splitddl)
- Pentium III mobile, 650 MHz (no improvement through splitddl)
- Power PC, 450 MHz
- Power PC, 450 MHz (using splitddl)
- UltraSparc IIi, 300 MHz
- UltraSparc IIi, 300 MHz (using splitddl)
- UltraSparc II, 450 MHz (no improvement through splitddl)
Download
The most recent version (1.8) of the WHT package is available for download here. File size is 170 KB.Change History
| v1.8 | 05/16/03 | Minor memory leakage removed. |
| v1.7 | 04/02/02 | Support for multiprocessor machines using OpenMP. |
| v1.6 | 03/01/02 | Ported to Mac OS X (Darwin). Benchmark tool added. |
| v1.5 | 01/22/02 | Loop interleaving extended to five levels. |
| v1.4 | 12/03/01 | Loop interleaving added. Measure method changed |
| v1.3 | 12/05/00 | Better installation on alphas |
| v1.2 | 11/21/00 | New split method "splitddl" integrated |
| v1.1 | 08/08/00 | Pcl profiling added |
| v1.0 | 08/01/00 | Bug removed which affects left expanded trees; simpler, automated installation and genetic algorithm added. |
| v0.0 | 05/10/99 | First version of WHT package released. |
References
- Kang Chen and Jeremy Johnson
A Prototypical Self-Optimizing Package for Parallel Implementation of Fast Signal Transforms
Proc. International Parallel and Distributed Processing Symposium (IPDPS), pp. 58-63, 2002 - Neungsoo Park and Viktor K. Prasanna
Cache Conscious Walsh-Hadamard Transform
Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 2, pp. II-1205-II-1208, 2001 - Jeremy Johnson and Markus Püschel
In Search of the Optimal Walsh-Hadamard Transform
Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vol. 6, pp. 3347-3350, 2000 - More of our WHT papers