Seminar Speaker
Date: Thursday, September 23rd, 2010, 2:30PM, SB Conference Room 233
Title: Analysis and Approximation for Bank Selection Instruction Minimization on Partitioned Memory Architecture
Speaker: Minming Li -- City University of Hong Kong (CS)
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 talk, 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.
Biography
Minming Li is currently an assistant professor in the Department of Computer Science, City University of Hong Kong. He received his Ph. D. and B.E. degree in the Department of Computer Science and Technology at Tsinghua University in 2006 and 2002 respectively. His research interests include algorithm design, analysis in wireless networks, energy efficient scheduling and combinatorial optimization.