Improving the memory behavior of vertical filtering in the discrete wavelet transform

ABSTRACT

The discrete wavelet transform (DWT) is used in several image and video compression standards, in particular JPEG2000. A 2D DWT consists of horizontal filtering along the rows followed by vertical filtering along the columns. It is well-known that a straightforward implementation of vertical filtering (assuming a row-major layout) induces many cache misses, due to lack of spatial locality. This can be avoided by interchanging the loops. This paper shows, however, that the resulting implementation suffers significantly from 64K aliasing, which occurs in the Pentium 4 when two data blocks are accessed that are a multiple of 64K apart, and we propose two techniques to avoid it. In addition, if the filter length is longer than four, the number of ways of the L1 data cache of the Pentium 4 is insufficient to avoid cache conflict misses. Consequently, we propose two methods for reducing conflict misses. Although experimental results have been collected on the Pentium 4, the techniques are general and can be applied to other processors with different cache organizations as well. The proposed techniques improve the performance of vertical filtering compared to already optimized baseline implementations by a factor of 3.11 for the (5,3) lifting scheme, 3.11 for Daubechies' transform of four coefficients, and by a factor of 1.99 for the Cohen, Daubechies, and Feauveau 9/7 transform.

REFERENCES

• 1: G. Bernabe, J. M. Garcia, and J. Gonzales. Reducing 3D Wavelet Transform Execution Time Through the Streaming SIMD Extensions. In Proc. 11th Euromicro Conf. on Parallel Distributed and Network based Processing, February 2003.
• 2: R. E. Bryant and D. R. O'Hallaron. Computer Systems: A Programmer's Perspective. Prentice Hall, 2003.
• 3: S. Chatterjee and C. D. Brooks. Cache-Efficient Wavelet Lifting in JPEG 2000. In Proc. IEEE Int. Conf. on Multimedia, pages 797--800, August 2002.
• 4: Daniel Chaver , Christian Tenllado , Luis Piñuel , Manuel Prieto , Francisco Tirado, -D Wavelet Transform Enhancement on General-Purpose Microprocessors: Memory Hierarchy and SIMD Parallelism Exploitation, Proceedings of the 9th International Conference on High Performance Computing, p.9-21, December 18-21, 2002
• 5: D. Chaver , C. Tenllado , L. Piñuel , M. Prieto , F. Tirado, Vectorization of the 2D Wavelet Lifting Transform Using SIMD Extensions, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.228.2, April 22-26, 2003
• 6: B. D. Choi, K. S. Choi, M. C. Hwang, J. K. Cho, and S. J. Ko. Real-time DSP Implementation of Motion-JPEG2000 Using Overlapped Block Transferring and Parallel-Pass Methods. Real-Time Imaging, 10:277--284, 2004.
• 7: C. Chrysafis and A. Ortega. Line-Based, Reduced Memory, Wavelet Image Compression. IEEE Trans. on Image Processing, 9(3):378--389, March 2000.
• 8: A. Cohen, I. Daubechies, and J. C. F. Eauveau. Biorthogonal Bases of Compactly Supported Wavelets. Communications on Pure and Appl. Math., 45(5):485--560, June 1992.
• 9: I. Daubechies and W. Sweldens. Factoring Wavelet Transforms into Lifting Steps. Journal of Fourier Analysis and Applications, 4(3):247--269, 1998.
• 10: D. He and W. Zhang. The Parallel Algorithm of 2-D Discrete Wavelet Transform. In Proc. 4th IEEE Int. Conf. on Parallel and Distributed Computing Applications and Technologies, pages 738--741, August 2003.
• 11: Intel Corporation. IA-32 Intel Architecture Optimization, 2004. Order Number: 248966-011.
• 12: Intel Corporation. The IA-32 Intel Architecture Software Developer's Manual Volume 3 System Programming Guide, 2004. Order Number: 253668.
• 13: Michael W. Marcellin , Ali Bilgin , Michael J. Gormish , Martin P. Boliek, An Overview of JPEG-2000, Proceedings of the Conference on Data Compression, p.523, March 28-30, 2000
• 14: P. Meerwald, R. Norcen, and A. Uhl. Cache Issues with JPEG2000 Wavelet Lifting. In Proc. of Visual Communications and Image Processing, January 2002.
• 15: M. Rabbani and R. Joshi. An Overview of the JPEG2000 Still Image Compression Standard. Signal Processing: Image Communication, 17(1):3--48, January 2002.
• 16: J. A. Shafer. Embedded Vector Processor Architecture for Real-Time Wavelet Video Compression. Master's thesis, Department of Electrical and Computer Eng. University of Dayton, 2004.
• 17: Asadollah Shahbahrami , Ben Juurlink , Stamatis Vassiliadis, Performance Comparison of SIMD Implementations of the Discrete Wavelet Transform, Proceedings of the 2005 IEEE International Conference on Application-Specific Systems, Architecture Processors (ASAP'05), p.393-398, July 23-25, 2005
• 18: A. N. Skodras, C. A. Christopoulos, and T. Ebrahimi. JPEG 2000: The Upcoming Still Image Compression Standard. In Proc. 11th Portugues Conf. on Pattern Recongnition, pages 359--366, May 2000.
• 19: D. B. Stewart. Measuring Execution Time and Real-Time Performance. In Embedded Systems Conf., pages 1--15, April 2001.
• 20: Eric J. Stollnitz , Tony D. Derose , David H. Salesin, Wavelets for computer graphics: theory and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 21: W. Sweldens. The Lifting Scheme: A Custom-Design Construction of Biorthogonal Wavelets. Journal of Applied and Computational Harmonic Analysis, 3(2):186--200, 1996.
• 22: M. A. Trenas, J. Lopez, E. L. Zapata, and F. Arguello. A Memory System Supporting the Efficient SIMD Computation of the Two Dimensional DWT. In IEEE Int. Conf. on Acoustics Speech and Signal Processing, volume 3, pages 1521--1524, May 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Algorithms, Performance

Keywords:
cache, discrete wavelet transform, memory hierarchy, performance