Handling Large-size Discrete Wavelet Transform On Network-based Computing Systems - Parallelization Via Divisible Load Paradigm

摘要

The discrete wavelet transform (DWT) is a powerful signal processing tool, but comes with a considerable computation cost. In this paper, we consider the problem of parallelizing the DWT computation on loosely-coupled networked systems. We first systematically analyze the data dependencies among DWT computations, identify the partitionable portions and then by applying the divisible load theory (DLT), we derive a novel scheduling strategy to schedule DWT computation onto bus networks. Our study is first of its kind in the DLT literature to demonstrate handling a highly coupled recursive computational nature of this problem towards gaining a significant speed-up.rnWe conduct a wide variety of rigorous simulation experiments to quantify the performance of our strategy. Results demonstrate that using the proposed method of scheduling, the parallel DWT computation scales significantly with respect to the input signal size, with no compromise in performance observed when the input size was increased. However, the algorithm is shown to be sensitive to the speed (delay) of the communication channel.