Optimal eviction policies for stochastic address traces

DOI10.1016/J.TCS.2013.01.016zbMATH Open1277.68022arXiv1109.6643OpenAlexW2121243500MaRDI QIDQ386897FDOQ386897

Authors: Gianfranco Bilardi, Francesco Versaci 

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1109.6643

Recommendations

• An optimality proof of the LRU- K page replacement algorithm
• A simple proof of optimality for the MIN cache replacement policy
• On adequate performance measures for paging
• On the separation and equivalence of paging strategies
• Probabilistic methods for web caching

zbMATH Keywords

Markov chainsmultiobjective optimizationoptimal controlpagingonline problemsalgorithms and data structureseviction policies

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Mathematical problems of computer architecture (68M07)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Nonlinear multiobjective optimization
• An efficient algorithm for determining the convex hull of a finite planar set
• The Complexity of Markov Decision Processes
• Multicriteria Optimization
• Competitive paging with locality of reference
• On paging with locality of reference
• Discrete Dynamic Programming
• The working set model for program behavior
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
• Title not available (Why is that?)
• Beyond Competitive Analysis
• Markov Paging
• Title not available (Why is that?)
• Minimization of demand paging for the LRU stack model of program behavior
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Horizons of parallel computation
• On adequate performance measures for paging
• Some Distribution-Free Aspects of Paging Algorithm Performance
• Dynamic storage allocation in the Atlas computer, including an automatic use of a backing store
• A geometric framework for solving subsequence problems in computational biology efficiently
• Title not available (Why is that?)
• Title not available (Why is that?)
• LRU Stack Processing
• Use of the LRU stack depth distribution for simulation of paging behavior
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms – ESA 2004
• A model of memory contention in a paging machine

This page was built for publication: Optimal eviction policies for stochastic address traces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386897)