Architectures and APIs: assessing requirements for delivering FPGA performance to applications

ABSTRACT

Reconfigurable computing leveraging field programmable gate arrays (FPGAs) is one of many accelerator technologies that are being investigated for application to high performance computing (HPC). Like most accelerators, FPGAs are very efficient at both dense matrix multiplication and FFT computations, but two important aspects of how to deliver that performance to applications have received too little attention. First, the standard API for important compute kernels hides parallelism from the system. Second, the issue of system architecture is virtually never addressed. This paper explores both issues and their implications for applications. We find that high bandwidth, low latency connectivity can be important, but the right API can be even more important.

REFERENCES

• 1: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 2: 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]
• 3: 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]
• 4: Frigo, M., and Johnson, S. G. 1998. FFTW: An adaptive software architecture for the FFT. In Proceedings of International Conference on Acoustics, Speech and Signal Processing, vol. 3, 1381--1384.
• 5: Govindu, G., Zhuo, L., Choi, S., Gundala, P., and Prasanna, V. K. 2003. Area and power performance analysis of a floating-point based application on FPGAs. In Proceedings of the Seventh Annual Workshop on High Performance Embedded Computing (HPEC 2003).
• 6: Govindu, G., Choi, S., Prasanna, V. K., Daga, V., Gangadharpalli, S., and Sridhar, V. 2004. A high-performance and energy-efficient architecture for floating-point based lu decomposition on fpgas. In Proceedings of the 11th Reconfigurable Architectures Workshop (RAW).
• 7: Govindu, G., Zhuo, L., Choi, S., Gundala, P., and Prasanna, V. K. 2004. Analysis of high-performance floating-point arithmetic on FPGAs. In Proceedings of the 11th Reconfigurable Architectures Workshop (RAW).
• 8: K. Scott Hemmert , Keith D. Underwood, An Analysis of the Double-Precision Floating-Point FFT on FPGAs, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'05), p.171-180, April 18-20, 2005 [doi>10.1109/FCCM.2005.16]
• 9: Janssen, C. Personal communications.
• 10: Volodymyr Kindratenko , David Pointer, A case study in porting a production scientific supercomputing application to a reconfigurable computer, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06), p.13-22, April 24-26, 2006 [doi>10.1109/FCCM.2006.5]
• 11: Gerald R. Morris , Viktor K. Prasanna , Richard D. Anderson, A Hybrid Approach for Mapping Conjugate Gradient onto an FPGA-Augmented Reconfigurable Supercomputer, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06), p.3-12, April 24-26, 2006 [doi>10.1109/FCCM.2006.8]
• 12: Plimpton, S. J., Pollock, R., and Stevens, M. 1997. Particle-mesh ewald and rRESPA for parallel molecular dynamics. In Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing.
• 13: Steve Plimpton, Fast parallel algorithms for short-range molecular dynamics, Journal of Computational Physics, v.117 n.1, p.1-19, March 1, 1995 [doi>10.1006/jcph.1995.1039]
• 14: Ronald Scrofano , Maya Gokhale , Frans Trouw , Viktor K. Prasanna, Hardware/Software Approach to Molecular Dynamics on Reconfigurable Computers, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06), p.23-34, April 24-26, 2006 [doi>10.1109/FCCM.2006.46]
• 15: Justin L. Tripp , Henning S. Mortveit , Anders A. Hansson , Maya Gokhale, Metropolitan Road Traffic Simulation on FPGAs, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'05), p.117-126, April 18-20, 2005 [doi>10.1109/FCCM.2005.46]
• 16: Keith D. Underwood , K. Scott Hemmert, Closing the Gap: CPU and FPGA Trends in Sustainable Floating-Point BLAS Performance, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.219-228, April 20-23, 2004
• 17: Keith Underwood, FPGAs vs. CPUs: trends in peak floating-point performance, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968305]
• 18: Williamson, D. L., Drake, J. B., Hack, J. J., Jakob, R., and Swarztrauber, P. N. 1992. A standard test set for numerical approximations to the shallow water equations in spherical geometry. J. Comput. Phys. 102, 211--224.
• 19: Zhuo, L., and Prasanna, V. K. 2004. Scalable and modular algorithms for floating-point matrix multiplication on fpgas. In 18th International Parallel and Distributed Processing Symposium (IPDPS'04).
• 20: Design Tradeoffs for BLAS Operations on Reconfigurable Hardware, Proceedings of the 2005 International Conference on Parallel Processing (ICPP'05), p.78-86, June 14-17, 2005 [doi>10.1109/ICPP.2005.31]
• 21: Ling Zhuo , Viktor K. Prasanna, High Performance Linear Algebra Operations on Reconfigurable Systems, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.2, November 12-18, 2005 [doi>10.1109/SC.2005.31]
• 22: 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:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Fast Fourier transforms (FFT)

General Terms:
Algorithms, Design

Keywords:
FFT, FPGA, IEEE floating point, matrix multiply, reconfigurable computing