University of Calgary
In this paper the authors present several parallel FFT algorithms with different degree of communication overhead for multiprocessors in Network-on-Chip (NoC) environment. Three different methods of parallel FFT are presented. One is the reference parallel FFT for comparison and the other two with well-distributed computation as well as reduced communication overhead. By evenly distributing parallel computation tasks which uses data locality, the execution time for completing each stage of FFT can be reduced. Moreover, by optimizing data exchanges they minimize the communication overhead.