Computation reuse in domain-specific optimization of signal recognition

ABSTRACT

Domain-specific optimizations that exploit specific arithmetic and representation formats have been shown to achieve significant performance/area gains in FPGA hardware designs. In this work, we describe an approach to domain-specific optimization that goes beyond this representation level. We perform a joint optimization from a high-level mathematical abstract representation and hardware implementation point of view. We focus on a signal recognition system that distinguishes between spoken digits. We construct transform matrices from Walsh wavelet packets in conjunction with a BestBasis algorithm. The resulting transform matrices exhibit a rich algebraic structure and contain significant overlap across rows, exhibiting significant computation reuse in the dot-product operation of the transform matrix applied to the signal vector. We have developed an algorithm for identifying the computation reuse and scheduling the row computations across various computation units to significantly reduce the overall amount of computation.

We have implemented a custom-built dot-product multiplication unit targeting a Virtex-II-Pro FPGA device that exploits computation reuse. A baseline dot-product multiplication unit, without reuse, exhibits a maximum clock rate of 199.3 MHz while utilizing only 2% of the device capacity. The optimized system that exploits reuse also includes a computation scheduler and attains a respectable clock rate of 196 MHz while using 8,183 (57%) slices of the FPGA device. The FPGA hardware implementation reduces the amount of computation for an individual matrix by as much as 6.35× and an average of 2× for a single pipelined dot-product unit over the baseline implementation. Although it is larger in area than the baseline, the implementation that exploits reuse even achieves a 2× computation reduction when compared to 3 concurrently-executing simpler accumulation units with the same aggregate FPGA design area.

While the results in this paper reflect the opportunities of a specific signal processing problem, this work highlights the concept of exploiting computation reuse derived from a higher-level abstract representation at a mathematical and hardware level. As such, we believe this approach can also be leveraged in other signal recognition problems with specific well-characterized computational structures and signal dictionaries.

REFERENCES

• 1: R. Coifman and M. Wickerhauser. Entropy-based algorithms for best basis selection. IEEE Trans. on Information Theory, 38(2):713--718, 1992.
• 2: Paolo D'Alberto , Peter A. Milder , Aliaksei Sandryhaila , Franz Franchetti , James C. Hoe , Jose M. F. Moura , Markus Puschel , Jeremy R. Johnson, Generating FPGA-Accelerated DFT Libraries, Proceedings of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.173-184, April 23-25, 2007 [doi>10.1109/FCCM.2007.34]
• 3: Michael deLorimier , André DeHon, Floating-point sparse matrix-vector multiply for FPGAs, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046203]
• 4: Melina Demertzi , Pedro Diniz , Mary W. Hall , Anna C. Gilbert , Yi Wang, A Combined Hardware/Software Optimization Framework for Signal Representation and Recognition, Proceedings of the 7th international conference on Computational Science, Part I: ICCS 2007, p.1230-1237, May 27-30, 2007, Beijing, China [doi>10.1007/978-3-540-72584-8_160]
• 5: Yong Dou , S. Vassiliadis , G. K. Kuzmanov , G. N. Gaydadjiev, 64-bit floating-point FPGA matrix multiplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046204]
• 6: Matteo Frigo, A fast Fourier transform compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.169-180, May 01-04, 1999, Atlanta, Georgia, United States
• 7: O. C. D. G. A. N. M. Peardon. High performance scientific computing using FPGAs with IEEE floating point and logarithmic arithmetic for lattice QCD. In Proc. of the Intl. Conf. on Field Programmable Logic and Applications (FPL'06), pages 1--6, August 2006.
• 8: M. Puschel, J. Moura, J. Johnson, D. Padua, M. Veloso, B. Singer, J. Xiong, F. Franchetti, A. Gacic, Y. Voronenko, K. Chen, R. Johnson, and N. Rizzolo. Spiral: Code generation for dsp transforms. Proc. of the IEEE special issue on Program Generation, Optimization, and Adaptation, 93(2):232--275, 2005.
• 9: N. Saito and R. Coifman. Local discriminant bases. Mathematical Imaging: Wavelet Applications in Signal and Image Processing, Proc. SPIE, 2303, July 1994.
• 10: Ling Zhuo , Viktor K. Prasanna, Sparse Matrix-Vector multiplication on FPGAs, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046202]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

General Terms:
Design, Performance

Keywords:
computation reuse, fpga, signal recognition