Article

Minimizing bank selection instructions for partitioned memory architecture

Authors:

Bernhard Scholz,

Bernd Burgstaller,

Jingling XueAuthors Info & Claims

CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems

Pages 201 - 211

https://doi.org/10.1145/1176760.1176786

Published: 22 October 2006 Publication History

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]

R. Banakar, S. Steinke, B. Lee, M. Balakrishnan, and P. Marwedel. Scratchpad Memory: A Design Alternative for Cache On-chip Memory in Embedded Systems. In Proceedings of the 10th International Workshop on Hardware/Software Codesign, CODES, Estes Park (Colorado) May 2002.

Digital Library

[2]

Jeonghun Cho, Yunheung Paek, and David Whalley. Fast Memory Bank Assignment for Fixed-Point Digital Signal Processors. ACM Transactions on Design Automation of Electronic Systems 9(1):52--74, 2004.

Digital Library

[3]

V. Delaluz, M. Kandemir, N. Vijaykrishnan, and M. J. Irwin. Energy-Oriented Compiler Optimizations for Partitioned Memory Architectures. In CASES '00: Proceedings of the 2000 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems pages 138--147, New York, NY, USA, 2000. ACM Press.

Digital Library

[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.

Digital Library

[8]

Tokuzo Kiyohara, Scott Mahlke, William Chen, Roger Bringmann, Richard Hank, Sadun Anik, and Wen-Mei Hwu. Register Connection:A New Approach to Adding Registers into Instruction Set Architectures. In ISCA '93: Proceedings of the 20th Annual International Symposium on Computer Architecture pages 247--256, New York, NY, USA, 1993. ACM Press.

Digital Library

[9]

Jon M. Kleinberg and Eva Tardos. Approximation Algorithms for Classi cation Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science pages 14--23, 1999.

Digital Library

[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.

Digital Library

[11]

Lian Li, Lin Gao, and Jingling Xue. Memory Coloring: A Compiler Approach for Scratchpad Memory Management. In PACT '05: Proceedings of the 2005 International Conference on Parallel Architectures and Compilation Techniques pages 329--338, 2005.

Digital Library

[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 and Alexandre E. Eichenberger. Effective Cluster Assignment for Modulo Scheduling. In MICRO 31: Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture pages 103--114, 1998.

Digital Library

[16]

P. R. Panda, F. Catthoor, N. D. Dutt, K. Danckaert, E. Brockmeyer, C. Kulkarni, A. Vandercappelle, and P. G. Kjeldsberg. Data and Memory Optimization Techniques for Embedded Systems. ACM Transactions on Design Automation of Electronic Systems 6(2):149--206, 2001.

Digital Library

[17]

Preeti Ranjan Panda, Nikil D. Dutt, and Alexandru Nicolau. On-Chip vs. O -Chip Memory:The Data Partitioning Problem in Embedded Processor-Based Systems. ACM Transactions on Design Automation of Electronic Systems 5(3):682--704, 2000.

Digital Library

[18]

PICC ANSI C Compiler. http://www.htsoft.com/ 2006.

[19]

Mazen A. R. Saghir, Paul Chow, and Corinna G. Lee. Exploiting Dual Data-Memory Banks in Digital Signal Processors. In ASPLOS-VII: Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems pages 234--243, New York, NY, USA, 1996. ACM Press.

Digital Library

[20]

Bernhard Scholz and Erik Eckstein. Register Allocation for Irregular Architectures. In LCTES-SCOPES '02: Proceedings of the Joint Conference on Languages, Compilers and Tools for Embedded Systems pages 139--148. ACM, 2002.

Digital Library

[21]

A. Sudarsanam and S. Malik. Memory Bank and Register Allocation in Software Synthesis for ASIPs. In ICCAD '95: Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design pages 388--392, 1995.

Digital Library

[22]

The Gpsim SW Simulator for PIC Microcontrollers. http://www.dattalo.com/gnupic/gpsim.html 2006.

[23]

Sumesh Udayakumaran and Rajeev Barua. Compiler-Decided Dynamic Memory Allocation for Scratch-Pad Based Embedded Systems. In CASES'03: Proceedings of the 2003 International Conference on Compilers, Architecture and Synthesis for Embedded Systems pages 276--286. ACM Press, 2003.

Digital Library

[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.

Digital Library

[25]

Xiaotong Zhuang, Santosh Pande, and John S. Greenland Jr. A Framework for Parallelizing Load/Stores on Embedded Processors. In PACT '02: Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques pages 68--79. IEEE Computer Society, 2002.

Digital Library

[26]

Qingfeng Zhuge, Bin Xiao, and Edwin Hsing-Mean Sha. Variable Partitioning and Scheduling of Multiple Memory Architectures for DSP. In IPDPS '02: Proceedings of the 16th International Parallel andDistributed Processing Symposium page 332, Washington, DC, USA, 2002. IEEE Computer Society.

Digital Library

Cited By

Li MLiu TXue CZhao Y(2018)Analysis and approximation for bank selection instruction minimization on partitioned memory architectureJournal of Combinatorial Optimization10.1007/s10878-010-9365-z23:2(274-291)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1007/s10878-010-9365-z
Yang JJiang HHu W(2017)A Methodology for the Optimization Of Multi-program Shared Scratchpad MemoryInternational Journal on Smart Sensing and Intelligent Systems10.21307/ijssis-2017-4234:1(1-20)Online publication date: 12-Dec-2017
https://doi.org/10.21307/ijssis-2017-423
Ciszewski MIwanicki K(2017)Efficient Automated Code Partitioning for Microcontrollers with Switchable Memory BanksACM Transactions on Embedded Computing Systems10.1145/305551116:4(1-26)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3055511
Show More Cited By

Index Terms

Minimizing bank selection instructions for partitioned memory architecture
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Minimal placement of bank selection instructions for partitioned memory architectures

We have devised an algorithm for minimal placement of bank selections in partitioned memory architectures. This algorithm is parameterizable for a chosen metric, such as speed, space, or energy. Bank switching is a technique that increases the code and ...
Minimizing code size via page selection optimization on partitioned memory architectures
CASES '13: Proceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems

For 8-bit microcontrollers, bank-switching is commonly used to increase memory capacity. The disadvantage of this technique is that bank (page) selection instructions are introduced when switching active data (program) bank. The page selection problem ...
Analysis and approximation for bank selection instruction minimization on partitioned memory architecture
LCTES '10

A large number of embedded systems include 8-bit microcontrollers for their energy efficiency and low cost. Multi-bank memory architecture is commonly applied in 8-bit microcontrollers to increase the size of memory without extending address buses. To ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems

October 2006

448 pages

ISBN:1595935436

DOI:10.1145/1176760

General Chairs:
Seongsoo Hong
Seoul National University
,
Wayne Wolf
Princeton University
,
Program Chairs:
Krisztian Flautner
ARM Ltd.
,
Taewhan Kim
Seoul National University

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESWEEK06

Sponsor:

ESWEEK06: Second Embedded Systems Week 2006

October 22 - 25, 2006

Seoul, Korea

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
341
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li MLiu TXue CZhao Y(2018)Analysis and approximation for bank selection instruction minimization on partitioned memory architectureJournal of Combinatorial Optimization10.1007/s10878-010-9365-z23:2(274-291)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1007/s10878-010-9365-z
Yang JJiang HHu W(2017)A Methodology for the Optimization Of Multi-program Shared Scratchpad MemoryInternational Journal on Smart Sensing and Intelligent Systems10.21307/ijssis-2017-4234:1(1-20)Online publication date: 12-Dec-2017
https://doi.org/10.21307/ijssis-2017-423
Ciszewski MIwanicki K(2017)Efficient Automated Code Partitioning for Microcontrollers with Switchable Memory BanksACM Transactions on Embedded Computing Systems10.1145/305551116:4(1-26)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3055511
Lee JMoon SPark J(2017)Region-based dual bank register allocation for reduced instruction encoding ArchitecturesMicroprocessors & Microsystems10.1016/j.micpro.2017.09.00555:C(26-43)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.micpro.2017.09.005
Hu WGuo HGeng HZhang KLiu JLiu X(2017)A Novel Design of Software System on Chip for Embedded SystemJournal of Signal Processing Systems10.1007/s11265-015-1099-986:2-3(135-147)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11265-015-1099-9
Mengting YXue CYong CQing'an LZhao YRabbah RRaghunathan A(2013)Minimizing code size via page selection optimization on partitioned memory architecturesProceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.5555/2555729.2555741(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555729.2555741
Krause PCorporaal HStuijk S(2013)Optimal placement of bank selection instructions in polynomial timeProceedings of the 16th International Workshop on Software and Compilers for Embedded Systems10.1145/2463596.2463598(23-30)Online publication date: 19-Jun-2013
https://dl.acm.org/doi/10.1145/2463596.2463598
Liu TXue CLi M(2013)Joint variable partitioning and bank selection instruction optimization for partitioned memory architecturesACM Transactions on Embedded Computing Systems (TECS)10.1145/2442116.244212612:3(1-27)Online publication date: 8-Apr-2013
https://dl.acm.org/doi/10.1145/2442116.2442126
Mengting YXue CYong CQing'an LZhao Y(2013)Minimizing code size via page selection optimization on partitioned memory architectures2013 International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES)10.1109/CASES.2013.6662516(1-10)Online publication date: Sep-2013
https://doi.org/10.1109/CASES.2013.6662516
Liu TLi MXue CLin Y(2010)Joint variable partitioning and bank selection instruction optimization on embedded systems with multiple memory banksProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899745(113-118)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1899721.1899745
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten