Storage allocation for embedded processors

ABSTRACT

In an embedded system, it is common to have several memory areas with different properties, such as access time and size. An access to a specific memory area is usually restricted to certain native pointer types. Different pointer types vary in size and cost. For example, it is typically cheaper to use an 8-bit pointer than a 16-bit pointer. The problem is to allocate data and select pointer types in the most effective way. Frequently accessed variables should be allocated in fast memory, and frequently used pointers and pointer expressions should be assigned cheap pointer types. Common practice is to perform this task manually.We present a model for storage allocation that is capable of describing architectures with irregular memory organization and with several native pointer types. This model is used in an integer linear programming (ILP) formulation of the problem. An ILP solver is applied to get an optimal solution under the model. We describe allocation of global variables and local variables with static storage duration.A whole program optimizing C compiler prototype was used to implement the allocator. Experiments were performed on the Atmel AVR 8-bit microcontroller [2] using small to medium sized C programs. The results varied with the benchmarks, with up to 8% improvement in execution speed and 10% reduction in code size.

REFERENCES

• 1: Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, ACM SIGPLAN Notices, v.36 n.5, p.243-253, May 2001
• 2: Atmel Corporation.The AVR Instruction Set http://www.atmel.com/atmel/acrobat/doc0865.pdf
• 3: Robert E. Bixby , Ken Kennedy , Ulrich Kremer, Automatic Data Layout Using 0-1 Integer Programming, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.111-122, August 24-26, 1994
• 4: Keith D. Cooper , Timothy J. Harvey, Compiler-controlled memory, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.2-11, October 02-07, 1998, San Jose, California, United States
• 5: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 6: Corporate Intel Corp., Embedded microcontrollers & processors (vol. I), Intel Corporation, Santa Clara, CA, 1992
• 7: David Seal, ARM Architecture Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 8: M. Kandemir , P. Banerjee , A. Choudhary , J. Ramanujam , E. Ayguadé, An integer linear programming approach for optimizing cache locality, Proceedings of the 13th international conference on Supercomputing, p.500-509, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305247]
• 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: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory data organization for improved cache performance in embedded processor applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.384-409, Oct. 1997 [doi>10.1145/268424.268464]
• 11: 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
• 12: J.Sjodin,B.Fr~derberg,and T.Lindgren -.Allocation of global data object in on-chip ram.Presented at the CASES '98 workshop,http://www.capsl.udel.edu/ conferences/cases99/cases98/paper04.ps
• 13: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 14: Ashok Sudarsanam , Sharad Malik, Simultaneous reference allocation in code generation for dual data memory bank ASIPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.242-264, April 2000 [doi>10.1145/335043.335047]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Performance