Automatic translation of software binaries onto FPGAs

ABSTRACT

The introduction of advanced FPGA architectures, with built-in DSP support, has given DSP designers a new hardware alternative. By exploiting its inherent parallelism, it is expected that FPGAs can outperform DSP processors. This paper describes the process and considerations for automatically translating binaries targeted for general DSP processors into Register Transfer Level (RTL) VHDL or Verilog code to be mapped onto commercial FPGAs. The Texas Instruments C6000 DSP processor architecture is chosen as the DSP processor platform, and the Xilinx Virtex II as a target FPGA. Various optimizations are discussed, including data dependency analysis, procedure extraction, induction variable analysis, memory optimizations, and scheduling. Experimental results on resource usage and performance are shown for ten software binary benchmarks. Results show performance gains of 3-20X in the FPGA designs over that of the DSP processors in terms of reductions of execution cycles.

REFERENCES

• 1: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 2: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: Synplicity. Synplify Pro Datasheet, www.synplicity.com.
• 4: Texas Instruments, TMS320C6000 Architecture Description, www.ti.com
• 5: Norman Ramsey , Mary F. Fernández, Specifying representations of machine instructions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.492-524, May 1997 [doi>10.1145/256167.256225]
• 6: N. Ramsey, and M.F. Fernandez, "New Jersey Machine-Code toolkit", Proceedings of the 1995 USENIX Technical Conference, January 1995.
• 7: C. Cifuentes and K.J. Gough, "A Methodology for Decompilation", XIX Conferencia Latinoamericana de Informatica, August 1993.
• 8: Cristina Cifuentes , Vishv M. Malhotra, Binary Translation: Static, Dynamic, Retargetable?, Proceedings of the 1996 International Conference on Software Maintenance, p.340-349, November 04-08, 1996
• 9: A. Klaiber, "The Technology Behind Crusoe Processors," Transmeta Corp., White Paper, Jan. 2000, www.transmeta.com http://www.transmeta.com
• 10: Alex Jones , Debabrata Bagchi , Satrajit Pal , Xiaoyong Tang , Alok Choudhary , Prith Banerjee, PACT HDL: a C compiler targeting ASICs and FPGAs with power and performance optimizations, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581659]
• 11: Greg Stitt , Frank Vahid, Hardware/software partitioning of software binaries, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.164-170, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774596]
• 12: Greg Stitt , Roman Lysecky , Frank Vahid, Dynamic hardware/software partitioning: a first approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775896]
• 13: Benjamin A. Levine , Herman H. Schmit, Efficient Application Representation for HASTE: Hybrid Architectures with a Single, Transformable Executable, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.101, April 09-11, 2003
• 14: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada
• 15: CriticalBlue, Cascade Tool Set, www.criticalblue.com
• 16: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 17: Michael Gschwind , Erik R. Altman , Sumedh Sathaye , Paul Ledak , David Appenzeller, Dynamic and Transparent Binary Translation, Computer, v.33 n.3, p.54-59, March 2000 [doi>10.1109/2.825696]
• 18: David Callahan , Alan Carle , Mary Wolcott Hall , Ken Kennedy, Constructing the Procedure Call Multigraph, IEEE Transactions on Software Engineering, v.16 n.4, p.483-487, April 1990 [doi>10.1109/32.54302]
• 19: Xilinx VirtexII Datasheets, www.xilinx.com
• 20: K. Cooper et al, "Building a Control-Flow Graph from Scheduled Assembly Code," Dept. of Computer Science, Rice University.
• 21: Mark W. Bailey , Jack W. Davidson, A formal model and specification language for procedure calling conventions, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.298-310, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199517]
• 22: G. Mittal, D. Zaretsky, P. Banerjee, "Automatic Extraction of Function Bodies from Software Binaries," Submitted to Int. Conf. Computer Aided Design (ICCAD), Santa Clara, CA, Nov. 2004.
• 23: David Zaretsky , Gaurav Mittal , Xiaoyong Tang , Prith Banerjee, Evaluation of scheduling and allocation algorithms while mapping assembly code onto FPGAs, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989048]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.0 General
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages; Optimization

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Retargetable compilers; Code generation

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
binary translation, compiler, decompilation, hardware-software co-design, reconfigurable computing