Minimizing bank selection instructions for partitioned memory architecture

ABSTRACT

Bank switching is a technique that increases the code and data memory in microcontrollers without extending the address buses. Given a program in which variables have been assigned to data banks, we present a novel optimization technique that minimizes the overhead of bank switching through cost-effective placement of bank selection instructions. The optimal placement is controlled by a variety of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the problem as a form of Partitioned Boolean Quadratic Programming (PBQP).We implemented the optimization as part of a PIC Micro-chip backend and evaluated the approach for several optimization objectives. Our benchmark suite comprises programs from MiBench and DSPStone plus a microcontroller real-time kernel and drivers for microcontroller hardware devices. Our optimization achieved a reduction of program memory space between 2.7% and 18.2%, and an overall improvement with respect to instruction cycles between 5.1% and 28.8%. Our optimization achieved an optimal solution for all benchmark programs.

REFERENCES

• 1: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 2: Jeonghun Cho , Yunheung Paek , David Whalley, Fast memory bank assignment for fixed-point digital signal processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.1, p.52-74, January 2004 [doi>10.1145/966137.966140]
• 3: V. Delaluz , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Energy-oriented compiler optimizations for partitioned memory architectures, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.138-147, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354900]
• 4: Erik Eckstein. Code Optimizations for Digital Signal Processors PhD thesis, Institute of Computer Languages, Compilers and Languages Group, Vienna University of Technology, 2003.
• 5: Gartner Dataquest. 2003 Microcontroller Market Share and Unit Shipments, July 2004.
• 6: Gartner Dataquest. Top Companies Revenue from Shipments of 8-bit MCU?All Applications, April 2005.
• 7: M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, andR. B. Brown. MiBench: A Free, Commercially Representative Embedded Benchmark Suite. In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization December 2001.
• 8: Tokuzo Kiyohara , Scott Mahlke , William Chen , Roger Bringmann , Richard Hank , Sadun Anik , Wen-Mei Hwu, Register connection: a new approach to adding registers into instruction set architectures, Proceedings of the 20th annual international symposium on Computer architecture, p.247-256, May 16-19, 1993, San Diego, California, United States
• 9: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 10: R. Leupers and D. Kotte. Variable Partitioning for Dual Memory Bank DSPs. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing pages 1121--1124, 2001.
• 11: Lian Li , Lin Gao , Jingling Xue, Memory Coloring: A Compiler Approach for Scratchpad Memory Management, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.329-338, September 17-21, 2005 [doi>10.1109/PACT.2005.27]
• 12: Microchip Technology Inc. PICmicro Mid-Range MCU Family Reference Manual, 1997.
• 13: Microchip Technology Inc. PIC16F87XA Data Sheet, 2003.
• 14: MicrochipC.com PIC Micros and C. http://www.microchipc.com/2006.
• 15: Erik Nystrom , Alexandre E. Eichenberger, Effective cluster assignment for modulo scheduling, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.103-114, November 1998, Dallas, Texas, United States
• 16: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 17: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.682-704, July 2000 [doi>10.1145/348019.348570]
• 18: PICC ANSI C Compiler. http://www.htsoft.com/ 2006.
• 19: 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
• 20: Bernhard Scholz , Erik Eckstein, Register allocation for irregular architectures, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 21: 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
• 22: The Gpsim SW Simulator for PIC Microcontrollers. http://www.dattalo.com/gnupic/gpsim.html 2006.
• 23: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, 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.951747]
• 24: Manish Verma, Lars Wehmeyer, and Peter Marwedel. Cache-Aware Scratchpad Allocation Algorithm. In DATE '04: Proceedings of the Conference on Design, Automation and Test in Europe pages 1264--1269, Washington, DC, USA, 2004. IEEE Computer Society.
• 25: Xiaotong Zhuang , Santosh Pande , John S. Greenland, Jr., A Framework for Parallelizing Load/Stores on Embedded Processors, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.68, September 22-25, 2002
• 26: Qingfeng Zhuge , Bin Xiao , Edwin Hsing-Mean Sha, Variable Partitioning and Scheduling of Multiple Memory Architectures for DSP, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.332, April 15-19, 2002

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
PBQP, RAM allocation, bank-switching, compiler optimization, microcontrollers, partitioned memory architecture