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. 1.R. Barua, W. Lee, S. Amarasinghe, A. Agarwal, "Maps: A compiler-managed memory system for Raw machines," Proceedings of the Twenty-Sixth International Symposium on Computer Architecture (ISCA-26), June 1999.
2. 2.T. J. Callahan and J. Warzynek, Instruction-level parallelism for reconfigurable computing, International Workshop on Field Programmable Logic, September 1998.
3. 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, IEEE Workshop on FPGA-based Custom Computing Machines, Napa, Ca, April 1997.
4. 4.J. Babb, M. Rinard, C.A. Moritz, W. Lee, M. Frank, R, Barua, S. Amarasinghe, Parallelizing applications into silicon, IEEE Symposium on FPGAs for Custom Computing Machines, pp. 70-80, April 1999.
5. 5.W. Lee, R. Barua, M. Frank, D. Srikrishna, J. Babb, V. Sarkar, S. Amarasinghe, Space-time scheduling of instructionlevel parallelism on a Raw machine, Proceedings of the 8th International Conference on Architectural support for Programming Languages and Operating Systems, pp. 46-57, October 1998.
6. 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, April 1999.
7. 7.N. Wirth, Hardware compilation: translating programs into circuits, Computer, pp 25-31, June 1998.
8. 8.M. Gokhale, B. Schott, Data-parallel C on a reconfigurable logic array, Journal of Supercomputing, no. 9, pp. 291-313, 1995.
9. 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. 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. 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. 12.BRASS Research Group, Automatic C compilation to SW + reconfigurable HW, http://brass.cs.berkeley.edu/compile. html.
13. 13.D. Galloway, The transmogrifier C hardware description anguage and compiler for FPGAs, IEEE Symposium on FPGAs for Custom Computing Machines (FCCM '95), Napa, California, pp. 136-144, April 1995.
14. 14.C. Iseli, E. Sanchez, A C++ compiler for FPGA custom execution units synthesis, IEEE Symposium on FPGAs for Custom Computing Machines (FCCM '95), pp. 173-179, April 1995.
15. 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. 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. 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. 18.M. Brown, Handel-C and the Alex APAC509, Embedded Solutions Application Note 002, pp. 1-4, Feb. 6, 1998.
19. 19.X. Zhu and B. Lin, Hardware compilation for FPGA-based configurable computing machines, Proceedings of the 36th Design Automation Conference, pp. 697-702, June 1999.
20. 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. 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. 22.P.L. Flake, S.J. Davidmann, D.J. Kelf, Superlog, A Next Generation Systems Design Language, International HDL Conference, March 2000.
23. 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. 24.J Heath, P. Kuekes, G. Snider, R. Williams, A Defect-Tolerant Computer Architecture: Oppotunities for Nanotechnology, Science, June 12, 1998.
25. 25.T. Toffoli and N. Margolous, Cellular Automata Machines, MIT Press, 1987.
26. 26.E. Gamma, Design Patterns, Addison-Wesley, 1995.
27. 27.S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, p. 258, 1997.
28. 28.B. Rau, Iterative Modulo Scheduling, Hewlett-Packard Laboratories Technical Report HPL-94-115, 1994.
29. 29.A. Elbirt, An FPGA Implementation and Performance Evaluation of the Serpent Block Cipher, Proceedings, Eighth International Symposium on Field Programmable Gate Arrays, pp.33-40, February 9-11, 2000.
30. 30.C. Ebeling, Mapping Applications to the RaPiD Configurable Architecture, Proceedings, IEEE Workshop on FPGA's for Custom Computing Machines, April, 1997.
31. 31.S. Goldstein, PipeRench: A Coprocessor for Streaming Multimedia Accelleration, Proceedings, 26th International symposium on Computer Architecture
32. 32.O. Mencer, M. Morf, M. Flynn, PAM-Blox: High Performance FPGA Design for Adaptive Computing, IEEE Symposium on FPGAs for Custom Computing Machines (FCCM '98), pp. 167-174, April 1998.
33. 33.P. Bellows, B. Hutchings, JHDL An HDL for Reconfigurable Systems, IEEE Symposium on FPGAs for Custom Computing Machines (FCCM '98), pp. 175-184, April 1998.
34. 34.S. Mahlke, "Exploiting Instruction-Level Parallelism in the Presence of Conditional Branches, Ph.D. dissertation, Department of Electrical and Computer Engineering, University of Illinois, Urbana IL, Sept. 1996.
35. 35.M. Brandis, Optimizing Compilers for Structured Programming Languages, Ph.D. dissertation, Swiss Federal Institute of Technology Zurich, 1995.

Index Terms

• Hardware

  • Electronic design automation

    • Hardware description languages and compilation

    • Physical design (EDA)

      • Placement

      • Wire routing