Title :
Parallel implementation of multidimensional transforms without interprocessor communication
Author :
Marino, Francescomaria ; Swartzlander, Earl E., Jr.
Author_Institution :
Dipt. di Ingegneria Elettrotecnica ed Elettronica, Politecnico di Bari, Italy
fDate :
9/1/1999 12:00:00 AM
Abstract :
Presents a modular algorithm which is suitable for computing a large class of multidimensional transforms in a general-purpose parallel environment without interprocessor communication. Since it is based on matrix-vector multiplication, it does not impose restrictions on the size of the input data as many existing algorithms do. The method is fully general, since it does not depend on the specific nature of the transform kernel and, therefore, it may be used for a wide variety of transforms. Moreover, since some 1D fast Fourier transform algorithms map the input sequence onto two or more dimensions, the new method also may be employed to efficiently compute the 1D FFT in parallel. In addition, the proposed algorithm is exploited to derive a fully systolic VLSI architecture performing multidimensional transforms, which does not need the transposer required by classical architectures
Keywords :
VLSI; fast Fourier transforms; mathematics computing; matrix multiplication; parallel algorithms; systolic arrays; transforms; vectors; 1D fast Fourier transform algorithms; general-purpose parallel environment; input data size; input sequence mapping; interprocessor communication; matrix-vector multiplication; modular algorithm; multidimensional transforms; parallel implementation; systolic VLSI architecture; transform kernel; Computer architecture; Computer vision; Concurrent computing; Discrete Fourier transforms; Discrete transforms; Fast Fourier transforms; Fourier transforms; Kernel; Multidimensional systems; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on