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

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.