Formal datapath representation and manipulation for implementing DSP transforms

ABSTRACT

We present a domain-specific approach to representing datapaths for hardware implementations of linear signal transform algorithms. We extend the tensor structure for describing linear transform algorithms, adding the ability to explicitly characterize two important dimensions of datapath architecture. This representation allows both algorithm and datapath to be specified within a single formula and gives the designer the ability to easily consider a wide space of possible datapaths at a high level of abstraction.

We have constructed a formula manipulation system based on this representation and have written a compiler that can translate a formula into a hardware implementation. This enables an automatic "push button" compilation flow that produces a register transfer level hardware description from high-level datapath directives and an algorithm (written as a formula). In our experimental results, we demonstrate that this approach yields efficient designs over a large tradeoff space.

REFERENCES

• 1: J. Astola and D. Akopian. Architecture-oriented regular algorithms for discrete sine and cosine transforms. IEEE Transactions on Signal Processing, 47(4):1109--1124, 1999.
• 2: D. Cohen. Simplified control of FFT hardware. IEEE Transactions on Acoustics, Speech, and Signal Processing, 24(6):577--579, 1976.
• 3: J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of compex Fourier series. Mathematics of Computation, 19(90), 1965.
• 4: N. Dave, M. Pellauer, S. Gerding, and Arvind. 802.11a transmitter: a case study in microarchitectural exploration. In MEMOCODE, 2006.
• 5: J. Granata, M. Conner, and R. Tolimieri. The tensor product: a mathematical programming language for FFTs and other fast DSP operations. Signal Processing Magazine, IEEE, 9(1):40--48, 1992.
• 6: Shousheng He , Mats Torkelson, A New Approach to Pipeline FFT Processor, Proceedings of the 10th International Parallel Processing Symposium, p.766-770, April 15-19, 1996
• 7: P. Kumhom, J. Johnson, and P. Nagvajara. Design, optimization, and implementation of a universal FFT processor. In Proc. 13th IEEE ASIC/SOC Conference, 2000.
• 8: Grace Nordin , Peter A. Milder , James C. Hoe , Markus Püschel, Automatic generation of customized discrete fourier transform IPs, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065703]
• 9: Marshall C. Pease, An Adaptation of the Fast Fourier Transform for Parallel Processing, Journal of the ACM (JACM), v.15 n.2, p.252-264, April 1968 [doi>10.1145/321450.321457]
• 10: M. Püschel, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, B. W. Singer, J. Xiong, F. Franchetti, A. Gačić, Y. Voronenko, K. Chen, R. W. Johnson, and N. Rizzolo. SPIRAL: Code generation for DSP transforms. Proc. of the IEEE, 93(2):232--275, 2005.
• 11: Charles Van Loan, Computational frameworks for the fast Fourier transform, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Design

Keywords:
discrete Fourier transform, high-level synthesis, linear transform, streaming