An ILP based approach to address code generation for digital signal processors

ABSTRACT

One of the most important problems in resource-constrained embedded systems is limited memory space for code and data. This paper targets at DSP based architectures and proposes an ILP (integer linear programming) based approach for reducing code memory space requirements by exploiting the auto-increment and auto-decrement addressing modes provided by DSPs. Specifically, we address the problem of effective use of address registers, demonstrate how we can take advantage of additional capabilities that exists in some recent DSPs (such as modify registers), and discuss how our ILP-based solution can be used for performing tradeoffs between code memory and data memory space requirements. We also compare our approach to a previously-proposed heuristic solution. Our experimental analysis using several applications indicate that the proposed ILP-based approach is very effective in reducing both code memory demand and execution cycles, and the solution times it takes are within tolerable limits.

REFERENCES

• 1: Guido Araujo , Ashok Sudarsanam , Sharad Malik, Instruction Set Design and Optimizations for Address Computation in DSP Architectures, Proceedings of the 9th international symposium on System synthesis, p.105, November 06-08, 1996
• 2: David H. Bartley, Optimizing stack frame accesses for processors with restricted addressing modes, Software—Practice & Experience, v.22 n.2, p.101-110, Feb. 1992 [doi>10.1002/spe.4380220202]
• 3: Wei-Kai Cheng , Youn-Long Lin, Addressing optimization for loop execution targeting DSP with auto-increment/decrement architecture, Proceedings of the 11th international symposium on System synthesis, p.15-20, December 02-04, 1998, Hsinchu, Taiwan, China
• 4: Alain Darte , Rob Schreiber , Gilles Villard, Lattice-based memory allocation, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951749]
• 5: Eddy De Greef , Francky Catthoor , Hugo De Man, Memory size reduction through storage order optimization for embedded parallel multimedia applications, Parallel Computing, v.23 n.12, p.1811-1837, Dec. 1997 [doi>10.1016/S0167-8191(97)00089-6]
• 6: J.-Y. Lee , I.-C. Park, Address code generation for DSP instruction-set architectures, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.384-395, July 2003 [doi>10.1145/785411.785417]
• 7: R. Leupers. Offset assignment showdown: evaluation of DSP address code optimization algorithms. In Proceedings of the 12th International Conference on Compiler Construction, 2003.
• 8: 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
• 9: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steven Tjiang , Albert Wang, Storage assignment to decrease code size, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.235-253, May 1996 [doi>10.1145/229542.229543]
• 10: Clifford Liem , Pierre Paulin , Ahmed Jerraya, Address calculation for retargetable compilation and exploration of instruction-set architectures, Proceedings of the 33rd annual conference on Design automation, p.597-600, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240631]
• 11: Guilherme Ottoni , Sandro Rigo , Guido Araujo , Subramanian Rajagopalan , Sharad Malik, Optimal Live Range Merge for Address Register Allocation in Embedded Programs, Proceedings of the 10th International Conference on Compiler Construction, p.274-288, April 02-06, 2001
• 12: Amit Rao , Santosh Pande, Storage assignment optimizations to generate compact and efficient code on embedded DSPs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.128-138, May 01-04, 1999, Atlanta, Georgia, United States
• 13: Byoungro So , Mary W. Hall , Heidi E. Ziegler, Custom Data Layout for Memory Parallelism, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.291, March 20-24, 2004, Palo Alto, California
• 14: Sathishkumar Udayanarayanan , Chaitali Chakrabarti, Address code generation for digital signal processors, Proceedings of the 38th conference on Design automation, p.353-358, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378521]
• 15: B. Wess and M. Gotsclich. Optimal DSP memory layout generation as a quadratic assignment problem. In Proceedings of the International Symposium on Circuits and Systems, June 1997.
• 16: Xiaotong Zhuang , ChokSheak Lau , Santosh Pande, Storage assignment optimizations through variable coalescence for embedded processors, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 17: Xpress-MP, http://www.dashoptimization.com/pdf/Mosel1.pdf, May 2002.
• 18: TMS 320 Second Generation Digital Signal Processors, Data Sheet. http://focus.ti.com/lit/ds/sprs010b/sprs010b.pdf, November 1990. Texas Instruments.
• 19: TigerSHARC Embedded Processor, 300MHz, 6Mbits, Data Sheet. Analog Devices.
• 20: Motorola DSP56000/DSP56001 User Manual Motorola Inc., 1990.
• 21: SC1200 DSP Soft Macro Core http://www.starcore-dsp.com/documents/10026_PB_SC1200_DSP_Core.pdf StarCore LLC., 2003.

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:
Algorithms, Design, Experimentation

Keywords:
DSP, code generation, integer linear programming