Computer Generation of Hardware for Linear Digital Signal Processing Transforms

Peter A. Milder, Franz Franchetti, James C. Hoe, Markus PüschelACM Trans. Design Autom. Electr. Syst 2012 · DOI

TL;DR

This paper introduces Spiral, a framework that automatically generates hardware implementations for linear signal processing transforms like the DFT. By using a high-level mathematical language to describe both algorithms and hardware structures, Spiral can explore a vast design space and produce optimized hardware that rivals hand-designed solutions, significantly easing the burden on hardware designers.

What Problem Does This Paper Address?

Designing efficient hardware for linear signal processing transforms, such as the Discrete Fourier Transform (DFT), is a complex challenge. This complexity arises from the multitude of algorithmic options (e.g., various FFT algorithms) and the numerous ways these algorithms can be mapped to hardware architectures (datapaths). The optimal choice for an algorithm and datapath is highly dependent on specific performance goals and resource constraints, making manual exploration a time-consuming and difficult process. Designers often resort to using pre-built IP cores, which may not meet the increasingly demanding requirements of modern applications. This paper aims to automate this design process, allowing for the exploration of a wide range of cost/performance trade-offs.

Methods

The core of the proposed solution is the Spiral framework, which leverages a domain-specific, formula-based language called SPL (Signal Processing Language).

  • Algorithm Specification (SPL): SPL uses a mathematical formalism, extending matrix algebra, to represent transform algorithms as formulas. These formulas explicitly capture the structure and regularity of algorithms, allowing them to be translated into combinational datapaths.
  • Hardware Specification (HSPL): To address hardware implementation details, SPL is extended into HSPL (Hardware SPL). HSPL introduces concepts like "streaming reuse" (reusing hardware over multiple cycles for parallel data streams) and "iterative reuse" (reusing a single hardware block multiple times). These are represented by specific tags within the formulas.
  • Automatic Compilation: The framework consists of several stages:
  • Formula Generation: Selects an appropriate algorithm and generates an SPL formula.
  • Formula Rewriting: Uses the HSPL tags (e.g., stream(w), depth(d)) to rewrite the SPL formula into an HSPL formula, explicitly describing the desired sequential datapath structure. This stage also performs optimizations.
  • RTL Generation: Translates the HSPL formula into a synthesizable Register-Transfer Level (RTL) Verilog description.

Datasets

Not discussed in the paper. The paper focuses on generating hardware for transforms based on mathematical specifications, not on training models with datasets.

Key Insights and Ideas

  • Unified Language for Algorithm and Hardware: The key innovation is using a single mathematical language (SPL/HSPL) to describe both the transform algorithm and its hardware implementation, including reuse strategies. This bridges the gap between algorithmic design and hardware architecture.
  • Automated Design Space Exploration: By parameterizing algorithms and reuse strategies within formulas, Spiral can automatically explore a vast design space, generating implementations that span a wide range of cost/performance trade-offs.
  • Hardware Reuse Strategies: The formalization of "streaming reuse" and "iterative reuse" provides a powerful way to describe and generate efficient hardware structures that balance parallelism, latency, and resource utilization.
  • Pareto Optimality: The paper demonstrates that the generated designs can achieve Pareto optimality, meaning they represent the best possible trade-offs between metrics like throughput and area for a given set of constraints.

Key Results

  • Competitive Performance: Generated hardware designs for transforms like DFT, DCT, and RDFT on FPGAs and ASICs match or exceed the performance of existing hand-designed IP cores and commercial solutions.
  • Wide Trade-off Space: The system can generate designs that are up to 76 times faster than the slowest but require significantly more resources, demonstrating the ability to span a broad cost/performance spectrum.
  • Flexibility: The framework allows designers to specify hardware directives (e.g., streaming width, iterative reuse depth) to tailor implementations to specific application needs. For example, for DFT256, designs with different radices, iterative reuse depths, and streaming widths were generated and evaluated, showing how these parameters influence performance and resource usage.
  • ASIC and FPGA Targets: The system successfully targets both FPGAs (Xilinx Virtex-6) and ASICs (65nm standard cell library), demonstrating its versatility.

Limitations and Future Work

  • Limited Transform Types: While the system handles a good range of linear transforms, it is primarily focused on those expressible within the SPL framework.
  • Complexity of Memory: The paper mentions that memory compilation was not fully integrated, relying on external tools like CACTI for estimation, which could be a limitation for highly memory-intensive designs.
  • Future Work: The authors suggest extending the framework to support more complex transforms, exploring more sophisticated memory models, and further refining the optimization capabilities. They also highlight the potential for integrating this into a more comprehensive design flow.

Summary updated

BibTeX
@article{milder2012computer,
  author = {Peter A. Milder and Franz Franchetti and James C. Hoe and Markus Püschel},
  title = {{Computer Generation of Hardware for Linear Digital Signal Processing Transforms}},
  journal = {ACM Trans. Design Autom. Electr. Syst.},
  year = {2012},
  doi = {10.1145/2159542.2159547},
}
Figure