On the Scalability of 2-D Discrete Wavelet Transform Algorithms |
| |
Authors: | Fridman José Manolakos Elias S |
| |
Affiliation: | (1) Communications and Digital Signal Processing (CDSP), Center for Research and Graduate Studies, Electrical and Computer Engineering Department, Northeastern University, 409 Dana Research Building, Boston, MA, 02115 |
| |
Abstract: | The ability of a parallel algorithm to make efficient use of increasing computational resources is known as its scalability. In this paper, we develop four parallel algorithms for the 2-dimensional Discrete Wavelet Transform algorithm (2-D DWT), and derive their scalability properties on Mesh and Hypercube interconnection networks. We consider two versions of the 2-D DWT algorithm, known as the Standard (S) and Non-standard (NS) forms, mapped onto P processors under two data partitioning schemes, namely checkerboard (CP) and stripped (SP) partitioning. The two checkerboard partitioned algorithms
(Non-standard form, NS-CP), and as
(Standard form, S-CP); while on the store-and-forward-routed (SF-routed) Mesh and Hypercube they are scalable as
(NS-CP), and as
(S-CP), respectively, where M
2 is the number of elements in the input matrix, and (0,1) is a parameter relating M to the number of desired octaves J as
. On the CT-routed Hypercube, scalability of the NS-form algorithms shows similar behavior as on the CT-routed Mesh. The Standard form algorithm with stripped partitioning (S-SP) is scalable on the CT-routed Hypercube as M
2 = (P
2), and it is unscalable on the CT-routed Mesh. Although asymptotically the stripped partitioned algorithm S-SP on the CT-routed Hypercube would appear to be inferior to its checkerboard counterpart S-CP, detailed analysis based on the proportionality constants of the isoefficiency function shows that S-SP is actually more efficient than S-CP over a realistic range of machine and problem sizes. A milder form of this result holds on the CT- and SF-routed Mesh, where S-SP would, asymptotically, appear to be altogether unscalable. |
| |
Keywords: | wavelets scalability parallel processing |
本文献已被 SpringerLink 等数据库收录! |
|