A Combinatorial Problem Related to Interleaved Memory Systems
Gerald J. Burnett, E. G. Coffman · Journal of the ACM · 1973
A combinatorial problem arising from the analysis of a model of interleaved memory systems is studied. The performance measure whose calculation defines this problem is based on the distribution of the number of modules in operation during a memory cycle, assuming saturated demand and an arbitrary but fixed number of modules. In general terms the problem is as follows. Suppose we have a Markov chain of n states numbered 0, 1, ···, n - 1. For each i assume that the one-step transition probability from state i to state ( i + 1) mod n is given by the parameter α and from state i to any other state is β = (1 - α )/( n - 1). Given an initial state, the problem is to find the expected number of states through which the system passes before returning to a state previously entered. The principal result of the paper is a recursive procedure for computing this expected number of states. The complexity of the procedure is seen to be small enough to enable practical numerical studies of interleaved memory systems.