Slipstream Transcomputation of the Fast Fourier Transform
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.
Copyright (c) 2019 Stephen Leach
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors retain copyright and, if appropriate, performance rights but licence the journal to publish submissions. The lead author confirms that the submission is bound by the CC Attributtion Share Alike 4.0 licence.