|
Abstract : |
The Walsh-Hadamard Transform (WHT) is an important algorithmin signal processing because of its simplicity. However, in computing large size WHT, non-unit stride access results in poor cache performance leading to severe degradation in performance. This poor cache performance is also a critical problem in achieving high performance in other large size signal transforms. In this paper, we develop a cache friendly technique that improves the performance of large size WHT. In our approach, data reorganization is performed between computationstages to reduce cache pollution. Furthermore, we develop an efficient search algorithm to determine the optimal factorization tree based upon problem size and stride access in the decomposition. Experimental results show that our approach achieves upto 180%performance improvement over the state of the art package on Alpha 21264 and MIPS R10000. In addition, the proposed optimization is applicable to other signal transforms and is portable across various platforms., |
