The Parallel Algorithm for the 2-D Discrete Wavelet Transform
This work addresses a performance issue in image-processing algorithms for users of multi-core processors, representing an incremental improvement over existing methods.
The paper tackled the performance bottleneck of the discrete wavelet transform on multi-core CPUs by proposing a new parallel-friendly scheme that rearranges calculations to reduce steps, achieving consistent improvements over the original lifting scheme on 61-core Intel Xeon Phi and 8-core Intel Xeon processors.
The discrete wavelet transform can be found at the heart of many image-processing algorithms. Until now, the transform on general-purpose processors (CPUs) was mostly computed using a separable lifting scheme. As the lifting scheme consists of a small number of operations, it is preferred for processing using single-core CPUs. However, considering a parallel processing using multi-core processors, this scheme is inappropriate due to a large number of steps. On such architectures, the number of steps corresponds to the number of points that represent the exchange of data. Consequently, these points often form a performance bottleneck. Our approach appropriately rearranges calculations inside the transform, and thereby reduces the number of steps. In other words, we propose a new scheme that is friendly to parallel environments. When evaluating on multi-core CPUs, we consistently overcome the original lifting scheme. The evaluation was performed on 61-core Intel Xeon Phi and 8-core Intel Xeon processors.