Optimized address assignment for DSPs with SIMD memory accesses

ABSTRACT

This paper deals with address assignment in code generation for digital signal processors (DSPs) with SIMD (single instruction multiple data) memory accesses. In these processors data are organized in groups (or partitions), whose elements share one common memory address. In order to optimize program performance for processors with such memory architectures it is important to have a suitable memory layout of the variables. We propose a two-step address assignment technique for scalar variables using a genetic algorithm based partitioning method and a graph based heuristic which makes use of available DSP address generation hardware. We show that our address assignment techniques lead to a significant code quality improvement compared to heuristics.

REFERENCES

• 1: Motorola. DSP56000, Digital Signal Processor, User's Manual, 1986.
• 2: GEPARD - Familiy of Embedded Software Programmable DSP Cores. http://asic.amsint.com/databooks/digital/gepard.html.
• 3: 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
• 4: Mazen A. R. Saghir , Paul Chow , Corinna G. Lee, Exploiting dual data-memory banks in digital signal processors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.234-243, October 01-04, 1996, Cambridge, Massachusetts, United States
• 5: Craig Hansen, MicroUnity's MediaProcessor Architecture, IEEE Micro, v.16 n.4, p.34-41, August 1996 [doi>10.1109/40.526923]
• 6: G. Fettweis, M. Weiss, W. Drescher, U. Walther, F. Engel, and S. Kobayashi. Breaking new grounds over 3000 MOPS: A broadband mobile multimedia modem DSP. In Proc. of ICSPAT'98, pages 1547- 1551, Toronto, Canada, 1998.
• 7: M. H. Weiss and G. P. Fettweis. Dynamic Codewidth Reduction for VLIW Instruction Set Architectures in Digital Signal Processors. In 3rd International Workshop on Image and Signal Processing, pages 517-520. IEEE, 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. In Bell System Technical Journal, volume 49, pages 291-307, 1970.
• 11: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 12: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 13: K. R. Baker. Introduction to Sequencing and Scheduling. Wiley, New York, 1974.
• 14: 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
• 15: 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
• 16: B. Wess and M. Gotschlich. Optimal DSP Memory Layout Generation as a Quadratic Assignment Problem. In Proceedings IEEE International Symposium on Circuits and Systems, volume 3, pages 1712 - 1715, Hong Kong, 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

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

General Terms:
Algorithms, Design, Performance, Theory