On the scalability of 2-D discrete wavelet transform algorithms (Q678247)

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\).