Conflict-free parallel memory access scheme for FFT processors

Author

Takala, Jarmo H. ; Jarvinen, T.S. ; Sorokin, Harri T.

Author_Institution

Tampere Univ. of Technol., Finland

Volume

4

fYear

2003

fDate

25-28 May 2003

Abstract

In this paper, a parallel access scheme for constant geometry FFT algorithms is proposed, which allows conflict-free access of operands distributed over parallel memory modules. The scheme is a linear transformation and the address generation is performed with the aid of bit-wise XOR operations. Different FFT lengths can be supported with the aid of a simple address rotation unit. The scheme is general supporting several radices in FFT computations and different numbers of parallel memory modules. The scheme allows parallel butterfly computations independent of the FFT length.

Keywords

digital arithmetic; fast Fourier transforms; parallel memories; signal flow graphs; storage allocation; Cooley-Tukey fast Fourier transform algorithm; FFT lengths; FFT processors; address generation; address rotation unit; bit-wise XOR operations; conflict-free parallel memory access scheme; constant geometry FFT algorithms; linear transformation; parallel butterfly computations; parallel memory modules; signal flow graphs; stride permutation access scheme; Concurrent computing; Delay; Flexible printed circuits; Flow graphs; Geometry; Parallel processing; Partitioning algorithms; Read-write memory; Registers; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on

Print_ISBN

0-7803-7761-3

Type

conf

DOI

10.1109/ISCAS.2003.1205957

Filename

1205957