ON THE SCALABILITY OF 2-D DISCRETE WAVELET TRANSFORM ALGORITHMS

The ability of a parallel algorithm to make efficient use of increasin g computational resources is known as its scalability. In this paper, we develop four parallel algorithms for the 2-dimensional Discrete Wav elet Transform algorithm (2-D DWT), and derive their scalability prope rties on Mesh and Hypercube interconnection networks. We consider two versions of the 2-D DWT algorithm, known as the Standard (S) and Non-s tandard (NS) forms, mapped onto P processors under two data partitioni ng schemes, namely checkerboard (CP) and stripped (SP) partitioning. T he two checkerboard partitioned algorithms on the cut-through-routed ( CT-routed) Mesh are scalable as M(2) = Omega(P log P) (Non-standard fo rm, NS-CP), and as M(2) = Omega(P log(2) P) (Standard form, S-CP); whi le on the store-and-forward-routed (SF-routed) Mesh and Hypercube they are scalable as M(2) = Omega(P-3/3-gamma) (NS-CP), and as M(2) = Omeg a (P-2/2-gamma) (S-CP), respectively, where M(2) is the number of elem ents in the input matrix, and gamma is an element of (0, 1) is a param eter relating M to the number of desired octaves J as J = [gamma log M ]. On the CT-routed Hypercube, scalability of the NS-form algorithms s hows similar behavior as on the CT-routed Mesh. The Standard form algo rithm with stripped partitioning (S-SP) is scalable on the CT-routed H ypercube as M(2) = Omega(P-2), and it is unscalable on the CT-routed M esh. Although asymptotically the stripped partitioned algorithm S-SP o n the CT-routed Hypercube would appear to be inferior to its checkerbo ard counterpart S-CP, detailed analysis based on the proportionality c onstants of the isoefficiency function shows that S-SP is actually mor e efficient than S-CP over a realistic range of machine and problem si zes. A milder form of this result holds on the CT- and SF-routed Mesh, where S-SP would, asymptotically, appear to be altogether unscalable.