Time complexity modeling and the comparison of parallel implementations of Fourier transform algorithms

A model has been developed to permit analysis of the expected execution-time performance of Fourier transform algorithms. This graph theoretic model (AAT model) allows inclusion of algorithm-, architecture-, and technology-related parameters into the computation of time complexity performance measures. The AAT model consists of the specification of a model structure, definition of parameters that comprise the graph, a methodology to perform mapping of algorithm and implementation into the model, and specification of an analysis procedure. As an illustration of the utility of the model, implementations of several Fourier transform algorithms are analyzed. Three of these algorithms; SRFFT, RCFA, and FFCT have the same arithmetic complexity, but have different development and structure. Application of the model for a wide variety of architecture and technology parameter choices shows that these algorithms are not the same in terms of the time complexity. Comparison of results also shows that the algorithm with lowest arithmetic complexity does not necessarily have the lowest time complexity when parameters of the implementation are considered. While this research is concerned with the application of the AAT model to Fourier transform algorithms, the model can be generalized for the analysis of other digital signal processing algorithms