Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We address the problem of instruction selection in code generation for embedded DSP microprocessors. Such processors have highly irregular data-paths, and conventional code generation methods typically result in inefficient code. Instruction selection can be formulated as directed acyclic graph (DAG) covering. Conventional methods for instruction selection use heuristics that break up the DAG into a forest of trees and then cover them independently. This breakup can result in suboptimal solutions for the original DAG. Alternatively, the DAG covering problem can be formulated as a binate covering problem, and solved exactly or heuristically using branch-and-bound methods. We show that optimal instruction selection on a DAG in the case of accumulator-based architectures requires a partial scheduling of nodes in the DAG, and we augment the binate covering formulation to minimize spills and reloads. We show how the irregular data transfer costs of typical DSP data-paths can be modeled in the binate covering formulation.

REFERENCES

• 1: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: Guido Araujo , Sharad Malik, Optimal code generation for embedded memory non-homogeneous register architectures, Proceedings of the 8th international symposium on System synthesis, p.36-41, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224493]
• 5: R.K. Brayton and F. Somenzi. Boolean Relations and the Incomplete Specification of Logic Networks. In Proceedings of the Int' 1 Conference on Computer-Aided Design, pages 316- 319, November 1989.
• 6: Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
• 7: Jack G. Ganssle, The Art of Programming Embedded Systems, Academic Press, Inc., Orlando, FL, 1991
• 8: J. Gimpel. The Minimization of TANT Networks. IEEE Transactions on Electronic Computers, EC- 16(1): 18-38, February 1967.
• 9: A. Grasselli and F. Luccio. A Method for Minimizing the Number of Internal States in Incompletely Specified Machines. IEEE Transactions on Electronic Computers, EC-14(3):350- 359, June 1965.
• 10: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Code optimization techniques for embedded DSP microprocessors, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.599-604, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217596]
• 11: R. Rudell. Logic Synthesis for VLSI Design. In U. C. Berkeley, ERL Memo 89/49, April 1989.
• 12: Ashok Sudarsanam , Sharad Malik, Memory bank and register allocation in software synthesis for ASIPs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.388-392, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Theory

Keywords:
code generation, digital signal processors, instruction selection