On the scalability of 2-D discrete wavelet transform algorithms
The paper describes four parallel algorithms for the 2-D discrete wavelet transform. Two versions of the 2-D discrete wavelet transform algorithm, the standard (S) and non-standard (NS) form, are considered. The scalability (i.e., the ability to make use of increasing computational resources) of these parallel algorithms is studied on hypercube- and Mesh-connected networks with \(P\) processing elements, and the data partitioning schemes used are checkerboard (CP) and stripped (SP) partitioning. The results are summarized in the following table (CT and SF denotes a cut-through-routed and store-and-forward Mesh or Hypercube, respectively): \[ \begin{matrix} \text{Network} & \vrule & \text{NS-CP} & \text{S-SP} & \text{S-CP} & \text{NS-SP}\phantom{y} \\ \noalign {\hrule} \text{CT Hypercube} & \vrule & \Omega (P\log P) & \Omega (P^2) & \Omega (P\log^2P) & \Omega (P^2) \\ \text{CT Mesh} & \vrule & \Omega (P\log P) & \text{unscalable} & \Omega (P\log^2P) & \Omega (P^2)\\ \text{SF Mesh, Hypercube} & \vrule & \Omega (P^{3/(3-\gamma)}) & \text{unscalable} & \Omega (P^{2/(2-\gamma)}) & \Omega(P^2) \end{matrix} \] The parameter \(\gamma\) relates the square root \(M\) of the number of input elements to the total number of octaves \(J=\lceil \gamma \log M\rceil\).
- A fine-grain load-adaptive algorithm of the 2D discrete wavelet transform for multithreaded architectures
- Parallelizing Mallat algorithm for 2-D wavelet transforms
- Parallel performance of fast wavelet transforms
- Translation-invariant two-dimensional discrete wavelet transform on graphics processing units
- scientific article; zbMATH DE number 833639 (Why is no real title available?)
This page was built for publication: On the scalability of 2-D discrete wavelet transform algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q678247)
