Analysis and approximation for bank selection instruction minimization on partitioned memory architecture

Minming Li (), Tiantian Liu (), Chun Jason Xue () and Yingchao Zhao ()
Additional contact information
Minming Li: City University of Hong Kong
Tiantian Liu: City University of Hong Kong
Chun Jason Xue: City University of Hong Kong
Yingchao Zhao: City University of Hong Kong

Journal of Combinatorial Optimization, 2012, vol. 23, issue 2, No 8, 274-291

Abstract: Abstract 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 switch among different memory banks, a special instruction, Bank Selection, is used. How to minimize the number of bank selection instructions inserted is important to reduce code size for embedded systems. In this paper, we consider how to insert the minimum number of bank selection instructions in a program to achieve feasibility. A program can be represented by a control flow graph (CFG). We prove that it is NP-hard to insert the minimum number of bank selection instructions if all the variables are pre-assigned to memory banks. Therefore, we introduce a 2-approximation algorithm using a rounding method. When the CFG is a tree or the out-degree of each node in the CFG is at most two, we show that we can insert the bank selection instructions optimally in polynomial time. We then consider the case when there are some nodes that do not access any memory bank and design a dynamic programming method to compute the optimal insertion strategy when the CFG is a tree. Finally, if the variables are not yet assigned, we show that it is NP-hard to decide the variable assignment with the minimum number of insertions needed even if the input CFG is a tree.

Keywords: Approximation algorithms; Rounding; NP-hardness; Bank selection instruction minimization; Partitioned memory architecture (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9365-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:23:y:2012:i:2:d:10.1007_s10878-010-9365-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9365-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().