2. |
- Kiselyov, Oleg, et al.
(författare)
-
Relating FFTW and Split-Radix
- 2004
-
Ingår i: Embedded Software and Systems. - Berlin : Springer Berlin/Heidelberg. - 9783540281283 - 9783540318231 ; , s. 488-493
-
Konferensbidrag (refereegranskat)abstract
- Recent work showed that staging and abstract interpretation can be used to derive correct families of combinatorial circuits, and illustrated this technique with an in-depth analysis of the Fast Fourier Transform (FFT) for sizes 2n. While the quality of the generated code was promising, it used more floating-point operations than the well-known FFTW codelets and split-radix algorithm. This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms. © Springer-Verlag Berlin Heidelberg 2005.
|
|