Evaluation of scheduling and allocation algorithms while mapping assembly code onto FPGAs

ABSTRACT

Migration of software from older general purpose embedded processors onto newer mixed hardware/software Systems-On-Chip (SOC) platforms is becoming an increasingly important topic. Automatic translation of general purpose software binaries and assembly code onto hardware implementations using FPGAs require sophisticated scheduling and allocation algorithms to maximize the resource utilization of such hardware devices. This paper describes the effects of scheduling and chaining of node operations in a CDFG onto an FPGA. The effects of register allocation on scheduled nodes are also discussed. The Texas Instruments C6000 DSP processor architecture was chosen as the DSP processor platform and assembly code, and the Xilinx Virtex II XC2V250 was chosen as the target FPGA. Results are reported on ten benchmarks, which show that scheduling with chaining operations produces the best results on FPGAs, while the addition of register allocation in fact generates poorer designs in terms of area and frequency.

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: Texas Instruments, TMS320C6000 Architecture Description, www.ti.com
• 4: 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]
• 5: N. Ramsey, and M.F. Fernandez, "New Jersey Machine-Code toolkit", Proceedings of the 1995 USENIX Technical Conference, January 1995.
• 6: Synplicity. Synplify Pro Datasheet, www.synplicity.com.
• 7: G. Chaitin et al., "Register Allocation via Coloring," Computer Languages, 6, pp. 47--57, 1981.
• 8: G. J. Chaitin, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices, v.17 n.6, p.98-101, June 1982
• 9: Omri Traub , Glenn Holloway , Michael D. Smith, Quality and speed in linear-scan register allocation, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.142-151, June 17-19, 1998, Montreal, Quebec, Canada
• 10: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 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: CriticalBlue, Cascade Tool Set, www.criticalblue.com

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.0 General

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration); Gate arrays; Algorithms implemented in hardware

General Terms:
Algorithms, Design, Experimentation, Performance, Verification

Keywords:
FPGAs, binary translation, chaining, compilers, hardware synthesis, optimizations, scheduling