Harvard Architecture Memory Access Optimization

In a Harvard‐architecture microcontroller, instructions and data are stored in physically separate memories. Modern microcontrollers often have several data memory banks, each holding the same number of data items. A data‐referencing instruction accesses one byte by using a byte offset \(f\) and a bit \(a\). If \(a=0\) the variable is accessed from bank 0. If \(a=1\) then an external bank select register (BSR) identifies the bank to be used. Changing the BSR requires an extra instruction, so it is beneficial to access several variables consecutively from the same (nonzero) bank.

The memory is organized in \(M\) banks of \(S\) bytes each. You are given a program that is a sequence of operations. An operation is either a variable reference of the form Vi (where i is a positive integer) or a repetition of the form Rn <program> E, which means that the enclosed program is executed \(n\) times sequentially. The program’s execution consists solely of memory referencing instructions. Each memory reference costs 1 instruction if the variable is in bank 0. For a variable in any other bank, a memory reference costs 1 instruction if the bank selected by the previous memory reference is the same; otherwise, the BSR must be set first (costing 1 extra instruction) and then the memory reference is executed (costing 1 instruction). The BSR is initially undefined and changes only when an instruction to set it is executed.

Your task is to decide an assignment of variables to memory banks (each bank can hold at most \(S\) variables) in order to minimize the total number of instructions executed. Formally, if a variable is assigned to bank 0, every reference to it uses a single instruction, while if it is assigned to a nonzero bank, every reference costs 1 instruction plus an extra instruction whenever its reference does not immediately follow another reference to a variable in the same nonzero bank. Determine the minimum total running time (i.e. minimum number of instructions) needed to execute the given program, assuming an optimal mapping.

Note: If two consecutive memory references refer to variables in the same nonzero bank, then only the first reference of the contiguous block incurs the extra cost (to set the BSR), while subsequent references cost 1 instruction each. References to variables in bank 0 always cost 1 instruction (and cannot be chained for savings).

inputFormat

The input begins with a line containing two integers \(M\) and \(S\) (the number of banks and the size of each bank). The next tokens describe the program. The program is given as a sequence of tokens separated by whitespace. A token is either:

• Vi (a variable reference, where \(i\) is a positive integer), or
• Rn indicating the beginning of a repetition block (with \(n\) a positive integer), which is terminated by the token E.

The structure of the program is defined by the following grammar:

[ \texttt{} ;:=; \epsilon ;|; \texttt{} ;\texttt{}\quad,\ \texttt{} ;:=; \texttt{V}i ;|; \texttt{R}n ; \texttt{} ;\texttt{E} ]

You may assume that the total number of variable references in the executed program (after expanding repetitions) is reasonably small so that an algorithm with exponential time in the number of distinct variables is acceptable.

outputFormat

Output a single integer: the minimum number of instructions executed to run the program under an optimal assignment of variables to memory banks.

sample

4 8
V1

1