A single-loop approach to SIMD parallelization of 2D wavelet lifting
Author:
Open Access
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10666192,p. 8 pp.
Abstract
Widespread use of wavelet transforms as in JPEG2000 demands efficient implementations on general purpose computers as well as dedicated hardware. The increasing availability of SIMD technologies is a great challenge since efficient SIMD parallelizations are not trivial. This work presents a parallelized 2D wavelet transform following a single-loop approach, i.e. a loop fusion of the lifting steps of horizontal filtering, and interleaving horizontal and vertical filtering for optimal temporal locality. In this way, each input value is read only once and each output value is written once without subsequent updates. Such an approach turns out to be a necessary basis for an efficient SIMD parallelization. Results are obtained on a general purpose processor with a 4-fold single-precision SIMD extension. Speedups of about 3.7 due to the use of SIMD, 2.55 due to the single-loop approach and up to 6 due to cache effects for pathologic data sizes are obtained, giving total speedups of up to 56.Keywords
This publication has 13 references indexed in Scilit:
- Cache issues with JPEG2000 wavelet lifting2002
- Optimization of 3-D Wavelet Decomposition on MultiprocessorsJournal of Computing and Information Technology, 2000
- Line-based, reduced memory, wavelet image compressionIEEE Transactions on Image Processing, 2000
- Hardware and Software Aspects for 3-D Wavelet Decomposition on Shared Memory MIMD ComputersLecture Notes in Computer Science, 1999
- Factoring wavelet transforms into lifting stepsJournal of Fourier Analysis and Applications, 1998
- The Lifting Scheme: A Construction of Second Generation WaveletsSIAM Journal on Mathematical Analysis, 1998
- A new, fast, and efficient image codec based on set partitioning in hierarchical treesIEEE Transactions on Circuits and Systems for Video Technology, 1996
- The Lifting Scheme: A Custom-Design Construction of Biorthogonal WaveletsApplied and Computational Harmonic Analysis, 1996
- Efficient realizations of the discrete and continuous wavelet transforms: from single chip implementations to mappings on SIMD array computersIEEE Transactions on Signal Processing, 1995
- Wavelet transform on parallel SIMD architectures1993