C is for circuits: capturing FPGA circuits as sequential code for portability

ABSTRACT

Synthesizing common sequential algorithms, captured in a language like C, to FPGA circuits is now well-known to provide dramatic speedups for numerous applications, and to provide tremendous portability and adaptability advantages over circuit implementations of an application. However, many applications targeted to FPGAs are still designed and distributed at the circuit level, due in part to tremendous human ingenuity being exercised at that level to achieve exceptional performance and efficiency. A question then arises as to whether applications for FPGAs will have to be distributed as circuits to achieve desired performance and efficiency, or if instead a more portable language like C might be used. Given a set of common synthesis transformations, we studied the extent to which circuits published in FCCM in the past 6 years could be captured as sequential code and then synthesized back to the published circuit. The study showed that a surprising 82% of the 35 circuits chosen for the study could be re-derived from some form of standard C code, suggesting that standard C code, without extensions, may be an effective means for distributing FPGA applications

REFERENCES

• 1: Michael Attig , John Lockwood, A Framework for Rule Processing in Reconfigurable Network Systems, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.225-234, April 18-20, 2005 [doi>10.1109/FCCM.2005.7]
• 2: Navid Azizi , Ian Kuon , Aaron Egier , Ahmad Darabiha , Paul Chow, Reconfigurable Molecular Dynamics Simulator, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.197-206, April 20-23, 2004
• 3: Paul Baker , Tim Todman , Henry Styles , Wayne Luk, Reconfigurable Designs for Radiosity, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.95-104, April 18-20, 2005 [doi>10.1109/FCCM.2005.57]
• 4: Zachary K. Baker , Viktor K. Prasanna, Efficient Hardware Data Mining with the Apriori Algorithm on FPGAs, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.3-12, April 18-20, 2005 [doi>10.1109/FCCM.2005.31]
• 5: Zachary K. Baker , Viktor K. Prasanna, An Architecture for Efficient Hardware Data Mining using Reconfigurable Computing Systems, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.67-75, April 24-26, 2006 [doi>10.1109/FCCM.2006.22]
• 6: John Sachs Beeckler , Warren J. Gross, FPGA Particle Graphics Hardware, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.85-94, April 18-20, 2005 [doi>10.1109/FCCM.2005.36]
• 7: Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984 [doi>10.1145/2514.2516]
• 8: A. Bogdanov , M. C. Mertens, A Parallel Hardware Architecture for fast Gaussian Elimination over GF(2), Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.237-248, April 24-26, 2006 [doi>10.1109/FCCM.2006.12]
• 9: Uday Bondhugula , Ananth Devulapalli , James Dinan , Joseph Fernando , Pete Wyckoff , Eric Stahlberg , P. Sadayappan, Hardware/Software Integration for FPGA-based All-Pairs Shortest-Paths, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.152-164, April 24-26, 2006 [doi>10.1109/FCCM.2006.48]
• 10: CATAPULTC. http://www.mentor.com/products/c-based_design/
• 11: CELOXICA. http://www.celoxica.com/
• 12: Young H. Cho , William H. Mangione-Smith, Deep Packet Filter with Dedicated Logic and Read Only Memories, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.125-134, April 20-23, 2004
• 13: DINIZ, P., HALL, M., PARK, J., SO, B., AND ZIEGLER, H. 2005. Automatic mapping of C to FPGAs with the DEFACTO compilation and synthesis systems. Journal on Microprocessors and Microsystems, Vol. 29, Issues 2-3, pp. 51--62.
• 14: Travis Doom , Jennifer White , Anthony S. Wojcik , Greg Chisholm, Identifying High-Level Components in Combinational Circuits, Proceedings of the Great Lakes Symposium on VLSI '98, p.313, February 19-24, 1998
• 15: James P. Durbano , Fernando E. Ortiz , John R. Humphrey , Petersen F. Curt , Dennis W. Prather, FPGA-Based Acceleration of the 3D Finite-Difference Time-Domain Method, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.156-163, April 20-23, 2004
• 16: ELES, P., PENG, Z., KUCHCHINSKI, K. AND DOBOLI, A. 1997. System level hardware/software partitioning based on simulated annealing and tabu search. Journal on Design Automation for Embedded Systems, Vol. 2, No. 1, pp. 5--32.
• 17: Alessandro Fin , Franco Fummi , Maurizio Martignano , Mirko Signoretto, SystemC: a homogenous environment to test embedded systems, Proceedings of the ninth international symposium on Hardware/software codesign, p.17-22, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371657]
• 18: Jan Frigo , Maya Gokhale , Dominique Lavenier, Evaluation of the streams-C C-to-FPGA compiler: an applications perspective, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.134-140, February 2001, Monterey, California, United States [doi>10.1145/360276.360326]
• 19: Thomas W. Fry , Scott Hauck, Hyperspectral Image Compression on Reconfigurable Platforms, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.251, September 22-24, 2002
• 20: Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, SPARK: A High-Lev l Synthesis Framework For Applying Parallelizing Compiler Transformations, Proceedings of the 16th International Conference on VLSI Design, p.461, January 04-08, 2003
• 21: GUPTA, S., AND G. DEMICHELI 1991. VULCAN -- A System for High-Level Partitioning of Synchronous Digital Circuits. Technical Report.
• 22: Mark C. Hansen , Hakan Yalcin , John P. Hayes, Unveiling the ISCAS-85 Benchmarks: A Case Study in Reverse Engineering, IEEE Design & Test, v.16 n.3, p.72-80, July 1999 [doi>10.1109/54.785838]
• 23: Arash Hariri , Reza Rastegar , Morteza Saheb Zamani , Mohammad R. Meybodi, Parallel Hardware Implementation of Cellular Learning Automata Based Evolutionary Computing (CLA-EC) on FPGA, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.311-314, April 18-20, 2005 [doi>10.1109/FCCM.2005.51]
• 24: C. Haubelt , J. Teich , K. Richter , R. Ernst, System Design for Flexibility, Proceedings of the conference on Design, automation and test in Europe, p.854, March 04-08, 2002
• 25: Chuan He , Mi Lu , Chuanwen Sun, Accelerating Seismic Migration Using FPGA-Based Coprocessor Platform, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.207-216, April 20-23, 2004
• 26: Chuan He , Wei Zhao , Mi Lu, Time Domain Numerical Simulation for Transient Waves on Reconfigurable Coprocessor Platform, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.127-136, April 18-20, 2005 [doi>10.1109/FCCM.2005.65]
• 27: INTEL QUICKASSIST TECHNOLOGY http://www.intel.com/technology/magazine/45nm/quickassist-0507.htm
• 28: Jörg Henkel, A low power hardware/software partitioning approach for core-based embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.122-127, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309896]
• 29: S. Hezel , A. Kugel , R. Männer , D. M. Gavrila, FPGA-Based Template Matching Using Distance Transforms, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.89, September 22-24, 2002
• 30: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• 31: Zhijun Huang , Milos D. Ercegovac, FPGA Implementation of Pipelined On-Line Scheme for 3-D Vector Normalization, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.61-70, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.23]
• 32: Impulse CoDeveloper. http://www.impulsec.com/
• 33: Phil James-Roxby , Gordon Brebner , Dennis Bemmann, Time-Critical Software Deceleration in an FCCM, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.3-12, April 20-23, 2004
• 34: Philip B. James-Roxby , Daniel J. Downs, An Efficient Content-Addressable Memory Implementation Using Dynamic Routing, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.81-90, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.12]
• 35: Steven D. Krueger , Peter-Michael Seidel, Design of an On-Line IEEE Floating-Point Addition Unit for FPGAs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.239-246, April 20-23, 2004
• 36: Dong-U Lee , Wayne Luk , John Villasenor , Peter Y. K. Cheung, A Hardware Gaussian Noise Generator for Channel Code Evaluation, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.69, April 09-11, 2003
• 37: Wagdy H. Mahmoud , Roger L. Haggard , Mohamed Abdelrahman, Hardware Implementation of Automated Sensor Self-Validation System for Cupola Furnaces, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.291-299, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.24]
• 38: Tulika Mitra , Tzi-cker Chiueh, An FPGA Implementation of Triangle Mesh Decompression, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.22, September 22-24, 2002
• 39: James Moscola , John Lockwood , Ronald P. Loui , Michael Pachos, Implementation of a Content-Scanning Module for an Internet Firewall, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.31, April 09-11, 2003
• 40: Walid A. Najjar , Wim Böhm , Bruce A. Draper , Jeff Hammes , Robert Rinker , J. Ross Beveridge , Monica Chawathe , Charles Ross, High-Level Language Abstraction for Reconfigurable Computing, Computer, v.36 n.8, p.63-69, August 2003 [doi>10.1109/MC.2003.1220583]
• 41: Christian Plessl , Marco Platzner, Custom Computing Machines for the Set Covering Problem, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.163, September 22-24, 2002
• 42: 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, p.23-34, April 24-26, 2006 [doi>10.1109/FCCM.2006.46]
• 43: SGI ALTIX. http://www.sgi.com/products/servers/altix/
• 44: Reetinder Sidhu , Viktor K. Prasanna, Fast Regular Expression Matching Using FPGAs, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.227-238, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.22]
• 45: Ioannis Sourdis , Dionisios Pnevmatikatos, Pre-Decoded CAMs for Efficient and High-Speed NIDS Pattern Matching, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.258-267, April 20-23, 2004
• 46: V. Srinivasan , S. Radhakrishnan , R. Vemuri, Hardware/software partitioning with integrated hardware design space exploration, Proceedings of the conference on Design, automation and test in Europe, p.28-35, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 47: Greg Stitt , Frank Vahid , Gordon McGregor , Brian Einloth, Hardware/software partitioning of software binaries: a case study of H.264 decode, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084905]
• 48: Greg Stitt , Frank Vahid , Walid Najjar, A code refinement methodology for performance-improved synthesis from C, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233649]
• 49: David B. Thomas , Wayne Luk, Efficient Hardware Generation of Random Variates with Arbitrary Distributions, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.57-66, April 24-26, 2006 [doi>10.1109/FCCM.2006.39]
• 50: 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, p.117-126, April 18-20, 2005 [doi>10.1109/FCCM.2005.46]
• 51: K. H. Tsoi , K. H. Lee , P. H. W. Leong, A Massively Parallel RC4 Key Search Engine, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.13, September 22-24, 2002
• 52: K. H. Tsoi , K. H. Leung , P. H. W. Leong, Compact FPGA-based True and Pseudo Random Number Generators, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.51, April 09-11, 2003
• 53: Miljan Vuletic , Laura Pozzi , Paolo Ienne, Virtual Memory Window for a Portable Reconfigurable Cryptography Coprocessor, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.24-33, April 20-23, 2004
• 54: Heather A. Wake , Duncan A. Buell, Congruential Sieves on a Reconfigurable Computer, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.11, April 09-11, 2003
• 55: Xiaojun Wang , Brent E. Nelson, Tradeoffs of Designing Floating-Point Division and Square Root on Virtex FPGAs, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.195, April 09-11, 2003
• 56: Kevin Whitton , X. Sharon Hu , Cedric X. Yi , Danny Z. Chen, An FPGA Solution for Radiation Dose Calculation, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.227-236, April 24-26, 2006 [doi>10.1109/FCCM.2006.23]
• 57: Yanjun Zhang , S. Q. Zheng, Design and analysis of a systolic sorting architecture, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.652, October 25-28, 1995
• 58: Heidi Ziegler , Byoungro So , Mary Hall , Pedro C. Diniz, Coarse-Grain Pipelining on Multiple FPGA Architectures, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.77, September 22-24, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.4 Sequential Programming

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
FPGA, circuit design, portability, sequential code, synthesis