Paper Info
Title
Minimal placement of bank selection instructions for partitioned memory architectures
Abstract
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 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 placement is controlled by a number of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the minimal placement of bank selection instructions as a discrete optimization problem that is mapped to a partitioned boolean quadratic programming (PBQP) problem. We implemented the optimization as part of a PIC Microchip 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 in program memory space of between 2.7 and 18.2&percent;, and an overall improvement with respect to instruction cycles between 5.0 and 28.8&percent;. Our optimization achieved the minimal solution for all benchmark programs. We investigated the scalability of our approach toward the requirements of future generations of microcontrollers. This study was conducted as a worst-case analysis on the entire MiBench suite. Our results show that our optimization (1) scales well to larger numbers of memory banks, (2) scales well to the larger problem sizes that will become feasible with future microcontrollers, and (3) achieves minimal placement for more than 72&percent; of all functions from MiBench.
Year
DOI
Venue
2008
10.1145/1331331.1331336
ACM Trans. Embedded Comput. Syst.
Keywords
Field
DocType
bank switching,bank selection,data bank,minimal placement,partitioned memory architecture,optimization objective,partitioned boolean quadratic programming,partitioned memory architectures,novel optimization technique,cost-effective placement,memory bank,bank selection instruction,discrete optimization problem,discrete optimization,real time,quadratic program,cost effectiveness
Kernel (linear algebra),Memory bank,Code size,Suite,Computer science,Bank switching,Parallel computing,Real-time computing,Microcontroller,Quadratic programming,Scalability
Journal
Volume
Issue
ISSN
7
2
1539-9087
Citations 
PageRank 
References 
9
0.55
24
Authors
3
Name
Order
Citations
PageRank
Bernhard Scholz110410.59
Bernd Burgstaller213317.54
Jingling Xue31627124.20