DocumentCode :
1250155
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
Volume :
48
Issue :
9
fYear :
1999
fDate :
9/1/1999 12:00:00 AM
Firstpage :
951
Lastpage :
960
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;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.795223
Filename :
795223
Link To Document :
بازگشت