Slipstream Transcomputation of the Fast Fourier Transform

Abstract

Computation based on a total arithmetic eliminates the need to handle arithmetical exceptions, which is one of the major obstacles to the exploitation of fine-grain, massive, multi-processor architectures. We have been designing and investigating a family of fine-grained architectures that exploit exception-free arithmetic to implement a statically assigned, systolic, dataflow technique that we call ``slipstreaming.'' In this paper, we report on the simulation of a slipstreamed implementation of the Fast Fourier Transform (FFT), which is an important numerical algorithm in engineering. We consider its properties and compilation challenges. The compilation challenges additionally include using the output of the FFT to dynamically compute a match against a fixed target. We find, empirically, that the latency is a good aproximation to linear in the number of sample points transformed by the FFT.