Optimal Eviction Policies for Stochastic Address Traces

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

39 pages, 3 figures

Scientific paper

The eviction problem for memory hierarchies is studied for the Hidden Markov Reference Model (HMRM) of the memory trace, showing how miss minimization can be naturally formulated in the optimal control setting. In addition to the traditional version assuming a buffer of fixed capacity, a relaxed version is also considered, in which buffer occupancy can vary and its average is constrained. Resorting to multiobjective optimization, viewing occupancy as a cost rather than as a constraint, the optimal eviction policy is obtained by composing solutions for the individual addressable items. This approach is then specialized to the Least Recently Used Stack Model (LRUSM), a type of HMRM often considered for traces, which includes $V-1$ parameters, where $V$ is the size of the virtual space. A gain optimal policy for any target average occupancy is obtained which (i) is computable in time $O(V)$ from the model parameters, (ii) is optimal also for the fixed capacity case, and (iii) is characterized in terms of priorities, with the name of Least Profit Rate (LPR) policy. An $O(\log C)$ upper bound (being $C$ the buffer capacity) is derived for the ratio between the expected miss rate of LPR and that of OPT, the optimal off-line policy; the upper bound is tightened to O(1), under reasonable constraints on the LRUSM parameters. Using the stack-distance framework, an algorithm is developed to compute the number of misses incurred by LPR on a given input trace, simultaneously for all buffer capacities, in time $O(\log V)$ per access. Finally, some results are provided for miss minimization over a finite horizon and over an infinite horizon under bias optimality, a criterion more stringent than gain optimality.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Optimal Eviction Policies for Stochastic Address Traces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Eviction Policies for Stochastic Address Traces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Eviction Policies for Stochastic Address Traces will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-152874

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.