Algorithmic-level exploration of discrete signal transforms for partitioning to distributed hardware architectures

High-level partitioning is an essential process for obtaining effective algorithm implementations to distributed hardware architectures (DHAs). Discrete signal transforms (DST) in general have well-known algorithmic properties that can be exploited to improve their partitioning in hardware implementations. A high-level partitioning methodology which uses formulation-level discrete signal transform properties to guide DST partitioning onto DHAs is introduced. It has been discussed how such characteristics were taken into account to focus design exploration during partitioning. A set of experiments carried to determine the effect of formulation-level properties on solution quality are also presented. Perceived patterns in experimental results were used to generate ´partition-friendly´ fast Fourier transform (FFT) formulations for DHAs. Results for various FFT sizes achieved over 21% reduction in estimated latency over a general-purpose high-level partitioning method.