On the abstracted dataflow complexity of Fast Fourier Transforms
Alexander Boehm, Robert E. Hiromoto, K.A. Kelly, John M. Ashley · University of North Texas Digital Library (University of North Texas) · 1992
In this paper we develop and analyze the simulated performance of codes for the Fast Fourier Transform written in If and targeted for execution on Motorola's dataflow machine Monsoon. The FFT application is of interest because of its computational parallelism, its requirement for global communications, and its array element data dependences. We use the parallel profiling simulator Id World to study the dataflow performance of various implementations. Our approach is comparative. We study two approaches, a recursive and an iterative one, and in each version we examine the effect of a variety of implementations. We contend that only through such comparative evaluations can significant insight be gained in understanding the computational and structural details of functional algorithms.