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.

In these tables we omitted small for brevity.

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