Address code generation for digital signal processors

ABSTRACT

In this paper we propose a procedure to generate code with minimum number of addressing instructions. We analyze different methods of generating addressing code for scalar variables and quantify the improvements due to optimizations such as offset assignment, modify register optimization and address register assignment. We propose an offset assignment heuristic that uses &kgr; address registers, an optimal dynamic programming algorithm for modify register optimization, and an optimal formulation and a heuristic algorithm for the address register assignment problem.

REFERENCES

• 1: Guido Costa Souza De Araujo, Code generation algorithms for digital signal processors, Princeton University, Princeton, NJ, 1997
• 2: William J. Cook , William H. Cunningham , William R. Pulleyblank , Alexander Schrijver, Combinatorial optimization, John Wiley & Sons, Inc., New York, NY, 1998
• 3: Catherine Gebotys, DSP address optimization using a minimum cost circulation technique, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.100-103, November 09-13, 1997, San Jose, California, United States
• 4: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 5: Rainer Leupers , Fabian David, A uniform optimization technique for offset assignment problems, Proceedings of the 11th international symposium on System synthesis, p.3-8, December 02-04, 1998, Hsinchu, Taiwan, China
• 6: Rainer Leupers , Peter Marwedel, Algorithms for address assignment in DSP code generation, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.109-112, November 10-14, 1996, San Jose, California, United States
• 7: Stan Yi-Huang Liao , Srinivas Devadas, Code generation and optimization for embedded digital signal processors, 1996
• 8: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.186-195, June 18-21, 1995, La Jolla, California, United States
• 9: James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62249]
• 10: Ashok Sudarsanam , Stan Liao , Srinivas Devadas, Analysis and evaluation of address arithmetic capabilities in custom DSP architectures, Proceedings of the 34th annual conference on Design automation, p.287-292, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266103]
• 11: The SPAM Project. SPAM project home page. http://www.ee.princeton.edu/spam.
• 12: S. Udayanarayanan. Energy efficient code generation for DSPs. Master's thesis, Department of Electrical Engineering, Arizona State University, 2000.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

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

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

  J. Computer Applications

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory