Building Conflict-Free FFT Schedules

Author

Richardson, Stephen ; Markovic, Dejan ; Danowitz, Andrew ; Brunhaver, John ; Horowitz, Mark

Author_Institution

Stanford Univ., Stanford, CA, USA

Volume

62

Issue

4

fYear

2015

fDate

Apr-15

Firstpage

1146

Lastpage

1155

Abstract

A conflict-free schedule lets an FFT run to completion without ever having to pause for memory-conflict resolution. We show how to build such schedules for FFTs having any number of butterfly units B operating at any radix R, transforming any number of datapoints D. Our algorithm works for FFT datapaths with or without pipeline overlap, and for memory banks having any number of access ports. Specifically, it enables construction of conflict-free schedules using single-ported memory banks, which require less area than more traditional multi-ported designs.

Keywords

channel bank filters; fast Fourier transforms; telecommunication scheduling; FFT datapaths; butterfly units; conflict-free FFT schedules; fast Fourier transform; memory-conflict resolution; pipeline overlap; single-ported memory banks; Algorithm design and analysis; Hardware; Memory management; Pipelines; Random access memory; Schedules; Transforms; Conflict-free scheduling; FFT; digital signal processor; fast Fourier transform; single-ported memory;

fLanguage

English

Journal_Title

Circuits and Systems I: Regular Papers, IEEE Transactions on

Publisher

ieee

ISSN

1549-8328

Type

jour

DOI

10.1109/TCSI.2015.2402935

Filename

7070875