The fast Fourier transform as a test case for a systolic data flow machine

A fast Fourier transform (FFT) algorithm is mapped onto a suggested processing element topology in order to demonstrate the utility of the systolic data flow machine (SDFM) approach. The SDFM is based on the partitioning of dataflow programs (graphs) into subgraphs that are small enough that they can be loaded into programmable systolic arrays, called processing elements. Mapability and performance criteria are suggested, such as the number of allocated primitive processors (in a systolic array) and the number of primitive processors and systolic arrays that are active at any one time. Conclusions about system attributes, such as the ratio of local to global communication, granularity, instruction execution and communication time, parallelism, processor utilization, are also presented