Implementation of 2-D wavelet transform on TESH connected parallel processors

Publisher Website
Google Scholar
Abstract
This paper presents the mapping of the 2-D wavelet transform onto a TESH connected multi-processor system. TESH (Tori connected mESHes) is a recently developed interconnection network. Key features of the network are the following: it is hierarchical, thus allowing exploitation of computation locality as well as easy expansion up to a million processors; it permits efficient VLSI/ULSI realization, and appears to be well suited for 3-D VLSI/ULSI implementation. Specifically, the paper develops a parallel algorithm implementation on TESH network, in such a way so as to completely hide the communication overhead. Correspondingly, the system performance is evaluated both for the TESH and for the familiar MESH network with B/spl times/B blocks of pixels assigned to each PE, 2J+1 taps per H0 and H1 FIR filters, and S stages of wavelet transform. The time complexity of these two implementations are estimated to be O(B/sup 2//spl times/J) for both MESH and TESH networks, under the assumption that B=2/sup S/(J+I) for some non-negative integer I. The TESH network has an additional requirement that J/spl ges/2/sup m//spl middot/(L-1) where 2/sup m/ denotes the size of the Basis Module, and L is the number of levels in TESH's hierarchy. Thus, the performance of a TESH implemented algorithm is comparable with the MESH based algorithm. However, large TESH networks are easier to implement because of the significantly reduced bisection width compared to large MESH networks.

This publication has 9 references indexed in Scilit: