High-level synthesis for large bit-width multipliers on FPGAs: a case study

ABSTRACT

In this paper, we present the analysis, design and implementation of an estimator to realize large bit width unsigned integer multiplier units. Larger multiplier units are required for cryptography and error correction circuits for more secure and reliable transmissions over highly insecure and/or noisy channels in networking and multimedia applications. The design space for these circuits is very large when integer multiplication on large operands is carried out hierarchically. In this paper, we explore automated synthesis of high bit-width unsigned integer multiplier circuits by defining and validating an estimator function used in search and analysis of the design space of such circuits. We focus on analysis of a hybrid hierarchical multiplier scheme that combines the throughput advantages of parallel multipliers and the resource cost-effectiveness of serial ones. We present an analytical model that rapidly predicts timing and resource usage for selected model candidates. We evaluate the estimator model in the design of a practical application, a 256-bit elliptic curve adder implemented on a Xilinx FPGA fabric. We show that our estimator allows implementation of fast, efficient circuits, where resultant designs provide order-of-magnitude performance improvements when compared with that of software implementations on a high performance computing platform.

REFERENCES

• 1: S. Hauck, "The roles of FPGAs in reprogrammable systems," Proceedings of the IEEE, Vol. 86, 1998, pp. 615--639.
• 2: Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002 [doi>10.1145/508352.508353]
• 3: Robert P. Dick , Niraj K. Jha, CORDS: hardware-software co-synthesis of reconfigurable real-time distributed embedded systems, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.62-67, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288561]
• 4: An algorithm for synthesis of large time-constrained heterogeneous adaptive systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.207-225, April 2001 [doi>10.1145/375977.375979]
• 5: S.C. Goldstein and M. Budiu, "The DIL Language and Compiler Manual," Carnegie Mellon University, www.ece.cmu.edu/research/piperench/dil.ps, 1999
• 6: J. Hammes, R. Rinker, W. Bohm, and W. Jajjar, "Compiling a High-Level Language to Reconfigurable Systems," CASES, 1999.
• 7: Byoungro So , Pedro C. Diniz , Mary W. Hall, Using estimates from behavioral synthesis tools in compiler-directed design space exploration, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775963]
• 8: Byoungro So , Mary W. Hall , Pedro C. Diniz, A compiler approach to fast hardware design space exploration in FPGA-based systems, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 9: Carlo Brandolese , William Fornaciari , Fabio Salice, An area estimation methodology for FPGA based designs at systemc-level, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996606]
• 10: A. Nayak , M. Haldar , A. Choudhary , P. Banerjee, Accurate Area and Delay Estimators for FPGAs, Proceedings of the conference on Design, automation and test in Europe, p.862, March 04-08, 2002
• 11: Dhananjay Kulkarni , Walid A. Najjar , Robert Rinker , Fadi J. Kurdahi, Fast Area Estimation to Support Compiler Optimizations in FPGA-Based Reconfigurable Systems, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.239, September 22-24, 2002
• 12: Mentor Graphics Inc. MonetTM User's Manual, 2002
• 13: "CoCentric SystemC Compiler, Behavioral User and Modelling Guide," Synopsys,http://www.synopsys.com
• 14: N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, 48:203-209, 1987.
• 15: Victor S Miller, Use of elliptic curves in cryptography, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.417-426, June 1986, Santa Barbara, California, United States
• 16: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 17: SRC High Performance Computer www.srccomp.com/default.htm, 2004
• 18: Carsten Menn , Oliver Bringmann , Wolfgang Rosenstiel, Controller estimation for FPGA target architectures during high-level synthesis, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581213]
• 19: National Institute of Standards and Technology (NIST), Recommended Elliptic Curves for Federal Government Use, found at http://csrc.nist.gov/csrc/fedstandards.html, July 1999.
• 20: Peter L. Montgomery. "Modular multiplication without trial division". Mathematics of Computation, 44(170):519--521, 1985
• 21: D.A. Buell, J.P. Davis, and G. Quan, "Reconfigurable Computing Applied to Problems in Communications Security", in Proceedings MAPLD-02, Laurel, MD, 2002.
• 22: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 23: Ulrich Junker, Preference-based search and multi-criteria optimization, Eighteenth national conference on Artificial intelligence, p.34-40, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 24: U. Junker, "Design space exploration of Elliptic curve arithmetic on a reconfigurable platform," MS Thesis, 2004
• 25: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 26: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Cost/performance

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA devices, design exploration, high level synthesis, large-scale integer multipliers, reconfigurable computing