Coarse-Grained Parallel Algorithms for Multi-Dimensional Wavelet Transforms

摘要

This paper presents parallel algorithms for computing multi-dimensional wavelet transforms on both shared memory and distributed memory machines. Traditional data partitioning methods for n-dimensional Discrete Wavelet Transforms (DWTs) call for data redistribution once a one dimensional wavelet transform is Computed along each dimension. To avoid the data communication inherent in this redistribution, two new Partitioning methods called CRBP (Communication Reduced Block Partitioning) and CRLP (Communication Reduced Layer Partitioning) are proposed.