Attacking the semantic gap between application programming languages and configurable hardware

ABSTRACT

It is difficult to exploit the massive, fine-grained parallelism of configurable hardware with a conventional application programðming language such as C, Pascal or Java. The difficulty arises from the mismatch between the synchronous, concurrent processing capability of the hardware and the expressiveness of the lanðguage-the so-called "semantic gap." We attack this problem by using a programming model matched to the hardware's capabilities that can be implemented in any (unmodified) object-oriented lanðguage, and building a corresponding compiler. The result is appliðcation code that can be developed, compiled, debugged and executed on a personal computer using conventional tools (such as Visual C++ or Visual Cafe), and then recompiled without modifiðcation to the configurable hardware target. A straightforward C++ implementation of the Serpent encryption algorithm compiled with our compiler onto a Virtex XCV1000 FPGA yielded an implemenðtation that was smaller (3200 vs. 4502 CLBs) and faster (77 MHz vs. 38 MHz) than an independent VHDL implementation with the same degree of pipelining. A tuned version of the source yielded an implementation that ran at 95 MHz.

REFERENCES

• 1: Rajeev Barua , Walter Lee , Saman Amarasinghe , Anant Agarwal, Maps: a compiler-managed memory system for raw machines, Proceedings of the 26th annual international symposium on Computer architecture, p.4-15, May 01-04, 1999, Atlanta, Georgia, United States
• 2: Timothy J. Callahan , John Wawrzynek, Instruction-Level Parallelism for Reconfigurable Computing, Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm, p.248-257, August 31-September 03, 1998
• 3: J. Babb , M. Frank , V. Lee , E. Waingold , R. Barua , M. Taylor , J. Kim , S. Devabhaktuni , A. Agarwal, The RAW benchmark suite: computation structures for general purpose computing, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.134, April 16-18, 1997
• 4: Jonathan Babb , Martin Rinard , Csaba Andras Moritz , Walter Lee , Matthew Frank , Rajeev Barua , Saman Amarasinghe, Parallelizing Applications into Silicon, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.70, April 21-23, 1999
• 5: Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
• 6: S. Vernalde , P. Schaumont , I. Bolsens, An Object Oriented Programming Approach for Hardware Design, Proceedings of the IEEE Computer Society Workshop on VLSI'99, p.68, April 08-09, 1999
• 7: Niklaus Wirth, Hardware Compilation: Translating Programs into Circuits, Computer, v.31 n.6, p.25-31, June 1998 [doi>10.1109/2.683004 ]
• 8: Maya Gokhale , Brian Schott, Data-parallel C on a reconfigurable logic array, The Journal of Supercomputing, v.9 n.3, p.291-313, 1995 [doi>10.1007/BF01212873]
• 9: J. Hammes, R. Rinker, W. Bohm, W. Najjar, B. Draper, A High-Level, Algorithmic Programming Language and Compiler for Reconfigurable Systems, Computer Science Department, Colorado State University.
• 10: J.M.P. Cardoso, H.C. Neto, Fast hardware compilation of behaviors into an FPGA-based dynamic reconfigurable computing system, Proceedings of the XII Symposium on Integrated Circuits and Systems Design (SBCCI'99), Natal- RN, Brazil, pp. 150-153, Sept. 29-Oct. 2, 1999.
• 11: R. Schreiber, S. Aditya, B.R. Rau, V. Kathail, S. Mahlke, S. Abraham, G. Snider, S. Anik, High-level synthesis of nonprogrammable hardware accelerators, submitted to CODES2000.
• 12: BRASS Research Group, Automatic C compilation to SW + reconfigurable HW, http://brass.cs.berkeley.edu/compile. html.
• 13: D. Galloway, The Transmogrifier C hardware description language and compiler for FPGAs, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.136, April 19-21, 1995
• 14: C. Iseli , E. Sanchez, A C++ compiler for FPGA custom execution units synthesis, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.173, April 19-21, 1995
• 15: D. Davis, S. Edwards, J. Harris, Forge-J, LavaLogic white paper available from: http://www.lavalogic.com/product/ wp_forge.html, pp. 1-8, 2000.
• 16: D. Davis, Java for digital circuit design, LavaLogic ratepayer available from: http://www.lavalogic.com/product/ wp_java.html, pp. 1-5, 2000.
• 17: P. Clarke and R. Goering, C Level fields C++ class library, eeTimes.com, available from: http://www.eet.com/story/ OEG20000103S0020, Aug. 30, 2000.
• 18: M. Brown, Handel-C and the Alex APAC509, Embedded Solutions Application Note 002, pp. 1-4, Feb. 6, 1998.
• 19: Xiaohan Zhu , Bill Lin, Hardware compilation for FPGA-based configurable computing machines, Proceedings of the 36th ACM/IEEE conference on Design automation, p.697-702, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310030]
• 20: D. Ku, HardwareCa language for hardware design version 2.0, HardwareC Language Manual, available from: http:// www.ics.uci.edu/~jian/olympus/hardwarec.html#manual.
• 21: L.E. Thon, K. Rimey, L. Svensson, From C to silicon, Chapter: 17, The PUMA Processor, available from: http:// infopad.eecs.berkeley.edu/~burd/software/maker2html/ex10/ CtoSilicon.html, Sept. 1995.
• 22: P.L. Flake, S.J. Davidmann, D.J. Kelf, Superlog, A Next Generation Systems Design Language, International HDL Conference, March 2000.
• 23: S.E. Mitchell, TAOA model for the integration of concurrency and synchronisation in object-oriented programming, Ph.D. Thesis, University of York, UK, pp. 1-167, March 1995.
• 24: J Heath, P. Kuekes, G. Snider, R. Williams, A Defect-Tolerant Computer Architecture: Oppotunities for Nanotechnology, Science, June 12, 1998.
• 25: Tommaso Toffoli , Norman Margolus, Cellular automata machines: a new environment for modeling, MIT Press, Cambridge, MA, 1987
• 26: E. Gamma, Design Patterns, Addison-Wesley, 1995.
• 27: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 28: B. Rau, Iterative Modulo Scheduling, Hewlett-Packard Laboratories Technical Report HPL-94-115, 1994.
• 29: A. J. Elbirt , C. Paar, An FPGA implementation and performance evaluation of the Serpent block cipher, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.33-40, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329176]
• 30: C. Ebeling , D. C. Cronquist , P. Franklin , J. Secosky , S. G. Berg, Mapping applications to the RaPiD configurable architecture, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.106, April 16-18, 1997
• 31: Seth Copen Goldstein , Herman Schmit , Matthew Moe , Mihai Budiu , Srihari Cadambi , R. Reed Taylor , Ronald Laufer, PipeRench: a co/processor for streaming multimedia acceleration, Proceedings of the 26th annual international symposium on Computer architecture, p.28-39, May 01-04, 1999, Atlanta, Georgia, United States
• 32: Oskar Mencer , Martin Morf , Michael J. Flynn, PAM-Blox: High Performance FPGA Design for Adaptive Computing, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.167, April 15-17, 1998
• 33: P. Bellows , B. Hutchings, JHDL - An HDL for Reconfigurable Systems, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.175, April 15-17, 1998
• 34: Scott Alan Mahlke, Exploiting instruction level parallelism in the presence of conditional branches, University of Illinois at Urbana-Champaign, Champaign, IL, 1997
• 35: M. Brandis, Optimizing Compilers for Structured Programming Languages, Ph.D. dissertation, Swiss Federal Institute of Technology Zurich, 1995.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Design, Experimentation